lecutre_12回溯法2.pptVIP

如果要找到所有解 如果要找到所有解，则需要立即输出当前x数组所代表的一个可行解，继续有哪些信誉好的足球投注网站 如果要找到所有解 如果要找到所有解，则需要立即输出当前x数组所代表的一个可行解，继续有哪些信誉好的足球投注网站 Backtrack( int t ) { if (tn) { //得到一个解，flag=1;exit; } else for (int i=1;i=n;i++) { x[t]=i; if (place(x，t)) Backtrack(t+1); } } Int Ok(int L[N][N],int x[N], int t) {// 检查颜色可用性 for (int j=1;j=n;j++) if ((L[t][j]==1)(x[j]==x[t])) return false; return true; } 皇后位置合法性判断 bool Queen::Place(int x[N]，int t) { for (int j=1;jt;j++) if ((abs(t-j)==abs(x[j]- x[t]))||(x[j]==x[t])) return false; return true; } 3着色问题的非递归算法 void 3_Colorrec(int L[N][N],int x[N]) {1、x数组初始化为0 2、flag=0;t=1; 3、While(t=1) 4、 {x[t]++; 5、 while(顶点t没有试遍所有颜色且目前颜色x[t]不合法） 顶点t取下一种颜色 （ x[t]+ +）； 6 、 if(顶点t有合法着色) 7、 if(t已是第n个顶点） 则得到一个合法着色方案输出方案，终止程序； 8、 else //只是的到部分解 t++; //为下一个顶点寻找合法着色 9、 else //顶点t试遍所有颜色，都不合法 {x[t]=0;t—;} //回上一行 } N后问题的非递归算法 void nqueen(int n) {1、x数组初始化为0 2、flag=0;t=1; 3、While(t=1) 4、 {x[t]++; 5、 while(第t行皇后没有试遍所有位置且目前位置x[t]不合法） 试探本行下一个位置 （ x[t]+ +）； 6 、 if(在第t行找到合法) 7、 if(t已是第n行） 则得到一个合法放置方案，输出方案，终止程序； 8、 else //只是的到部分解 t++; //为下一个皇后寻找合法位置 9、 else //第t试行遍所有位置，都不合法 {x[t]=0;t—;} //回上一行 } N后问题的非递归算法 void nqueen(int n) {1、x数组初始化为0 2、flag=0;t=1; 3、While(t=1) 4、 {x[t]++; 5、 while(x[t]=n!ok(x，t)) x[t]+ +； 6 、 if(x[t]=n)) 7、 if(t==n） 则得到一个合法放置方案，输出方案，终止程序； 8、 else //只是的到部分解 t++; //为下一个皇后寻找合法位置 9、 else //第t试行遍所有位置，都不合法 {x[t]=0;t—;} //回上一行 } 上机作业 实现求解n后问题的递归和非递归算法 问题的解空间 问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。 如：３着色问题中｛１,２,３,３,２}表示这五个顶点、分别用颜色１，颜色２，颜色３,颜色３,颜色２着色 　　n后问题