算法设计与分析 3回溯法—地图填色问题 pre ppt

仅做参考，copy冲查重塔峰 算法设计与分析 3回溯法—地图填色问题 pre ppt 回溯法地图填色 路径选择(MRV DH) 剪枝策略(向前检测和颜色轮换) 运行时间随图规模增大而增大 图密度 （1） 通过本次实验，我了解到回溯法的基本思想： 不断尝试每一条可行路径，出错时回退，直到找到可行解或全部解。提高回溯法的效率关键在于剪枝和路径选择策略。 （2） 在本次实验中，我尝试利用回溯法实现地图填色： ① 路径选择策略：即结点选择策略我采用了选择（MRV）和度最大选择（DH）策略，优先MRV再DH。 ② 剪枝策略：采用向前检测和颜色轮换策略。 ③ 每个区域可当做结点用结构体表示。需要记录最少剩余量(可选色)和度。 ④ 地图文件数据的获取：可采用文件流fstream读取。 ⑤ 邻接关系：可用邻接矩阵实现。 （3） 由运行时间可以看出随着图规模的增大，运行时间会相应增大。根据图密度的不同获得全部答案的难度也不同。当点规模较大且图密度较大时，运行时间和获得全部解的难度大大增加。