《算法设计与分析》课件 chp6回溯与分支限界法

回溯与分支限界法在算法设计与分析中,回溯算法和分支限界法是两种重要的策略,广泛应用于解决各种组合优化问题和决策问题。虽然这两种方法在基本原理和应用场景上有所不同,但它们都基于对解空间的系统性探索,以寻找满足特定条件的最优解或所有可行解。回溯法基本思想设想一个复杂的迷宫问题:迷宫的起点位于左上角,终点位于右下角。迷宫由若干个房间构成,各房间之间通过通道相连,而部分通道可能因墙壁阻挡而无法通行。问题要求找到一条从起点到终点的路径,保证路径上每一步均合法且畅通。走迷宫的思路面对走迷宫这一问题,常用的思路是:从起点出发,在每个房间可能有多个选择,例如向左、向右、向上或向下移动。在选择一条通道前进后,如果到达的房间发现所有通往未探索区域的通道均已堵塞而无法继续前行,则需要退回到上一个分叉点,重新选择另一条未曾尝试的通道,继续进行探索。这个过程可能需要重复多次,直至找到一条通往终点的有效路径。回溯法的核心特点做出选择在每个房间都需要做出选择,决定下一步的移动方向排除路线在不断地探索中,需要排除那些无法通往终点的路线回溯尝试当发现当前选择无法达到目标时,必须回溯到先前的决策点,尝试其他可能的选择回溯法的应用范围这些特点正是回溯法的核心思想。回溯法通过系统地尝试所有可能的选择,并逐步剔除不符合条件的路径,最终找到满足目标的解答。该方法不仅适用于解决迷宫问题,而且在组合优化、排列组合、图遍历等多个领域都有广泛应用。0-1背包问题回顾

之前,我们已使用枚举法、动态规划和贪心算法来求解此问题。在本章中,我们尝试使用回溯法进行求解。0-1背包问题示例问题参数以3个物品为例:

解空间特征对于每个物品,都有"装入背包"或"不装入背包"两种选择,因此整个搜索空间可以用一棵满二叉树表示,这棵树称为解空间树。解空间树结构根节点A对应起始状态,对于物品1有选择和不选择两种状态,分别对应树第二层的节点B和C。接下来,在节点B或C上,对物品2也有选择和不选择两种状态,产生第三层的4个节点。对于3个物品,解空间树共有8个叶节点,代表所有8种可能的方案。回溯法求解0-1背包问题就相当于对这棵解空间树的搜索过程。回溯搜索过程(1)01从根节点A开始按照深度优先的顺序搜索,从A到B,访问节点B。假设向左子树移动表示装入物品,而向右子树移动表示不装入物品,则节点B表示选择装入物品1。此时,背包剩余容量为14(即30-16),背包中物品总价值为45。当前搜索路径为:A→B。

回溯搜索过程(2)02

尝试装入物品2从节点B开始,按照深度优先的顺序搜索,访问节点D。由于物品2的重量大于背包剩余容量,无法装入物品2,因此这一分支无效,需回溯到其父节点B。回溯搜索过程(3)03

不装入物品2在节点B,搜索完D子树后,继续搜索E子树。在状态E下,决策为不装入物品2,此时背包剩余容量仍为14,物品总价值仍为45。当前搜索路径为:A→B→E。回溯搜索过程(4)

尝试装入物品3:

物品3的重量大于背包剩余容量,无法装入,故此分支无效,回溯至节点E找到第一个可行解:节点E的右子树尚未访问,接着访问节点K。此时得到一个可行解,背包总价值为45。当前搜索路径为:A→B→E→K。回溯到根节点:K访问完毕,回溯到其父节点E;E的子树均已访问,继续回溯到B,再回溯到节点A,此时发现节点A的右子树尚未访问。不装入物品1:A访问C。此时背包剩余容量为30,物品总价值为0。装入物品2:访问节点F。背包剩余容量为15(30-15),物品总价值为25。当前搜索路径为:A→C→F。回溯搜索过程(5)

找到最优解:从F出发,访问L,对应装入物品3。此时背包剩余容量为0,物品总价值增至50。继续探索:L为叶子节点,回溯至F。F的右子树尚未访问,随后访问M,得到一个可行解:仅装入物品2,背包总价值为25。搜索其他分支:M访问完毕后,回溯到F;回溯至C。此时C的右子树尚未访问,接着访问节点G。完成搜索：在节点G,首先访问其N,表示装入物品3,得到一个可行解:背包总价值为25。从节点N回溯到父节点G,再访问O,得到一个可行解:不装入物品3,背包总价值为0。0-1背包问题的回溯算法

回溯法的求解范式从初始状态出发,通过深度递归搜索在每一步中尝试所有可能的决策选项对每个选项进行合法性和可行性判断,不符合要求的立即剪枝,符合条件的则继续深入;当达到可行解或终止条件时回溯返回,最终收集所有解或最优解。n皇后问题接下来,我们再次思考如何求解n皇后问题。问题描述为:在一个n×n的棋盘上,摆放n个皇后,使得任意两个皇后不处于同一行、同一列以及同一对角线上,求共有多少种不同的摆放方法。此前,我们曾采用枚举法求解该问题,此方法需要枚举n!种可能的摆放方式,导致时间复杂度较高。为此,在本章中,我们尝试使用回溯法来求解n皇后问题。4皇后问题求解过程(1)以4皇后问题为例,对于第一个皇后(Q1),可以放在棋盘第一行的4个位置中的任意一个,共有4种选择。之后,对于第二个皇后(Q2),可以放在棋盘第二行的4个位置中的任意一个。依此类推,构成的解空间树是一棵深度为4的满4叉树。我们用Q1、Q2、Q3、Q4分别表示放在第一行、第二行、第三行和第四行的皇后,用(i,j)表示棋盘的第i行第j列。4皇后问题求解过程(2)放置Q1将Q1放在第1行的第一个位置(1,1)放置Q2对于Q2,尝试放在(2,1)或(2,2)均与Q1冲突,因此不可行;于是将Q2放置在不冲突的位置(2,3)Q3无法放置对于Q3,发现第三行的4个位置均与Q1或Q2冲突,因此无法放置Q3,需要回溯到Q2调整Q2位置在Q2已放在(2,3)的子树探索完毕后,尝试将Q2放在下一个位置,即(2,4)4皇后问题求解过程(3)继续放置Q3对于Q3,尝试将其放在(3,1)时,与Q1冲突,因此改尝试(3,2)Q4无法放置对于Q4,在第四行的4个位置均与前面的皇后冲突,因此Q4无法放置,需要回溯到Q3多次回溯由于Q3在(3,2)的情况已探索完毕,继续尝试Q3的其他摆放位置,但发现(3,3)或(3,4)均与Q2冲突,于是Q3需要回溯到Q2;而Q2在(2,4)的情况也已探索完毕,故回溯到Q14皇后问题求解过程(4)01调整Q1位置将Q1从(1,1)移到下一个位置,即(1,2)02放置Q2和Q3Q2只能放在(2,4)才能与Q1不冲突。将Q3放在(3,1)03找到第一个可行解对于Q4,在第四行(4,1)和(4,2)与Q3或Q1冲突,因此选择将Q4放在(4,3),此时得到一个可行的摆放方案04继续搜索尝试将Q4放在(4,4)时,与Q2冲突,因此回溯到Q3;而Q3在(3,2)、(3,3)和(3,4)均与前面的皇后冲突,故再次回溯到Q2;Q2已探索完毕,继续回溯到Q1。4皇后问题求解过程(5)将Q1移到下一个位置,即(1,3)。考虑到4×4的棋盘关于中线对称,Q1放在(1,3)的搜索路线与Q1放在(1,2)的情况对称,因此可根据Q1在(1,2)时获得的可行解直接推出一个新的可行解。最终,得到两个可行的摆放方案。n皇后问题的回溯算法回溯法遍历完整个解空间树的时间复杂度为O(n!)数独求解问题数独问题的目标是将一个9×9的网格填满数字1至9,使得每一行、每一列以及每个3×3的子网格中的数字均不重复。在本节中,我们尝试使用回溯法求解数独问题。我们将数独问题视为一个决策序列问题:从左到右、从上到下依次扫描每一个空格。数独求解的回溯策略决策过程当处理到某个空格时,尝试填入数字1至9中的某个数字(前提是不违反所在行、所在列以及所属3×3网格的约束条件)。如果存在可行的数字,则递归地填入下一个空格。回溯机制如果所有数字均不可行,则说明当前路径无效,需要回溯到上一个决策点,尝试其他数字。数独问题的解空间树通过这种深度优先搜索的过程,我们实际上在一棵隐含的解空间树上进行搜索。树的根节点对应初始状态,即给定的数独盘面;从根节点出发,当我们为第一个空格填入某个数字时,就相当于沿着树的一条分支向下走,形成一个新的状态。类似地,为下一个空格填数又会在该状态上拓展出若干子节点,每个子节点代表一次新的决策。最终,当搜索深入到树的叶子节点时,如果所有空格均已合法填满,则说明找到了一个完整的可行解;否则,在某个节点发现无法为当前空格填入合适的数字,该分支即被判定为死路,需要回溯到上一个节点,选择其他数字继续尝试。回溯法的一般性说明在本节中,我们将概括性地介绍回溯法。回溯法通常适用于一类通过搜索求解的决策问题和组合问题。这些问题的求解过程可以分解为一系列有序的决策步骤,每一步从有限的候选选项中选择其一。

回溯法的约束条件同时,这类问题通常伴随着一组约束条件,用以判断当前部分解是否满足要求。例如,n皇后问题要求所有皇后之间互不攻击;0-1背包问题要求选取的物品总重量不超过给定容量。此外,我们可以将问题的所有可能决策序列看作是一棵解空间树,其中每个节点对应一次决策或一个状态,每条边代表一次具体的选项选择。当搜索遍历到树的叶子节点时,如果该叶节点对应的解满足所有约束条件,则该解为一个可行解。回溯法的求解步骤状态定义与搜索起点从初始状态出发(例如:棋盘上尚未放置任何皇后,背包为空),确定搜索过程的起点。逐步决策与探索在每个决策点,尝试为下一个需要决策的元素选择一个可行的选项。如果所选选项与已选择的部分无冲突,则继续深入到下一个决策点;若发生冲突,则尝试其他选项。到达递归出口当所有决策点均已完成选择且满足所有约束条件时,即找到一个可行解。如果需要求得所有解,则继续搜索其他分支。回溯过程当在某个决策点无法找到合适的选项时,回溯到上一个决策点修改选择,探索另一条可能路径。回溯法算法框架回溯法的优化策略剪枝策略剪枝策略在搜索过程中起着至关重要的作用。具体来说,在发现当前部分解已经不可能产生最终的可行解或最优解时,我们立即停止沿该分支继续搜索。例如,在n皇后问题中,如果某一列已被占用,则无需在该列上重复尝试。高效数据结构借助更高效的数据结构也能显著提高状态检查的速度。通过使用额外的标记数组、位运算、散列表等手段,可以实现对某些约束条件的常量时间检查,从而减少不必要的计算开销。回溯法与穷举法的区别穷举法穷举法往往"盲目"地枚举所有排列组合,不论中途是否能提前判定失败,都需要生成所有可能的结果再进行检查。回溯法回溯法则是"按需搜索",在发现某条路径不可行时,立即剪枝,停止继续沿该路径搜索。回溯法明确地将问题映射为一棵解空间树,并采用深度优先策略有序地探索各个状态。分支限界法的基本思想在前面章节中,我们系统研究了回溯法的核心原理。回溯法通过构建解空间树并实施剪枝策略,为解决约束满足问题和组合优化问题提供了一种普适性框架。然而,其深度优先的搜索策略与保守的剪枝机制,可能导致在最坏情况下需要遍历指数级数量的节点。这促使我们思考:能否通过更精确的剪枝判断,在搜索早期识别并剪除无效分支?回溯法的工作机制解空间建模回溯法将问题的所有解映射为一棵解空间树,树的每一层代表一个决策步骤,每一条分支代表一次决策选项,每个节点表示部分解深度优先搜索沿树的分支纵向深入,直至发现完整解或不可行解时回溯可行性剪枝在搜索过程中,我们通过判断当前部分解是否违反约束条件来进行剪枝。一旦检测到无解或无望成为更优解的分支,立即回溯,省略对该分支下所有后续节点的访问分支限界法的核心思想那么,能否在回溯基础上进一步增强剪枝效率,使我们在搜索早期就能判定某个分支的未来潜力,从而尽早地"剪掉"更多分支,减少无谓的搜索?这便是"分支限界法"(BranchandBound)的核心思想所在。分支限界法与回溯法同样以解空间树为基本框架,对解空间进行有序、系统的搜索。分支限界法的基本要素分支(Branching)与回溯法类似,分支限界法在问题求解中也通过分解决策步骤,使解空间展现为一棵搜索树。每个节点对应一个部分解,每次决策产生新的分支节点。限界(Bounding)对于搜索树中的每个节点,利用限界函数为其部分解提供一个估计值(下界或上界),以预测在最理想情况下该分支能达到的最佳目标值。如果某分支的"最优潜力"低于当前已知的最优解,则可立即剪枝。搜索策略与分支选择分支限界法通常采用广度优先或优先队列来选择下一个扩展节点,而非简单的深度优先。通过灵活调整搜索策略和利用限界值判断,分支限界法有望在较早的时间点就发现高质量的可行解。分支限界法的优势总的来说,分支限界法本质上仍是对解空间树的搜索,但相比回溯法,"限界"这一机制使得剪枝更加高效。在解决0-1背包问题、旅行商问题和分配问题等组合优化问题时,分支限界法往往能够大幅减少实际访问的节点数量,从而提升求解效率。0-1背包问题的上界函数让我们再次回顾0-1背包问题。传统的回溯法主要依赖于超重剪枝(即当当前部分解的总重量超过容量时立即终止该分支)以及在到达叶子节点后更新最优解,从而减少搜索工作。然而,在最坏情况下,回溯法仍可能遍历大量无用分支。为了进一步提高搜索效率,我们希望在尚未遍历到叶子节点时,就能够判断当前分支的潜在最优性。如果当前分支的"最佳潜在结果"已经不可能超过当前已知的最优解,则继续搜索该分支便毫无意义。为此,我们为每个节点定义一个上界函数,该函数估计从当前节点继续向下搜索时能获得的最大装包价值。上界函数的设计

方式1假设剩余容量全部用来装入单位价值最高的物品,即全部装入物品1,则背包的价值上界为10×10=100。方式2按照价值密度依次装入物品。先装入物品1,使用4的容量,剩余6;然后用剩余容量全部装入物品2,其单位价值为6,上界为40+6×6=76。显然,方式1得到的100是一个比方式2更宽松的上界,但其计算更为简单。为了便于展示,我们默认采用方式1来计算上界。分支限界法求解0-1背包问题从根节点开始,生成左右两个节点,分别对应装入物品1和不装入物品1,并计算这两个节点的上界,分别为76和60。随后,选择上界较高的节点(根节点的左孩子)继续搜索,并生成其左右子节点。由于无法装入物品2,因此无需搜索其左子树;右子树的上界为70,进一步扩展其左右子树后,计算得到上界分别为69和64。接着,搜索左子树时得到了一个可行解,其总价值为65。随后,考虑其他未搜索的节点,其上界均小于当前已知的可行解65,因而无需继续搜索。最终,整个搜索过程结束,得到最优解65。优先队列的使用在上述过程中,当存在多个未探索的节点时,我们总是优先选择上界最大的节点进行搜索。这样做的原因在于:优先扩展上界较高的节点更有可能在较早阶段发现更优的可行解。一旦找到更优解,就能及时更新当前的最优值,从而提高后续剪枝的效率。这种策略能够在搜索深入之前就淘汰大量无望的分支,减少无效探索,从而使得整个搜索过程更加高效。因此,我们可以使用优先队列来组织节点,并以其上界值作为关键字进行排序。算法时间复杂度分析

虽然评估在平均情况下限界函数和优先队列的剪枝效果较为困难,但直观上看,限界函数越严格,剪枝效果越好,实际需要搜索的节点数就越少,从而降低算法的运行时间。然而,如果限界函数过于复杂,其计算开销可能会抵消剪枝带来的收益,因此在设计限界函数时需要在剪枝效果与计算成本之间取得平衡。分支限界法的求解范式01问题建模与初始化定义解空间树结构;定义限界函数;初始化优先队列。02搜索与分支当优先队列Q不为空时,循环执行:从Q中取出具有最高优先级的节点;如果该节点的上界值小于或等于当前最优解值,则剪枝;否则扩展该节点生成子节点。03终止条件与输出结果当优先队列为空时,搜索过程结束,记录的最优解即为问题的最优解。旅行商问题让我们再次回顾旅行商问题。旅行商问题的目标是找到一条最短路径,使得旅行商从某个城市出发,访问每个城市恰好一次,并最终返回起始城市。之前我们已经讨论了使用枚举法求解该问题的方法。本节中,我们尝试采用分支限界法来求解旅行商问题。由于旅行商问题要求求解最短路径,即一个最小化问题,因此我们需要设计一个下界函数,用以估计从当前节点继续扩展所能达到的最短路径长度。TSP问题的下界估计假设图中有5个节点和10条边,并且以A节点为出发点。我们已知在最优路径中,旅行商需要访问6个节点(起点与终点均为A),因此整条路径由5条边组成,这5条边的权重之和构成了路径的总成本。如果我们在每一步都选择边权最小的边(例如总是选择从A到C的最小边权),则这5条边权重的总和自然可以作为一个下界。然而,单纯采用每条边选择最小权重的策略往往会得到一个过于宽松的下界,从而导致剪枝效果不佳。更精确的下界估计

对所有未访问节点的贡献值求和后,由于每条边会在其两个端点中各被计算一次,为避免双重计数,我们需要将总和除以2,从而得到一个更贴近实际的下界估计。下界估计的局限性例如,在示例图中,节点A的贡献为1+3,节点B的贡献为3+6,节点C的贡献为1+2,节点D的贡献为3+4,节点E的贡献为3+2。因此,计算得到的估计下界为14。然而,这种方法仅考虑了每个节点的入边和出边,虽然反映了局部连通性,但未考虑整体路径的连通性,可能导致形成多个不连通的子路径甚至孤立的节点,而非一个完整的回路。1-树下界那么,如何保证所估计的下限对应的是一条连通的路径。可以从剩余节点(除起点外)构建一颗最小生成树,这就确保所有节点连通而且边的权重之和最小。然后,将最小生成树的代价加上起点的两条最小边权重,就得到了一个下界。以示例图为例,假设起始点为A,则{B,C,D,E}对应的最小生成树为{(D,E),(E,C),(C,B)},代价为3+2+6=11。起点A的两条最小权重边为AC和AB,则估计的下界为15(11+1+3)。这种方法称为1-树下界。它结合了起点两条最小边和剩余顶点的最小生成树,不仅考虑了各节点的局部连通性,还保证了整体路径的连通性,从而提供了一个更紧凑、有效的下界。分支限界法求解TSP问题(1)下面我们以示例图为例,使用分支限界法求解TSP问题:01问题建模与初始化以A为起始顶点。创建根节点node1,并计算其下限为14(采用入边出边方案计算最短路径下限);初始化优先队列Q(关键字为节点下限),并将根节点加入优先队列Q,此时Q={node1(14)}。02扩展根节点从Q中取出下限最低的节点node1,扩展生成根节点的4个子节点。节点2对应于走AB边,计算得到节点2的下限为14。节点3对应于走AC这条边,但由于图是无向图且解空间具有对称性,节点3可剪枝。分支限界法求解TSP问题(2)03扩展节点2从Q中取出下限最低的节点,即节点2。扩展节点2,生成3个子节点。节点6对应于走BC这条边,下限为16。节点7对应于走BD这条边,下限为16。节点8对应于走BE这条边,下限为19。04扩展节点6从Q中取出下限最低的节点,即节点6。扩展节点6,生成2个孩子节点。节点9对应于走CD这条边,其对应着路径A->B->C->D->E->A,代价为24,更新最优解为24。节点10对应于走CE这条边,代价为19,更新最优解为19。分支限界法求解TSP问题(3)05扩展节点7从Q中取出下限最低的节点,即节点7。扩展节点7,生成2个孩子节点。节点11对应于走DC这条边,代价为24。节点12对应于走DE这条边,更新最优解为16。06剪枝与终止从Q中取出下限最低的节点,即节点4。由于节点4的下限为16,等于目前已搜索到的最低的路径代价16,因此,不扩展此节点。从Q中取出下限最低的节点,即节点5,其下限大于已知可行解,不予扩展。同理,节点8也不予扩展。优先队列Q为空,算法结束,求得最短路径为A->B->D->E->C->A,代价为16。图着色问题图着色问题的目标是在给定的无向图中为每个顶点分配颜色,使得任意相邻顶点使用不同的颜色,同时尽可能减少所使用的颜色总数。换句话说,我们需要找到一个最小的合法着色方案,其中"合法"意味着不存在一条边的两个端点使用相同的颜色。图着色问题属于最小化问题,因为我们希望尽量减少使用的颜色数量。当采用分支限界法求解图着色问题时,关键在于设计一个下界函数,用于估计从当前节点(即部分着色状态)继续扩展后所必需的最少颜色数。图着色问题的下界函数以示例图为例,假设该图包含5个顶点和若干条边。若从零开始对图进行着色,最坏情况下每个顶点都需要使用不同的颜色,因此初始下界为5。这一下界虽然简单,但较为宽松,因为在实际图中,由于顶点间的邻接关系,很可能只需要少于5种颜色即可完成合法着色。除此之外,一个简单的下