马的周游问题

马的周游问题报告姓名：XXXXX学号：XXXXX1、原题中文大意对于一个8*8的棋盘，用下列的方式编号12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364如果它走63步正好经过除起点外的其他位置各一次，这样一种走法则称马的周游路线，设计一个算法，从给定的起点出发，找出它的一条周游路线。马的走法是“日”字形路线。输入有若干行。每行一个整数N(1=N=64)，表示马的起点。最后一行用-1表示结束，不用处理。对输入的每一个起点，求一条周游线路。对应地输出一行，有64个整数，从起点开始按顺序给出马每次经过的棋盘方格的编号。相邻的数字用一个空格分开。2、算法思想及解题用到的主要数据结构这是一道比较明显要用深度优先搜索算法的题目，求出马的周游路线。用广度优先除了浪费时间、空间，给解题增加困难以外是没有任何好处的。解题时用一个结构体来存储路线中的节点，结构体中包含在棋盘中的横坐标、纵坐标、子节点的数目这3个属性。因为我们的目的是找出一条完整的路径，也就是从初始的父节点开始用正确的方式搜索到第63层子树，所以显而易见，先搜索子节点数目较少的节点会大大地提高效率，这样有主要2个好处：（1）如果路径正确，只需要很小的时间和空间复杂度就可以达到目标；（2）如果路径不正确，也容易返回然后走到正确的道路上。这是本题用到的主要思想，主要的数据结构就是结构体。3、详细解题思路对于一个输入的编号值，首先要转化为对应的节点，然后从这个节点开始进行深度优先搜索。将这个节点标记为true，即已走过。计算出当前节点的可以走向的下一个节点的数目，并得到所有的子节点，然后对所有的子节点进行排序，含子节点较少的子节点优先级比较高，然后从优先级比较高的子节点进行下一步的搜索，直到搜索到第63层节点。我们需要一个二维数组flag[8][8]来存储节点是否走过的信息，开始时都为false，走过则标记为true；一个二维数组nextStep[8][2]来表示可能的8个子节点与当前节点的坐标差；一个一维数组road[64]来记录路线。深度有先算法中有一个参数degr来传递搜索树的深度，每向下搜索一层，则degr加1，能加到63说明沿着这条路有解，路线存储在数组road[]中。4、逐步求精算法描述（含过程及变量说明）//三个全局变量：boolflag[8][8];//记录每个节点是否已经走过，走过设为true，未走过为false//左上开始顺时针旋转的方向,记录马下一步可能走的八个方向intnextStep[8][2]={1,-2,2,-1,2,1,1,2,-1,2,-2,1,-2,-1,-1,-2};introad[64]={0};//记录马走过的编号序列//计算子节点的数目：/*计算某个节点有多少个子节点，子节点为从当前位置可以走向的下一位置依次对八个方向进行判断，得出子节点的数目*/inlineintnum(inta,intb){intn=0;for(inti=0;i8;i++){intx=a+nextStep[i][0];inty=b+nextStep[i][1];if(judge(x,y))n++;}returnn;}//存储节点的数据结构：/*节点的数据结构为结构体，节点有3个属性：节点的横坐标，纵坐标，子节点的数目*/structnode{intx;inty;intnextNum;node(){x=-1;y=-1;nextNum=-1;}node(inta,intb){x=a;y=b;nextNum=num(a,b);}};//深度优先算法：/*深度优先搜索函数，用一个堆栈保存搜索的节点，在搜索的过程中子节点数目少的节点优先搜索，用sort()函数排序确定。*/booldfs(nodestart,intdegr){if(degr==63){road[degr]=nodeToNum(start);returntrue;}inta=start.x;intb=start.y;flag[a][b]=true;vectornodesear;road[degr]=nodeToNum(start);for(inti=0;i8;i++){nodene=getNode(start,i);if(judge(ne.x,ne.y))sear.push_back(ne);}sort(sear.begin(),sear.end(),cmp);for(intj=0;jsear.size();j++){if(dfs(sear[j],degr+1))returntrue;}flag[a][b]=false;returnfalse;}5、注释清单#includeiostream#includevector#includealgorithm#includecstringusingnamespacestd;boolflag[8][8];//记录每个节点是否已经走过，走过设为true，未走过为false//左上开始顺时针旋转的方向,记录马下一步可能走的八个方向intnextStep[8][2]={1,-2,2,-1,2,1,1,2,-1,2,-2,1,-2,-1,-1,-2};introad[64]={0};//记录马走过的编号序列/*判断某个节点是否可走，判断条件为此节点在棋盘上，并且还未走过*/booljudge(inta,intb){if(a=0&&a=7&&b=0&&b=7&&!flag[a][b])returntrue;returnfalse;}/*计算某个节点有多少个子节点，子节点为从当前位置可以走向的下一位置依次对八个方向进行判断，得出子节点的数目*/inlineintnum(inta,intb){intn=0;for(inti=0;i8;i++){intx=a+nextStep[i][0];inty=b+nextStep[i][1];if(judge(x,y))n++;}returnn;}/*节点的数据结构为结构体，节点有3个属性：节点的横坐标，纵坐标，子节点的数目*/structnode{intx;inty;intnextNum;node(){x=-1;y=-1;nextNum=-1;}node(inta,intb){x=a;y=b;nextNum=num(a,b);}};/*根据当前位置和要走的方向得到子节点*/nodegetNode(nodeno,intdir){inta=no.x+nextStep[dir][0];intb=no.y+nextStep[dir][1];returnnode(a,b);}/*比较两个节点的优先级，子节点数目少的节点的优先级要高，用于深度优先搜索的排序*/boolcmp(noden1,noden2){returnn1.nextNumn2.nextNum;}/*根据节点的编号，转化为相应的节点*/nodenumToNode(intk){intx=(k-1)/8;inty=(k-1)%8;if(judge(x,y))return(node(x,y));}/*将节点转化为相应的编号*/intnodeToNum(nodeno){return(8*no.x+no.y+1);}/*深度优先搜索函数，用一个堆栈保存搜索的节点，在搜索的过程中子节点数目少的节点优先搜索，用sort()函数排序确定。*/booldfs(nodestart,intdegr){if(degr==63){road[degr]=nodeToNum(start);returntrue;}inta=start.x;intb=start.y;flag[a][b]=true;vectornodesear;road[degr]=nodeToNum(start);for(inti=0;i8;i++){nodene=getNode(start,i);if(judge(ne.x,ne.y))sear.push_back(ne);}sort(sear.begin(),sear.end(),cmp);for(intj=0;jsear.size();j++){if(dfs(sear[j],degr+1))returntrue;}flag[a][b]=false;returnfalse;}intmain(){/*调试用代码for(intj=0;j8;j++)coutnextStep[j][0]nextStep[j][1]endl;*/intn;while(cinn&&n!=-1&&n=1&&n=64){memset(flag,0,sizeof(flag));nodestart=numToNode(n);dfs(start,0);coutroad[0];for(inti=1;i64;i++)coutroad[i];coutendl;}return0;}6、测试数据（5-10组有梯度的测试数据,要考虑边界条件）7、对时间复杂度，空间复杂度方面的分析、估算及程序优化的分析和改进在sicily上的runtime是0sec，速度还是比较快的。如果在进行深度优先搜索的时候，不优先搜索子节点较少的节点，会大大增加时间和空间的复杂度，甚至无法通过sicily的测试，所以，一定要选择子节点较少的节点优先进行搜索。