1、实验六 回溯算法设计与应用一基本原理的概括DFS+剪枝（在状态空间树上作带剪枝的 DFS 搜索）剪枝：若搜索到某结点，其对应的部分解不满足解的约束条件且可断定以其为根的子树上不包含答案结点，则不搜索该子树，直接回到其父结点，继续 DFS。 利用回溯法可求问题的一个解，多个解，所有解，最优解，还可判断解的存在性。 二该类算法设计与实现的要点回溯法通常包含以下 3 个步骤： 1)定义给定问题的解空间； 2)确定并表示解的约束条件和其它的剪枝条件； 3)结合剪枝深度优先搜索相应的状态空间树。 注意：回溯法的一个特征是在搜索过程中动态的产生问题的状态空间树，任何时候只存根到当前搜索的结点的路径。三实验
2、目的和要求理解回溯法的基本原理，掌握回溯法设计的基本方法及步骤，并应用于具体问题的解决。四实验内容(一) 马的周游问题1. 问题描述在 n x n 棋盘（有 n x n 个格点的棋盘）的某个格点上有一个中国象棋马，马走日字。求一条周游棋盘的路径，使得马能够从起始位置起沿着该路径每个格点恰好走一次最后回到出发位置。2. 具体要求用回溯法解决该问题。输入一个正整数 n，输出一个解，解的输出形式尽可能直观。 3. 设计与实现代码如下：#include #include #include #include using namespace std;inline int good(int x,int y,
3、int s3030,int n) if(x=0switch(cd)case 1:enum roadd11,d12,d21,d22,d31,d32,d41,d42;road d100;int m=0;int x=0,y=0;int p=0,q=0;int s3030;int i,j;int w=1;int num=0;int n;coutn;for(i=0;ip;coutq;p-;q-;x=p;y=q;d0=d11;syx=1;doif(dm=d11y=y-2;d+m=d11;syx=+w;num+;else if(dm=d12y-;d+m=d11;syx=+w;num+;else if(dm=
4、d21y+;d+m=d11;syx=+w;num+;else if(dm=d22y=y+2;d+m=d11;syx=+w;num+;else if(dm=d31y=y+2;d+m=d11;syx=+w;num+;else if(dm=d32y+;d+m=d11;syx=+w;num+;else if(dm=d41y-;d+m=d11;syx=+w;num+;else if(dm=d42y=y-2;d+m=d11;syx=+w;num+;elsewhile(dm=d42)m-;if(dm=d11)syx=88;-w;x-;y=y+2;if(dm=d12)syx=88;-w;x=x-2;y+;if
5、(dm=d21)syx=88;-w;x=x-2;y-;if(dm=d22)syx=88;-w;x-;y=y-2;if(dm=d31)syx=88;-w;x+;y=y-2;if(dm=d32)syx=88;-w;x=x+2;y-;if(dm=d41)syx=88;-w;x=x+2;y+;if(m!=0-w;x+;y=y+2;dm=road(dm+1);while(m!=0|d0!=d42|good(x-1,y-2,s,n)coutusing namespace std;int main()char a1010;int n,m,x,y,i,j,sx,sy,x1,y1,x2,y2,min,k100,
6、flag1010=0;int tag82=-1,0,0,1,1,0,0,-1,-2,2,2,2,2,-2,-2,-2;cinn;while(n-)cinxy;for(i=0;iaij;if(aij=S)x1=i;y1=j;min=32767;i=1;k0=0;ki=-1;flagx1y1=1;while(i=1)while(ki=0else if(flagx2y2=0)flagx2y2=1;x1=x2;y1=y2;i+; ki=-1; i-;flagx1y1=0;x1=x1-tagki0;y1=y1-tagki1; if(min32767)coutminendl;elsecout“NO ANSWER“endl;return 0;
