《数据结构与算法分析》课件第9章

第9章搜索算法9.1回溯法9.2分支界限法

9.1回溯法

9.1.1回溯法的算法框架

1．问题的解空间

应用回溯法求解问题时，首先应明确定义问题的解空间，该解空间应至少包含问题的一个最优解。例如，对于有n种物品的0-1背包问题，其解空间由长度为n的0-1向量组成，该解空间包含了对变量的所有可能的0-1赋值。当n=3时，其解空间是

{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),

(1,1,0),(1,1,1)}在定义了问题的解空间后，还需要将解空间有效地组织起来，使得回溯法能方便地搜索整个解空间，通常将解空间组织成树或图的形式。例如，对于n=3的0-1背包问题，其解空间可以用一棵完全二叉树表示，如图9-1所示。从树根到叶子结点的任意一条路径可表示解空间中的一个元素，如从根结点A到结点J的路径对应于解空间中的一个元素(1,0,1)。图9-10-1背包问题的解空间树

2．回溯法的基本思想

确定了问题的解空间结构后，回溯法将从开始结点(根结点)出发，以深度优先的方式搜索整个解空间。开始结点成为活结点，同时也成为扩展结点。在当前的扩展结点处，向纵深方向搜索并移至一个新结点，这个新结点就成为一个新的活结点，并成为当前的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。此时应往回移动(回溯)至最近的一个活结点处，并使其成为当前的扩展结点。回溯法以上述工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。图9-2四个顶点的无向带权图

图9-3旅行售货员问题的解空间树综上所述，运用回溯法解题的关键要素有以下三点：

(1)针对给定的问题，定义问题的解空间；

(2)确定易于搜索的解空间结构；

(3)以深度优先方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

3．递归和迭代回溯

一般情况下可以用递归函数实现回溯法，递归函数模板如下：采用迭代的方式也可实现回溯算法，迭代回溯算法的模板如下：

4．子集树与排列树

图9-1和图9-3中的两棵解空间树是回溯法解题时常用的两类典型解空间树。

当给定的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树。例如，n个物品的0-1背包问题所对应的解空间树是一棵子集树，该类树通常有2n个叶子结点，总结点数为2n+1-1，遍历子集树的任何算法需要的计算时间复杂度均为O(2n)。9.1.2最大团问题

1．问题描述

给定一个无向图G=(V,E)，如果U

V，且对任意u,v∈U有(u,v)∈E，则称U是G的一个完全子图。G的完全子图U是G的一个团当且仅当U不包含在G的更大的完全子图中；G的最大团是指G中所含顶点数最多的团。(注：完全图是全连通图)。

在图9-4中，子集 {1,2} 是G的一个大小为2的完全子图，它不是一个团，原因是它包含于G的更大完全子图 {1,2,5} 中；而 {1,2,5} 是G的一个最大团。同理，完全子图 

{1,4,5}和 {2,3,5} 也是G的最大团。图9-4无向图G及其补图G'

2．算法设计

无向图G的最大团和最大独立集问题都可以用回溯法在时间复杂度为O(n2n)以内解决，且都可以看做图G的顶点集

V的子集选取问题，因此可以用子集树表示问题的解空间。9.1.3图的m着色问题

1．问题描述

给定一个无向连通图G和m种不同的颜色，用这些颜色为图G的各顶点着色，每个顶点染一种颜色，那么是否存在一种着色方案使得相邻顶点不重色。若一个图至少需要m种颜色才能使图中任何相邻顶点不重色，则m称为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。

2．算法设计

对于任意一个图G=(V,E)和m种颜色，如果这个图不是m可着色的，则给出不能着色；如果这个图是m可着色的，则找出所有不同的着色方案。图9-5n=3和m=3时的解空间树示意图9.1.4旅行售货员问题

设某旅行售货员要到多个城市推销商品，已知各城市之间的路程(旅费)，现在为其设计一条售货路线，要求从某驻地出发经过每个城市一遍，最后又回到驻地，且使总的路程(旅费)最小。

9.2分 支 界 限 法

9.2.1分支界限法的基本思想

分支界限法以广度优先或最小耗费(最大效益)优先的方式搜索问题的解空间树。常见的解空间树有子集树和排列树。从活结点表中选择下一个扩展结点作为当前扩展结点，常用的方法有两种：

(1)一般队列方法。一般队列方法是将活结点表组织成一般队列，并按队列中结点先进先出的原则选取下一个结点作为当前扩展结点。

(2)优先级队列方法。优先级队列方法是将活结点表组织成一个优先级队列，并按优先级队列中规定的结点优先级来选取优先级最高的下一个结点作为当前扩展结点。9.2.2装载问题

设有n个集装箱，计划将其装上两艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且wi≤c1+c2。那么是否有一个合理的装载方案，可将n个集装箱装上这两艘轮船。

当wi=c1+c2时，装载问题就等价于子集和问题；当c1=c2，且wi=2c1时，装载问题就等价于划分问题。如果给定的装载问题有解，则采用下面的策略可以得到一个最优装载方案：

(1)将第一艘轮船尽可能地装满；

(2)将剩余的集装箱装到第二艘轮船上。

第一艘轮船尽可能地装满等价于选取全体集装箱的一个子集，使该子集中的集装箱重量之和最接近c1。由此可知，装载问题等价于以下特殊的0-1背包问题：

1．一般队列分支界限法

求解装载问题的一般队列分支界限法只求出所要求的最优值，最优解将在后续内容介绍。

2．算法改进

设bestw是当前最优解，Ew是当前扩展结点对应的重量，r是剩余集装箱的重量。若Ew+r≤bestw，则可以将扩展结点所对应的子树剪去。

函数MaxLoading将bestw初始化为0，直至搜索到叶子结点时才更新bestw，因此在算法搜索到第一个叶子结点之前bestw=0，且r＞0，故Ew+r＞bestw总成立，即此时右子树测试不起作用。

3．构造最优解

为了在算法结束后能方便地构造出与最优值相对应的最优解，算法必须记录相应子集树中从活结点到根的路径，为此，必须设置指向其双亲结点的指针，并设置左右孩子标志。9.2.3布线问题

印刷电路板将布线区域划分成n m个方格阵列，如图

9-6(a)所示。电路布线问题要求确定连接方格a的中点和方格b的中点的最短布线方案。在布线时，电路只能沿直线或直角布线，并且要求所布线路不能相交，如图9-6(b)所示。图9-6印制电路板布线方格阵列在实现上述算法中，首先考虑记录电路板上某方格的位置：用结构体表示，结构体中有row和col两个成员。其次需要表示布线前进的方向：布线可沿右、下、左、上四个方向移动，分别用0、1、2、3表示。再用offset[i].row和offset[i].col(i=0,1,2,3)表示沿着四个方向移动一步时对于当前方格的相对位移，如表9-1所示。在一个7×7方格阵列中布线的例子如图9-7所示，其中，起始位置a=(3,2)；目标位置b=(4,6)；阴影方格表示被封锁的