求哈密尔顿链问题（骑士周游问题）的求解高效算法。

来源：百度知道 编辑：UC知道 时间：2024/06/15 14:33:51
与骑士周游问题类似但是不同。8*8的格子，可以上下左右四个方向移动，给定入口和出口（均在以上格子内），要求得到从入口到出口的路径，能够走遍所有网格且不重复走任何一格。
如果采用普通求解骑士周游问题的回溯法来求解这个问题，会因为时间复杂度过大而几乎无法计算。在这里求时间效率很高的算法，多谢！！！

我用C实现了一个高效算法。
此算法用不到1秒钟就可以算出结果啦！

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int dir[4][2] = {{0,-1},{-1,0},{0,1},{1,0}};
int start_i,start_j,end_i,end_j;
int maze[10][10];
int path[64][2];

void init()
{
int i,j;
for (i = 0; i <= 9; i++)
{
maze[0][i] = 0;
maze[9][i] = 0;
maze[i][0] = 0;
maze[i][9] = 0;
}
maze[1][1] = 2;
maze[1][8] = 2;
maze[8][1] = 2;
maze[8][8] = 2;
for (i = 2; i <= 7; i++)
{
maze[1][i] = 3;
maze[8][i] = 3;
maze[i][1] = 3;
maze[i][8] = 3;
}
for (i = 2; i <= 7; i++)
for (j = 2; j <= 7; j++)
{