仅做参考，copy冲查重塔峰
算法设计与分析 3回溯法—地图填色问题 pre ppt
回溯法地图填色
路径选择(MRV DH)
剪枝策略(向前检测和颜色轮换)
运行时间随图规模增大而增大
图密度
（1） 通过本次实验，我了解到回溯法的基本思想：
不断尝试每一条可行路径，出错时回退，直到找到可行解或全部解。提高回溯法的效率关键在于剪枝和路径选择策略。
（2） 在本次实验中，我尝试利用回溯法实现地图填色：
① 路径选择策略：即结点选择策略我采用了选择（MRV）和度最大选择（DH）策略，优先MRV再DH。
② 剪枝策略：采用向前检测和颜色轮换策略。
③ 每个区域可当做结点用结构体表示。需要记录最少剩余量(可选色)和度。
④ 地图文件数据的获取：可采用文件流fstream读取。
⑤ 邻接关系：可用邻接矩阵实现。
（3） 由运行时间可以看出随着图规模的增大，运行时间会相应增大。根据图密度的不同获得全部答案的难度也不同。当点规模较大且图密度较大时，运行时间和获得全部解的难度大大增加。
2022-06-18 22:05:50
10.8MB
仅供参考，copy冲查重塔峰
算法设计与分析 3回溯法地图填色报告.doc
(1) 回溯法算法设计思想。
(2) 地图填色问题的回溯法解法。
（1） 通过本次实验，我了解到回溯法的基本思想：
不断尝试每一条可行路径，出错时回退，直到找到可行解或全部解。提高回溯法的效率关键在于剪枝和路径选择策略。
（2） 在本次实验中，我尝试利用回溯法实现地图填色：
① 路径选择策略：即结点选择策略我采用了选择（MRV）和度最大选择（DH）策略，优先MRV再DH。
② 剪枝策略：采用向前检测和颜色轮换策略。
③ 每个区域可当做结点用结构体表示。需要记录最少剩余量(可选色)和度。
④ 地图文件数据的获取：可采用文件流fstream读取。
⑤ 邻接关系：可用邻接矩阵实现。
（3） 由运行时间可以看出随着图规模的增大，运行时间会相应增大。根据图密度的不同获得全部答案的难度也不同。当点规模较大且图密度较大时，运行时间和获得全部解的难度大大增加。
2022-06-18 22:05:49
1.99MB
仅供参考，copy冲查重塔峰
算法设计与分析-回溯法地图填色源代码.cpp
(1) 回溯法算法设计思想。
(2) 地图填色问题的回溯法解法。
（1） 通过本次实验，我了解到回溯法的基本思想：
不断尝试每一条可行路径，出错时回退，直到找到可行解或全部解。提高回溯法的效率关键在于剪枝和路径选择策略。
（2） 在本次实验中，我尝试利用回溯法实现地图填色：
① 路径选择策略：即结点选择策略我采用了选择（MRV）和度最大选择（DH）策略，优先MRV再DH。
② 剪枝策略：采用向前检测和颜色轮换策略。
③ 每个区域可当做结点用结构体表示。需要记录最少剩余量(可选色)和度。
④ 地图文件数据的获取：可采用文件流fstream读取。
⑤ 邻接关系：可用邻接矩阵实现。
（3） 由运行时间可以看出随着图规模的增大，运行时间会相应增大。根据图密度的不同获得全部答案的难度也不同。当点规模较大且图密度较大时，运行时间和获得全部解的难度大大增加。
（4） 在本次实验中需要注意几个点：
① 我使用c++编程，注意map为关键字不可使用。
② 为了确保地图获取功能和填色结果的正确性，可分别编写测试模块进行检查。
2022-06-18 22:05:49
8KB