《用回溯法求解图的m着色问题》由会员分享，可在线阅读，更多相关《用回溯法求解图的m着色问题（4页珍藏版）》请在金锄头文库上搜索。
1、实验二用回溯法求解图的m 着色问题一、实验目的 1 2、使用回溯法编程求解图的m 着色问题。 二、实验原理 回溯法是一个既带有系统性又带有跳跃性的的搜索算法。回溯法在包含问题 的所有解的解空间树中， 按照深度优先的策略， 从根结点出发搜索解空间树。算 法搜索至解空间树的任何一个结点时，总是先判断该结点是否肯定不包含问题的 解，如果肯定不包含，则跳过对以该结点为根的子树搜索。否则，进入该子树， 继续按深度优先的策略进行搜索。 回溯法在用来求问题的所有解时，要回溯到根， 且根结点的所有子树都已被 搜索遍才结束。 而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就 可结束。 回溯法从开始结点
2、(根结点 )出发，以深度优先搜索的方式搜索整个解空间。 这个开始结点就成为一个活结点，同时也成为当前的扩展结点。 在当前的扩展结 点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并 成为当前扩展结点。 如果在当前的扩展结点处不能再向纵深方向移动，则当前的 扩展结点就成为死结点。此时，应往回移动(回溯)至最近的一个活结点处，并使 这个活结点成为当前的扩展结点。 回溯法即以这种工作方式递归地在解空间中搜 索，直至找到所要求的解或解空间中已无活结点时为止。 三、问题描述 给定一个无向连通图G 和 m 种不同的颜色。用这些颜色为图G 的各顶点着 色，每个顶点着一种颜色。若一个图最少
3、需要m 种颜色才能使图中任何一条边 连接的 2 个顶点着有不同的颜色，则称这个数m 为该图的色数。求一个图的色 数 m 的问题称为图的 m 可着色优化问题。设计一个算法，找出用m 种颜色对一 个图进行着色的不同方案。 四、算法设计与分析 用邻接矩阵 a来表示一个无向连通图G=(V,E)。 用整数 1,2,m 来表示 m 种 不同的颜色。 xi 表示顶点 i 所着的颜色来，则问题的解向量可以表示为n 元组 x1:n 。问题的解空间可表示一棵高度为n+1 的完全 m 叉树。解空间树的第i 层 中每一结点都有 m 个儿子，每个儿子相应于xi 的 m 个可能的着色之一， 第 n+1 层结点均为叶结点。
4、 在回溯算法 Backtrack 中，当 in 时，表示算法已搜索至一个叶结点，得到 一个新的 m 着色方案，因此当前已找到的可m 着色方案数 sum增 1。 当 in 时， 当前扩展结点 Z 是解空间树中的一个内部结点。该结点有 xi=1,2, ,m。对当前 扩展结点 Z 的每一个儿子结点 ,由函数Ok 检查其可行性，并以深度优先的方式 递归地对可行子树进行搜索，或剪去不可行子树。 五、实验结果 源程序： #include using namespace std; int color100,sum; bool ok(int k,int c100100) for(int i=1;in) for(int i=1;in; cinm; coutcij; cout“着色所有可能的解:n“; backtrack(1,n,m,c); cout“着色可能解的总数为:“sumendl; system(“pause“); return 0;
