山东理工大学：《计算机算法设计与分析》课程教学课件（PPT讲稿）第五章 回溯算法 Backtrack Algorithm

山东程子太军 计算机算法设计与分析 Design and Analysis of Computer Algorithms 第五章回湖算法 Backtrack Algorithm 王红震 理学院

计算机算法设计与分析 Design and Analysis of Computer Algorithms 第五章 回溯算法 Backtrack Algorithm 王红霞 理学院

山东程子太军程 学习要点 SHANDONG UNIVERSITY OF TECHNOLOOY 华3会3会学会华A品 ● 理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 ● (1) 递归回溯 ● (2)迭代回溯 ● （3)子集树算法框架 ,(4)排列树算法框架 2025年4月3日

2025年4月3日 2 • 理解回溯法的深度优先搜索策略。 • 掌握用回溯法解题的算法框架 • （1）递归回溯 • （2）迭代回溯 • （3）子集树算法框架 • （4）排列树算法框架 学习要点

归本程子末军 提纲 SHANDONG UNIVERSITY OF TECHNOLOGY 器纹点会器空会空是路 一、回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题 2025年4月3日 3

2025年4月3日 3 提纲 一、回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题

归东理子太军 提纲 SHANDONG UNIVERSITY OF TECINOLOGY 一、 回溯法的算法框架 二、装载问题 三、n后问题 四、 0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题 2025年4月3日

2025年4月3日 4 提纲 一、回溯法的算法框架 二、装载问题 三、n后问题 四、0-1背包问题 五、最大团问题 六、图的m着色问题 七、旅行售货员问题

归本程子未军 深度优先搜索算法 SHANDONG UNIVERSITY OF TECINOLOGY 深度优先搜索算法(Depth-First-Search), 是搜索算法的一种。是沿着树的深度遍历树的 节点，尽可能深的搜索树的分支，如果发现目 标，则算法中止，属于盲目搜索。 深度优先搜索是图论中的经典算法，利用 深度优先搜索算法可以产生目标图的相应拓扑 排序表，利用拓扑排序表可以方便的解决很多 相关的图论问题，如最大路径问题等等。 2025年4月3日

2025年4月3日 5 深度优先搜索算法 深度优先搜索算法（Depth-First-Search）， 是搜索算法的一种。是沿着树的深度遍历树的 节点，尽可能深的搜索树的分支，如果发现目 标，则算法中止，属于盲目搜索。 深度优先搜索是图论中的经典算法，利用 深度优先搜索算法可以产生目标图的相应拓扑 排序表，利用拓扑排序表可以方便的解决很多 相关的图论问题，如最大路径问题等等

归本程子末军 SHANDONG UNIVERSITY OF TECHNOLOOY 3会会会会a会空是条 同时深度优先搜索算法的时间复杂度不高（为 线性时间复杂度)，遍历图的效率往往非常高。 因此，鉴于深度优先搜索算法的强大功能以及高 效性往往被研究图论问题的专家所推崇，他们常 建议在遇到未知性质的图时，先对图进行深度优 先遍历，以了解未知图的性质。 因发明“深度优先搜索算法”，霍普克洛夫特 与陶尔扬共同获得计算机领域的最高奖：图灵奖 2025年4月3日 6

2025年4月3日 6 同时深度优先搜索算法的时间复杂度不高（为 线性时间复杂度），遍历图的效率往往非常高。 因此，鉴于深度优先搜索算法的强大功能以及高 效性往往被研究图论问题的专家所推崇，他们常 建议在遇到未知性质的图时，先对图进行深度优 先遍历，以了解未知图的性质。 因发明“深度优先搜索算法”，霍普克洛夫特 与陶尔扬共同获得计算机领域的最高奖：图灵奖

归本程上太军 SHANDONG UNIVERSITY OF TECHNOLOGY 搜索与回溯是计算机解题中常用的算法， 很多问题无法根据某种确定的计算法则来求 解，可以利用搜索与回溯的技术求解。回溯 是搜索算法中的一种控制策略。它的基本思 想是：为了求得问题的解，先选择某一种可 能情况向前探索，在探索过程中，一旦发现 原来的选择是错误的，就退回一步重新选择 继续向前探索，如此反复进行，直至得到解 或证明无解。 2025年4月3日 7

2025年4月3日 7 搜索与回溯是计算机解题中常用的算法， 很多问题无法根据某种确定的计算法则来求 解，可以利用搜索与回溯的技术求解。回溯 是搜索算法中的一种控制策略。它的基本思 想是：为了求得问题的解，先选择某一种可 能情况向前探索，在探索过程中，一旦发现 原来的选择是错误的，就退回一步重新选择， 继续向前探索，如此反复进行，直至得到解 或证明无解

山东理子太军 ●迷宫游戏 SHANDONG UNIVERSITY OF TECHNOLOOY 营店 2025年4月3日

2025年4月3日 8 ⚫迷宫游戏

归东程子末军 ●例：迷宫游戏 SHANDONG UNIVERSITY OF TECHNOLOGY 会会是会会8会 开始 第一次回朔 第二次回朔第三次回朔 其他回朔 2025年4月 结束

2025年4月3日 9 ⚫例：迷宫游戏

归东程子太军 例：N后问题 SHANDONG UNIVERSITY OF TECHNOLOOY 会是3会☆ 2025年4月3日 10

2025年4月3日 10 例：N后问题