资源描述：
《马的周游问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、科学院大学ersityofChineseAcademyofSciences马的周游问题报告姓名：xxxxx学号：xxxxx1、原题中文大意对于一个8*8的祺盘，川K列的方式编号123456789101112131415161718192()2122232425262728293031323334353637383940414243444546474849505152535455565758596061626364如果它走63步正好经过除起点外的其他位置各一次,这样一•种走法则称马的周游路线,设计一个算法，从给定的起点出发，找出它的一条周游路线。马的走法是
2、“闩”字形路线。输入奋若干行。每行一个整数N（1<=N<=64）,表示马的起点。最后一行川-1表示结束，不用处理。对输入的每一个起点，求一条周游线路。对应地输出一行，冇64个整数，从起点开始按顺序给出马毎次经过的棋盘方格的编号。相邻的数字用一个空格分幵。2、算法思想及解题用到的主要数据结构这是一道比较明敁要用深度优先搜索算法的题FI,求出马的周游路线。用广度优先除了浪费时闽、空叫，给解题增加闲难以外是没有任何好处的。解题时用一个结构体來存储路线中的节点，结构体中仏含在棋盘中的横处标、纵叱标、子节点的数n这3个屈性。因为我们的H的是找出一条完整的路径，也就
3、是从初始的父节点开始用正确的方式搜索到第63层子树，所以显而易见，先搜索子节点数0较少的节点会人人地提高效率，这样宥主要2个好处：（1）如果路径正确，只需耍很小的吋间和空间s杂度就可以达到n标；（2）如果路径不正确，也容易返回然后走到正确的道路上。这楚本题川到的主要思想，主要的数据结构就足结构体。3、详细解题思路对于一个输入的编号值，首先要转化为对应的节点，然后从这个节点开始进行深度优先搜索。将这个节点杯记为true,即已走过。计算出当前节点的可以走IN的下一个节点的数目，外得到所柯的子节点，然后对所有的子节点进行排序，含子节点较少的子节点优先级比较高，
4、然后从优先级比较髙的子节点进行下一步的搜索，直到搜索到笫63层节点。我们需要一个二维数组flagPl[81来存储节点是否走过的信息，丌始时都为false,走过则标记为true；—个二维数组nextStep[8][2]来表示可能的8个了点与当前卞点的坐标差;一个一维数组road[64]来记录路线。深度有先算法中有一个参数degr來传递搜索树的深度，每向K搜索-层，则degr加1，能加到63说明沿着这条路有解，路线存储在数纟IIroadU^o4、逐步求精算法描述(含过程及变量说明)//三个全局变量：boolflag[8][8];//记录毎个节点是也已经走:过
5、，史过设为true,未史过为false//左上开始顺吋针旋转的方向，记录马不一步可能走的八个方向intnextStep[8][2]={1,-2,2,-1,2,1,1,2,-1,2,-2,1,-2,-1,-1,-2);introad[64]={0};//记录马走:过的编号序列//计算子节点的数0:计算某个节点有多少个子节点，子节点为从当前位置可以走向的下一位置依次对八个方向进行判断，得出了•节点的数鬥*/inlineintnum(inta,intb){intn=();for(inti=0;i<8;i++){intx=a+nextStep[i][0];int
6、y=b+nextStepliJLlJ;if(judge(x,y))n++;}returnn;//存储节点的数据结构：/*节点的数裾结构为结构体，节点冇3个属怦：节点的横坐标，纵坐标，子节点的数H*/structnode{intx;inty;intnextNum;node(){x=-l;y=-l;nextNum=-l;node(inta,intb){x=a;y=b;nextNum=num(a,b);}}；//深度优先算法：/*深度优先搜索函数，川一个堆栈保存搜索的节点，在搜索的过程屮子节点数0少的节点优先搜索，川sort()函数排序确定。booldfs(n
7、odestartjntdegr){if(degr==63){road[degrl=nodeToNum(start);returntrue;inta=start.x;intb=start.y;flag[a][b]=truc;vectorsear;road[degr]=nodeToNum(start);for(inti=0;i<8;i++){nodene=getNode(start,i);if(judge(ne.x，ne.y))sear.push_back(ne);)sort(sear.begin()，sear.end()，cmp);for(in
8、tj=0;j
