用回溯法求解图的m着色问题

《用回溯法求解图的m着色问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验二用回溯法求解图的m着色问题一、实验目的1、掌握回溯法求解问题的一般特征和步骤2、使用冋溯法编程求解图的m着色问题。二、实验原理回溯法是一个既带冇系统性又带冇跳跃性的的搜索算法。回溯法在包含问题的所宥解的解空问树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任何一个结点时，总是先判断该结点是否肯定不包含问题的解，如果肯定不含，则跳过对以该结点为根的子树搜索。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解吋，要回溯到根，且根结点的所冇子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只耍搜索到问题的一个解就口J冋溯法从开始结点（根

2、结点）出发，以深度优先搜索的方式搜索整个解空问。这个开始结点就成为一个活结点，同吋也成为当前的扩展结点。在当前的扩展结点处，搜索A纵深方A移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如来在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。冋溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点吋为止。三、问题描述给定一个无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。若一个阁最少需要m种颜色冰能使阁屮任何一条边连

3、接的2个顶点着有不同的颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。设计一个算法，找出用m种颜色对一个图进行着色的不同方案。四、算法设计与分析用邻接矩阵a来表示一个无向连通阁G=（V,E）。用整数1，2,…，m来表示m种不同的颜色。X[i]表示顶点i所着的颜色来，则问题的解向量可以表示为II元组x[l:nl。问题的解空间可表示一棵高度为n+1的完全m叉树。解空间树的第i层中每一结点都有m个儿子，每个儿+相应于x[i]的m个可能的着色之一，第n+1M结点均为叶结点。在回溯算法Backtrack中，当i〉n时，表示算法己搜索至一个叶结点，得到—个新的m着色方案

4、，因此当前已找到的可m着色方案数sum增1。当时，当前扩展结点Z是解空间树屮的一个内部结点。该结点有xfil=l，2,…，m。对当前扩展结点Z的每一个儿子结点，由函数Ok检查其可行性，并以深度优先的方式递归地对可行子树进行搜索，或剪去不可行子树。五、实验结果源程序：#includeusingnamespacestd;intcolor[100]，sum;boolok(intk,intc[100][l00]){for(inti=l;i

5、cktrack(intk，intn，intm，intc[100][100]){if(k>n){for(inti=l;i<=n;i++)cout«color[i]«’’’’；cout«endl;sum++;}elsefor(inti=l;i<=m;i++){color[k]=i;if(ok(k，c))backtrack(k+l，n，m，c);color[k]=0;}}intmain(){inti，j，n，m;intc[100][100];cout«n输入顶点数n和着色数m:n;cin»n;cin»m;cout«n输入无向图的邻接矩阵:";for(i=l;i<=n;i++)for(j=

6、l；j<=n;j++)cin»c[i][j]；cout«n着色所有可能的解An”；backtrack(l，n，m，c);cout«"着色可能解的总数力:,,«sum«endl;system(’’pause’’)；return0;A:(1,2,14)B:(14，l，3)C:(l，2,3,2)D:(l，3，l，2)E:(1343)F:(l，3,2,3)G:(2,12J)H:(2,L23)I:(24,3，l)J：(2,343)K:(2344)L:(23^3)M:(3，1J，1)N:(3,134)0:(343,2)P:(3,2，l，2)Q：(3,234)R：(3,23^)