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

第4讲优先队列分支限界法每节一经典有选择地搜索3654789第4讲分支限界法上节课，我们介绍了3种不同的分支搜索方式：FIFO、LIFO、优先队列，详细分析了FIFO搜索方式。当然用LIFO搜索方式也同样可以设计出对应的算法，请同学们尝试！

本节我们将详细分析如何用优先队列分支限界法来解决类似问题。

优先队列式分支限界法：3654789搜索算法：分支搜索（例：深度优先，广度优先，均为按深度或宽度顺序，在全部解空间搜索）分支限界搜索（例：与分枝搜索类似，并加入结点限制，对不满足条件的结点为根的分枝子树不再进行搜索）优先队列分支限界搜索例：在分支限界搜索基础上，对搜索结点的顺序按优先队列组织，使每一步搜索向最优解目标靠近，不满足条件的结点为根的分支子树不再进行搜索，遇到叶结点，即可得到一个解）第4讲分支限界法优先队列组织：结点优先级确定后,简单地按结点优先级进行排序,就生成了优先队列.但是,排序算法的时间复杂度较高。考虑到搜索算法每次只扩展一个结点,数据结构中堆排序方法适合这一特点,并且元素比较和交换的次数最少.堆通常有两类：最大堆(根部的数最大,由大到小构造堆)，最小堆(根部的数最小,由小到大构造堆)，第4讲分支限界法定义：堆(heap)是一个满足下列条件的完全二叉数：（1）父结点比其左、右儿子结点都大（或小）。（2）左、右儿子分别是一个堆。即：n个元素的序列{k1,k2,…kn},当且仅当满足：

ki≤k2i

ki≥k2i

ki≤k2i+1

ki≥k2i+1

堆定义或(i=1,2,……n/2)第4讲分支限界法例：6，4，7，9构造的大堆（从根到叶子数值减小）647969749674无序序列4筛选后的状态建堆6筛选后建成堆第4讲分支限界法例:3,8,7,4,5,9,1,6构造的小堆(从根到叶子数值增大)初始堆根节点1出队，最后节点6做根节点位后的状态出堆6和3交换后的状态135478696354781913654789第4讲分支限界法例:3,8,7,4,5,9,1,6构造的小堆(从根到叶子数值增大)6和4交换后的状态出堆34567891第4讲分支限界法例:3,8,7,4,5,9,6构造的小堆(从根到叶子数值增大)初始堆进堆1进堆后建成新堆演示过程3468597134685971新堆建成第4讲分支限界法

优先队列式搜索通过结点的优先级,可以使搜索尽快朝着解空间树上能到达最优解的分支推进,这样当前最优解一定较接近真正的最优解.其后，我们将当前最优解作为一个“界”,对上界(或下界)不可能达到(大于)这个界的分支则不去进行搜索(结点不入队),这样就能缩小搜索范围，从而提高搜索效率.这种搜索策略称为优先队列分支限界法，简称LC-检索(LeastCostSearch)。优先队列式分支限界法：第4讲分支限界法结点扩展方式：无论那种分支限界法，都需要有一张活结点表。优先队列分支限界法将活结点组织成一个优先队列，并按优先队列中规定的结点优先级

选取优先级最高的活结点成为当前扩展结点.结点优先级确定：优先队列中结点优先级通常是一个与该结点相关的数值p,它一般表示其接近最优解的程度，装载问题就可以当前结点的装载上界为该结点的优先级。结点是否入队判定标准：结点装载上界>当前最优方案bestw,并且从该结点到根的装载方案下，装载量不超过船装载量c1优先队列式分支限界法算法设计要点：第4讲分支限界法例如：装载问题W={10，30，50}，c1=60，所构成的子集树如下图所表示：方框中红色数表示该结点的装载上界，作为结点的优先级。装载上界=已装入物品重量+未来可能装入物品的重量注意：已经“处理”过的物品(已判断是否装入)不再计算为未来可能装入物品的重量。AEJBKX1=1DHIGNOFLMCX1=0X2=1X2=1X3=1X3=1X3=1X3=1X2=0X2=0X3=0X3=0X3=0X3=090909090606040108080805050300第4讲分支限界法例4.装载问题:有三个货物，其重量为W={10，30，50}，有2辆货车，其载重量为c1=60，c2=50,问：是否有方案把所有货物运走？关键概念：(1)每个字母表示车当前装货状态。(2)当前状态下剩余装载量(ew)：当前状态下剩余装载量。(3)当前状态下装载量上界：已装入货物和未来可能装入的货物总重量(排除已打算不装入的货物重量)。(4)当前状态最优已装载上界：截至目前状态(包括目前状态)，所有已搜索的局部装载方案中的最大装载量(已装入的最大重量)。装50装10装30装50装50装30装50不装10不装30第4讲分支限界法1）

初始队列中只有结点A；2）

结点A变为E-结点扩充B入队,bestw=10;结点C的装载上界为30+50=80>bestw，也入队；3）

结点B变为E-结点扩充D入队,bestw=40;结点E的装载上界为60>bestw，也入队；4）

结点C变为E-结点扩充F入队,bestw仍为40;结点G的装载上界为50>bestw,也入队；5）

结点D变为E-结点,叶结点H超过容量,不入队；叶结点I的装载上界为40=bestw=40,不入队；6）

结点E变为E-结点,叶结点J装载上界为60>bestw=40,入队，并将bestw更新为60;叶结点K的装载上界为10<bestw=40,不入队,即被剪掉；7）

结点F变为E-结点，叶结点L超过容量，不入队，bestw仍为60；叶结点M的装载上界为30<bestw=60,被剪掉；8）

结点G变为E-结点,叶结点N、O都被剪掉;9)结点J变为E-结点,由于J是叶子结点，算法结束。FIFO+限界搜索过程：物品的重量W={10,30,50}，c1=60FIFO+限界搜索(超剩余容量)AEJBKX1=1DHIGNOFLMCX1=0X2=1X2=1X3=1X3=1X3=1X3=1X2=0X2=0X3=0X3=0X3=0X3=090909090606040108080805050300H)J所有出队结点中的叶子结点到根结点的路径就是最优装载方案，即最优解（可能有多个最优解）。1)A2)3)4)5)6)EFGJ7)8)ABCCBCDEDEFGDEFGFGJGJ9)J叶子，队列空，算法结束第4讲分支限界法1）

初始队列中只有结点A;2）

结点A变为E-结点扩充B入堆,bestw=10;结点C的装载上界为30+50=80>bestw,也入堆;堆中B上界为90，在优先队列之首;3）

结点B变为E-结点扩充D入堆,bestw=40;结点E的装载上界为60>bestw,也入堆;此时堆中D上界为90，在优先队列之首;4）

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

结点C变为E-结点扩充F入堆,bestw仍为40;结点G的装载上界为50>bestw,也入堆;此时堆中E上界为60，在优先队列之首。6）

结点E变为E-结点,叶结点J装载量为60，入堆,bestw变为60;叶结点K上界为10<bestw，被剪掉；此时堆中J上界为60，在优先队列之首。7）

结点J变为E-结点（叶子结点），扩展的层次为4（或队首结点为叶子），算法结束。虽然此时堆并不空，但可以确定已找到了最优解。物品的重量W={10,30,50}方框数字为装载上界，Bestw为当前最优装载量优先队列+限界搜索A90909090606040108080805050300Bestw=0Bestw=10Bestw=40Bestw=40Bestw=40Bestw=40Bestw=10Bestw=40如果装入x3,则超重Bestw=60如果装入则超重不是最优方案裁剪AEJBKX1=1DHIGNOFLMCX1=0X2=1X2=1X3=1X3=1X3=1X3=1X2=0X2=0X3=0X3=0X3=0X3=0BC9080ADC9080E60BCI8040E60DFE8040I50CG60E60IFG4050J60IEG4050J60扩展层数4(叶子)，算法结束第4讲分支限界法1)输出解方案,在搜索过程中仍需要生成解结构树,其结点信息包括指向父结点的指针和标识物品取舍(或是父结点的左、右孩子)。2)堆结点首先应该包括结点优先级信息：结点所在分支的装载上界uweight；堆中无法体现结点的层次信息(level),层次信息只能存储在结点中。数据结构设计：第4讲分支限界法3)不同于分枝限界算法,由于扩展结点不是按层进行的，计算结点所在分支的装载上界时,要用数组变量r记录当前层以下的最大重量，这样可以随时方便使用各层结点的装载上界。数据结构设计：第4讲分支限界法同样为了突出算法本身的思想，对堆操作也只进行抽象的描述用HeapNode代表队列类型,则HeapNodeH;定义了一个堆H,相关操作有：

Insert(Q,…)表示入堆

DeleteMax(Q,…)表示出堆数据结构设计：第4讲分支限界法算法3

HeapNodeH[1000];structbbnode{bbnode*parent;//父节点指针intLChild;};//当且仅当是父节点的左孩子时，取值为1structHeapNode{bbnode*ptr;//活节点指针

floatuweight;//活节点的重量上限

intlevel;};//活节点所在层第4讲分支限界法AddLiveNode(floatwt,intlev,bbnode*E,intch){bbnode*b=newbbnode;b->parent=E;b->LChil=ch;HeapNodeN;N.uweight=wt;N.level=lev;N.ptr=b;Insert(H，N);}第4讲分支限界法MaxLoading(floatc,intn,intbestx[]){froatr[100],Ew,bestw=0;r[n]=0;For(intj=n-1;j>0;j--)r[j]=r[j+1]+w[j+1];Inti=1;bbnode*E=0;Ew=0;//搜索子集空间树while(i!=n+1)//不在叶子上

{if(Ew+w[i]<=c)//可行的左孩子

{AddLiveNode(E,Ew+w[i]+r[i],1,i+1);}if(bestw<Ew+w[i])bestw=Ew+w[i];if(bestw<Ew+r[i])AddLiveNode(E,Ew+r[i],0,i+1);DeleteMax(H,E);i=N.level;E=N.ptr;Ew=N.uweight-r[i-1];}for(intj=n;j>0;j--){bestx[j]=E->LChild;E=E->parent;}returnEw;}第4讲分支限界法算法的复杂度仍为O(2n)。但通过限界策略,并没有搜索子集树中的所有结点,由于每次都是选取的最接近最优解的结点扩展，所以一旦搜索到叶结点作E结点时算法就可以结束了,所以算法实际执行时复杂度远远低于O(2n).需要说明的是,算法结束时堆并不一定为空。算法分析：第4讲分支限界法

FIFO限界算法搜索解空间的过程是按广度优先搜索子集树过程中生成的一般队列的元素顺序，搜索最优解，而优先队列限界搜索解空间的过程是按动搜索过程中态构造的优先队列的首结点顺序搜索最优解。

看了上面的例子大家会发现，优先队列法扩展结点的过程，一开始实际是在进行类似“深度优先”的搜索。第4讲分支限界法FIFO搜索或LIFO搜索也可以通过加入“限界”策略加速搜索吗?与优先队列式分支限界法—LC—检索的区别在哪儿呢？答案：由于FIFO搜索或LIFO搜索是盲目扩展结点,当前最优解距真正的最优解距离较大,作为“界”所起到的剪枝作用很有限,不能有效提高搜索速度其实,优先队列式扩展结点的过程，一开始实际是在进行类似“深度优先”的搜索。讨论：第4讲分支限界法上一小节的例子是求最大值的最优化问题，下面我们以求解”最小成本“的最优化问题为例，给出FIFO分支搜索算法框架。假定问题解空间树为T,T至少包含一个解结点（即答案结点）.u为当前的最优解,初值为一个较大的数;E表示当前扩展的活结点,x为E的儿子,s(x)为结点x下界函数,当其值比u大时,不可能为最优解,不继续搜索此分支,该结点不入队;当其值比u小时,可能达到最优解,继续搜索此分支,该结点入队;cost(X)为当前叶结点所在分支的解。举一反三：找最小成本的分枝限界法和优先队列分枝限界法第4讲分支限界法search（T）//为找出最小成本答案结点检索T。

{leaf=0;

初始化队；ADDQ（T）；//根结点入队parent（E）=0；//记录扩展路径，当前结点的父结点

while（队不空）{DELETEQ(E)//队首结点出队为新的E结点；for（E的每个儿子X）

if(s（X）<u)//当是可能的最优解时入队

{ADDQ（X）；

parent（X）=E;

if(X是解结点)//x为叶结点

{U=min（cost（X），u）;

leaf=x;}//方案的叶结点存储在leaf中

}}FIFO算法框架：第4讲分支限界法

print（”leastcost=’，u）；

while（leaf<>0）//输出最优解方案

{print（leaf）；

leaf=parent（leaf）；}

}

第4讲分支限界法找最小成本的LC分支-限界算法框架与FIFO分支-限界算法框架结构大致相同，只是扩展结点的顺序不同，因而存储活结点的数据结构不同。FIFO分支-限界算法用队列存储活结点，LC分枝-限界算法用堆存储活结点，以保证比较优良的结点先被扩展。且对于LC分支-限界算法，一旦扩展到叶结点就已经找到最优解，可以停止搜索。而用FIFO算法需要队列为空时才可以停止搜索。找最小成本的LC分支-限界算法第4讲分支限界法例5：单源最短路径问题（LC算法） 给定带权有向图G=(V,E),其中每条边的权是非负实数.另外,还给定V中的一个顶点,称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。ISabcdefghijlmnopqrtu第2讲分支限界法ISabcdefghilmnopqrtuj下面以一个例子来说明单源最短路径问题:在有向图G中,每一边都有一个非负边权。求从源顶点I到目标顶点S之间的最短路径。单源最短路径问题具体问题实例：IS2342239279l35122871ABCDEFGHJ用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点内数字表示该结点所对应的当前路长IS2342239279l35122871ABCDEFGHJI活节点入堆（解空间树生成过程）根节点出堆IIABC对出堆节点扩展234构造堆A2B3C4A2B3C4判断B,E,F是否入堆(只有E,F可入)注：判断A的子节点E是否入堆的方法：从源点经过A到E的路径长度如果小于经过目前解空间树上从源点到E的其他最短路径长度，则E入堆，否则E不入堆。判定其他节点入堆的方法与此相同。用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点内数字表示该结点所对应的当前路长IS2342239279l35122871ABCDEFGHJ活节点入堆（解空间树生成过程）根节点出堆IABC对出堆节点扩展234B3C4整理堆判断B,E,F是否入堆B3C4E4F9B3EFD判断E,D是否入堆(只有D可入)注：判断B的子节点E是否入堆的方法：从源点经过B到E的路径长度(12)如果小于经过目前解空间树上从源点到E的其他最短路径长度(4)，则E入堆，否则E不入堆。判定其他节点入堆的方法与此相同。C4F9E4构造堆272用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点内数字表示该结点所对应的当前路长IS2342239279l35122871ABCDEFGHJ活节点入堆（解空间树生成过程）根节点出堆IABC对出堆节点扩展234整理为堆判断D是否入堆（不）C4E4F9C4EFDD5C4E4D5F9整理为堆E4D5F9整理为堆注：判断C的子节点D是否入堆的方法：从源点经过C到D的路径长度(6)如果小于经过目前解空间树上其他源点到D的最短路径长度(5)，则E入堆，否则D不入堆。D不入堆272用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点内数字表示该结点所对应的当前路长IS2342239279l35122871ABCDEFGHJ活节点入堆（解空间树生成过程）根节点出堆IABC对出堆节点扩展234判断H,D是否入堆（H入）EFDE4D5F9整理为堆E4HD5F9H7D5判断H,J是否入堆（J入）J整理为堆J6F9H7整理为堆D5F9D5F9H7H入2721用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树。其中，每一个结点内数字表示该结点所对应的当前路长IS2342239279l35122871ABCDEFGHJ活节点入堆（解空间树生成过程）根节点出堆IABC对出堆节点扩展234判断H,S是否入堆（S入）EFD整理为堆HJJ6F9H7J6SH7F9S8H7判断S是否入堆（S不入）整理为堆S8F9S8因S是叶子，结束；最优解从S到I272312第4讲分支限界法

while(true)//搜索问题的解空间

{for(intj=1;j<=n;j++)

((c[E.i][j]<inf)&&(E.length+c[E.i][j]<dist[j])){//顶点i到顶点j可达，且满足控制约束

dist[j]=enode.length+a[enode.i][j];p[j]=enode.i;HeapNodenode=newHeapNode(j,dist[j]);heap.put(node);//加入活结点优先队列}

if(heap.isEmpty())break;elseenode=(HeapNode)heap.removeMin();}算法设计顶点I和j间有边，且此路径长小于原先从原点到j的路径长(伪代码)第4讲分支限界法动态规划解单源最短路径由于图的关系复杂而无序,一般难以呈现阶段特征(除了特殊的图，如多段图--参见例5),因此动态规划在图论中的应用不多.但有一类图,它的顶点却是有序的,这就是无环有向图。在无环有向图中,我们可以对点进行拓扑排序,使其体现出有序的特征,据此划分阶段.在有向无环图中求最短路径的算法,体现出简单的动态规划思想.请看下面的例子。例5:单源最短路径问题

已知从A到S的路线及费用如下图，求从A到S的最小费用路线。A32745542BCEFGS3第4讲单源最短路径第4讲单源最短路径问题的分析A32745542BCEFGS3枚举搜索图中的每条路径，但当图的规模较大时，搜索的效率显然不尽人意。试用动态规划的思路分析这道题:从图中可以看到,A点要到达S点必然要经过B和C中的一个,所以A到S的最短距离必然等于B到S的最短距离加上5,或是C到S的最短距离加上2.同样,B到S的最短距离等于E到S的最短距离加上3或是F到S的最短距离加上2,…….第4讲单源最短路径设G[i]为点i到点S的距离,显G[E]=4,G[F]=3,G[G]=5,根据上面的分析,有：G[B]=min{G[E]+3，G[F]+2}=5，G[C]=min{G[F]+7，G[G]+4}=9，G[A]=min{G[B]+5，G[C]+2}=10，所以A到S的最短距离是10，最短路径ABFSA32745542BCEFGS3第4讲单源最短路径阶段:我们按虚线所示来划分阶段,按1,2,3,4的顺序来逐阶段求解子问题.因为只有前一阶段的所有子问题计算了,才能正确计算当前阶段的子问题,所以这样的划分是正确合理的。划分阶段A32745542BCEFGS3阶段1阶段4阶段3阶段2第4讲单源最短路径状态：状态可看成一个阶段中的多个子问题。第1个阶段有一个状态即S，第2个阶段是三个状态E，F和G，而第3个阶段有两个状态B和C，第4个阶段只有一个状态A。A32745542BCEFGS3状态4状态3状态2状态1第4讲单源最短路径A32745542BCEFGS3决策：决策就是状态转移。状态转移方程：

G(i)=min{G(j)+A[i][j]}，j=1,…,n,

n是从节点i一步可达的节点个数，即节点i的直接邻居节点个数。A[i][j]表示从i到j的一步可达线段长度。G[C]=min{G[F]+7，G[G]+4}=9，第4讲单源最短路径Step1:realCOST(n),integerD(n-1),P(k),r,j,k,nCOST(n)←0Step2:forj←n-1to1by-1do设r是一个这样的结点，<j,r>∈E且使c(j,r)+COST(r)取最小值。Step3:

COST（j）←c(j,r)+COST(r)Step4:

D(j)←rStep5:repeatStep6:

P(1)←1;P(k)←nStep7:

forj←2tok-1doStep8:P(j)←D(P(j-1))Step9:

repeatStep10:

endFGRAPH第4讲分支限界法回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先（优先队列）的方式搜索解空间树T。由于它们在问题的解空间树T上搜索的方法不同,适合解决的问题也就不同。一般情况下,回溯法的求解目标是找出T中满足约束条件的所有解的方案，而分支限界法的求解目标则是找出满足约束条件的一个最优解，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。图的搜索算法小结回溯与分支限界法第4讲分支限界法相对而言,分支限界算法的解空间比回溯法大得多,因此当内存容量有限时,回溯法成功的可能性更大。

回溯法和分支限界法区别：方法搜索方法数据结构节点存储特性应用回溯深度优先搜索堆栈活节点的所有可行子节点被遍历后才被栈中弹出满足约束条件的所有解的方案分支限界广度优先搜索或者最小消耗优先搜索队列、优先队列每个节点只有一次成为活节点的机会满足约束条件的一个解,或者在某种意义下的最优解第4讲分支限界法采用穷举法、回溯法或分支限界法都可以通过利用当前最