图着色问题论述

在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。贪心法它适用于解一些组合数较大的问题。根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。

【关键词】图着色 回溯法 贪心法

1 图着色问题的分类

1.1 回溯法

回溯法是一种系统地搜索问题解的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。

用回溯法解题的一般步骤：

（1）描述解的形式，定义一个解空间，它包含问题的所有解。

（2）构造状态空间树。

（3）构造约束函数（用于杀死节点）。

1.2 贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对一些问题它能产生整体最优解或者是整体最优解的近似解。

贪心算法没有固定的算法框架，算法设计的关键是贪婪策略的选择。一定要注意，选择的贪婪策略要具有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的策略影响，也就是说某个状态以后的过程不会影响以前的状态，只与当前状态有关，也称为这种特性为无后效性。因此，适应用贪婪策略解决的问题类型较少，对所采用的贪婪策略一定要仔细分析其是否满足无后效性。

图的着色问题是由地图的着色问题引申而来的：用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。

2 问题处理

如果把每一个区域收缩为一个顶点，把相邻两个区域用一条边相连接，就可以把一个区域图抽象为一个平面图。

2.1 回溯法思想

回溯法有“通用解题法”之称，是一种比穷举“聪明”的搜索技术，在搜索过程中动态地产生问题的解空间，系统地搜索问题的所有解。当搜索到解空间树的任一结点时，判断该结点是否包含问题的解。如果该结点肯定不包含，则“见壁回头”，跳过以该结点为根的子树的搜索，逐层向其祖先结点回溯，可大大缩减无效操作，提高搜索效率。因此，结合具体案例的实际设计合适的回溯点是应用回溯法的关键所在。值得注意的是，递归具有回溯的功能，很多问题应用递归回溯可探索出问题的所有解。

2.2 贪心算法思想

贪心算法的思想是首先用第一种颜色对图中尽可能多的顶点着色，然后用第二种颜色对余下的顶点中尽可能多的顶点着色；如此等等，直到把所有的顶点都着完色。当用一种新颜色对余下的顶点着色时，我们采取下列步骤：

（1）选取某个未着色的顶点，并且用新颜色对它着色。

（2）扫描所有未着色的顶点集，对其中的每个顶点，确定它是否与已着新颜色的任何顶点相邻。若不相邻，则用新颜色对它着色。

首先把所有顶点的颜色初始化为0，然后依次为每个顶点着色。如果其中i个顶点已经着色，并且相邻两个顶点的颜色都不一样，就称当前的着色是有效的局部着色；否则，就称为无效的着色。如果由根节点到当前节点路径上的着色，对应于一个有效着色，并且路径的长度小于n，那么相应的着色是有效的局部着色。这时，就从当前节点出发，继续探索它的儿子节点，并把儿子结点标记为当前结点。在另一方面，如果在相应路径上搜索不到有效的着色，就把当前结点标记为死结点，并把控制转移去搜索对应于另一种颜色的兄弟结点。如果对所有m个兄弟结点，都搜索不到一种有效的着色，就回溯到它的父亲结点，并把父亲结点标记为死结点，转移去搜索父亲结点的兄弟结点。这种搜索过程一直进行，直到根结点变为死结点，或者搜索路径长度等于n，并找到了一个有效的着色为止。

图的m色优化问题：给定无向连通图G，为图G的各顶点着色， 使图中任2邻接点着不同颜色，问最少需要几种颜色。所需的最少颜色的数目m称为该图的色数。

4 色定理的应用

在一个平面或球面上的任何地图能够只用4种颜色来着色使得相邻的国家在地图上着有不同颜色，任意图的着色，采用的是Welch Powell法。

这次实验主要解决了一个问题，那就是图着色问题 ，用两种不同的方法来解决，分别用回溯法及贪心法。

用回溯法求图着色的时候，固定了数组的长度及颜色。按一下回车就可以出结果了，再利用空余的时间我想再去扩充，变成键盘输入。

用贪心法求图着色的时候，我输入一个值就变成了这个值的倍数为2。没有确定颜色，这比用回溯法求图着色占有优势一些。

参考文献

[1]吴昊等.ACM程序设计培训教程[M].北京：中国铁道出版社，2007.

[2]黄同成.程序设计基础教程（C语言）[M].长沙：湖南人民出版社，2011.

[3]黄同成，黄磊.程序设计实践教程（C语言）[M].长沙：湖南人民出版社，2011.

作者简介

王豪（1991-），男，湖南人。学士学位。研究方向为软件开发。

作者单位

邵阳学院 湖南省邵阳市 422000