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

实验二 用回溯法求解图的m着色问题一、 实验目的1、 掌握回溯法求解问题的一般特征和步骤2、 使用回溯法编程求解图的m着色问题。二、 实验原理回溯法是一个既带有系统性又带有跳跃性的的搜索算法。回溯法在

m 实验二用回溯法求解图的着色问题 一、实验目的 、掌握回溯法求解问题的一般特征和步骤 1 、使用回溯法编程求解图的着色问题。 2m 二、实验原理 回溯法是一个既带有系统性又带有跳跃性的的搜索算法。回溯法在包含问题 的所 有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算 法搜索至解 空间树的任何一个结点时，总是先判断该结点是否肯定不包含问题的 解，如果肯定不包 含，则跳过对以该结点为根的子树搜索。否则，进入该子树， 继续按深度优先的策略进 行搜索。 回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被 搜索遍 才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就 可结束。 回溯法从开始结点（根结点）出发，以深度优先搜索的方式搜索整个解空间。 这个 开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结 点处，搜索 向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并 成为当前扩展结点。 如果在当前的扩展结点处不能再向纵深方向移动，则当前的 扩展结点就成为死结点。此 时，应往回移动（回溯）至最近的一个活结点处，并使 这个活结点成为当前的扩展结点。 回溯法即以这种工作方式递归地在解空间中搜 索，直至找到所要求的解或解空间中已无 活结点时为止。 三、问题描述 给定一个无向连通图和种不同的颜色。用这些颜色为图的各顶点着 色，每 GmG 个顶点着一种颜色。若一个图最少需要种颜色才能使图中任何一条边 连接的个顶 m2 点着有不同的颜色，则称这个数为该图的色数。求一个图的色 数的问题称为图的 mm 可着色优化问题。设计一个算法，找出用种颜色对一 个图进行着色的不同方案。 mm 四、算法设计与分析 用邻接矩阵来表示一个无向连通图。用整数来表示种 不 ， aG=（V,E）1,2…,mm 同的颜色。表示顶点所着的颜色来，则问题的解向量可以表示为元组 。问 x[i]inx[l:n] 题的解空间可表示一棵高度为的完全叉树。解空间树的第层 中每一结点都有 n+1mi 个儿子，每个儿子相应于的个可能的着色之一，第层结点均为叶结点。 mx[i]mn+1 在回溯算法中，当时，表示算法已搜索至一个叶结点，得到 一个新 Backtracki>n 的着色方案，因此当前已找到的可着色方案数增。当时, 当前扩展结 mmsum1iWn 点是解空间树中的一个内部结点。该结点有。对当前 扩展结点的每一 Zx[i]=l,2,…,mZ 个儿子结点,由函数检查其可行性，并以深度优先的方式 递归地对可行子树进行搜 Ok 索，或剪去不可行子树。 五、实验结果 源程序： #include<iostream> using namespace std; int color [100],sum; bool ok(int k,int c[100][100]) ( for(int i=l;i<k;i++)