贪婪算法解决跳马回路

《贪婪算法解决跳马回路》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、【问题描述】马的遍历问题。在８×８方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时

2、间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。下面这个算法可以求跳马问题的近似解，偶数100×100之内都可以计算。n*n的格子里，如果n为奇数，可用数学证明，它必然不存在一个跳马回路（用国际象棋的黑白棋盘可以得到启示）//贪心法//跳马问题#include#include#include#defineROW16#defineLINE16#defineNUMROW*LINEintboard[ROW][LINE];//两个数组存储对应的偏移量intstepRow[8]={

3、-1,-2,-2,-1,1,2,2,1};intstepLine[8]={-2,-1,1,2,2,1,-1,-2};//求(i,j)的出口数，各个出口对应的号存在a[]中。intexitn(inti,intj,ints,inta[]){inti1,j1,k,count;for(count=k=0;k<8;k++){i1=i+stepRow[(s+k)%8];j1=j+stepLine[(s+k)%8];if(i1>=0&&i1=0&&j1

4、个出口，s是顺序选择法的开始序号intnext(inti,intj,ints){intm,kk,a[8],b[8],temp;m=exitn(i,j,s,a);if(m==0)return-1;//没有出口的情况for(intmin=9,k=0;k

5、r(intsx=0;sxNUM

6、

7、no==-1)break;}while(step<=NUM);if(n

8、o!=-1&&((sx+2==i

9、

10、sx-2==i)&&(sy+1==j

11、

12、sy-1==j))

13、

14、((sx+1==i

15、

16、sx-1==i)&&(sy+2==j

17、

18、sy-2==j))){cout<<"ok"<