贪婪算法Horse的遍历时间复杂度
马的遍历问题。在有8×8个方格的棋盘上，从任意指定的方格开始，找一条路让马穿过棋盘的每一个方格，只通过一次。
初步设计
首先，这是一个搜索问题，用深度优先搜索来解决。算法如下:
1，输入初始位置坐标x，y；
2.步骤c:
如果c & gt64输出一个解决方案并返回到上一步c-
(x，y) ← c
计算(x，y)在八个方向的子节点，选择可行的子节点。
遍历所有可行的子节点，对2重复步骤c++。
显然，(2)是一个递归调用过程，大致如下:
void dfs(int x，int y，int count)
{
int i，tx，ty；
if(count & gt；N*N)
{
输出解决方案()；//输入解决方案
返回；
}
for(I = 0；我& lt8;++i)
{
tx=hn[i]。x；//hn[]保存八个方位角子节点。
ty=hn[i]。y；
s[tx][ty]= count；
dfs(tx，ty，count+1)；//递归调用
s[tx][ty]= 0；
}
}
这样做是完全可行的。它输入了所有的解，但是马遍历8×8的时候，解是如此之多，无法用天文数字来描述，所以求解的过程非常慢，一个解也非常慢。
怎样才能快速得到部分解决方案？
贪婪算法
其实马踩棋盘的问题早就提出来了，早在1823，J.C.Warnsdorff就提出了一个著名的算法。当每个节点选择它的子节点时，它优先选择出口最小的节点。‘退出’是指这些子节点中可行子节点的数量，即‘孙子’节点越少，越优先跳转。为什么选择这种方式？这是一种局部优化。如果先选择出口多的子节点，出口少的子节点会越来越多。很有可能会出现‘死’节点(顾名思义，没有出口，没有跳转的节点)，所以后面的搜索纯粹是徒劳的，会浪费很多无用的时间。反之，如果每次优先选择退出少的节点，退出少的节点会越来越少，那么成功的几率会更大。这种算法称为贪婪算法，也称为贪婪算法或启发式算法。它对整个求解过程进行最优调整，只适合寻找更好的解或部分解，而不适合寻找最优解。这种调整方法叫做贪婪策略。至于什么问题需要什么样的贪婪策略，不确定，具体问题具体分析。实验证明，应用上述贪婪策略后，马遍历问题的求解速度明显提高。如果只需要求一个解，不需要回溯就可以完成，因为这个算法提出的时候世界上还没有计算机，这种方法完全可以手工求解，效率可想而知。
在前面算法的基础上，增加一些程序来实现:
函数1:计算节点出口数。
int ways_out(int x，int y)
{
int i，count=0，tx，ty；
if(x & lt；0 | | y & lt0 | | x & gt= N | | y & gt= N | | s[x][y]& gt；0)
return-1；//-1表示该节点非法或已被跳过。
for(I = 0；我& lt8;++i)
{
tx = x+dx[I]；
ty = y+dy[I]；
if(tx & lt；0 | | ty & lt0 | | tx & gt= N | | ty & gt=N)
继续；
if(s[tx][ty]==0)
++计数；
}
返回计数；
}
功能2:按节点出口排序
Void sortnode(h_node *hn，int n)//采用简单排序方式，因为子节点最多只有8个。
{
int i，j，t；
h _节点温度；
for(I = 0；我& ltn；++i)
{
for(t=i，j = I+1；j & ltn；++j)
if(hn[j].waysout & lthn[t]。waysout)
t = j；
if(t & gt；我)
{
temp = HN[I]；
HN[I]= HN[t]；
HN[t]= temp；
}
}
}
功能3:修改后的搜索功能
void dfs(int x，int y，int count)
{
int i，tx，ty；
h _ node HN[8]；
if(count & gt；N*N)
{
输出解决方案()；
返回；
}
for(I = 0；我& lt8;++i)//找到子节点并退出
{
hn[i]。x = tx = x+dx[I]；
hn[i]。y = ty = y+dy[I]；
hn[i]。waysout=ways_out(tx，ty)；
}
sortnode(hn，8)；
for(I = 0；hn[i]。waysout & lt0;++ I)；//不考虑无用节点
for(；我& lt8;++i)
{
tx=hn[i]。x；
ty=hn[i]。y；
s[tx][ty]= count；
dfs(tx，ty，count+1)；
s[tx][ty]= 0；
}
}
功能4:音调功能
void main()
{
int i，j，x，y；
for(I = 0；我& ltn；++i)//初始化
for(j = 0；j & ltn；++j)
s[I][j]= 0；
printf(" N = % d时跳马\ N输入开始位置:"，N)；
scanf("%d%d "，& ampx & amp；y)；//输入初始位置
while(x & lt；0 | | y & lt0 | | x & gt= N | | y & gt=N)
{
printf("错误！x，y应该在0~%d”内，N-1)；
scanf("%d%d "，& ampx & amp；y)；
}
s[x][y]= 1；
dfs(x，y，2)；//开始搜索
}
QQ:547758555
如果有问题，QQ说