1 /* 2 *问题描述：给定无向连通图G和m种不同的颜色。用这些颜色为图G的各个顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的两个顶点着不同的颜色。 3 *           这个问题是图的m可着色判定问题。若一个图最少需要m中颜色才能使图中每条边连接的2个顶点着不同的颜色，则称这个数m为该图的色数。 4 *算法分析：给定图G=(V,E)和m中颜色，如果这个图不是m可着色，给出否定回答；如果这个图是m可着色的，找出所有不同的着色法。 5 *           回溯法+子集树 6 *           问题的解空间可表示为一棵高度为n+1的完全m叉树，解空间树的第i层中每一个结点都有m个儿子，每个儿子相应于x[i]的m个可能的着色之一，第n+1层结点均为叶结点。         7 *算法效率：图m可着色问题的解空间树中的内结点个数是m^i之和（i从0到n-1），在最坏的情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色的可用性需耗时O(mn)。 8            因此回溯总的耗时为mn(m^n-1)/(m-1)=O(nm^n) 9 *附    注：初始化无向图矩阵的时候对角线赋值为0！！！ 10 *Author：xymaqingxiang11 *Time：2014--5-2212 */13 14 #include <fstream>15 #include <iostream>16 #include <stdlib.h>17 #include <conio.h>18 using namespace std;19 20 #define MAX_v 50 //定义一个最大顶点个数21 typedef struct{22     int a[MAX_v][MAX_v]; //无向图G的邻接矩阵23     int n; //无向图G的顶点数24     int m; //无向图G的颜色数25     int x[50]; //当前解26     long sum;//当前已找到的可m着色的方案数27 }MC;28 29 void Creat(MC &G);30 void Backtrack(MC &G,int t);31 32 void Creat(MC &G){33     int i,j;34     ifstream fin("data.txt");35     if (!fin)36     {37         cout<<"不能打开文件:"<<"data.txt"<<endl;38         exit(1);39     }40     fin>>G.n;41     fin>>G.m;42     for (int i=1;i<=G.n;i++)43         for (int j=1;j<=G.n;j++)44             fin>>G.a[i][j];45     for(i=1;i<=G.n;i++) //初始化46     {47         G.x[i]=0;48         G.sum=0;49     }50     cout<<"———回溯法求解图的m着色问题———"<<endl;51     cout<<"输入初始化无向图矩阵为:"<<endl; //初始化52     for(i=1;i<=G.n;i++)53     {54         for(j=1;j<=G.n;j++)55             cout<<G.a[i][j]<<" ";56         cout<<endl;57     }58     cout<<"输入初始化无向图顶点数为:"<<" "; //初始化59     cout<<G.n<<endl;60     cout<<"输入初始化无向图着色数为:"<<" "; //初始化61     cout<<G.m<<endl;62 }63 64 bool ok(MC &G,int k)65 {66     for(int j=1;j<=G.n;j++)67         if(G.a[k][j]==1&&G.x[j]==G.x[k])    //先后顺序——先判断是否相邻，然后判断颜色是否相同68             return false;69     return true;70 }71 72 void Backtrack(MC &G,int t){73     if (t>G.n){        //output()阶段74         G.sum++;75         for (int j=1; j<=G.n; j++)76             cout<<G.x[j]<<‘ ‘;77         cout<<endl;78     }79     else80     {81         for(int i=1;i<=G.m;i++)82         {83             G.x[t]=i;84             if(ok(G,t))85                 Backtrack(G,t+1);86             G.x[t]=0;    //递归回退时返回上一层，着色赋初值087         }88     }89 }90 91 int main(){92     MC G;93     Creat(G);94     Backtrack(G,1);95     getch();96 }

  1 /*  2 问题描述：将n块电路板以最佳排列方式插入带有n个插槽的机箱中。n块电路板的不同排列方式对应于不同的电路板插入方案。  3           设B={1, 2, …, n}是n块电路板的集合，L={N1, N2, …, Nm}是连接这n块电路板中若干电路板的m个连接块。Ni是B的一个子集，且Ni中的电路板用同一条导线连接在一起。  4           设x表示n块电路板的一个排列，即在机箱的第i个插槽中插入的电路板编号是x[i]。x所确定的电路板排列Density (x)密度定义为跨越相邻电路板插槽的最大连线数。  5           在设计机箱时，插槽一侧的布线间隙由电路板的排列的密度确定。因此，电路板排列问题要求对于给定的电路板连接条件(连接块)，确定电路板的最佳排列，使其具有最小密度。  6   7 算法设计：电路板排列问题是NP难问题，因此不大可能找到解此问题的多项式时间算法。考虑采用回溯法系统的搜索问题解空间的排列树，找出电路板的最佳排列。设用数组B表示输入。  8           B[i][j]的值为1当且仅当电路板i在连接块Nj中。设total[j]是连接块Nj中的电路板数。对于电路板的部分排列x[1:i]，设now[j]是x[1:i]中所包含的Nj中的电路板数。  9           由此可知，连接块Nj的连线跨越插槽i和i+1当且仅当now[j]>0且now[j]！=total[j]。用这个条件来计算插槽i和i+1间的连线密度。 10  11           在算法Backtrack中，当i=n时，所有n个电路板都已排定，其密度是cd。由于算法仅完成那些比当前最优解更好的排列，故cd肯定优于bestd，此时应更新bestd。 12           当i<n时，电路板排列尚未完成。x[1:i-1]是当前扩展点所相应的部分排列，cd是相应的部分排列的密度。在当前部分排列之后加入一块未排定的电路板，扩展当前部分排列产生当前扩展结点的一个儿子结点。 13           对于这个儿子结点，计算新的部分排列密度ld。仅当ld<bestd时，算法搜索相应子树，否则该子树剪去。 14  15 算法效率：在解空间排列树的每个节点处，算法Backtrack花费O(m)计算时间为每个儿子节点计算密度。因此计算密度所消耗的总计算时间为O(mn!)。 16           另外，生成排列树需要O(n!)时间。每次更新当前最优解至少使bestd减少1，而算法运行结束时bestd>=0。因此最优解被更新的额次数为O(m)。更新最优解需要O(mn)时间。 17           综上，解电路板排列问题的回溯算法Backtrack所需要的计算时间为O(mn!)。 18  19 Auther：xymaqingxiang 20 Time：2014-05-23 21 */ 22  23 //#include "stdafx.h" 24 #include <iostream> 25 #include <fstream>  26 #include <stdlib.h> 27 #include <conio.h> 28 using namespace std; 29  30 int k=0; 31  32 class Board 33 { 34     friend int Arrangement(int **B, int n, int m, int bestx[]); 35     private: 36         void Backtrack(int i,int cd); 37         int n,        //电路板数 38             m,        //连接板数 39             *x,        //当前解 40             *bestx,//当前最优解 41             bestd,  //当前最优密度 42             *total, //total[j]=连接块j的电路板数 43             *now,   //now[j]=当前解中所含连接块j的电路板数 44             **B;    //连接块数组 45 }; 46  47 template <class Type> 48 inline void Swap(Type &a, Type &b); 49  50 int Arrangement(int **B, int n, int m, int bestx[]); 51  52 int main() 53 { 54     int m ,n; 55     int bestx[9]; 56  57     ifstream fin("data.txt");  58  59     fin>>m; 60     fin>>n; 61     cout<<"m="<<m<<",n="<<n<<endl; 62     cout<<"N1={4,5,6},N2={2,3},N3={1,3},N4={3,6},N5={7,8}"<<endl; 63     cout<<"二维数组B如下："<<endl; 64      65     //构造B 66     int **B = new int*[n+1]; 67     for(int i=1; i<=n; i++) 68         B[i] = new int[m+1]; 69  70     for(int i=1; i<=n; i++) 71     { 72         for(int j=1; j<=m ;j++) 73         { 74             fin>>B[i][j]; 75             cout<<B[i][j]<<" "; 76         } 77         cout<<endl; 78     } 79  80     //第一种方案——只打印其中一种最优的电路排列 81     //cout<<"返回的其中一种最优解:"<<endl; 82     //cout<<"当前最优密度为:"<<Arrangement(B,n,m,bestx)<<endl; 83     //cout<<"最优排列为："<<endl; 84     //for(int i=1; i<=n; i++) 85         //cout<<bestx[i]<<" "; 86     //cout<<endl; 87  88     //第二种方案——打印出所有的最优电路排列 89     Arrangement(B,n,m,bestx); 90  91     for(int i=1; i<=n; i++) 92         delete[] B[i]; 93     delete[] B; 94  95     cout<<"总方案数为："<<k<<endl; 96     getch(); 97  98     return 0; 99 }100 101 void Board::Backtrack(int i,int cd)//回溯法搜索排列树102 {103     104     if(i == n)105     {106         cout<<endl;107         k++;108         cout<<"第"<<k<<"种最优密度为：";109         cout<<cd<<endl;110         cout<<"最优电路排列为：";111         for(int i=1; i<=n; i++)112             cout<<x[i]<<" ";113         cout<<endl;114         cout<<endl;115 116         for(int j=1; j<=n; j++)117             bestx[j] = x[j];118         bestd = cd;119     }120     else121     {122         for(int j=i; j<=n; j++)123         {124             //选择x[j]为下一块电路板125             int ld = 0;126             for(int k=1; k<=m; k++)127             {128                 now[k] += B[x[j]][k];129                 if(now[k]>0 && total[k]!=now[k])130                     ld ++;131             }132 133             //更新ld134             if(cd>ld)135                 ld = cd;136 137             if(ld<=bestd)//搜索子树————剪枝函数（ld<bestd时只打印其中一种最优排列；ld<=bestd可以打印出所有的最优排列）138             {139                 Swap(x[i],x[j]);140                 Backtrack(i+1,ld);141                 Swap(x[i],x[j]);142 143                 //恢复状态144                 for(int k=1; k<=m; k++)145                     now[k] -= B[x[j]][k];146             }147         }148     }    149 }150 151 int Arrangement(int **B, int n, int m, int bestx[])152 {153     Board X;154 155     //初始化X156     X.x = new int[n+1];157     X.total = new int[m+1];158     X.now = new int[m+1];159     X.B = B;160     X.n = n;161     X.m = m;162     X.bestx = bestx;163     X.bestd = m+1;164 165     //初始化total和now166     for(int i=1; i<=m; i++)167     {168         X.total[i] = 0;169         X.now[i] = 0;170     }171 172     //初始化x为单位排列并计算total173     for(int i=1; i<=n; i++)174     {175         X.x[i] = i;176         for(int j=1; j<=m; j++)177         {178             X.total[j] += B[i][j];179         }180     }181 182     //回溯搜索183     X.Backtrack(1,0);184     delete []X.x;185     delete []X.total;186     delete []X.now;187     return X.bestd;188 }189 190 template <class Type>191 inline void Swap(Type &a, Type &b)192 {  193     Type temp=a; 194     a=b; 195     b=temp;196 }

 1 template<class Type> 2 class Traveling 3 { 4     friend Type TSP(int **,int [],int,Type); 5     friend void main(void); 6 public: 7     Type BBTSP(int v[]); 8 private: 9     void Backtrack(int i);10     int n,               //图G的顶点数11         *x,              //当前解12         *bestx;          //当前最优解13     Type **a,            //图G的邻接矩阵14          cc,             //当前费用15          bestc,          //当前最优值16          NoEdge;         //无边标记17 };18 19 template<class Type>20 void Traveling<Type>::Backtrack(int i)21 {22     if(i==n)23     {24         if(a[x[n-1]][x[n]]!=NoEdge&&a[x[n][1]!=NoEdge&&25             cc+a[x[n-1]][x[n]]+a[x[n]][1]<bestc||bestc==NoEdge))26             for(int j=1;j<=n;j++)27                 bestx[j]=x[j];28         bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];29     }30     else31     {//是否进入左子树？32         for(int j=i;j<=n;j++)33             if(a[x[i-1][x[j]]!=NoEdge&&34                 (cc+a[x[i-1][x[j]]<bestc||bestc==NoEdge))35             {36                 //搜索子树37                 Swap(x[i],x[j]);38                 cc+=a[x[i-1][x[i]];39                 Backtrack(i+1);40                 cc-=a[x[i-1]][x[i]];41                 Swap(x[i],x[j]);42             }43     }44 }45 46 template<class Type>47 Type TSP(Type **a,int v[],int n,Type NoEdge)48 {49     Traveling<Type> Y;50     //初始化Y51     Y.x=new int[n+1];52     //置x为单位排列53     for(int i=1;i<=n;i++)54         Y.x[i]=i;55     Y.a=a;56     Y.n=n;57     Y.bestc=NoEdge;58     Y.bestx=v;59     Y.cc=0;60     Y.NoEdge=NoEdge;61     //搜索x[2:n]的全排列62     Y.Backtrack(2);63     delete []Y.x;64     return Y.bestc;65 }