骑士的旅游算法 [英] Knight's tour algorithm
问题描述
所以，我必须写这个算法（这个版本并不需要结束在同一地点的骑士开始），我得到它的工作，但它的速度太慢。它的工作原理与开始位置x = 0和y = 0的大小为= 8，但如果我试图操纵x和y以例如2和4不几分钟后结束。任何人都可以帮忙吗？
的#include＆LT; stdio.h中＆GT;
＃定义尺寸8
INT ruch_x [] = {-1，1，-2,2，-2，2，-1,1}; //阵列可能骑士的动作，例如第二个举措是[1,2] //
INT ruch_y [] = {2,2，1，1，-1，-1，-2，-2};
诠释做（INT szach [] [尺寸]）
{
的for（int i = 0; I＆LT;大小;我++）
{
对于（INT J = 0; J＆LT;大小; J ++）
{
如果（szach [I] [J] == 0）
返回0;
}
}
返回1;
}
// licz - 变量计算骑士举动//
无效konik（INT szach [] [尺寸]，INT X，INT Y，INT licz）
{
szach [X] [Y] = licz;
如果（licz＆LT;大小*尺寸）{
的for（int i = 0; I＆LT; = 7;我++）{//循环，检查每一个可能的骑士举动//
if(szach[x+ruch_x[i]][y+ruch_y[i]]==0&&x+ruch_x[i]>=0&&x+ruch_x[i]<size&&y+ruch_y[i]>=0&&y+ruch_y[i]<size)
//检查是否candidat已经访问过，如果它的董事会不在外面// {
konik（szach中，x + ruch_x [I]，Y + ruch_y [I]中，licz + 1）;}}}
如果（做（szach）== 1）返回; //检查是否整板充满了数字，如果是则跳过零电流举动//
szach [X] [Y] = 0;
}
诠释的main（）
{
INT I，J，X，Y;
的printf（集X \ N）;
scanf函数（％D，与放大器，X）;
的printf（设置Y \ N）;
scanf函数（％D，与安培; Y）;
INT szach [大小] [尺寸]
对于（i = 0; I＆LT;大小;我++）{//零数组//
为（J = 0; J＆LT;大小; J ++）{
szach [I] [J] = 0; }}
konik（szach，X，Y，1）;
的for（int i = 0; I＆LT;大小;我++）{
对于（INT J = 0; J＆LT;大小; J ++）{
的printf（％D \ T，szach [J] [我]）; }
的printf（\ñ\ N）;}
的printf（\ N）;
返回0;
}
这可能是一个坏主意，只是蛮力，尽可能序列的数量可超过10 ^ 50的8x8板。
骑士的旅游在维基百科上的文章对问题像样的信息，我会建议从那里开始。
其中最有名的方法可以找到哈密顿路径是这样的：从任何节点 U 顺序由它们在图度非降序排列的邻居。让我们从 U 表示，骑士可以移动到 P 和①（即 U 有两个邻居），然后在您的递归考虑最初 P 如果有少可用的邻居比①。这通常导致到显著优化，特别是如果图有很多哈密尔顿路径作为在此情况下
关于你提到的code。你不需要调用完成（）每次。如果在任何时刻 licz＆GT; =尺寸*尺寸，那么你知道你找到你的答案。您可以将一个全球性的布尔做来代替的例子。这将有助于一点点，但在所有情况下都没有帮助。
P.S。如果你需要的任意的为您的项目单一解决方案，我会推荐给存储单个汉密尔顿的周期的，对于任何 X，Y 只是简单的转移序列来获得一个有效的解决方案。
So I have to write this algorithm (this version does not need to end in the same spot that knight started), and I got it to work, but it's too slow. It works with starting positions x=0 and y=0 for size=8, but if I try to manipulate x and y to for example 2 and 4 it doesn't end after a few minutes. Can anyone help?
#include <stdio.h>
#define size 8
int ruch_x[]={ -1, 1, -2, 2, -2, 2, -1, 1}; //arrays of possible knight moves, for example 2nd move is [1,2]//
int ruch_y[]={ 2, 2, 1, 1, -1, -1, -2, -2};
int done(int szach[][size])
{
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
if(szach[i][j]==0)
return 0;
}
}
return 1;
}
//licz - variable for counting knights moves//
void konik(int szach[][size], int x, int y, int licz)
{
szach[x][y]=licz;
if(licz<size*size){
for(int i=0;i<=7;i++){ //loop that checks every possible knight move//
if(szach[x+ruch_x[i]][y+ruch_y[i]]==0&&x+ruch_x[i]>=0&&x+ruch_x[i]<size&&y+ruch_y[i]>=0&&y+ruch_y[i]<size)
// checking if candidat was already visited and if it's not outside of the board// {
konik(szach, x+ruch_x[i], y+ruch_y[i], licz+1);}}}
if(done(szach)==1) return; //checking if whole board is filled with numbers, if yes then skip zeroing current move//
szach[x][y]=0;
}
int main()
{
int i, j, x,y;
printf("set x\n");
scanf("%d", &x);
printf("set y\n");
scanf("%d", &y);
int szach[size][size];
for(i=0;i<size;i++) { //zeroing array//
for(j=0;j<size; j++) {
szach[i][j]=0; }}
konik(szach, x, y, 1);
for(int i=0;i<size;i++) {
for(int j=0;j<size; j++) {
printf("%d\t",szach[j][i]); }
printf("\n\n");}
printf("\n");
return 0;
}
It is probably a bad idea to simply brute-force, as the number of possible sequences can exceed 10^50 for 8x8 board.
Knight's tour article on wikipedia has decent information on the problem, I would recommend to start from there.
One of the most famous heuristics for finding Hamiltonian Path is the following: from any node u order the neighbours in non-decreasing order by their degrees in the graph. Let's say from u the knight can move to p and q (i.e. u has two neighbours), then in your recursion consider initially p if it has less available neighbours than q. This usually leads to to significant optimizations, especially if the graph has a lot of Hamilton Paths as in this case.
Regarding your code. You don't need to call done() everytime. If at any moment licz >= size*size, then you know that you found your answer. You can store a global boolean done instead for example. This should help a little bit, but won't help in all cases.
P.S. If you need any single solution for your project, I would recommend to store a single Hamilton cycle, and for any x,y just simply shift the sequence to get a valid solution.
这篇关于骑士的旅游算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
