算法第5章-第4讲-图搜索-优先队列分枝限界法

1、第第4 4讲讲 优先队列分支限界法优先队列分支限界法每节一经典每节一经典有选择地搜索有选择地搜索3654789第第4 4讲讲 分支限界法分支限界法 上节课，我们介绍了上节课，我们介绍了3 3种不同的分支搜索方式：种不同的分支搜索方式：FIFOFIFO、LIFOLIFO、优先队列，详细分析了、优先队列，详细分析了FIFOFIFO搜索方式。搜索方式。 当然用当然用LIFOLIFO搜索方式也同样可以设计出对应的算法，搜索方式也同样可以设计出对应的算法，请同学们尝试！请同学们尝试！ 本节我们将详细分析如何用优先队列分支限界法来本节我们将详细分析如何用优先队列分支限界法来解决类似问题。解决类似问题。 优

2、先队列式分支限界法：优先队列式分支限界法：3654789搜索算法：搜索算法：分支搜索分支搜索 （例：深度优先，广度优先，均为按深度或宽度顺例：深度优先，广度优先，均为按深度或宽度顺 序，在全部解空间搜索序，在全部解空间搜索）分支限界搜索分支限界搜索（例：与分枝搜索类似，并加入结点限制，对不例：与分枝搜索类似，并加入结点限制，对不 满足条件的结点为根的分枝子树不再满足条件的结点为根的分枝子树不再 进行进行 搜索搜索）优先队列分支限界搜索优先队列分支限界搜索例：在例：在分支限界搜索基础上，分支限界搜索基础上，对搜索结点的顺序按优先队列组对搜索结点的顺序按优先队列组织，使每一步搜索向最优解目标靠近，

3、不满足条件的结点为根织，使每一步搜索向最优解目标靠近，不满足条件的结点为根的分支子树不再进行搜索，遇到叶结点，即可得到一个解的分支子树不再进行搜索，遇到叶结点，即可得到一个解）第第4 4讲讲 分支限界法分支限界法p 优先队列组织：结点优先级确定后优先队列组织：结点优先级确定后, ,简单地按结点优先简单地按结点优先 级进行排序级进行排序, ,就生成了优先队列就生成了优先队列. .但是但是, ,排序算法的时间排序算法的时间 复杂度较高。复杂度较高。p 考虑到搜索算法每次只扩展一个结点考虑到搜索算法每次只扩展一个结点, ,数据结构中堆排数据结构中堆排 序方法适合这一特点序方法适合这一特点, ,并且元

4、素比较和交换的次数最少并且元素比较和交换的次数最少. . 堆堆通常有两类：最大堆通常有两类：最大堆( (根部的数最大根部的数最大, ,由大到小构造由大到小构造堆堆 ) )，最小堆最小堆(根部的数最小根部的数最小,由小到大构造堆由小到大构造堆 )，第第4 4讲讲 分支限界法分支限界法定义：堆定义：堆(heap)(heap)是一个满足下列条件的完全二叉数：是一个满足下列条件的完全二叉数： （1 1）父结点比其左、右儿子结点都大（或小）。）父结点比其左、右儿子结点都大（或小）。 （2 2）左、右儿子分别是一个堆。）左、右儿子分别是一个堆。即：即：n n个元素的序列个元素的序列kk1 1,k,k2 2

5、, ,k kn n,当且仅当满足：当且仅当满足： kik2i kik2i kik2i+1 ki k2i+1 堆定义堆定义或或(i=1,2, n/2 )第第4 4讲讲 分支限界法分支限界法例：例：6 6，4 4，7 7，9 9构造的大堆（从根到叶子数值减小）构造的大堆（从根到叶子数值减小）647969749674无序序列无序序列4筛选后的状态筛选后的状态建建 堆堆6筛选后建成堆筛选后建成堆第第4 4讲讲 分支限界法分支限界法例例: 3,8,7,4,5,9,1,6: 3,8,7,4,5,9,1,6构造的小堆构造的小堆( (从根到叶子数值增大从根到叶子数值增大) )初始堆初始堆根节点根节点1出队，最

6、后节点出队，最后节点6做根节点位后的状态做根节点位后的状态出出 堆堆6和和3交换后的状态交换后的状态135478696354781913654789第第4 4讲讲 分支限界法分支限界法例例: 3,8,7,4,5,9,1,6: 3,8,7,4,5,9,1,6构造的小堆构造的小堆( (从根到叶子数值增大从根到叶子数值增大) )6和和4交换后的状态交换后的状态出出 堆堆34567891第第4 4讲讲 分支限界法分支限界法例例: 3,8,7,4,5,9,6: 3,8,7,4,5,9,6构造的小堆构造的小堆( (从根到叶子数值增大从根到叶子数值增大) )初始堆初始堆进进 堆堆1进堆后建成新堆演示过程进堆

7、后建成新堆演示过程3468597134685971新新堆堆建建成成第第4 4讲讲 分支限界法分支限界法 优先队列式搜索优先队列式搜索通过结点的优先级通过结点的优先级,可以使搜索尽快可以使搜索尽快朝着解空间树上能朝着解空间树上能到达最优解的分支推进到达最优解的分支推进,这样当前最这样当前最优解一定较接近真正的最优解优解一定较接近真正的最优解. 其后，我们将当前最优解作为一个其后，我们将当前最优解作为一个“界界”,对上界对上界(或下界或下界)不可能达到不可能达到(大于大于)这个界的分支则不去进行搜这个界的分支则不去进行搜索索(结点不入队结点不入队),这样就能缩小搜索范围，从而提高搜这样就能缩小搜索

8、范围，从而提高搜索效率索效率. 这种搜索策略称为这种搜索策略称为优先队列优先队列分支限界分支限界法，简称法，简称LC-检索检索(Least Cost Search )。优先队列式分支限界法：优先队列式分支限界法：第第4 4讲讲 分支限界法分支限界法p 结点扩展方式：无论那种分支限界法，都需要有一结点扩展方式：无论那种分支限界法，都需要有一 张活结点表。优先队列分支限界法将张活结点表。优先队列分支限界法将活结点活结点组织组织成成 一个一个优先队列优先队列，并按优先队列中规定的结点优先，并按优先队列中规定的结点优先级级 选取优先级最高的活结点成为当前扩展结点选取优先级最高的活结点成为当前扩展结点.

9、 .p 结点优先级确定：优先队列中结点优先级通常是结点优先级确定：优先队列中结点优先级通常是 一个与该结点相关的数值一个与该结点相关的数值p, ,它一般表示其接近最它一般表示其接近最优优 解的程度，装载问题就可以解的程度，装载问题就可以当前结点的装载上界当前结点的装载上界为为 该结点的优先级。该结点的优先级。结点是否入队判定标准：结点装载上界结点是否入队判定标准：结点装载上界 当前最优方案当前最优方案bestw,bestw,并并且从该结点到根的装载方案下，装载量不超过船装载量且从该结点到根的装载方案下，装载量不超过船装载量c1c1优先队列式分支限界法算法设计要点：优先队列式分支限界法算法设计要

10、点：第第4 4讲讲 分支限界法分支限界法例如：例如：装载问题装载问题 W=10，30，50，c1=60， 所构成的子集树所构成的子集树如下图所表示：如下图所表示：方框中方框中红色数红色数表示表示 该结点的装载上界，该结点的装载上界，作为结点的优先级。作为结点的优先级。装载上界装载上界=已装入物品重量已装入物品重量+未来可能装入物品的重量未来可能装入物品的重量注意：已经注意：已经“处理处理”过的物品过的物品( (已判断是否装入已判断是否装入) )不再计不再计算算为未来可能装入物品的重量。为未来可能装入物品的重量。AEJBKX1=1DHIGNOFLMCX1=0X2=1X2=1X3=1X3=1X3=

11、1X3=1X2=0X2=0X3=0X3=0X3=0X3=090909090606040108080805050300第第4 4讲讲 分支限界法分支限界法例例4.4.装载问题装载问题: :有三个货物，其重量为有三个货物，其重量为 W=10W=10，3030，5050，有，有2 2辆货辆货车，其载重量为车，其载重量为c1=60c1=60，c2=50,c2=50,问：是否有方案把所有货物运走？问：是否有方案把所有货物运走？关键概念：关键概念：(1)每个字母表示车当前装货状态。每个字母表示车当前装货状态。(2)当前状态下剩余装载量当前状态下剩余装载量 (ew)：当前状：当前状 态下剩余装载量。态下剩余

12、装载量。(3)当前状态下装载量上界当前状态下装载量上界：已装入货物：已装入货物 和未和未 来可能来可能 装入的货物总重量装入的货物总重量(排除排除 已打已打 算不装入的货物重量算不装入的货物重量)。(4)当前状态当前状态最优已最优已装载上界装载上界：截至目前：截至目前 状状 态态(包包 括目前状态括目前状态)，所有已搜索的，所有已搜索的 局局 部装载方案中的最大装载量部装载方案中的最大装载量(已装入已装入 的的 最大重量最大重量)。装装50装装10装装30装装50装装50装装30装装50不装不装10不装不装30第第4 4讲讲 分支限界法分支限界法1 1） 初始队列中只有结点初始队列中只有结点A

13、 A；2 2） 结点结点A A变为变为E-E-结点扩充结点扩充B B入队入队, ,bestwbestw=10;=10;结点结点C C的装载上界为的装载上界为 30+50=80 30+50=80bestwbestw，也入队；也入队；3 3） 结点结点B B变为变为E-E-结点扩充结点扩充D D入队入队, ,bestwbestw=40;=40;结点结点E E的装载上界为的装载上界为 60 60bestwbestw，也入队；也入队；4 4） 结点结点C C变为变为E-E-结点扩充结点扩充F F入队入队, ,bestwbestw仍为仍为40;40;结点结点G G的装载上界为的装载上界为 50 50be

14、stwbestw, ,也入队；也入队；5 5） 结点结点D D变为变为E-E-结点结点, ,叶结点叶结点H H超过容量超过容量, ,不入队；叶结点不入队；叶结点I I的装载上界的装载上界 为为40=bestw=40,40=bestw=40,不入队；不入队；6 6） 结点结点E E变为变为E-E-结点结点, ,叶结点叶结点J J装载上界为装载上界为60bestw=40, 60bestw=40, 入队，并将入队，并将 bestw bestw更新为更新为60;60;叶结点叶结点K K的装载上界为的装载上界为10bestw=40,不入队不入队,即即被被 剪掉；剪掉；7 7） 结点结点F F变为变为E-

15、E-结点，叶结点结点，叶结点L L超过容量，不入队，超过容量，不入队，bestwbestw仍为仍为6060； 叶结点叶结点M M的装载上界为的装载上界为3030+50=80bestwbestw, ,也入堆也入堆; ;堆中堆中B B上界为上界为9090，在，在 优先队列之首优先队列之首; ;3 3） 结点结点B B变为变为E-E-结点扩充结点扩充D D入堆入堆, ,bestwbestw=40;=40;结点结点E E的装载的装载 上界为上界为6060bestwbestw, ,也入堆也入堆; ;此时堆中此时堆中D D上界为上界为9090，在优，在优 先队列之首先队列之首; ;4 4） 结点结点D D

16、变为变为E-E-结点结点, ,叶结点叶结点H H超过容量超过容量, ,叶结点叶结点I I的装载的装载 上界为上界为40=bestw=40,40=bestw=40,入堆入堆; ;此时堆中此时堆中C C上界为上界为8080， 在优先队列之首。在优先队列之首。分支限界分支限界(LC)-搜索的过程如下：搜索的过程如下：优先队列分枝限界搜优先队列分枝限界搜索索第第4 4讲讲 分支限界法分支限界法5） 结点结点C变为变为E-结点扩充结点扩充F入堆入堆,bestw仍为仍为40; 结点结点G 的装载上界为的装载上界为50bestw,也入堆也入堆;此时堆中此时堆中E 上界为上界为 60，在优先队列之首。，在优先

17、队列之首。6） 结点结点E变为变为E-结点结点,叶结点叶结点J装载量为装载量为60，入堆，入堆, bestw变为变为60; 叶结点叶结点K上界为上界为10parent=E; b-LChil = ch; HeapNode N; N.uweight = wt; N.level=lev; N.ptr=b; Insert(H，N) ; 第第4 4讲讲 分支限界法分支限界法 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

18、i = 1; bbnode *E = 0; Ew = 0; / 搜索子集空间树搜索子集空间树while (i != n+1) / 不在叶子上不在叶子上 if ( Ew + wi = c) / 可行的左孩子可行的左孩子 AddLiveNode(E,Ew+wi+ri, 1, i+1); if (bestwEw+wi) bestw=Ew+wi; if( bestw 0; j-) bestxj = E-LChild; E = E-parent; return Ew; 第第4 4讲讲 分支限界法分支限界法 算法的复杂度仍为算法的复杂度仍为O(2O(2n n) )。但通过限界策略。但通过限界策略, ,并没

19、有并没有搜索子集树中的所有结点搜索子集树中的所有结点, ,由于每次都是选取的最接近由于每次都是选取的最接近最优解的结点扩展，所以一旦搜索到叶结点作最优解的结点扩展，所以一旦搜索到叶结点作E E结点时结点时算法就可以结束了算法就可以结束了, ,所以算法实际执行时复杂度远远低所以算法实际执行时复杂度远远低于于O(2n). .需要说明的是需要说明的是, ,算法结束时堆并不一定为空。算法结束时堆并不一定为空。 算法分析：算法分析：第第4 4讲讲 分支限界法分支限界法 FIFO限界算法搜索解空间的过程是按广度优先搜限界算法搜索解空间的过程是按广度优先搜索子集树过程中生成的一般队列的元素顺序，搜索最索子集

20、树过程中生成的一般队列的元素顺序，搜索最优解，而优先队列限界搜索解空间的过程是按动搜索优解，而优先队列限界搜索解空间的过程是按动搜索过程中态构造的优先队列的首结点顺序搜索最优解。过程中态构造的优先队列的首结点顺序搜索最优解。 看了上面的例子大家会发现，优先队列法扩展结点看了上面的例子大家会发现，优先队列法扩展结点的过程，一开始实际是在进行类似的过程，一开始实际是在进行类似“深度优先深度优先”的搜的搜索。索。第第4 4讲讲 分支限界法分支限界法p FIFO FIFO搜索或搜索或LIFOLIFO搜索也可以通过加入搜索也可以通过加入“限界限界”策略策略加加 速搜索吗速搜索吗? ?与优先队列式分支限界

21、法与优先队列式分支限界法LC检索的检索的 区别在哪儿呢？区别在哪儿呢？p 答案：由于答案：由于FIFO搜索或搜索或LIFO搜索是盲目扩展结点搜索是盲目扩展结点, 当前最优解距真正的最优解距离较大当前最优解距真正的最优解距离较大,作为作为“界界”所所起起 到的剪枝作用很有限到的剪枝作用很有限,不能有效提高搜索速度不能有效提高搜索速度p 其实其实,优先队列式扩展结优先队列式扩展结 点的过程，一开始实际是点的过程，一开始实际是在进行类似在进行类似“深度优先深度优先” 的的 搜索。搜索。讨论：讨论：第第4 4讲讲 分支限界法分支限界法 上一小节的例子是求最大值的最优化问题，下面我们上一小节的例子是求最

22、大值的最优化问题，下面我们以求解以求解”最小成本最小成本“的最优化问题为例，给出的最优化问题为例，给出FIFO分支分支搜索算法框架。搜索算法框架。 假定问题解空间树为假定问题解空间树为T,T至少包含一个解结点（即答至少包含一个解结点（即答案结点）案结点）. .u为当前的最优解为当前的最优解, ,初值为一个较大的数初值为一个较大的数;E;E表示表示当前扩展的活结点当前扩展的活结点, ,x为为E E的儿子的儿子, ,s(x)为结点为结点x x下界函数下界函数, ,当当其值比其值比u u大时大时, ,不可能为最优解不可能为最优解, ,不继续搜索此分支不继续搜索此分支, ,该结点该结点不入队不入队;

23、;当其值比当其值比u u小时小时, ,可能达到最优解可能达到最优解, ,继续搜索此分支继续搜索此分支, ,该结点入队该结点入队; ;cost(X)为当前叶结点所在分支的解。为当前叶结点所在分支的解。 举一反三：举一反三：找最小成本的分枝限界法和优先队列分枝限界法找最小成本的分枝限界法和优先队列分枝限界法第第4 4讲讲 分支限界法分支限界法search（T） /为找出最小成本答案结点检索为找出最小成本答案结点检索T T。 leaf=0; 初始化队；初始化队；ADDQ（T）；）； /根结点入队根结点入队 parent（E）=0； /记录扩展路径，当前结点的父结点记录扩展路径，当前结点的父结点 wh

24、ile （队不空）队不空）DELETEQ(E) /队首结点出队为新的队首结点出队为新的E E结点；结点；for （E E的每个儿子的每个儿子 X X） if (s（X）u) /当是可能的最优解时入队当是可能的最优解时入队 ADD Q（X）；）； parent（X）=E; if (X是解结点是解结点 ) /x/x为叶结点为叶结点 U=min（cost（X），），u）; leaf=x; /方案的叶结点存储在方案的叶结点存储在leafleaf中中 FIFO算法框架：算法框架：第第4 4讲讲 分支限界法分支限界法 print（”least cost=，u）；）； while （leaf0） /输出最优

25、解方案输出最优解方案 print（leaf）；）； leaf=parent（leaf）；）；第第4 4讲讲 分支限界法分支限界法 找最小成本的找最小成本的LC分支分支- -限界算法限界算法框架框架与与FIFO分支分支- -限限界算法界算法框架结构大致相同，只是扩展结点的顺序不同，框架结构大致相同，只是扩展结点的顺序不同，因而存储活结点的数据结构不同。因而存储活结点的数据结构不同。FIFO分支分支- -限界算限界算法用法用队列队列存储活结点，存储活结点，LC分枝分枝- -限界算法用限界算法用堆堆存储活存储活结点，以保证比较优良的结点先被扩展。且对于结点，以保证比较优良的结点先被扩展。且对于LCL

26、C分分支支- -限界算法，一旦扩展到叶结点就已经找到最优解，限界算法，一旦扩展到叶结点就已经找到最优解，可以停止搜索。可以停止搜索。而用而用FIFOFIFO算法需要队列为空时才可以算法需要队列为空时才可以停止搜索。停止搜索。找最小成本的找最小成本的LC分支分支-限界算法限界算法第第4 4讲讲 分支限界法分支限界法例例5：单源最短路径问题（：单源最短路径问题（LC算法）算法）给定带权有向图给定带权有向图G =(V,E),G =(V,E),其中每条边的权是非负其中每条边的权是非负实数实数. .另外另外, ,还给定还给定V V中的一个顶点中的一个顶点, ,称为源。现在要计称为源。现在要计算从源到所有

27、其它各顶点的最短路长度。这里路的长算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为度是指路上各边权之和。这个问题通常称为单源最短单源最短路径问题路径问题。ISabcdefghijlmnopqrtu第第2 2讲讲 分支限界法分支限界法ISabcdefghilmnopqrtuj下面以一个例子来说明单源最短路径问题下面以一个例子来说明单源最短路径问题: :在有向图在有向图G G中中, ,每一边都有一个非负边权。求从源顶点每一边都有一个非负边权。求从源顶点I I到目标顶点到目标顶点S S之之间的最短路径。间的最短路径。单源最短路径问题单源最短路径问题具体问题实例具体

28、问题实例：IS2342239279l35122871ABCDEFGHJ用用优先队列式分支限界法优先队列式分支限界法解有向解有向图图G G的单源最短路径问题产生的解的单源最短路径问题产生的解空间树。其中，每一个结点内数空间树。其中，每一个结点内数字表示该结点所对应的当前路长字表示该结点所对应的当前路长I2342239279l35122871ABCDEFGHJI活节点入堆活节点入堆（解空间树生成过程）（解空间树生成过程）根节点出堆根节点出堆IIABC对出堆节点扩展对出堆节点扩展234构造堆构造堆A2B3C4A2B3C4判断判断B,E,F是否入堆是否入堆(只有只有E,F可入可入)注：判断注：判断A的

29、子节点的子节点E是否入堆的方法：从源是否入堆的方法：从源点经过点经过A到到E的路径长度如果小于经过目前解的路径长度如果小于经过目前解空间树上从源点到空间树上从源点到E的其他最短路径长度，的其他最短路径长度，则则E入堆，否则入堆，否则E不入堆。判定其他节点入堆不入堆。判定其他节点入堆的方法与此相同。的方法与此相同。用用优先队列式分支限界法优先队列式分支限界法解有向解有向图图G G的单源最短路径问题产生的解的单源最短路径问题产生的解空间树。其中，每一个结点内数空间树。其中，每一个结点内数字表示该结点所对应的当前路长字表示该结点所对应的当前路长I2342239279l35122871ABCDEFGH

30、J活节点入堆活节点入堆（解空间树生成过程）（解空间树生成过程）根节点出堆根节点出堆IABC对出堆节点扩展对出堆节点扩展234B3C4整理堆整理堆判断判断B,E,F是是否入堆否入堆B3C4E4F9B3EFD判断判断E,D是否入堆是否入堆(只有只有D可入可入)注：判断注：判断B的子节点的子节点E是否入堆的方法：从源点经过是否入堆的方法：从源点经过B到到E的路径长度的路径长度(12)如果小于经过目前解空间树上从源点到如果小于经过目前解空间树上从源点到E的其他最短路径长度的其他最短路径长度(4)，则则E入堆，否则入堆，否则E不入堆。不入堆。 判定其他节点入堆的方法与此相同。判定其他节点入堆的方法与此相

31、同。C4F9E4构造堆构造堆272用用优先队列式分支限界法优先队列式分支限界法解有向解有向图图G G的单源最短路径问题产生的解的单源最短路径问题产生的解空间树。其中，每一个结点内数空间树。其中，每一个结点内数字表示该结点所对应的当前路长字表示该结点所对应的当前路长I2342239279l35122871ABCDEFGHJ活节点入堆活节点入堆（解空间树生成过程）（解空间树生成过程）根节点出堆根节点出堆IABC对出堆节点扩展对出堆节点扩展234整理整理为堆为堆判断判断D是否是否入堆入堆（不）（不）C4E4F9C4EFDD5C4E4D5F9整理为堆E4D5F9整理为堆注：判断注：判断C的子节点的子节

32、点D是否入堆的方法：从源点经过是否入堆的方法：从源点经过C到到D的路径长度的路径长度(6)如果小于经过目前解空间树上其他源点到如果小于经过目前解空间树上其他源点到D的最短路径长度的最短路径长度(5)，则，则E入入堆，否则堆，否则D不入堆。不入堆。 D不入堆不入堆272用用优先队列式分支限界法优先队列式分支限界法解有向解有向图图G G的单源最短路径问题产生的解的单源最短路径问题产生的解空间树。其中，每一个结点内数空间树。其中，每一个结点内数字表示该结点所对应的当前路长字表示该结点所对应的当前路长I2342239279l35122871ABCDEFGHJ活节点入堆活节点入堆（解空间树生成过程）（解

33、空间树生成过程）根节点出堆根节点出堆IABC对出堆节点扩展对出堆节点扩展234判断判断H,D是否是否入堆入堆（H入）入）EFDE4D5F9整理为堆E4HD5F9H7D5判断判断H,J是否入是否入堆堆（J入）入）J整理为堆J6F9H7整理为堆D5F9D5F9H7H入入2721用用优先队列式分支限界法优先队列式分支限界法解有向解有向图图G G的单源最短路径问题产生的解的单源最短路径问题产生的解空间树。其中，每一个结点内数空间树。其中，每一个结点内数字表示该结点所对应的当前路长字表示该结点所对应的当前路长I2342239279l35122871ABCDEFGHJ活节点入堆活节点入堆（解空间树生成过程

34、）（解空间树生成过程）根节点出堆根节点出堆IABC对出堆节点扩展对出堆节点扩展234判断判断H,S是否入是否入堆堆（S入）入）EFD整理为堆HJJ6F9H7J6SH7F9S8H7判断判断S是否入堆是否入堆（S不入）不入）整理为堆S8F9S8因因S是叶子，结束；是叶子，结束；最优解从最优解从S到到I272312第第4 4讲讲 分支限界法分支限界法 while (true) / 搜索问题的解空间搜索问题的解空间 for (int j=1;j=n;j+) (cE.ijinf)&(E.length+cE.ijdistj) / 顶点顶点i到顶点到顶点j可达，且满足控制约束可达，且满足控制约束 distj

35、=enode.length+aenode.ij; pj=enode.i; HeapNode node = new HeapNode(j,distj); heap.put(node); / 加入活结点优先队列加入活结点优先队列 if (heap.isEmpty() break; else enode = (HeapNode) heap.removeMin();算法设计算法设计顶点顶点I I和和j j间有边，且间有边，且此路径长小于原先从此路径长小于原先从原点到原点到j j的路径长的路径长 (伪代码伪代码)第第4 4讲讲 分支限界法分支限界法动态规划解单源最短路径动态规划解单源最短路径p 由于图的

36、关系复杂而无序由于图的关系复杂而无序, ,一般难以呈现阶段特征一般难以呈现阶段特征( (除除 了特殊的图，如多段图了特殊的图，如多段图-参见参见例例5 5),),因此动态规划在图因此动态规划在图 论中的应用不多论中的应用不多. .但有一类图但有一类图, ,它的顶点却是有序的它的顶点却是有序的, ,这这 就是无环有向图。就是无环有向图。p 在无环有向图中在无环有向图中, ,我们可以对点进行拓扑排序我们可以对点进行拓扑排序, ,使其体使其体 现出有序的特征现出有序的特征, ,据此划分阶段据此划分阶段. .在有向无环图中求最在有向无环图中求最 短路径的算法短路径的算法, ,体现出简单的动态规划思想体

37、现出简单的动态规划思想. .请看下面请看下面 的例子。的例子。例例 5:单源最短路径问题单源最短路径问题 已知从已知从A A到到S S的路线及费用如下图，求从的路线及费用如下图，求从A A到到S S的最小的最小费用路线。费用路线。A32745542BCEFGS3第第4 4讲讲 单源最短路径单源最短路径第第4 4讲讲 单源最短路径单源最短路径问题的分析问题的分析A32745542BCEFGS3 枚举搜索图中的每条路径，但当图的规模较大时，搜枚举搜索图中的每条路径，但当图的规模较大时，搜索的效率显然不尽人意。索的效率显然不尽人意。 试用动态规划的思路分析这道题试用动态规划的思路分析这道题: :从图

38、中可以看到从图中可以看到,A,A点要到达点要到达S S点必然要经过点必然要经过B B和和C C中的一个中的一个, ,所以所以A A到到S S的最的最短距离必然等于短距离必然等于B B到到S S的最短距离加上的最短距离加上5,5,或是或是C C到到S S的最的最短距离加上短距离加上2.2.同样同样,B,B到到S S的最短距离等于的最短距离等于E E到到S S的最短的最短距离加上距离加上3 3或是或是F F到到S S的最短距离加上的最短距离加上2,2,. .第第4 4讲讲 单源最短路径单源最短路径 设设Gi为点为点i到点到点S的距离的距离,显显GE=4,GF=3,GG=5,根据上面的分析根据上面的

39、分析,有：有： GB=minGE+3，GF+2=5， GC=minGF+7，GG+4=9， GA=minGB+5，GC+2=10， 所以所以A到到S的最短距离是的最短距离是10，最短路径，最短路径ABFSA32745542BCEFGS3第第4 4讲讲 单源最短路径单源最短路径 阶段阶段: :我们按虚线所示来划分阶段我们按虚线所示来划分阶段, ,按按1,2,3,41,2,3,4的顺序的顺序来逐阶段求解子问题来逐阶段求解子问题. .因为只有前一阶段的所有子问因为只有前一阶段的所有子问题计算了题计算了, ,才能正确计算当前阶段的子问题才能正确计算当前阶段的子问题, ,所以这样所以这样的划分是正确合理

40、的。的划分是正确合理的。划分阶段划分阶段A32745542BCEFGS3阶段阶段1阶段阶段4 阶段阶段3阶段阶段2第第4 4讲讲 单源最短路径单源最短路径状态：状态可看成一个阶段中的多个子问题。第状态：状态可看成一个阶段中的多个子问题。第1个阶个阶段有一个状态即段有一个状态即S，第，第2个阶段是三个状态个阶段是三个状态E，F和和G，而第而第3个阶段有两个状态个阶段有两个状态B和和C，第，第4个阶段只有一个状个阶段只有一个状态态A。A32745542BCEFGS3状态状态4状态状态3状态状态2状态状态1第第4 4讲讲 单源最短路径单源最短路径A32745542BCEFGS3决策：决策就是状态转移

41、。状态转移方程：决策：决策就是状态转移。状态转移方程： G(i)=minG(j) + Aij ，j=1,n, n是从节点是从节点i一步可达的节点个数，即节点一步可达的节点个数，即节点i的直接邻居节的直接邻居节点个数。点个数。Aij表示从表示从i到到j的一步可达线段长度。的一步可达线段长度。GC=minGF+7，GG+4=9，第第4 4讲讲 单源最短路径单源最短路径Step1 :real COST(n), integer D(n-1),P(k), r, j, k, n COST(n)0Step2: for jn-1 to 1 by -1 do 设设r是一个这样的结点，是一个这样的结点，E且使且使

42、c(j, r) +COST(r)取最小值。取最小值。Step3: COST（j）c(j, r)+COST(r)Step4: D(j) rStep5: repeatStep6: P(1) 1;P(k) nStep7: for j2 to k-1 doStep8: P(j) D(P(j-1)Step9: repeatStep10: end FGRAPH第第4 4讲讲 分支限界法分支限界法p 回溯法以深度优先的方式搜索解空间树回溯法以深度优先的方式搜索解空间树T，而分支而分支 限界法则以广度优先或以最小耗费优先（优先队列）限界法则以广度优先或以最小耗费优先（优先队列） 的方式搜索解空间树的方式搜索解

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

44、小结图的搜索算法小结回溯与分支限界法回溯与分支限界法第第4 4讲讲 分支限界法分支限界法p 相对而言相对而言,分支限界算法的解空间比回溯法大得多分支限界算法的解空间比回溯法大得多, 因此当内存容量有限时因此当内存容量有限时,回溯法成功的可能性更大。回溯法成功的可能性更大。 回溯法和分支限界法区别：回溯法和分支限界法区别：方方法法搜索方法搜索方法数据数据结构结构节点存储特性节点存储特性应用应用回回溯溯深度优先搜索深度优先搜索堆栈堆栈活节点的所有可活节点的所有可行子节点被遍历行子节点被遍历后才被栈中弹出后才被栈中弹出满足约束满足约束 条件的所条件的所有解的方案有解的方案分分支支限限界界广度优先搜索

45、广度优先搜索或者最小消耗或者最小消耗优先搜索优先搜索队列队列、优、优先队先队列列每个节点只有一每个节点只有一次成为活节点的次成为活节点的机会机会满足约束条件的一满足约束条件的一个解个解,或者在某种意或者在某种意义下的最优解义下的最优解第第4 4讲讲 分支限界法分支限界法p 采用穷举法、回溯法或分支限界法都可以通过利用当采用穷举法、回溯法或分支限界法都可以通过利用当 前最优解和上界函数加速。前最优解和上界函数加速。p 仅对限界剪枝的效率而言，优先队列分支限界法显仅对限界剪枝的效率而言，优先队列分支限界法显 然要更充分一些。然要更充分一些。p 在穷举法中通过上界函数与当前情况下函数值的比在穷举法中

46、通过上界函数与当前情况下函数值的比 较，可以直接略过不合要求的情况而省去了更进一步较，可以直接略过不合要求的情况而省去了更进一步 的枚举和判断；的枚举和判断；p 回溯法则因为层次的划分，可以在上界函数值小于当回溯法则因为层次的划分，可以在上界函数值小于当 前最优解时，剪去以该结点为根的子树，也就节省了前最优解时，剪去以该结点为根的子树，也就节省了 搜索范围；搜索范围；第第4 4讲讲 分支限界法分支限界法p 分支限界法在这方面除了可以做到回溯法能做到的之分支限界法在这方面除了可以做到回溯法能做到的之外，同时若采用优先队列的分支限界法，用上界函数作外，同时若采用优先队列的分支限界法，用上界函数作为

47、活结点的优先级，一旦有叶结点成为当前扩展结点，为活结点的优先级，一旦有叶结点成为当前扩展结点，就意味着该叶结点所对应的解即为最优解，可以立即终就意味着该叶结点所对应的解即为最优解，可以立即终止其余的过程。止其余的过程。p在前面的例题中曾说明，优先队列的分支限界法更象是在前面的例题中曾说明，优先队列的分支限界法更象是有选择、有目的地进行有选择、有目的地进行深度优先搜索深度优先搜索，时间效率、空间效，时间效率、空间效率都是比较高的。率都是比较高的。第第4 4讲讲 分支限界法分支限界法p 撇开时空效率的因素不谈，在解决最优化问题的算撇开时空效率的因素不谈，在解决最优化问题的算 法中，搜索可以说是法中，搜索可以说是“万能万能”的。所以动态规划可的。所以动态规划可以以 解决的问题，搜索也一定可以解决。解决的问题，搜索也一定可以解决。p 动态规划要求阶段决策具有无后向性，而搜索算法没动态规划要求阶段决策具有无后向性，而搜索算法没 有此限制。有此限制。p 动态规划是动态规划是自底向上自底向上或或自顶向下自顶向下的递推求解，而无论的递推求解，而无论 深度优先搜索或广度优先搜索都是自顶向下求解。深度优先搜索或广度优先搜索都是自顶向下求解。 动态规划与搜索算法动态规划与搜索算法第第4 4讲讲 分支限界法分支限界法利用动态规划法进行算