分支限界-第九章算法设计与分析

9.6分支限界法本章学习的主要内容9.6.1分枝限界法的基本思想9.6.2用分枝限界法解0-1背包问题9.6.3用分枝限界法解单源最短路径问题分支限界法的基本思想(1)分支限界法类似回溯法，是一种在问题的解空间树T上搜索问题最优解的算法。分支限界法的基本思想(2)分支限界法是以广度优先的方式搜索解空间树。常见的解空间树包括子集树和排列树。在搜索解空间树时，每一个活结点只有一次机会成为扩展结点。分支限界法的基本思想(3)活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点作为当前扩展结点，并重复上述过程，过程一直持续到找到所需解或活结点表为空。从活结点表中选择下一扩展结点的方式FIFO

将活结点表组织成一个队列，并按队列的先进先出原则选取下一个结点作为当前扩展结点。优先FIFO

将活结点表组织成一个优先队列，并按优先级选取优先级最高的下一个结点作为当前扩展结点。返回考虑0-1背包的一个实例每个背包的重量W=[16,15,15]每个背包的价值V=[45,25,25]背包容量,C=30解空间的二叉树表示C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510每个背包的重量W=[16,15,15]每个背包的价值V=[45,25,25]背包容量,C=30活节点表组织成FIFO的分支限界法C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510A:0活节点表每个背包的重量W=[16,15,15]每个背包的价值V=[45,25,25]背包容量,C=30FIFO分支限界法C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510B:45C:0每个背包的重量W=[16,15,15]每个背包的价值V=[45,25,25]背包容量,C=30FIFO分支限界法C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510E:45C:0每个背包的重量W=[16,15,15]每个背包的价值V=[45,25,25]背包容量,C=30FIFO分支限界法C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510E:45F:25G:0每个背包的重量W=[16,15,15]每个背包的价值V=[45,25,25]背包容量,C=30FIFO分支限界法C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510F:25G:0叶K:45可行解每个背包的重量W=[16,15,15]每个背包的价值V=[45,25,25]背包容量,C=30FIFO分支限界法C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510G:0叶K:45叶L:50叶M:25每个背包的重量W=[16,15,15]每个背包的价值V=[45,25,25]背包容量,C=30FIFO分支限界法C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510叶K:45叶L:50叶M:25叶N:25叶O:0活节点表为空算法结束活节点表组织成优先FIFO的分支限界法C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510A:0每个背包的重量W=[16,15,15]每个背包的价值V=[45,25,25]背包容量,C=30优先FIFO分支限界法C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510B:45C:0每个背包的重量W=[16,15,15]每个背包的价值V=[45,25,25]背包容量,C=30优先FIFO分支限界法C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510E:45C:0每个背包的重量W=[16,15,15]每个背包的价值V=[45,25,25]背包容量,C=30优先FIFO分支限界法C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510C:0叶K:45每个背包的重量W=[16,15,15]每个背包的价值V=[45,25,25]背包容量,C=30优先FIFO分支限界法C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510F:25G:0叶K:45每个背包的重量W=[16,15,15]每个背包的价值V=[45,25,25]背包容量,C=30优先FIFO分支限界法C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510G:0叶K:45叶L:50叶M:25每个背包的重量W=[16,15,15]每个背包的价值V=[45,25,25]背包容量,C=30优先FIFO分支限界法C:0A:001B:4501D:01HIG:001N:25O:0E:4501J:K:45F:2501L:50M:2510叶K:25叶L:50叶M:25叶N:25叶O:0活节点表为空算法结束总结FIFO:活结点表形成一个队列，按队列的先进先出原则选取下一个结点作为当前扩展结点。优先FIFO活结点表形成一个优先队列，按优先级选取优先级最高的下一个结点作为当前扩展结点。优先FIFO含有贪心的思想优先队列的数据结构-堆为什么要用极大堆(或极小堆)来表示活结点表的优先队列？原因：每次都要从优先队列选出最大值(或最小值)？从n个数里找到最大值(或最小值)的代价为O(n)如果把这n个数组织成极大堆(或极小堆)，那么仅仅是第一次找到最大值(或最小值)的代价为O(n)，因为要建堆。堆一旦建立成功，以后每次找到最大值(或最小值)的代价为O(log(n))优先队列的数据结构-堆(1)我们用一个极大堆(或极小堆)来表示活结点表的优先队列。极小堆的定义：极小堆是一个关键码序列{K1，K2，…，Kn}，它具有如下特性：KiK2i；KiK2i+1；(i=1,2,…,n/2)

xxxx=3.3x=3x=4极大堆的定义：极大堆是一个关键码序列{K1，K2，…，Kn}，它具有如下特性：KiK2i；KiK2i+1；(i=1,2,…,n/2)优先队列的数据结构-堆(2)堆实际上是一棵二叉树结点的层次序列，此二叉树的每个结点对应于一个关键码。此二叉树最多只有最下面的2层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上。极小堆的二叉树表示K1:5K2:23K7:71K6:72K5:94K4:68K3:16K8:73K1K2K1K3K2K4K2K5K3K6K3K7K4K8K4K9K9:96堆的存储用一维数组存储堆。K1K2K3K4K5K6K7K8计算堆中关键字的父亲、子女的索引函数计算堆中第i个关键字的父亲索引PARENT(i){returni/2}计算堆中第i个关键字的左子女索引LEFT(i){return2i}计算堆中第i个关键字的右子女索引RIGHTT(i){return2i+1}堆的插入操作-向堆中增加一个关键字Insert(A,key)heap_sizeheap_size+1iheap_sizeA[i]keyWhilei>1andA[PARENT(i)]>A[i]DOexchangeA[i]A[PARENT(i)]iPARENT(i)Endwhile堆的二叉树表示-插入K9:2K1:5K2:23K7:71K6:72K5:94K4:68K3:16K8:73堆的二叉树表示-插入K9:2K1:5K2:23K7:71K6:72K5:94K4:68K3:16K8:73K9:2堆的二叉树表示K1:2K2:5K7:71K6:72K5:94K4:23K3:16K8:73K9:68堆的删除操作-删除堆顶关键字DeleteMin(A)Ifheap_size<1thenerror“heapunderflow”minA[1]A[1]A[heap_size]heap-sizeheap_size–1Build-MinHeap(A,1)//重新建堆堆的二叉树表示K1:5K2:23K7:71K6:72K5:94K4:68K3:16K8:73堆的二叉树表示K2:23K7:71K6:72K5:94K4:68K3:16K8:73堆的二叉树表示K2:23K7:71K6:72K5:94K4:68K3:16K1:73堆的二叉树表示K2:23K7:71K6:72K5:94K4:68K3:73K1:16堆的二叉树表示K2:23K7:73K6:72K5:94K4:68K3:71K1:16建堆-Build-MinHeapBuild-MinHeap(A,i)//以结点i为根建堆lLEFT(i)rRIGHT(i)Iflheap_sizeandA[l]<A[i]ThensmallestlELSEsmallestiIfrheap_sizeandA[r]<A[smallest]ThensmallestrIfsmallestiThenexchangeA[i]A[smallest]Build-MinHeap(A,smallest)Fori=n/2to1Do

Build-MinHeap(A,i)EndFor建堆的例子用一维数组存储堆。9

7

8

11

6

7

2

5建堆的例子-Build-MinHeap(A,4)K1:9K2:7K7:2K6:7K5:6K4:11K3:8K8:5n/2=4,smallest=8建堆的例子-Build-MinHeap(A,4)K1:9K2:7K7:2K6:7K5:6K4:5K3:8K8:11n/2=4,smallest=8建堆的例子-Build-MinHeap(A,3)K1:9K2:7K7:2K6:7K5:6K4:5K3:8K8:11n/2=4,smallest=7建堆的例子-Build-MinHeap(A,3)K1:9K2:7K7:8K6:7K5:6K4:5K3:2K8:11n/2=4,smallest=7建堆的例子-Build-MinHeap(A,2)K1:9K2:7K7:8K6:7K5:6K4:5K3:2K8:11n/2=4,smallest=4建堆的例子-Build-MinHeap(A,2)K1:9K2:5K7:8K6:7K5:6K4:7K3:2K8:11n/2=4,smallest=4建堆的例子-Build-MinHeap(A,smallest)K1:9K2:5K7:8K6:7K5:6K4:7K3:2K8:11n/2=4,smallest=4建堆的例子-Build-MinHeap(A,1)K1:9K2:5K7:8K6:7K5:6K4:7K3:2K8:11n/2=4,smallest=3建堆的例子-Build-MinHeap(A,1)K1:2K2:5K7:8K6:7K5:6K4:7K3:9K8:11n/2=4,smallest=3建堆的例子-Build-MinHeap(A,smallest)K1:2K2:5K7:8K6:7K5:6K4:7K3:9K8:11n/2=4,smallest=3建堆的例子-Build-MinHeap(A,3)K1:2K2:5K7:8K6:7K5:6K4:7K3:9K8:11n/2=4,smallest=6建堆的例子-Build-MinHeap(A,3)K1:2K2:5K7:8K6:9K5:6K4:7K3:7K8:11n/2=4,smallest=6返回单源最短路径-求源点1到其它顶点的最短路径V1V3V24610203054把图转换成解空间树-队列式v1:0V1:0Dist[1]=0Dist[2]=30Dist[3]=6Dist[4]=4把图转换成解空间树-队列式V2:30304v1:0v3:6v4:46V2:30V3:6V4:4Dist[1]=0Dist[2]=30Dist[3]=6Dist[4]=4把图转换成解空间树-队列式V2:30304v1:0v3:6v4:46V3:6V4:4105v3:35V4:40Dist[1]=0Dist[2]=30Dist[3]=6Dist[4]=4E---V2:30E.length=30E.length+c[E.i][j]=V3:35>Dist[3]=6E.length+c[E.i][j]=V4:40>Dist[4]=4把图转换成解空间树-队列式V2:30304v1:0v3:6v4:46V4:455v3:35V4:40Dist[1]=0Dist[2]=11<30Dist[3]=6Dist[4]=4205V2:11V4:26E---V3:6E.length=6E.length+c[E.i][j]=V2:11<Dist[2]=30E.length+c[E.i][j]=V4:26>Dist[4]=4V2:11把图转换成解空间树-队列式V2:30304v1:0v3:6v4:4655v3:35V4:40Dist[1]=0Dist[2]=11Dist[3]=6Dist[4]=4205V2:11V4:26E---V4:4E.length=4E.length+c[E.i][j]=V2:14>Dist[2]=11E.length+c[E.i][j]=V3:24>Dist[3]=6V2:112010V2:14V3:24把图转换成解空间树-队列式V2:30304v1:0v3:6v4:4655v3:35V4:40Dist[1]=0Dist[2]=11Dist[3]=6Dist[4]=4205V2:11V4:26E---V2:11E.length=11E.length+c[E.i][j]=V4:21>Dist[4]=4205V2:14V3:24V4:2110//定义队列容量为1000,活节点表

Queue<QueueNode<Type>>H(1000);//定义源为初始扩展结点

QueueNode<Type>E; E.i=v;E.length=0;dist[v]=0;H.Insert(E); //搜索问题的解空间

while(H.Size()>0){H.Delete(E);if(dist[E.i]>E.length){ for(intj=1;j<=n;j++){ if((c[E.i][j]<inf)&&(E.length+c[E.i][j]<dist[j])){ //从顶点i到顶点j可达,且满足控制约束

dist[j]=E.length+c[E.i][j]; prev[j]=E.i; //把顶点E.i的子女j加入活结点优先队列

QueueNode<Type>N; N.i=j; N.length=dist[j]; H.Insert(N); }//endif }//endfor}//endif}//endwhile把图转换成解空间树-优先队列式v1:0V1:0Dist[1]=0Dist[2]=30Dist[3]=6Dist[4]=4V2:30304v1:0v3:6v4:46V2:30V3:6V4:4Dist[1]=0Dist[2]=30Dist[3]=6Dist[4]=4把图转换成解空间树-优先队列式V2:30304v1:0v3:6v4:46V2:30V3:62010v2:14V3:24Dist[1]=0Dist[2]=14<30Dist[3]=6Dist[4]=4E---V4:4E.length=4E.length+c[E.i][j]=V2:14<Dist[2]=30E.length+c[E.i][j]=V3:24>Dist[4]=6V2:14把图转换成解空间树-优先队列式V2:30304v1:0v3:6v4:46V2:302010v2:14V3:24Dist[1]=0Dist[2]=11<14Dist[3]=6Dist[4]=4E---V3:6E.length=6E.length+c[E.i][j]=V2:11<Dist[2]=14E.length+c[E.i][j]=V4:26>Dist[4]=4V2:14205V2:11V4:26V2:11把图转换成解空间树-优先队列式V2:30304v1:0v3:6v4:46V2:302010v2:14V3:24Dist[1]=0Dist[2]=11<14Dist[3]=6Dist[4]=4E---V2:11E.length=11E.length+c[E.i][j]=V4:21>Dist[4]=4V2:14205V2:11V4:26V4:2110把图转换成解空间树-优先队列式V2:30304v1:0v3:6v4:46V2:302010v2:14V3:24Dist[1]=0Dist[2]=11Dist[3]=6Dist[4]=4E---V2:14E.length=14E.i=2E.Length>Dist[E.i]=11205V2:11V4:26V4:2110把图转换成解空间树-优先队列式V2:30304v1:0v3:6v4:462010v2:14V3:24Dist[1]=0Dist[2]=11Dist[3]=6Dist[4]=4E---V2:30E.length=14E.i=2E.Length>Dist[E.i]=11205V2:11V4:26