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

相关资源下载
回溯法地图填色pre ppt
回溯法地图填色报告word
回溯法地图填色c++源代码
目录
相关资源下载
碎碎念
概览
背景知识
问题描述：
原理
回溯算法原理
回溯法涉及几个概念
回溯法伪代码
地图填色（回溯法）
搜索顺序策略（按优先级排序）
剪枝策略
地图数据获取
回溯填色伪代码
区域结点选择顺序策略实现（MRV最少剩余量选择策略和DH最大度选择策略）
排序规则伪代码
颜色轮换的实现
颜色排列组合的实现伪代码
向前检测剪枝策略实现（填色过程）
填色伪代码
小规模数据
附件地图数据填涂；
统计数据
随机不同规模图
总结
碎碎念
可谓几个里面最折磨的，学了点c++硬打，换了几种方案，调了8天emmmm太费时间了（maybe多年后功力够深九科秒杀）
概览回溯法算法设计思想。地图填色问题的回溯法解法。背景知识
为地图或其他由不同区域组成的图形着色时，相邻国家/地区不能使用相同的颜色。我们可能还想使用尽可能少的不同颜色进行填涂。一些简单的“地图”（例如棋盘）仅需要两种颜色（黑白），但是大多数复杂的地图需要更多颜色。
每张地图包含四个相互连接的国家时，它们至少需要四种颜色。1852年，植物学专业的学生弗朗西斯·古思里（）于1852年首次提出“四色问题” 。他观察到四种颜色似乎足以满足他尝试的任何地图填色问题，但他无法找到适用于所有地图的证明。这个问题被称为四色问题。长期以来，数学家无法证明四种颜色就够了，或者无法找到需要四种以上颜色的地图。直到1976年德国数学家沃尔夫冈·哈肯（ Haken）（生于1928年）和肯尼斯·阿佩尔（ Appel，1932年-2013年）使用计算机证明了四色定理，他们将无数种可能的地图缩减为1936种特殊情况，每种情况都由一台计算机进行了总计超过1000个小时的检查。
他们因此工作获得了美国数学学会富尔克森奖。在1990年，哈肯（Haken）成为伊利诺伊大学（ of ）高级研究中心的成员，他现在是该大学的名誉教授。
四色定理是第一个使用计算机证明的著名数学定理，此后变得越来越普遍，争议也越来越小更快的计算机和更高效的算法意味着今天您可以在几个小时内在笔记本电脑上证明四种颜色定理。
问题描述：
我们可以将地图转换为平面图，每个地区变成一个节点，相邻地区用边连接，我们要为这个图形的顶点着色，并且两个顶点通过边连接时必须具有不同的颜色。附件是给出的地图数据，请针对三个地图数据尝试分别使用5个（），15个（），25个（）颜色为地图着色。
原理回溯算法原理
基本思想就是按一定规则沿某条路走，遇到死节点就倒退，直到找到成功的路。它在包含问题所有解空间树中，按照深度优先从根节点搜索。对于每个节点，如果不包含就跳过。通过加强剪枝力度和设计搜索顺序可优化算法。
回溯法涉及几个概念
约束函数：用于去除非法解，起剪枝作用。满足为活结点，不满足为死节点。
状态空间树：解空间。
回溯法伪代码
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)//当前解满足约束条件和不越界就查找下一个
地图填色（回溯法）
在地图填色中，每块区域可看做一个结点，相邻区域用边连接，该关系可用邻接矩阵存储。
搜索顺序策略（按优先级排序）颜色选择——最少约束值
尽量少选周围结点可用颜色，避免对周围结点造成约束。
剪枝策略颜色轮换：对于每一组解通过颜色轮换就可得到几组解。如n种颜色通过轮换可得到n!组解。相应的搜索时对于这些路径可删除。即每次用1种颜色时，剩余可选清空。地图数据获取通过读写文件流获得邻接关系，用451*451邻接矩阵表示地图，初始0表示未邻接，1表示邻接。第0列最终填充该节点颜色。同时记录结点的度在第一行。类型为Area的点集存编写测试函数测试地图获取情况。回溯填色伪代码
BACKTRACK(t)//t为回溯层数if t>areaNumSHOWMAP;//终止条件，输出地图returnwhile c in color//遍历全部可选颜色COLORAREA(area[t])//填色if(JUDGE())//如果通过检测，则继续下一区域填色BackTrack(t+1)
区域结点选择顺序策略实现（MRV最少剩余量选择策略和DH最大度选择策略）
优先使用MRV，相等时考虑DH 。
MRV的操作细节是：需要在每次区域结点填色时更新各点剩余可选颜色，以获得填色后剩余结点剩余可选颜色最少的区域结点，作为下一次填色对象。有多个可选颜色同为最少的区域结点的话，选择其中度最大的点（DH）。各点的度数在地图初始时已经获得。
我考虑用一个大小为颜色总数的数组记录区域结点选择顺序，按照上面的排序策略，每次填完一个区域结点就进行新的排序，得到下一最优先填涂的区域结点。
排序规则伪代码
CMP(area1,area2)sort by area1.colorAmount < area2.colorAmountelse by area1.adjAmount > area2.adjAmount
颜色轮换的实现
颜色轮换策略本质是对区域结点进行先分组再填色的策略。
分组结果我用一个大小为(颜色总数)*(对应每种颜色区域结点数)的二维数组[][]存放，每种颜色对应区域结点数是在回溯过程中获得的。组数与颜色总数相同，每个组别里的区域结点填同一种颜色。具体颜色轮换的实现，实际上就是对全部n种颜色进行排列组合。对于每一种分组可有对应的n!种颜色排列组合答案。颜色排列组合的实现伪代码
COLOR-ROTATIONwhile area in all//遍历全部区域结点进行分组colorGroup[area.color][j++]=area//将该结点放入对应组别show(colorGroup)//展示分组结果while permutation(answer)//排列各组填色结果show(answer)//输出每一组排列答案
向前检测剪枝策略实现（填色过程）在上色时发现有邻点无色可涂，则证明出错，需要回溯。所以向前检测剪枝策略的实现放在了涂色函数。另外为实现上面的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）
1 题1地图数据和填色结果
用程序进行填色成功。（图2）
2 运行结果：地图初始化和填色结果
颜色轮寻获得全部480个结果（图3），运行时间小于1ms 。
3 颜色轮换共480个结果
附件地图数据填涂；
：共3840种答案，共用时4.762s（图4 5）
4 的3840种结果和运行时间
：单个运行时间为0.017s(图5)
5 单个答案及时间
：单个运行时间为0.016s(图6)
6 单个答案运行时间为0.016s
统计数据
图表 7 运行时间
表格 1 附件数据实验结果
地图
题1地图
颜色数
15
25
区域结点数
450
450
450
方案数
480
3840
n*15!
n*25!
运行时间
(1.24ms/ans)
17ms/ans
16ms/ans
随机不同规模图

文章插图
分析算法效率与图规模的关系（四色）。
以点数规模100-500，边数为点数倍数递增统计。最大答案数为10亿，统计运行时间。
点数100，时间分别为7.582s、10.896s、13.533s、12.673s 。（图8）
8点数100
点数200，时间分别为7.726s、8.098s、10.869s、9.092s 。（图9）
9 点数200
点数300，时间分别为7.445s、7.659s、11.043s、22.895s 。（图10）
10 点数300
点数400，时间分别为7.444s、7.434s、8.312s 。（图11）
11 点数400
点数500，时间分别为7.62s、7.664s、8.312s 。（图12）
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
【【算法设计与分析】3.回溯法—地图填色问题】7.444
7.434
8.312
500
7.62
7.664
8.321
图表 1 算法效率与图规模的关系
总结
不断尝试每一条可行路径，出错时回退，直到找到可行解或全部解。提高回溯法的效率关键在于剪枝和路径选择策略。
由运行时间可以看出随着图规模的增大，运行时间会相应增大。根据图密度的不同获得全部答案的难度也不同。当点规模较大且图密度较大时，运行时间和获得全部解的难度大大增加。在本次实验中需要注意几个点：