计算机算法设计与分析（第6版）-课件 ch0501回溯法

回溯法LET'SEMBARKONTODAY'SSHARINGJOURNEYTOGETHER01回溯法概述Let'sembarkontoday'sjourneyofsharingandcommunicationtogether核心价值回溯法是一种深度优先搜索策略，能够在组合爆炸的问题中系统而跳跃地搜索解空间，既能求任一解也能求所有解。系统性与跳跃性它通过深度优先策略系统地探索解空间，同时利用剪枝函数跳过无望的分支，避免无效搜索，显著提高效率。应用广泛从0-1背包到旅行售货员问题，回溯法都能提供通用的解决方案，是解决复杂组合优化问题的强大工具。回溯法为何被称为通用解题法深度优先与剪枝协同机制深度优先搜索从根结点出发，沿着纵深方向逐层扩展，活结点与扩展结点交替，直至遇到死结点立即回溯至最近的活结点。剪枝功能利用约束函数和限界函数剪枝，剪去不可行子树和无望最优的子树，有效压缩搜索空间，提升搜索效率。02解空间构建Let'sembarkontoday'sjourneyofsharingandcommunicationtogether如何定义与组织解空间01将问题的所有可能解抽象成统一形式，如0-1背包问题的n维0-1向量，确保解空间至少包含一个最优解。定义解空间02通常用树或图来组织解空间，使搜索路径清晰可追踪，为算法实现提供直观蓝图。组织结构03通过树形结构，可以直观地表示从根结点到叶结点的路径，帮助理解搜索过程。可视化优势子集树与排列树典型结构排列树对应n个元素的全排列，叶结点有n!个，如旅行售货员问题，遍历复杂度为Ω(n!)。对应从n个元素中选取子集，叶结点有2^n个，如0-1背包问题，遍历复杂度为Ω(2^n)。子集树03回溯法的算法框架Let'sembarkontoday'sjourneyofsharingandcommunicationtogether递归回溯通用伪代码递归函数Backtrack(t)函数中，t表示当前深度，n控制递归出口。循环遍历for循环遍历可选值，Constraint与Bound双条件过滤，满足则递归深入下一层。通用性该框架与具体问题解耦，任何组合优化问题只需重写约束、限界与输出即可套用。迭代回溯非递归实现迭代实现用栈思想把递归转为迭代，维护变量t模拟栈顶，while循环控制回溯方向。优势迭代版在内存受限或需要精细控制搜索顺序的场景下更具优势，同时保持与递归版相同的剪枝逻辑。04经典应用案例Let'sembarkontoday'sjourneyofsharingandcommunicationtogether0-1背包回溯全过程示例以n=3、w=[16,15,15]、p=[45,25,25]、c=30为例，逐步演示搜索过程。问题实例从根A出发沿B-E-K路径得可行解(1,0,0)价值45，再回溯至C-F-L得价值50的更优解。搜索路径剪枝效果通过剩余容量与价值累加的实时计算，展示剪枝如何提前终止不可行分支。旅行售货员问题搜索轨迹用4城市带权图实例，展示解空间排列树的搜索路径。01从根到叶L得路线1-2-3-4-1费用59，经F-M得66被剪枝，后经D-H-N得25成为当前最优。

02搜索与剪枝问题实例05效率提升策略Let'sembarkontoday'sjourneyofsharingandcommunicationtogether约束函数与限界函数设计010203约束函数限界函数设计原则快速判定可行性，如背包容量超限立即剪枝，确保搜索效率。给出目标值上界或下界，如旅行售货员部分路线费用已高于当前最优即剪枝。约束与限界函数需在准确性与计算成本之间权衡，越紧致剪枝越强，但自身耗时需可控。内存与时间复杂度分析回溯法的空间复杂度仅为O(h(n))，即根到叶最长路径长度，因其只保存当前路径。空间复杂度时间复杂度取决于剪枝效果，最坏仍为遍历全树，但通过紧致剪枝可让平均情况远小于理论界。时间复杂度06算法模板与扩展Let'sembarkontoday'sjourneyofsharingandcommunicationtogether子集树算法模板速用模板结构初始化x数组，Backtrack(t)中循环0-1两种取值，先设x[t]=i再检查约束与限界。递归深入满足条件则深入下一层，通过递归实现深度优先搜索。适用场景适用于装载问题、最大团、0-1背包等多种需要子集树的问题。010203排列树算法模板速用01模板结构先初始化x为单位排列(1..n)，Backtrack(t)中从t到n循环交换x[t]与x[i]。02适用场景适用于旅行售货员、圆排列、电路板排列等需要全排列的问题。十大经典问题速查表以表格形式列出十大应用，每行列出问题名称、适用解空间树类型、核心约束与限界要点，方便快速匹配模板。问题速查回溯法只需三步——定义解空间、确定结构、深度优先加剪枝。三步法总结强调其通用性与易实现性，同时指出面对