回溯问题：m点着色、n皇后、tsp递归迭代算法.docVIP

PAGE  PAGE 7 m着色 回溯法 递归 //输入n为顶点个数，颜色数m，图的邻接矩阵c[][] //输出n个顶点的着色x[] //递归方法求解 #include iostream using namespace std; bool c[6][6]; int x[6]; int m=3; int n=5; bool ok(int k) //判断对顶点k着色以后是否合法着色 { int i; for(i = 1; i k; i++) if((c[k][i]==1 x[k] == x[i])) return false; return true; } void output(int x[]) { coutThe feasible result is:endl; for(int i=1;i=n;i++) coutx[i] ; coutendl; return; } void backtrack (int t) { if (tn) output(x); else for (int i=1;i=m;i++) { x[t]=i; if (ok(t)) backtrack(t+1); x[t]=0; } } int main() { int i, j; for(i = 1; i 5; i++) for(j = 1; j 5; j++) c[i][j] = false; c[1][2] = true; c[1][3] = true; c[2][3] = true; c[2][4] = true; c[2][5] = true; c[3][5] = true; c[4][5] = true; c[2][1] = true; c[3][1] = true; c[3][2] = true; c[4][2] = true; c[5][2] = true; c[5][3] = true; c[5][4] = true; backtrack(1); cout endl; return 0; } m着色 回溯法 迭代 //输入n为顶点个数，颜色数m，图的 邻接矩阵c[][]//输出n个顶点的着色 x[] //第一个结点也可以有m种着色方案 #include iostream using namespace std; bool c[6][6]; int x[6]; int m=3; int n=5; bool ok(int k) //判断对顶点k着色以后是否合法着色 { int i; for(i = 1; i k; i++) if((c[k][i]==1 x[k] == x[i])) return false; return true; } void m_coloring(int n, int m) { int i, k; for(i = 1; i = n; i++) x[i] = 0; k =1; while(k =1) { x[k]++; while(x[k] = m) if( ok(k)==1) break; else x[k]++; if(x[k] = m k==n) { for(i=1;i=n;i++) coutx[i] ; coutendl; k--; //return; 如果只需要一个解可以将上两句去掉，加入返回语句 } else if (x[k]=m kn) k++; else{ x[k]=0; k--; } } } int main() { int i, j; for(i = 1; i 5; i++) for(j = 1; j 5; j++) c[i][j] = false; c[1][2] = true; c[1][3] = true; c[2][3] = true; c[2][4] = true; c[2][5] = true; c[3][5] =