【算法设计与分析】3.回溯法—地图填色问题

相关资源下载

回溯法地图填色pre ppt

回溯法地图填色报告word

回溯法地图填色c++源代码

目录

相关资源下载

碎碎念

概览

背景知识

问题描述：

原理

回溯算法原理

回溯法涉及几个概念

回溯法伪代码

地图填色（回溯法）

搜索顺序策略（按优先级排序）

剪枝策略

地图数据获取

回溯填色伪代码

区域结点选择顺序策略实现（MRV最少剩余量选择策略和DH最大度选择策略）

排序规则伪代码

颜色轮换的实现

颜色排列组合的实现伪代码

向前检测剪枝策略实现（填色过程）

填色伪代码

小规模数据

附件地图数据填涂；

统计数据

随机不同规模图

总结

---

碎碎念

        可谓几个里面最折磨的，学了点c++硬打，换了几种方案，调了8天emmmm太费时间了（maybe多年后功力够深九科秒杀）

概览

1. 回溯法算法设计思想。
2. 地图填色问题的回溯法解法。

背景知识

        为地图或其他由不同区域组成的图形着色时，相邻国家/地区不能使用相同的颜色。 我们可能还想使用尽可能少的不同颜色进行填涂。一些简单的“地图”（例如棋盘）仅需要两种颜色（黑白），但是大多数复杂的地图需要更多颜色。 
        每张地图包含四个相互连接的国家时，它们至少需要四种颜色。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）颜色为地图着色。

原理

回溯算法原理

        基本思想就是按一定规则沿某条路走，遇到死节点就倒退，直到找到成功的路。它在包含问题所有解空间树中，按照深度优先从根节点搜索。对于每个节点，如果不包含就跳过。通过加强剪枝力度和设计搜索顺序可优化算法。

回溯法涉及几个概念

约束函数：用于去除非法解，起剪枝作用。满足为活结点，不满足为死节点。

状态空间树：解空间。

回溯法伪代码

BackTrack (t)  //t为层数
if ( t > n )output (x)
elsewhile i in tree   //所有满足结点x[t] = h(i)  //当前解if Constraint(t) and Bound(t)BackTrack (t+1)  //当前解满足约束条件和不越界就查找下一个

地图填色（回溯法）

        在地图填色中，每块区域可看做一个结点，相邻区域用边连接，该关系可用邻接矩阵存储。

搜索顺序策略（按优先级排序）

• 结点选择
  • 最少剩余量选择（MRV）：优先选择剩余可选颜色最小的区域。
  • 度最大选择（DH）：优先选择相邻最多的结点，因为他对其他块的约束最多，即度最多结点。
• 颜色选择——最少约束值

        尽量少选周围结点可用颜色，避免对周围结点造成约束。

剪枝策略

• • 每次区域填色后，删除相邻区域待选颜色中的该种颜色。
  • 向前检测：若出现有区域可选颜色为空，则证明为死结点，需要剪枝。（提前单步试错）
  • 约束传播：若出现有区域可选颜色只剩1种，也可先填上去，发现填后有区域无颜色可填，也证明为死节点，需要剪枝。（提前2步试错
• 颜色轮换：对于每一组解通过颜色轮换就可得到几组解。如n种颜色通过轮换可得到n!组解。相应的搜索时对于这些路径可删除。即每次用1种颜色时，剩余可选清空。

地图数据获取

1. 通过读写文件流fstream获得邻接关系，用451*451邻接矩阵表示地图，初始0表示未邻接，1表示邻接。第0列最终填充该节点颜色。同时记录结点的度在第一行。
2. • 地区结点的表示用结构体Area，包括序号id、色号color、可选色数chooseNum、可选色数组choose、邻点数adjNum、邻点数组adjArray
3. • 序号id从1开始。
   • 色号color用数字表示（colorNum表示最大色数）。
   • 可选色数chooseNum初始为最大色数（colorNum），用于填色顺序选择的第一策略指标，越小越优先填色（即MVR最小剩余量选择策略）。
   • 可选色数组choose为大小为colorNum+1、类型为bool的定长数组，下标表示色号。初始全为可选true。
   • 邻点数adjNum初始为0，用于填色顺序选择的第二策略指标，越大越优先填色（即DH最大度策略）。同时用于动态分配邻点数组adjArray。
   • 用邻点数adjNum动态分配邻点数组adjArray（int），存入邻点序号。
4. 类型为Area的点集存
5. 编写TestMap测试函数测试地图获取情况。

回溯填色伪代码

BACKTRACK(t)  //t为回溯层数
if t>areaNumSHOWMAP;  //终止条件，输出地图return
while c in color  //遍历全部可选颜色COLORAREA(area[t])  //填色if(JUDGE())  //如果通过检测，则继续下一区域填色BackTrack(t+1)

区域结点选择顺序策略实现（MRV最少剩余量选择策略和DH最大度选择策略）

        优先使用MRV，相等时考虑DH。

1. MRV的操作细节是：需要在每次区域结点填色时更新各点剩余可选颜色，以获得填色后剩余结点剩余可选颜色最少的区域结点，作为下一次填色对象。
2. 有多个可选颜色同为最少的区域结点的话，选择其中度最大的点（DH）。各点的度数在地图初始时已经获得。

        我考虑用一个大小为颜色总数colorNum的数组记录区域结点选择顺序，按照上面的排序策略，每次填完一个区域结点就进行新的排序，得到下一最优先填涂的区域结点。

排序规则伪代码

CMP(area1,area2)
sort by area1.colorAmount < area2.colorAmountelse by area1.adjAmount > area2.adjAmount

颜色轮换的实现

颜色轮换策略本质是对区域结点进行先分组再填色的策略。

1. 分组结果我用一个大小为colorNum(颜色总数)*areaNum(对应每种颜色区域结点数)的二维数组colorGroup[colorNum][areaNum]存放，每种颜色对应区域结点数是在回溯过程BACKTRACK中获得的。组数与颜色总数colorNum相同，每个组别里的区域结点填同一种颜色。
2. 具体颜色轮换的实现，实际上就是对全部n种颜色进行排列组合。对于每一种分组可有对应的n!种颜色排列组合答案。

颜色排列组合的实现伪代码

COLOR-ROTATION
while area in all  //遍历全部区域结点进行分组colorGroup[area.color][j++]=area  //将该结点放入对应组别
show(colorGroup)  //展示分组结果
while permutation(answer)  //排列各组填色结果show(answer)  //输出每一组排列答案

向前检测剪枝策略实现（填色过程）

1. 在上色时发现有邻点无色可涂，则证明出错，需要回溯。所以向前检测剪枝策略的实现放在了涂色函数。
2. 另外为实现上面的MRV剩余可选色更新以及颜色轮寻对新颜色的检测，填色时也要相应更新。

填色伪代码

COLOR-AREA(area,color)  //参数为待填区域结点和待填颜色area.color = color  //上色
if color is new  //该色未被使用（颜色轮寻）color.colorUseFirst= area //记录首次使用该色的结点(该点不可换色)LOCK(area.colorChoose)  //该点颜色更换锁定，不可换色while adjArea in area.adjArea //遍历该点全部邻点更新可选色(MRV)UPDATE-COLORCHOOSE(adjArea)  //邻点可选颜色更新if adjArea.chooseColorNum == 0//若某点无可选色,报错(向前检测)return false

小规模数据

        对下面这个小规模数据，利用四色填色测试算法的正确性

对于该地图，首先我对区域进行编号如下，抽象为区域结点，并将区域间的邻接关系记录于文档。（图1）

Figure 1 题1地图数据和填色结果

用程序进行填色成功。（图2）

Figure 2 运行结果：地图初始化和填色结果

颜色轮寻获得全部480个结果（图3），运行时间小于1ms。

         

Figure 3 颜色轮换共480个结果

附件地图数据填涂；

le450_5a：共3840种答案，共用时4.762s（图4 5）

Figure 4 le450_5a的3840种结果和运行时间

le450_15b：单个运行时间为0.017s(图5)

Figure 5 le450_15b单个答案及时间

le450_25a：单个运行时间为0.016s(图6)

 

Figure 6 单个答案运行时间为0.016s

统计数据

  

图表 7 运行时间

表格 1 附件数据实验结果

地图	题1地图	le450_5a	le450_15b	le450_25a
颜色数	4	5	15	25
区域结点数	9	450	450	450
方案数	480	3840	n*15!	n*25!
运行时间	<1ms	4762ms(1.24ms/ans)	17ms/ans	16ms/ans

随机不同规模图

        分析算法效率与图规模的关系（四色）。

    以点数规模100-500，边数为点数倍数递增统计。最大答案数为10亿，统计运行时间。

点数100，时间分别为7.582s、10.896s、13.533s、12.673s。（图8）

Figure 8点数100

点数200，时间分别为7.726s、8.098s、10.869s、9.092s。（图9）

Figure 9 点数200

点数300，时间分别为7.445s、7.659s、11.043s、22.895s。（图10）

Figure 10 点数300

点数400，时间分别为7.444s、7.434s、8.312s。（图11）

Figure 11 点数400

点数500，时间分别为7.62s、7.664s、8.312s。（图12）

  

Figure 12 点数500

随机生成地图不同图规模、最大10亿数据运行运行时间统计如下(s)，可见当数据量较大且边比较密集时，所需时间较大。（表2）

表格 2 随机地图不同图规模运行时间

点数vn      边数倍数	vn	2vn	3vn	4vn
100	7.582	10.896	13.533	12.673
200	7.726	8.098	10.869	9.092
300	7.445	7.659	11.043	22.895
400	7.444	7.434	8.312
500	7.62	7.664	8.321

图表 1 算法效率与图规模的关系

总结

• 通过本次实验，我了解到回溯法的基本思想：

不断尝试每一条可行路径，出错时回退，直到找到可行解或全部解。提高回溯法的效率关键在于剪枝和路径选择策略。

• 在本次实验中，我尝试利用回溯法实现地图填色：
  • 路径选择策略：即结点选择策略我采用了选择（MRV）和度最大选择（DH）策略，优先MRV再DH。
  • 剪枝策略：采用向前检测和颜色轮换策略。
  • 每个区域可当做结点用结构体表示。需要记录最少剩余量(可选色)和度。
  • 地图文件数据的获取：可采用文件流fstream读取。
  • 邻接关系：可用邻接矩阵实现。
• 由运行时间可以看出随着图规模的增大，运行时间会相应增大。根据图密度的不同获得全部答案的难度也不同。当点规模较大且图密度较大时，运行时间和获得全部解的难度大大增加。
• 在本次实验中需要注意几个点：
  • 我使用c++编程，注意map为关键字不可使用。
  • 为了确保地图获取功能和填色结果的正确性，可分别编写测试模块进行检查。
  • 最初的实现我只采用不断调用新的BackTrack函数进行前进和回溯，没有返回，这样导致的问题是一旦点规模和图密度增大时，调用次数过大而导致创建的栈帧过多，使栈溢出。所以需要在每一层调用完毕后及时返回，实现真正的回溯过程。
  • 对于死节点的回溯需要做好复原工作。