第11讲分支限界法

1、Design and Analysis of Computer Algorithms分支限界法分支限界法大连海事大学Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms5 55 51 1 分支搜索算法分支搜索算法 1 1基本思想基本思想 分支搜索法也是一种在问题解空间上进行尝试搜索算法。所谓分支搜索法也是一种在问题解空间上进行尝试搜索算法。所谓“分支分支”是采用广度优先的策略，依次生成是采用广度优先的策略，依次生成E-结点所有分支，也就结点所有分支，也就是所有的儿子结点。和回溯法

2、一样，在生成的节点中，抛弃那些不是所有的儿子结点。和回溯法一样，在生成的节点中，抛弃那些不满足约束条件（或者说不可能导出最优可行解）的结点，其余节点满足约束条件（或者说不可能导出最优可行解）的结点，其余节点加入活节点表。然后从表中选择一个节点作为下一个加入活节点表。然后从表中选择一个节点作为下一个E-节点。选择节点。选择下一个下一个E-节点的方式不同导致几种不同的分支搜索方式：节点的方式不同导致几种不同的分支搜索方式：1FIFO搜索 2LIFO搜索 3优先队列式搜索 Design and Analysis of Computer Algorithms1FIFO搜索搜索大连海事大学 一开始，根结

3、点是唯一的活结点，根结点入队。从活结点一开始，根结点是唯一的活结点，根结点入队。从活结点队中取出根结点后，作为当前扩展结点。对当前扩展结点，先队中取出根结点后，作为当前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点（队中最先进来的结点）为当前扩展结点，结点（队中最先进来的结点）为当前扩展结点，直到找，直到找到一个解或活结点队列为空为止。到一个解或活结点队列为空为止。 Design and Ana

4、lysis of Computer Algorithms2 2LIFOLIFO搜索搜索大连海事大学 一开始，根结点入栈。从栈中弹出一个结点为当一开始，根结点入栈。从栈中弹出一个结点为当前扩展结点。对当前扩展结点，先从左到右地产生它前扩展结点。对当前扩展结点，先从左到右地产生它的所有儿子，用约束条件检查，把所有满足约束函数的所有儿子，用约束条件检查，把所有满足约束函数的儿子入栈，再从栈中弹出一个结点（栈中最后进来的儿子入栈，再从栈中弹出一个结点（栈中最后进来的结点）为当前扩展结点，的结点）为当前扩展结点，直到找到一个解或，直到找到一个解或栈为空为止。栈为空为止。 Design and Analy

5、sis of Computer Algorithms3 3优先队列式搜索优先队列式搜索大连海事大学 为了加速搜索的进程，应采用有效地方式选择为了加速搜索的进程，应采用有效地方式选择E-结点进行扩展。优先队列式搜索，对每一活结点结点进行扩展。优先队列式搜索，对每一活结点计算一个优先级（某些信息的函数值），并根据这计算一个优先级（某些信息的函数值），并根据这些优先级，从当前活结点表中优先选择一个优先级些优先级，从当前活结点表中优先选择一个优先级最高（最有利）的结点作为扩展结点，使搜索朝着最高（最有利）的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出解空间树上有最优解的分支

6、推进，以便尽快地找出一个最优解。这种扩展方式要到下一节才用的到。一个最优解。这种扩展方式要到下一节才用的到。 Design and Analysis of Computer Algorithms552 分枝分枝-限界搜索算法限界搜索算法大连海事大学 【例例】有两艘船，有两艘船，n n 个货箱。第一艘船的载重量是个货箱。第一艘船的载重量是c c1，第二艘船，第二艘船的载重量是的载重量是c c2，w wi 是货箱是货箱i i 的重量的重量, ,且且 w 1+w2+wncc1+c+c2。我们希望确定是否有一种可将所有我们希望确定是否有一种可将所有n n 个货箱全部装船的方法。若有个货箱全部装船的方法

7、。若有的话，找出该方法的话，找出该方法 FIFO限界搜索算法限界搜索算法优先队列式分支限界法优先队列式分支限界法Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms算法算法1的缺点有的缺点有: : 1）在可解的情况下，没有给出每艘装载物品的方案。而要）在可解的情况下，没有给出每艘装载物品的方案。而要想记录第一艘船最大装载的方案，象回溯法中用想记录第一艘船最大装载的方案，象回溯法中用n个元素的数个元素的数组是不能实现的，可以象组是不能实现的，可以象5.2.2小节中的例子用数组队列下

8、标记小节中的例子用数组队列下标记录解方案。录解方案。 这里采用构造二叉树的方法，和这里采用构造二叉树的方法，和5.2.2小节中的例题一样只需小节中的例题一样只需要记录最优解的叶结点，这样二叉树就必需有指向父结点的指要记录最优解的叶结点，这样二叉树就必需有指向父结点的指针，以便从叶结点回溯找解的方案。又为了方便知道当前结点针，以便从叶结点回溯找解的方案。又为了方便知道当前结点对物品的取舍情况，还必须记录当前结点是父结点的哪一个儿对物品的取舍情况，还必须记录当前结点是父结点的哪一个儿子。子。数据结构：由此，树中结点的信息包括：数据结构：由此，树中结点的信息包括：weight;parent; wei

9、ght;parent; LChild;LChild;。同时这些结点的地址就是抽象队列的元素，队列操作。同时这些结点的地址就是抽象队列的元素，队列操作与算法与算法1 1相同相同 . .Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms 2 2）算法）算法1 1是在对子集树进行盲目搜索，我们虽然不能将搜索是在对子集树进行盲目搜索，我们虽然不能将搜索算法改进为多项式复杂度，但在算法中加入了算法改进为多项式复杂度，但在算法中加入了“限界限界”技巧，还技巧，还是能降低算法的复杂度。是能降

10、低算法的复杂度。 一个简单的现象，若当前分支的一个简单的现象，若当前分支的“装载上界装载上界”，比现有的最，比现有的最大装载小，则该分支就无需继续搜索。而一个分支的大装载小，则该分支就无需继续搜索。而一个分支的“装载上装载上界界”，也是容易求解的，就是假设装载当前物品以后的所有物品。，也是容易求解的，就是假设装载当前物品以后的所有物品。举一个简单的例子，举一个简单的例子，W=50W=50，1010，1010，C C1 1=60=60，所构成的子集树就，所构成的子集树就无需搜索结点无需搜索结点2 2的分支，因为扩展结点的分支，因为扩展结点1 1后，就知道最大装载量不后，就知道最大装载量不会小于会

11、小于5050；而扩展结点；而扩展结点2 2时，发现此分支的时，发现此分支的“装载上界装载上界”为为w w2 2+w+w3 3=2050=2050，无需搜索此分支，结点，无需搜索此分支，结点2 2不必入队。不必入队。Design and Analysis of Computer Algorithms数据结构：相应地，当前最大装载数据结构：相应地，当前最大装载bestwbestw不仅仅对叶结点计算，不仅仅对叶结点计算，每次搜索装载情况（搜索左儿子）时，都重新确定每次搜索装载情况（搜索左儿子）时，都重新确定bestwbestw的值。的值。为了方便计算一个分支的为了方便计算一个分支的“装载上界装载上界

12、”，用变量，用变量r r记录当前层以记录当前层以下的最大重量。下的最大重量。公共变量的定义：大连海事大学float bestw,w100,float bestw,w100,bestx100bestx100; ;int nint n；Queue Q;Queue Q;struct QNode struct QNode float weight; float weight; QNode QNode * *parent;parent; QNode LChild; QNode LChild; Design and Analysis of Computer AlgorithmsDesign and Ana

13、lysis of Computer Algorithms算法如下：算法如下：main( )main( )int c1,c2,n, s=0,i;int c1,c2,n, s=0,i;input(c1,c2input(c1,c2，n);n);for(i=1;i=n;i+) for(i=1;i=n;i+) input(wi) input(wi)； s=s+wis=s+wi； if (s=c1 or s=c2) if (s=c1 or sc1+c2) print(if (sc1+c2) print(“no solutionno solution”); return;); return;Design a

14、nd Analysis of Computer Algorithms大连海事大学MaxLoading(c1);MaxLoading(c1);if (s- bestw =c2);if (s- bestw =c2); print(“The first ship loading”, bestw print(“The first ship loading”, bestw，“chosechose：”);); for(i=1;i=n;i+) for(i=1;i=n;i+) if( if(bestxi=1bestxi=1) ) print(i print(i，“，”);); print(“ print(“换

15、行符换行符 The second ship loading”, s-bestw,“chose”);The second ship loading”, s-bestw,“chose”); for(i=1;i=n;i+) for(i=1;ibestw) / if (wtbestw) / 目前的最优解目前的最优解/ / bestE = E; bestE = E; bestxn = ch; /bestxn bestxn = ch; /bestxn取值为取值为chch return; return; b = new QNode; / b = new QNode; / 不是叶子不是叶子, , 添加到队列中

16、添加到队列中b-weight = wt;b-weight = wt;b-parent = E;b-parent = E;b-LChild = ch; /b-LChild = ch; /新节点是左孩子时新节点是左孩子时add (Q,b) ;add (Q,b) ; Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer AlgorithmsMaxLoading(int n, int bestx)MaxLoading(int n, int bestx)Qnode Qnode * *E; int i = 1;E

17、; int i = 1;E= new QNode;add (Q,0) ; / 0 E= new QNode;add (Q,0) ; / 0 代表本层的尾部代表本层的尾部E-weight=0; E-parent =null; E-Lchild=0; add (Q,E) ;E-weight=0; E-parent =null; E-Lchild=0; add (Q,E) ;bestw = 0; r = 0; / E-bestw = 0; r = 0; / E-节点中余下的重量节点中余下的重量Ew=E-weight;Ew=E-weight;for (int j =2; j = n; j+) r=r+

18、 wi;for (int j =2; j weight + wi; / wt = E-weight + wi; / 检查检查E-E-节点的左孩子节点的左孩子 if (wt = c) / if (wt bestw) if (wt bestw) bestw = wt; bestw = wt; AddLiveNode(wt,i, E ,1); AddLiveNode(wt,i, E ,1); if (Ew+r bestw) / if (Ew+r bestw) / 检查右孩子检查右孩子 AddLiveNode(Ew,i,E,0); AddLiveNode(Ew,i,E,0); Delete (Q,E

19、) ; / Delete (Q,E ) ; / 下一个下一个E-E-节点节点Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms if (!E) / if (!E) / 层的尾部层的尾部 if (Empty(Q ) if (Empty(Q ) break; break; add (Q 0 ) ; / add (Q 0 ) ; / 层尾指针层尾指针 Delete(Q,E ) ; / Delete(Q,E ) ; / 下一个下一个E-E-节点节点 i + + ; / E-i + +

20、; / E-节点的层次节点的层次 r = r - wi; / E-r = r - wi; / E-节点中余下的重量节点中余下的重量 Ew = E- w e i g h t ; / Ew = E- w e i g h t ; / 新的新的E-E-节点的重量节点的重量 / / 沿着从沿着从b e s t Eb e s t E到根的路径构造到根的路径构造x x ，x nx n由由AddLiveNodeAddLiveNode来设置来设置for (j = n - 1; j 0; j-) for (j = n - 1; j 0; j-) bestxj = bestE-LChild; / bestxj =

21、bestE-LChild; / 从从b o o lb o o l转换为转换为i n ti n t bestE = bestE-parent; bestE = bestE-parent;return bestw;return bestw; Design and Analysis of Computer Algorithms算法设计算法设计3：用优先队列式分支限界法解决【例】的问题大连海事大学 上一节介绍的优先队列式扩展方式，若不加入限界策略其实是上一节介绍的优先队列式扩展方式，若不加入限界策略其实是无意义的。因为要说明解的最优性，不搜索完所有问题空间是不能无意义的。因为要说明解的最优性，不搜索完

22、所有问题空间是不能下结论的，而要对问题空间进行完全搜索，考虑优先级也就没有意下结论的，而要对问题空间进行完全搜索，考虑优先级也就没有意义了。义了。 优先队列式搜索通过结点的优先级，可以使搜索尽快朝着解空优先队列式搜索通过结点的优先级，可以使搜索尽快朝着解空间树上有最优解的分支推进，这样当前最优解一定较接近真正的最间树上有最优解的分支推进，这样当前最优解一定较接近真正的最优解。其后我们将当前最优解作为一个优解。其后我们将当前最优解作为一个“界界”，对上界（或下界），对上界（或下界）不可能达到（大于）这个界的分支则不去进行搜索，这样就缩小搜不可能达到（大于）这个界的分支则不去进行搜索，这样就缩小搜

23、索范围，提高了搜索效率。这种搜索策略称为优先队列式分支限界索范围，提高了搜索效率。这种搜索策略称为优先队列式分支限界法法LC-LC-检索。检索。Design and Analysis of Computer Algorithms大连海事大学 1 1）结点扩展方式：无论那种分支限界法，都需要有一张活）结点扩展方式：无论那种分支限界法，都需要有一张活结点表。优先队列的分支限界法将活结点组织成一个优先队列，结点表。优先队列的分支限界法将活结点组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。点成为当前扩

24、展结点。 2 2）结点优先级确定：优先队列中结点优先级常规定为一个）结点优先级确定：优先队列中结点优先级常规定为一个与该结点相关的数值与该结点相关的数值p p，它一般表示其接近最优解的程度，本例，它一般表示其接近最优解的程度，本例题就以当前结点的所在分支的装载上界为优先值。题就以当前结点的所在分支的装载上界为优先值。 3 3）优先队列组织：结点优先级确定后，简单地按结点优先级）优先队列组织：结点优先级确定后，简单地按结点优先级进行排序，就生成了优先队列。排序算法的时间复杂度较高，考虑进行排序，就生成了优先队列。排序算法的时间复杂度较高，考虑到搜索算法每次只扩展一个结点，回忆数据结构中堆排序，适

25、合这到搜索算法每次只扩展一个结点，回忆数据结构中堆排序，适合这一特点且比较交换的次数最少。此题应该采用最大堆来实现优先队一特点且比较交换的次数最少。此题应该采用最大堆来实现优先队列。列。 Design and Analysis of Computer Algorithms大连海事大学数据结构设计：数据结构设计：1）要输出解的方案，在搜索过程中仍需要生成解结构树，其结）要输出解的方案，在搜索过程中仍需要生成解结构树，其结点信息包括指向父结点的指针和标识物品取舍（或是父结点的点信息包括指向父结点的指针和标识物品取舍（或是父结点的左、右孩子）。左、右孩子）。 2 2）堆结点首先应该包括结点优先级信息

26、：结点的所在分支）堆结点首先应该包括结点优先级信息：结点的所在分支的装载上界的装载上界uweightuweight；堆中无法体现结点的层次信息（；堆中无法体现结点的层次信息（levellevel），），只能存储在结点中；只能存储在结点中；AddLiveNodeAddLiveNode用于把用于把bbnodebbnode类型的活节点加到子树中，并把类型的活节点加到子树中，并把HeapNodeHeapNode类型的活节点插入最大堆。类型的活节点插入最大堆。 3）不同与算法）不同与算法2，由于扩展结点不是按层进行的计算结点，由于扩展结点不是按层进行的计算结点的所在分支的装载上界时，要用数组变量的所在分

27、支的装载上界时，要用数组变量r r记录当前层以下的最记录当前层以下的最大重量，这样可以随时方便使用各层结点的装载上界。大重量，这样可以随时方便使用各层结点的装载上界。 Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms算法设计算法设计3 3（3 3）：）：算法算法3 3如下：如下： HeapNode H1000;HeapNode H1000;struct bbnode struct bbnode bbnode bbnode * *parent; / parent; / 父节点指

28、针父节点指针int LChild; ; / int LChild; ; / 当且仅当是父节点的左孩子当且仅当是父节点的左孩子时，取值为时，取值为1 1struct HeapNodestruct HeapNode bbnode bbnode * *ptr; / ptr; / 活节点指针活节点指针 float uweight; / float uweight; / 活节点的重量上限活节点的重量上限 int level; ; / int level; ; / 活节点所在层活节点所在层 同样为了突出算法本身的思想，对堆操作也只进行抽象的描述：同样为了突出算法本身的思想，对堆操作也只进行抽象的描述：用用

29、HeapNodeHeapNode代表队列类型，则代表队列类型，则HeapNode HHeapNode H；定义了一个堆；定义了一个堆H H，相，相关操作有：关操作有：Insert (QInsert (Q，) )表示入堆；表示入堆； DeleteMax (QDeleteMax (Q，););表示出堆。表示出堆。 Design and Analysis of Computer Algorithms算法设计算法设计3 3（4 4）大连海事大学AddLiveNode(float wt, int lev,bbnode AddLiveNode(float wt, int lev,bbnode * *E,

30、int ch)E, int ch)bbnode bbnode * *b = new bbnode;b = new bbnode; b -parent = E; b -parent = E; b-LChild = ch; b-LChild = ch; HeapNode N; HeapNode N; N.uweight = wt; N.uweight = wt; N.level=lev; N.level=lev; N.ptr=b; N.ptr=b; Insert(H Insert(H，N) ;N) ; Design and Analysis of Computer Algorithms大连海事大学

31、MaxLoading(float c, int n, int bestx)MaxLoading(float c, int n, int bestx)froat r100,Ewfroat r100,Ew，bestw=0; rn = 0;bestw=0; rn = 0;for (int j = n-1; j 0; j-) rj=rj+1 + wj+1;for (int j = n-1; j 0; j-) rj=rj+1 + wj+1;int i = 1; bbnode int i = 1; bbnode * *E = 0; Ew = 0; / E = 0; Ew = 0; / 搜索子集空间树搜索子

32、集空间树while (i != n+1) / while (i != n+1) / 不在叶子上不在叶子上 if (Ew + wi = c) / if (Ew + wi = c) / 可行的左孩子可行的左孩子 AddLiveNode(E, Ew+wi+ri, 1, i+1);AddLiveNode(E, Ew+wi+ri, 1, i+1); if (bestwEw+wi) bestw=Ew+wi; if (bestwEw+wi) bestw=Ew+wi; if(bestwEw+ri) AddLiveNode(E, Ew+ri, 0, i+1); if(bestw 0; j-) for (int

33、j = n; j 0; j-) bestxj = E-LChild; E = E-parent; bestxj = E-LChild; E = E-parent;return Ew;return Ew; Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms算法说明：算法说明： 算法的复杂度仍为算法的复杂度仍为O O（2 2n n），但通过限界策略，并没有搜），但通过限界策略，并没有搜索子集树中的所有结点，且，由于每次都是选取的最接近最优索子集树中的所有结点，且，由于每次都是选取的

34、最接近最优解的结点扩展，所以一当搜索到叶结点作解的结点扩展，所以一当搜索到叶结点作E结点时算法就可以结点时算法就可以结束了。算法结束时堆并不一定为空。结束了。算法结束时堆并不一定为空。 Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms小结讨论：小结讨论：FIFO搜索或搜索或LIFO搜索也可以通过加入搜索也可以通过加入“限界限界”策略加速搜索策略加速搜索吗？吗？那与优先队列式分支限界法那与优先队列式分支限界法LCLC检索的区别在哪儿呢？检索的区别在哪儿呢？ 答案：由于答案：由于

35、FIFO搜索或搜索或LIFO搜索是盲目扩展地结点，当前最优解搜索是盲目扩展地结点，当前最优解距真正的最优解距离较大，作为距真正的最优解距离较大，作为“界界”所起到的剪枝作用很有限，所起到的剪枝作用很有限，不能有效提高搜索速度。其实看了下面的例子大家会发现，优先队不能有效提高搜索速度。其实看了下面的例子大家会发现，优先队列式扩展结点的过程，一开始实际是在进行类似列式扩展结点的过程，一开始实际是在进行类似“深度优先深度优先”的搜的搜索。索。 例如：例如：W=10，30，50，C1=60， 所构成的子集树如下图所表示：所构成的子集树如下图所表示：Design and Analysis of Comp

36、uter AlgorithmsFIFOFIFO限界搜索过程为：限界搜索过程为： 大连海事大学1 1） 初始队列中只有结点初始队列中只有结点A A；2 2） 结点结点A A变为变为E-E-结点扩充结点扩充B B入队，入队，bestw=10bestw=10； 结点结点C C的装载上界为的装载上界为30+50=80 bestw30+50=80 bestw，也入队；，也入队；3 3） 结点结点B B变为变为E-E-结点扩充结点扩充D D入队，入队，bestw=40bestw=40； 结点结点E E的装载上界为的装载上界为60 bestw60 bestw，也入队；，也入队；4 4） 结点结点C C变为变

37、为E-E-结点扩充结点扩充F F入队，入队，bestwbestw仍为仍为4040； 结点结点G G的装载上界为的装载上界为50 bestw50 bestw，也入队；，也入队；5 5） 结点结点D D变为变为E-E-结点，叶结点结点，叶结点H H超过容量，超过容量， 叶结点叶结点I I的装载为的装载为4040，bestwbestw仍为仍为4040；6 6） 结点结点E E变为变为E-E-结点，叶结点结点，叶结点J J装载量为装载量为6060，bestwbestw为为6060； 叶结点叶结点K K被剪掉；被剪掉；7 7） 结点结点F F变为变为E-E-结点，叶结点结点，叶结点L L超过容量，超过容

38、量，bestwbestw为为6060； 叶结点叶结点M M被剪掉；被剪掉；8 8） 结点结点G G变为变为E-E-结点，叶结点结点，叶结点N N、O O都被剪掉；都被剪掉； 此时队列空算法结束。此时队列空算法结束。 Design and Analysis of Computer AlgorithmsLC-LC-搜索的过程如下：搜索的过程如下： 大连海事大学1 1） 初始队列中只有结点初始队列中只有结点A A；2 2） 结点结点A A变为变为E-E-结点扩充结点扩充B B入堆，入堆，bestw=10bestw=10；结点结点C C的装载上界为的装载上界为30+50=80 bestw30+50=8

39、0 bestw，也入堆；堆中，也入堆；堆中B B上界为上界为9090在优先队列首。在优先队列首。3 3） 结点结点B B变为变为E-E-结点扩充结点扩充D D入堆，入堆，bestw=40bestw=40；结点结点E E的装载上界为的装载上界为60 bestw60 bestw，也入堆；此时堆中，也入堆；此时堆中D D上界为上界为9090为优先队列首。为优先队列首。4 4） 结点结点D D变为变为E-E-结点，叶结点结点，叶结点H H超过容量，叶结点超过容量，叶结点I I的装载为的装载为4040入堆，入堆， bestwbestw仍为仍为4040；此时堆中；此时堆中C C上界为上界为8080为优先队

40、列首。为优先队列首。5 5） 结点结点C C变为变为E-E-结点扩充结点扩充F F入堆，入堆，bestwbestw仍为仍为4040；结点结点G G的装载上界为的装载上界为50 bestw50 bestw，也入堆；此时堆中，也入堆；此时堆中E E上界为上界为6060为优先队列首。为优先队列首。6 6） 结点结点E E变为变为E-E-结点，叶结点结点，叶结点J J装载量为装载量为6060入堆，入堆，bestwbestw变为变为6060； 叶结点叶结点K K上界为上界为10bestw10bestw被剪掉；此时堆中被剪掉；此时堆中J J上界为上界为6060为优先队列首。为优先队列首。7 7） 结点结点

41、J J变为变为E-E-结点，扩展的层次为结点，扩展的层次为4 4算法结束。算法结束。 虽然此时堆并不空，但可以确定已找到了最优解。虽然此时堆并不空，但可以确定已找到了最优解。Design and Analysis of Computer Algorithms大连海事大学FIFO限界算法搜索解空间的过程是按图限界算法搜索解空间的过程是按图5-26子集树中字母子集树中字母序进行的，而优先队列限界搜索解空间的过程是：序进行的，而优先队列限界搜索解空间的过程是：A-B-D-C-E-J看了上面的例子大家会发现，优先队列法扩展结点的过程，看了上面的例子大家会发现，优先队列法扩展结点的过程，一开始实际是在进

42、行类似一开始实际是在进行类似“深度优先深度优先”的搜索。的搜索。Design and Analysis of Computer Algorithms553 算法框架算法框架 上一小节的例子是求最大值的最优化问题，下面我们以求找上一小节的例子是求最大值的最优化问题，下面我们以求找最小成本的最优化问题，给出最小成本的最优化问题，给出FIFO分支搜索算法框架。分支搜索算法框架。 假定问题解空间树为假定问题解空间树为T，T至少包含一个解结点（即答案结至少包含一个解结点（即答案结点）。点）。u为当前的最优解，初值为一个较大的数为当前的最优解，初值为一个较大的数;E表示当前扩表示当前扩展的活结点，展的活结

43、点，x为为E的儿子，的儿子，s(x)为结点为结点x下界函数，当其值比下界函数，当其值比u大时，不可能为最优解，不继续搜索此分支，该结点不入队；大时，不可能为最优解，不继续搜索此分支，该结点不入队；当其值比当其值比u小时，可能达到最优解，继续搜索此分支，该结点入小时，可能达到最优解，继续搜索此分支，该结点入队；队；cost（X）为当前叶结点所在分支的解。）为当前叶结点所在分支的解。算法框架如下：算法框架如下：大连海事大学Design and Analysis of Computer Algorithms2 2）：）： 大连海事大学search（T） /为找出最小成本答案结点检索为找出最小成本答案

44、结点检索T。 leaf=0; 初始化队；初始化队；ADDQ（T）；）； /根结点入队根结点入队 parent（E）=0； /记录扩展路径，当前结点的父结点记录扩展路径，当前结点的父结点 while （队不空）（队不空）DELETEQ(E) /队首结点出队为新的队首结点出队为新的E结点；结点；for （E的每个儿子的每个儿子 X） if (s（X）u) /当是可能的最优解时入队当是可能的最优解时入队 ADD Q（X）；）； parent（X）=E; if (X是解结点是解结点 ) /x为叶结点为叶结点 U=min（cost（X），），u）; leaf=x; /方案的叶结点存储在方案的叶结点存储在

45、leaf中中 Design and Analysis of Computer Algorithms3 3）：）： 大连海事大学 print（”least cost=，u）；）； while （leaf0） /输出最优解方案输出最优解方案 print（leaf）；）； leaf=parent（leaf）；）；Design and Analysis of Computer Algorithms大连海事大学 找最小成本的找最小成本的LC分支分支- -限界算法限界算法框架框架与与 F FIFO分支分支- -限界算法限界算法框框架结构大致相同，只是扩展结点的顺序不同，因而存储活结点架结构大致相同，只是扩

46、展结点的顺序不同，因而存储活结点的数据结构不同。的数据结构不同。 F FIFO分支分支- -限界算法用队限界算法用队存储活结点，存储活结点，LC分分支支- -限界算法用堆限界算法用堆存储活结点，以保证比较优良的结点先被扩展。存储活结点，以保证比较优良的结点先被扩展。且对于且对于LC分支分支- -限界算法，一当扩展到叶结点就已经找到最优限界算法，一当扩展到叶结点就已经找到最优解，可以停止搜索。解，可以停止搜索。Design and Analysis of Computer Algorithms56 图的搜索算法小结图的搜索算法小结 大连海事大学1 1深度优先搜索与广度优先搜索算法有何区别深度优先

47、搜索与广度优先搜索算法有何区别 通常深度优先搜索法不全部保留结点，扩展完的结点从数据存通常深度优先搜索法不全部保留结点，扩展完的结点从数据存储结构栈中弹出删去，这样，一般在数据栈中存储的结点数就是解储结构栈中弹出删去，这样，一般在数据栈中存储的结点数就是解空间树的深度，因此它占用空间较少。所以，当搜索树的结点较多，空间树的深度，因此它占用空间较少。所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。解方法。广度优先搜索算法，一般需存储产生的所有结点，占用的存储广度优先搜索算法，一般需存储产生的所有

48、结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入和节省内存空间的问题。但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些。栈和出栈的操作，所以运行速度比深度优先搜索要快些。 Design and Analysis of Computer Algorithms大连海事大学2 2回溯与分支限界法回溯与分支限界法 回溯法以深度优先的方式搜索解空间树回溯法以深度优先的方式搜索解空间树T T，而分支限界法则，而分支限界法则以广度优

49、先或以最小耗费优先的方式搜索解空间树以广度优先或以最小耗费优先的方式搜索解空间树T T。由于它由于它们在问题的解空间树们在问题的解空间树T上搜索的方法不同，适合解决的问题上搜索的方法不同，适合解决的问题也就不同。一般情况下，回溯法的求解目标是找出也就不同。一般情况下，回溯法的求解目标是找出T中满足中满足约束条件的所有解的方案，而分支限界法的求解目标则是找约束条件的所有解的方案，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出出满足约束条件的一个解，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下使用某一目标函数值达到极大或极小的解

50、，即在某种意义下的最优解。的最优解。相对而言，分支限界算法的解空间比回溯法大得相对而言，分支限界算法的解空间比回溯法大得多，多，因此当内存容量有限时，回溯法成功的可能性更大。因此当内存容量有限时，回溯法成功的可能性更大。下表列出了回溯法和分支限界法的一些区别：下表列出了回溯法和分支限界法的一些区别：Design and Analysis of Computer AlgorithmsDesign and Analysis of Computer Algorithms3 3. .Design and Analysis of Computer Algorithms在处理最优问题时，采用穷举法、回溯法

51、或分支限界法都可以在处理最优问题时，采用穷举法、回溯法或分支限界法都可以通过利用当前最优解和上界函数加速。仅就对限界剪支的效率而通过利用当前最优解和上界函数加速。仅就对限界剪支的效率而言，优先队列的分支限界法显然要更充分一些。在穷举法中通过言，优先队列的分支限界法显然要更充分一些。在穷举法中通过上界函数与当前情况下函数值的比较可以直接略过不合要求的情上界函数与当前情况下函数值的比较可以直接略过不合要求的情况而省去了更进一步的枚举和判断；回溯法则因为层次的划分，况而省去了更进一步的枚举和判断；回溯法则因为层次的划分，可以在上界函数值小于当前最优解时，剪去以该结点为根的子树，可以在上界函数值小于当

52、前最优解时，剪去以该结点为根的子树，也就是节省了搜索范围；分支限界法在这方面除了可以做到回溯也就是节省了搜索范围；分支限界法在这方面除了可以做到回溯法能做到的之外，同时若采用优先队列的分支限界法，用上界函法能做到的之外，同时若采用优先队列的分支限界法，用上界函数作为活结点的优先级，一旦有叶结点成为当前扩展结点，就意数作为活结点的优先级，一旦有叶结点成为当前扩展结点，就意味着该叶结点所对应的解即为最优解，可以立即终止其余的过程。味着该叶结点所对应的解即为最优解，可以立即终止其余的过程。在前面的例题中曾说明，优先队列的分支限界法更象是有选择、在前面的例题中曾说明，优先队列的分支限界法更象是有选择、

53、有目的地进行深度优先搜索，时间效率、空间效率都是比较高的。有目的地进行深度优先搜索，时间效率、空间效率都是比较高的。大连海事大学Design and Analysis of Computer Algorithms5 5. . 大连海事大学 3动态规划与搜索算法动态规划与搜索算法撇开时空效率的因素不谈，在解决最优化问题的算法中，搜索撇开时空效率的因素不谈，在解决最优化问题的算法中，搜索可以说是可以说是“万能万能”的。所以动态规划可以解决的问题，搜索也一的。所以动态规划可以解决的问题，搜索也一定可以解决。动态规划要求阶段决策具有无后向性，而搜索算法定可以解决。动态规划要求阶段决策具有无后向性，而搜索算法没有此限止。没有此限止。动态规划是自底向上的递推求解，而无论深度优先搜索或广度动态规划是自底向上的递推求解，而无论深度优先搜索或广度优先搜索都是自顶向下求解。利用动态规划法