第五章 图的搜索算法 55 分支限界法551 分枝搜索算法552 分枝-限界搜索算法553 算法框架 56 图的搜索算法小结 551 分枝搜索算法 1基本思想分支搜索法也是一种在问题解空间上进行尝试搜索算法。所谓 “分支”是采用广度优先的策略，依次生成E-结点所有分支，也就 是所有的儿子结点。和回溯法一样，在生成的节点中，抛弃那些不 满足约束条件（或者说不可能导出最优可行解）的结点，其余节点 加入活节点表。然后从表中选择一个节点作为下一个E-节点。选择 下一个E-节点的方式不同导致几种不同的分支搜索方式：1FIFO搜索 2LIFO搜索 3优先队列式搜索 上一页 下一页 返回首页 5.5.2 5.5.3 5.61FIFO搜索一开始，根结点是唯一的活结点，根结点入队。从活结点 队中取出根结点后，作为当前扩展结点。对当前扩展结点，先 从左到右地产生它的所有儿子，用约束条件检查，把所有满足 约束函数的儿子加入活结点队列中。再从活结点表中取出队首 结点（队中最先进来的结点）为当前扩展结点，直到找 到一个解或活结点队列为空为止。返回 上一页 下一页 返回首页 LIFO搜索 优先队列式搜索 5.5.2 5.5.3 5.62LIFO搜索一开始，根结点入栈。从栈中弹出一个结点为当前扩展结点。对当前扩展结点，先从左到右地产生它 的所有儿子，用约束条件检查，把所有满足约束函数 的儿子入栈，再从栈中弹出一个结点（栈中最后进来 的结点）为当前扩展结点，直到找到一个解或 栈为空为止。返回 上一页 下一页 返回首页 FIFO搜索 优先队列式搜索 5.5.2 5.5.3 5.63优先队列式搜索为了加速搜索的进程，应采用有效地方式选择 E-结点进行扩展。优先队列式搜索，对每一活结点计算一个优先级（某些信息的函数值），并根据这 些优先级，从当前活结点表中优先选择一个优先级 最高（最有利）的结点作为扩展结点，使搜索朝着 解空间树上有最优解的分支推进，以便尽快地找出 一个最优解。这种扩展方式要到下一节才用的到。返回 上一页 下一页 返回首页 FIFO搜索 LIFO搜索 5.5.2 5.5.3 5.6552 分枝-限界搜索算法【例2】有两艘船，n 个货箱。第一艘船的载重量是c1，第二艘船的载重量是c2，wi 是货箱i 的重量,且w 1+w2+wnc1+c2。我们希望确定是否有一种可将所有n 个货箱全部装船的方法。若有 的话，找出该方法 FIFO限界搜索算法优先队列式分支限界法上一页 下一页 返回首页 5.5.1 5.5.3 5.6算法1的缺点有:1）在可解的情况下，没有给出每艘装载物品的方案。而要 想记录第一艘船最大装载的方案，象回溯法中用n个元素的数组 是不能实现的，可以象5.2.2小节中的例子用数组队列下标记录 解方案。这里采用构造二叉树的方法，和5.2.2小节中的例题一样只需 要记录最优解的叶结点，这样二叉树就必需有指向父结点的指 针，以便从叶结点回溯找解的方案。又为了方便知道当前结点 对物品的取舍情况，还必须记录当前结点是父结点的哪一个儿 子。 数据结构：由此，树中结点的信息包括：weight;parent; LChild;。同时这些结点的地址就是抽象队列的元素，队列操作 与算法1相同 .上一页 下一页 返回首页 优先队列式分支限界法 5.5.1 5.5.3 5.62）算法1是在对子集树进行盲目搜索，我们虽然不能将搜索 算法改进为多项式复杂度，但在算法中加入了“限界”技巧，还 是能降低算法的复杂度。一个简单的现象，若当前分支的“装载上界”，比现有的最 大装载小，则该分支就无需继续搜索。而一个分支的“装载上界 ”，也是容易求解的，就是假设装载当前物品以后的所有物品。 举一个简单的例子，W=50，10，10，C1=60，所构成的子集树就 无需搜索结点2的分支，因为扩展结点1后，就知道最大装载量不 会小于50；而扩展结点2时，发现此分支的“装载上界”为 w2+w3=20c1+c2) print(“no solution”); return;上一页 下一页 返回首页 优先队列式分支限界法 5.5.1 5.5.3 5.6MaxLoading(c1); if (s- bestw bestw) / 目前的最优解/ bestE = E;bestxn = ch; /bestxn取值为chreturn; b = new QNode; / 不是叶子, 添加到队列中 b-weight = wt; b-parent = E; b-LChild = ch; /新节点是左孩子时 add (Q,b) ; 上一页 下一页 返回首页 优先队列式分支限界法 5.5.1 5.5.3 5.63MaxLoading(int n, int bestx) Qnode *E; int i = 1; E= new QNode;add (Q,0) ; / 0 代表本层的尾部 E-weight=0; E-parent =null; E-Lchild=0; add (Q,E) ; bestw = 0; r = 0; / E-节点中余下的重量 Ew=E-weight; for (int j =2; j weight + wi; / 检查E-节点的左孩子if (wt bestw) bestw = wt;AddLiveNode(wt,i, E ,1);if (Ew+r bestw) / 检查右孩子AddLiveNode(Ew,i,E,0); Delete (Q,E ) ; / 下一个E-节点上一页 下一页 返回首页 优先队列式分支限界法 5.5.1 5.5.3 5.64if (!E) / 层的尾部if (Empty(Q ) break;add (Q 0 ) ; / 层尾指针Delete(Q,E ) ; / 下一个E-节点i + + ; / E-节点的层次r = r - wi; / E-节点中余下的重量Ew = E- w e i g h t ; / 新的E-节点的重量 / 沿着从b e s t E到根的路径构造x ，x n由AddLiveNode来设置 for (j = n - 1; j 0; j-) bestxj = bestE-LChild; / 从b o o l转换为i n tbestE = bestE-parent; return bestw; 上一页 下一页 返回首页 优先队列式分支限界法 5.5.1 5.5.3 5.6上一节介绍的优先队列式扩展方式，若不加入限界策略其实是无意义的。因为要说明解的最优性，不搜索完所有问题空间是不能下结论的，而要对问题空间进行完全搜索，考虑优先级也就没有意义了。优先队列式搜索通过结点的优先级，可以使搜索尽快朝着解空间树上有最优解的分支推进，这样当前最优解一定较接近真正的最优解。其后我们将当前最优解作为一个“界”，对上界（或下界）不可能达到（大于）这个界的分支则不去进行搜索，这样就缩小搜索范围，提高了搜索效率。这种搜索策略称为优先队列式分支限界法LC-检索。上一页 下一页 返回首页 FIFO限界搜索算法 5.5.1 5.5.3 5.6算法设计3：用优先队列式分支限界法解决【例2】的问题1）结点扩展方式：无论那种分支限界法，都需要有一张活 结点表。优先队列的分支限界法将活结点组织成一个优先队列 ，并按优先队列中规定的结点优先级选取优先级最高的下一个 结点成为当前扩展结点。2）结点优先级确定：优先队列中结点优先级常规定为一个 与该结点相关的数值p，它一般表示其接近最优解的程度，本例 题就以当前结点的所在分支的装载上界为优先值。 3）优先队列组织：结点优先级确定后，简单地按结点优先级进行排序，就生成了优先队列。排序算法的时间复杂度较高，考虑 到搜索算法每次只扩展一个结点，回忆数据结构中堆排序，适合这 一特点且比较交换的次数最少。此题应该采用最大堆来实现优先队 列。 数据结构设计： 1）要输出解的方案，在搜索过程中仍需要生成解结构树，其结点信息包括指向父结点的指针和标识物品取舍（或是父结点的左、右孩子）。 2）堆结点首先应该包括结点优先级信息：结点的所在分支的装载上界uweight；堆中无法体现结点的层次信息（level）， 只能存储在结点中； AddLiveNode用于把bbnode类型的活节点加到子树中，并把 HeapNode类型的活节点插入最大堆。3）不同与算法2，由于扩展结点不是按层进行的计算结点的所在分支的装载上界时，要用数组变量r记录当前层以下的最 大重量，这样可以随时方便使用各层结点的装载上界。 算 发 设 计 3 （ 3 ） ：算法3如下： HeapNode H1000; struct bbnode bbnode *parent; / 父节点指针 int LChild; ; / 当且仅当是父节点的左孩子时 ，取值为1 struct HeapNodebbnode *ptr; / 活节点指针float uweight; / 活节点的重量上限int level; ; / 活节点所在层 同样为了突出算法本身的思想，对堆操作也只进行抽象的描述 ： 用HeapNode代表队列类型，则HeapNode H；定义了一个堆H，相关操作有： Insert (Q，)表示入堆； DeleteMax (Q，);表示出堆。 算发设计3（4）AddLiveNode(float wt, int lev,bbnode *E, int ch) bbnode *b = new bbnode;b -parent = E;b-LChild = ch;HeapNode N;N.uweight = wt;N.level=lev;N.ptr=b;Insert(H，N) ; 上一页 下一页 返回首页 FIFO限界搜索算法 5.5.1 5.5.3 5.6算发设计3（5）MaxLoading(float c, int n, int bestx) froat r100,Ew，bestw=0; rn = 0; for (int j = n-1; j 0; j-) rj=rj+1 + wj+1; int i = 1; bbnode *E = 0; Ew = 0; / 搜索子集空间树 while (i != n+1) / 不在叶子上 if (Ew + wi 0; j-) bestxj = E-LChild; E = E-parent; return Ew; 算法说明 ： 算法的复杂度仍为O（2n），但通过限界策略，并没有搜索 子集