回溯法实验(图的m着色问题).doc

《回溯法实验(图的m着色问题).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计实验报告第六次附加实验姓名学号班级时间12.26上午地点工训楼309实验名称回溯法实验(图的m着色问题)实验目的1.掌握回溯法求解问题的思想2.学会利用其原理求解图的m着色问题实验原理问题描述：给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。基本解题步骤：(1)针对所给问题，定义问题的解空间；(2)

2、确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。实验步骤（1）首先将给定的图利用抽象图表示出来；（2）判断该节点k当前的着色是否符合条件，需要判断x[k]与k节点其他相邻节点h的x[h]是否相等；（3）回溯过程，如果此时的节点值已经大于节点总数，代表已经着色完成，并且找到了一种可行解，此时可以将可行解数+1；（4）回溯从最后一个节点往上回溯，并一层一层更改节点至其他可用着色，以此来找到所有的填色方案。关键代码voidColor::Backtrack(intt){if(t>n)//到达叶子节点{sum++;//可行解+1

3、cout<<"着色：";for(inti=1;i<=n;i++)//输出可行解方案cout<

4、易找到解，解的个数也就越多。其次在这个问题上我们可以看到它的解空间树并不是一颗子集树，而是真个解空间，每一个结点都会将所有的颜色遍历一遍，从而找到合适的颜色，所以这个回溯问题还是相对于之前的子集树和排列树来说，还是相对简单一点的。实验心得着色问题是最早接触的回溯法问题，一开始起始只知道回溯法就是遇到不能满足条件的时候就换一种方法，如果找不到的话就返回到上一个节点换一种方式，图的着色问题和其他的着色问题很相似，但是更简单，因为它的限制条件只有一个，即相邻区域着色不能相同，当转化成抽象图时，即两个有连线的节点之间着色不能相同，而且不需要建立一个子集树来进行回溯，但是这个

5、有一个问题就是继续寻找下一层之后有一条语句是使x[t]=0，这条语句之前一直不能理解是什么意思，后来经过一些数据的手动测试，发现这个案例使用回溯法是使用了递归的方法，因此当完成叶子节点层之后，会回溯到其上一层，又重新更改其到另一种色号，在回溯叶子节点层，当这一层的所有颜色都尝试过之后，又会使再上一层的改变色号，再更改下两层色号，这样做的目的是因为回溯法可以找到所有的可行解，这样就通过回溯找到了所有的可行解。这个实验的完成是我更加熟悉了回溯法的原理和思想。实验得分助教签名附录：完整代码（回溯法）//图的m着色问题回溯法求解#includeusing

6、namespacestd;classColor{friendvoidmColoring(int,int,int**);private:boolok(intk);voidBacktrack(intt);intn,//图的顶点个数m,//可用颜色数**a,//图的邻接矩阵*x;//当前解longsum;//当前已找到的可m着色的方案数};boolColor::ok(intk)//检查颜色可用性{for(intj=1;j<=n;j++)if((a[k][j]==1)&&(x[j]==x[k]))//两个点之间有约束且颜色相同returnfalse;returntrue;}

7、voidColor::Backtrack(intt){if(t>n)//到达叶子节点{sum++;//可行解+1cout<<"着色：";for(inti=1;i<=n;i++)//输出可行解方案cout<