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

这篇具有很好参考价值的文章主要介绍了【算法设计与分析】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)
else
    while 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列最终填充该节点颜色。同时记录结点的度在第一行。
    • 地区结点的表示用结构体Area,包括序号id、色号color、可选色数chooseNum、可选色数组choose、邻点数adjNum、邻点数组adjArray
    • 序号id从1开始。
    • 色号color用数字表示(colorNum表示最大色数)。
    • 可选色数chooseNum初始为最大色数(colorNum),用于填色顺序选择的第一策略指标,越小越优先填色(即MVR最小剩余量选择策略)。
    • 可选色数组choose为大小为colorNum+1、类型为bool的定长数组,下标表示色号。初始全为可选true。
    • 邻点数adjNum初始为0,用于填色顺序选择的第二策略指标,越大越优先填色(即DH最大度策略)。同时用于动态分配邻点数组adjArray。
    • 用邻点数adjNum动态分配邻点数组adjArray(int),存入邻点序号。
  2. 类型为Area的点集存
  3. 编写TestMap测试函数测试地图获取情况。

回溯填色伪代码

BACKTRACK(t)  //t为回溯层数
if t>areaNum
    SHOWMAP;  //终止条件,输出地图
    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.colorAmount
    else 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

小规模数据

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

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

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

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

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

用程序进行填色成功。(图2)

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

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

颜色轮寻获得全部480个结果(图3),运行时间小于1ms。

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

Figure 3 颜色轮换共480个结果

附件地图数据填涂;

le450_5a:共3840种答案,共用时4.762s(图4 5)

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

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

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

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

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

Figure 5 le450_15b单个答案及时间

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

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

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

统计数据

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

图表 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)

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

Figure 8点数100

点数200,时间分别为7.726s、8.098s、10.869s、9.092s。(图9)

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

Figure 9 点数200

点数300,时间分别为7.445s、7.659s、11.043s、22.895s。(图10)

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

Figure 10 点数300

点数400,时间分别为7.444s、7.434s、8.312s。(图11)

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

Figure 11 点数400

点数500,时间分别为7.62s、7.664s、8.312s。(图12)

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

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

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

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

总结

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

不断尝试每一条可行路径,出错时回退,直到找到可行解或全部解。提高回溯法的效率关键在于剪枝和路径选择策略。文章来源地址https://www.toymoban.com/news/detail-421827.html

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

到了这里,关于【算法设计与分析】3.回溯法—地图填色问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法分析与设计】第八章-回溯法

    约束条件 分为 显式约束 和 隐式约束 显式:规定了问题的解的分量的取值范围。如求n的全排列每个位置只能取1~n 隐式:用于判定候选解是否为可行解。如全排列的每个数字不允许重复。 问题状态和状态空间树         状态空间树是 描述问题解空间 的树形结构,每个结

    2024年02月08日
    浏览(47)
  • 算法-回溯相关问题-生成所有n位长的二进制字符串 Java版

    生成所有n位长的二进制字符串。假设A[0…n-1]是一个大小为n的数组。

    2024年02月16日
    浏览(40)
  • 算法分析与设计考前冲刺 (算法基础、数据结构与STL、递归和分治、 动态规划、贪心算法、 回溯算法)

    算法分析与设计考前冲刺 算法基础 算法是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。 程序是算法用某种程序设计语言的具体的 具体实现 算法特征: 有穷性(有限步) 确定性 输入 输出 可行性(有限时间) 算法的复杂性: 时间复杂性 和空间复

    2024年02月02日
    浏览(42)
  • 数据结构:地图着色问题——图的应用——回溯法

    目录 前言 一、解决问题的思路 二、存储结构设计 三、代码 1.创建图函数 2.判断色号是否相同函数 3.回溯函数 4.整体代码 总结 本次解决的问题:用图模拟部分地图,对各省进行着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少。 先来一张效果图 将邻接矩阵

    2024年02月04日
    浏览(52)
  • 算法分析五:回溯法与分⽀限界法

    1. 基本思想与解题步骤 基本思想: 把问题的解空间转化成了图或者树的结构表⽰,然后使⽤深度优先搜索策略进⾏遍历,遍历的过程中记录和寻找所有可⾏解或者最优解。 解题步骤: 针对所给问题,定义问题的解空间; 确定易于搜索的解空间结构; 以深度优先⽅式搜索解

    2024年02月09日
    浏览(29)
  • 【回溯算法】旅行商问题--TSP问题

    一销售商从n个城市中的某一城市出发,不重复地走完其余n—1个城市并回到原出发点,在所有可能的路径中求出路径长度最短的一条。本题假定该旅行商从第1个城市出发。 输入 对每个测试例,第1行有两个整数:n(4≤n≤10)和m(4≤m≤20 ) ,n是结点数,m是边数。 接下来m行,描

    2024年02月08日
    浏览(47)
  • 旅行商问题(回溯算法)

    回溯问题适合于解由向量的形式来构成的,这个向量空间中使用搜索的方法进行搜索,搜索使用宽度优先的方法。货郎问题又名旅行商问题,但其实更多教科书中更通用的叫法叫旅行商问题,下面来对旅行商问题使用回溯算法证明。 有n个城市,已知任两个城市之间的距离,

    2024年02月06日
    浏览(46)
  • 回溯算法--01背包问题

    目录 回溯算法--01背包问题 [算法描述] [回溯法基本思想] 法一: 法二:  代码:  运行结果 代码改进  0-1背包问题是子集选取问题。一般情况下,0-1背包问题是NP完全问题。0-1背包问题的解空间可以用子集树表示。 解0-1背包问题的回溯法与解装载问题的回溯法十分相似。 在

    2023年04月09日
    浏览(34)
  • 【回溯算法篇】N皇后问题

    🌠 作者:@ 阿亮joy. 🎆 专栏:《数据结构与算法要啸着学》 🎇 座右铭:每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根 n 皇后问题研究的是如何将 n 个皇后放置在 n × n 的棋盘上,并且使皇后彼此之间不能相互攻击。

    2024年01月16日
    浏览(37)
  • 算法与数据结构——递归算法+回溯算法——八皇后问题

    八皇后问题是一个经典的回溯算法问题,目的是在8×8的国际象棋棋盘上放置八个皇后,使得没有皇后可以互相攻击(即没有两个皇后在同一行、同一列或同一对角线上)。 回溯算法是一种解决问题的算法,它通过尝试所有可能的解决方案来解决问题。在八皇后问题中,计算

    2024年02月09日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包