图的m着色问题
输入样例 5 4 1 3 1 2 1 4 2 3 2 4 2 5 3 4 4 5 0 0 输出样例 1 2 3 4 1 1 2 3 4 3 1 2 4 3 1 1 2 4 3 4 1 3 2 4 1 1 3 2 4 2 1 3 4 2 1 … 4 3 2 1 4 Total=48 对m种颜色编号为1，2，…，m，由于每个顶点可从m种颜色中选择一种颜色着色，如果无向连通图G=(V, E)的顶点数为n，则解空间的大小为mn种，解空间是非常庞大的，它是一棵m叉树。 图的m着色问题的约束函数是相邻的两个顶点需要着不同的颜色，但是没有限界函数。 假设无向连通图G=(V, E)的邻接矩阵为a，如果顶点i和j之间有边，则a[i][j]=1，否则a[i][j]=0。 设问题的解向量为X (x1, x2 , …, xm) ，其中xi∈{1, 2, …, m}，表示顶点i所着的颜色是x[i]，即解空间的每个结点都有m个儿子。
#define NUM 100 int n; //图的顶点数量 int m; //可用颜色数量 int a[NUM][NUM]; //图的邻接矩阵 int x[NUM]; //当前的解向量 int sum ; //已经找到的可m着色 //形参t是回溯的深度，从1开始 void BackTrack(int t ){ int i; //到达叶子结点，获得一个着色方案 if( t > n ) { sum ++ ; for(i=1; i<=n ;i++) printf("%d ",x[i]); printf("\n"); } else //搜索当前扩展结点的m个孩子 for(i=1; i<=m; i++ ){//尝试每种颜色 x[t] = i; if( Same(t) ) //判断t 和其邻接点的着色方法是否相同 BackTrack(t+1); x[t] = 0;//回溯的需要，恢复到未着色的状态 } }n皇后问题
在n×n格的棋盘上放置彼此不受攻击的n个皇后。 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n皇后问题等价于在n×n格的棋盘上放置n个皇后，任何两个皇后不放在同一行或同一列或同一斜线上。 编程要求：找出一个n×n格的棋盘上放置n个皇后并使其不能互相攻击的所有方案。
由于棋盘的每列/行只有一个皇后，所以可以用一维向量X( x1, x2, …, xn)，其中xi∈{1, 2, …, n}，表示第i列皇后所在的行x[i]，即解空间的每个结点都有n个儿子，因此解空间的大小为nn，这是一棵子集树。
#define NUM 20 int n; //棋盘的大小 int x[NUM]; //解向量 int sum; //当前已经找到的可行方案数 void Backtrack(int t) {//形参t是回溯的深度，从1开始 int i; //到达叶子结点，获得一个可行方案。累计总数，并输出该方案 if (t>n) { sum++; //是全局变量 for (i=1; i<=n; i++) printf(" %d", x[i]); printf("\n"); } else for (i=1; i<=n; i++) { x[t] = i; if (Place(t)) Backtrack(t+1); } } //形参t是回溯的深度 inline bool Place(int t) { int i; for (i=1; i<t; i++) if ((abs(t-i) == abs(x[i]-x[t])) || (x[i] == x[t])) //同一条对角线；同一行 return false; return true; }旅行商问题
是指一销售商从n个城市中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。本题假定该旅行商从第1个城市出发。 输入 对每个测试例，第1行有两个整数：n(4≤n≤10)和m(4≤m≤20 ) ，n是结点数，m是边数。接下来m行，描述边的关系，每行3个整数：(i，j)，length，表示结点i到结点j的长度是length。 当n＝0时，表示输入结束。 输出 对每个测试例，输出最短路径长度所经历的结点，最短的长度。
#define NUM 100 int n; //图G的顶点数量 int m; //图G的边数 int a[NUM][NUM]; //图G的邻接矩阵 int x[NUM]; //当前解 int bestx[NUM]; //当前最优解向量 int cc; //当前费用 int bestc; //当前最优值 int NoEdge = -1; //无边标记 //形参t是回溯的深度，从2开始。根结点为第1层。城市编号从1开始.从第1个城市出发 void Backtrack(int t){ //到达叶子结点的父结点。旅行路径上的倒数第二个城市。最后一个城市是出发点 if(t==n) { if(a[x[n-1]][x[n]]!= NoEdge && a[x[n]][1]!= NoEdge && (cc + a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc== NoEdge)) { for(int i=1; i<=n; i++) bestx[i] = x[i]; bestc = cc + a[x[n-1]][x[n]] + a[x[n]][1]; } return; } else { for(int i=t; i<=n; i++) { if(a[x[t-1]][x[i]]!= NoEdge && (cc + a[x[t-1]][x[i]]< bestc||bestc == NoEdge)) { swap(x[t],x[i]); // 先交换。此时，X[t]的值发变化。 cc += a[x[t-1]][x[t]]; //再计算。不能交换顺序。 Backtrack(t+1); // 如果要改变顺序，应该为cc += a[x[t-1]][x[i]]。 cc -= a[x[t-1]][x[t]]; swap(x[t],x[i]); } } } }