一、实验目的与要求
1、实验基本要求：
（1）掌握回溯法算法设计思想。
（2）掌握地图填色问题的回溯法解法。
2、实验亮点：
（1）通过回溯法完成了实验，并验证了结果的正确性。
（2）在使用回溯法的基础上，从贪心剪枝，置换剪枝，向前探查剪枝，矩阵记录和选择邻接表进行数据存储5个方面对程序进行优化，大幅降低程序运行时间并在附件中上传了所有实验过程中的输出结果并对结果都进行了验证。
（3）通过实际操作与理论分析结合的方式，从图规模，合法涂色数，图的边密度和图的连通分量四个方面分析对比算法的效率。
（4）有针对性地探究了找到全部可行解的方法。
（5）最后思考并探究了轮换等有效剪枝策略，极大提高算法效率。
二、实验内容与方法
背景知识：
为地图或其他由不同区域组成的图形着色时，相邻国家/地区不能使用相同的颜色。 我们可能还想使用尽可能少的不同颜色进行填涂。一些简单的“地图”（例如棋盘）仅需要两种颜色（黑白），但是大多数复杂的地图需要更多颜色。
每张地图包含四个相互连接的国家时，它们至少需要四种颜色。1852年，植物学专业的学生弗朗西斯·古思里（Francis Guthrie）于1852年首次提出“四色问题”。他观察到四种颜色似乎足以满足他尝试的任何地图填色问题，但他无法找到适用于所有地图的证明。这个问题被称为四色问题。长期以来，数学家无法证明四种颜色就够了，或者无法找到需要四种以上颜色的地图。直到1976年德国数学家沃尔夫冈·哈肯（Wolfgang Haken）（生于1928年）和肯尼斯·阿佩尔（Kenneth Appel，1932年-2013年）使用计算机证明了四色定理，他们将无数种可能的地图缩减为1936种特殊情况，每种情况都由一台计算机进行了总计超过1000个小时的检查。
他们因此工作获得了美国数学学会富尔克森奖。在1990年，哈肯（Haken）成为伊利诺伊大学（University of Illinois）高级研究中心的成员，他现在是该大学的名誉教授。
四色定理是第一个使用计算机证明的著名数学定理，此后变得越来越普遍，争议也越来越小 更快的计算机和更高效的算法意味着今天您可以在几个小时内在笔记本电脑上证明四种颜色定理。
问题描述：
我们可以将地图转换为平面图，每个地区变成一个节点，相邻地区用边连接，我们要为这个图形的顶点着色，并且两个顶点通过边连接时必须具有不同的颜色。附件是给出的地图数据，请针对三个地图数据尝试分别使用5个（le450_5a），15个（le450_15b），25个（le450_25a）颜色为地图着色。
三、实验步骤与过程
1、未优化的回溯：
（1）算法描述：
a. 拓展当前节点，并对当前节点进行搜索
b. 判断当前节点是否存在可行解，如果存在则进入c，如果不存在，则回溯上一节点，并进入a
c. 判断是否搜索结束，如果结束则直接输出结果并停止搜索；如果未结束，则进入a
d. 当全部搜索完毕后仍不存在可行解，则输出无解
未经过优化的回溯算法流程图大致如下
（2）编程实现
大致代码如下：
void dfs(int x) { //如果已经涂完整个地图，即找到可行解 if (x > n) { ans++; return; } //对每个点进行涂色 for (int i = 1; i <= m; i++) { color[x] = i;//模拟涂色 //进行涂色的合法性检测 for (int j = 1; j <= x; j++) { if (g[j][x] && color[j] == color[x]) { b = 1; break;//非法，重新染色 } } if (b) { b = 0; } else { dfs(x + 1);//当前解合法，对当前节点进行拓展搜索 } } }
（3）运行并测试：
为了对算法进行测试，我选择了实验时给定的如下地图数据，并进行填涂尝试。
①图像数据文字化：
由于对于代码而言，不能够存储图像，因此需要将图像数据转为邻接矩阵进行图的存储。
将每个小块看成图的一个点，将图与图之间的邻接关系映射成点与点之间的连边。
②进行小数据试涂：
采用输入流将每个连边读入后调用函数进行计算，并通过输出流将结果输出（全部运行结果在‘result’->‘9_4_480.txt’中）并利用系统函数进行计时，可得对于这个给定地图，未优化的回溯在0.8544ms下找到全部480个解。
③涂色正确性检验：
完成了对地图的涂色后，务必对算法进行正确性检验以证明我们的涂色方案是正确的。
易知，涂色的正确性检验即检测所填涂地图中相邻的边的涂色是否相同，如果相同则为非法涂色，如果所有相邻点涂色都不同则涂色合法。
检测方法也相对简单，仅需遍历整个边集，并依次对相邻点进行颜色检验即可。通过检验，②中试涂的480个结果全部正确。证明回溯算法具有正确性。
④大数据试涂：
完成了小数据下的试涂后，尝试对大数据进行涂色，不过发现对附件中450点使用5色填涂不能在短时间内运行结束，并且运行比较长一段时间（12h+）也很难得到结果。这说明，常规的回溯算法只适用于数量级较小的数据，回溯算法亟待优化。
2、对回溯进行优化（本部分中时间消耗均为完备搜索的时间消耗）：
从上面的实验中，我们可以知道，常规的回溯算法耗时很长，而且搜索效率较慢，只能处理较低数量级的数据。因此需要对算法进行一系列优化。通过对运算过程的分析与计算，提出了如下几种可行的优化方案：（每种优化方案均进行了测试，并将测试结果存在‘result’文件夹中）
（1）贪心剪枝策略：
①算法描述：
通过分析，我们不难发现，对于搜索过程中产生的搜索树最大深度一定，但分支数很大，因此需要采用策略去降低搜索树的分支个数，从而对搜索树进行剪枝。
通过分析，我们可以知道，对于每次搜索出的节点，拓展的节点为当前的可行解个数。而且，分支产生的越早，分支就会产生的越多。因此，需要降低搜索树树根处分支数，尽量将分支数靠近叶子节点，从而进行贪心剪枝。
通过分析可以得知，不论从哪个点开始搜索，得到的可行解不变。因此，只需从度数大的点开始搜起，并依次按照点度数降序顺序依次搜索，直至搜索到最后一个点即可。
②具体实现：
本算法的具体实现相对简单，只需在最开始读入图数据之后，进行搜索之前按照点度数降序排序对图进行重构，再进行搜索即可。
//比较点度数函数 bool comp(const MapNode tmp1, const MapNode tmp2) { return tmp1.value < tmp2.value; } //排序重构函数 void arraySort() { sort(vArray + 1, vArray + vNum + 1, comp); for (int i = 1; i <= vNum; i++) { oldToNew[vArray[i].id] = i; newToOld[i] = vArray[i].id; } }
③运行并测试：
对给定的大数据（450点5色）进行填涂，并将可行解全部输出，将程序运行20次取时间平均值做表如下：
| 优化前 | 优化后 |
| 449.4s | 109.4s |
这证明，使用贪心算法进行优化是切实有效的优化方式，但算法的运行时间仍然比较长，需要进一步优化。
（2）置换剪枝策略：
①算法描述：
通过观察第一次优化输出的可行解，我们不难发现，在起始搜索点的不同涂色方案下的可行解个数相同，这是因为对于第一个搜索点而言，不同涂色下的各个填涂方案是对称的。即对于在涂色x 0 下的解向量
，可以映射出n − 1 （n为可用颜色数）个等效可行解。因此搜索时只需固定第一个点，并将搜索出来的可行解个数乘以可用颜色数即可。大约可以将实际运行时间缩短至原来的
（n 为可用颜色数）。
②具体实现：
本算法的具体实现很简单，只需在搜索时固定第一个颜色即可
③运行并测试：
对给定的大数据（450点5色）进行填涂，并将可行解全部输出，将程序运行20次取时间平均值做表如下：
| 优化前 | 优化后 |
| 679s | 140.4s |
这证明，使用置换剪枝策略进行优化是切实有效的优化方式，但算法的运行时间仍然比较长，需要进一步优化。
（3）向前探查剪枝策略：
①算法描述：
在搜索过程中，对于一些无解的节点，可以做到提前探查，即拓展节点前先对是否存在可行解进行检查，如果不存在可行解，则剪枝并返回。
②具体实现：
在本题中，采用了colorMatrix数组对每个点可以使用的颜色进行计数。并在回溯搜索时对当前点的合法颜色进行检测，如果没有则直接返回，无需拓展。
③运行并测试：
对给定的大数据（450点5色）进行填涂，并将可行解全部输出，将程序运行20次取时间平均值做表如下：
| 优化前 | 优化后 |
| 264.1s | 249.5s |
这证明，使用向前探查剪枝策略进行优化是有效的优化方式，但优化并不十分明显。
