算法分析与设计分枝限界法.ppt

《算法分析与设计分枝限界法.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计分枝限界法.ppt（96页珍藏版）》请在三一办公上搜索。

1、第七章 分枝-限界法,2,上章知识回顾,问题状态解状态状态空间答案状态,状态空间树活结点E-结点死结点,通过对n-皇后问题的分析，复习以上概念和回溯法,3,n-皇后问题描述,将n个皇后放置在一个nn的棋盘上，要求没有两个皇后可以互相攻击。攻击的定义：两个皇后出现在同一行、或同一列、或者同一条斜线上都视为出现了攻击。,4,8-皇后问题的一个解,该解的8元组表示:(4,6,8,2,7,1,3,5),5,n-皇后问题,用n-元组(x1,x2,xn)表示棋盘上皇后的位置状态下标表示皇后i(i=1,2,n)xi表示放置皇后i所在的列号显式约束条件：每个xi只从集合Si=1,2,n取值满足显式约束的所有元

2、组确定一个可能的解空间 解空间由nn个n-元组组成隐式约束条件没有两个xi可以相同，而且没有两个皇后可以在同一条斜线上 由前者得，所有解都是n-元组(1,2,n)的置换，因此，解空间缩小为 n！个元组,6,4-皇后问题解空间的树结构,结点按深度优先检索编号叶子结点有4！24个,7,解空间树结构的术语,树中每个结点确定求解问题的一个问题状态(problem state)由根结点到其它结点的所有路径确定了这个问题的状态空间(state space)解状态(solution states)是这样一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组（满足显式约束）答案状态(s

3、olution states)是这样一些解状态S，由根到S的路径确定了问题的一个解（满足隐式约束）解空间的树结构为状态空间树(state space tree),8,利用状态空间树解题,1 设想状态空间树2 生成问题状态3 确定问题状态中哪些是解状态4 哪些解状态是答案状态生成问题状态 构造状态空间树,9,状态空间树术语,活结点：自己已经生成而其所有的儿子结点还没有全部生成的结点。E-结点（正在扩展的结点）：当前正在生成其儿子结点的活结点。死结点：不再进一步扩展或者其儿子结点已全部生成的生成结点。,10,构造状态空间树的两个方法,回溯法当前E-结点R，生成一个新的儿子C，则C就变成一个新的E-

4、结点，对子树C完全检测后，R结点再次成为E-结点。分枝-限界方法一个E-结点一直保持到变成死结点为止。限界函数以上两种方法都使用限界函数杀死还没有全部生成其儿子结点的那些活结点。,11,4-皇后问题的限界函数,如果(x1,x2,xi)是到当前E-结点的路径，那么具有父-子标记xi+1的所有儿子结点是一些这样的结点，它们使得(x1,x2,xi+1)表示没有两个皇后正在互相攻击的一种棋盘格局。,12,4-皇后问题回溯法vs状态空间树,结点按深度优先检索编号叶子结点有4！24个,13,4-皇后问题回溯期间的生成树,14,分枝限界法,在生成当前E-结点全部儿子之后再生成其它活结点的儿子，并且，用限界函

5、数帮助避免生成不包含答案结点子树的状态空间FIFO检索：活结点表采用队LIFO检索：活结点表采用栈,15,FIFO分枝限界法例7.1（4-皇后问题）,16,4-皇后问题回溯 vs FIFO分枝-限界,回溯 Win！,17,LC-检索（Least Cost）,分枝-限界失败的原因对下一个E-结点的选择规则过于死板。如何解决？排序，让答案结点排在前面！寻找一种“有智力”的排序函数C()，该函数能够让答案结点尽早生成。排序的标准下一个E-结点应当是生成答案结点花费成本最小的结点，因此C()又称作结点成本函数。LC：Least Cost,18,分枝-限界策略的种类,根据对状态空间树中结点检索次序的不同

6、，可将分枝-限界的设计策略分为：FIFO检索，活结点采用一张先进先出表LIFO检索，活结点采用一张先进后出表LC分枝-限界检索，活结点采用一张易于操作的线性表。,19,LC-检索（结点成本的两个标准）,一、在生成一个答案结点之前，子树X需要生成的结点数。二、在子树X中离X最近的那个答案结点到X的路径长度。以图7.1为例节点1、18和34、29和35、30和38的代价分别是4，3，2，1其他2，3，4级上的点代价应分别大于3，2，1生成结点（12 18 34 5019 24 2930 3231）,20,LC-检索（结点成本函数）,C()定义如果X是答案结点，则C(X)是由状态空间树的根结点到X的

7、成本（即花费的代价，可以是级数、计算复杂度等）。如果X不是答案结点且子树X不包含任何答案结点，则C(X)。如果X不是答案结点但子树X包含答案结点，则C(X)等于子树X中具有最小成本的答案结点的成本。,21,LC-检索（成本估计函数）,从前面的两个成本度量标准看，计算C()的工作量与原问题的解具有相同复杂度。这是因为计算一个结点的代价通常要检索包含一个答案结点的子树才能确定，而这正是解决此问题所要作的检索工作，因此要得到精确的成本函数一般是不现实的。因此需要成本估计函数g(X)出现的新问题仅利用g(X)会导致算法偏向纵深检查，无法有效处理下面这种情况：即g(W)g(Z)，但Z比W更接近答案结点,

8、22,LC分枝-限界检索,为使算法不过分偏向于纵深检查，需改进成本估计函数，使其不只考虑结点X到一个答案结点的估计成本，还应考虑根节点到结点X的成本。c(X)f(h(X)+g(X)h(X)为根结点到结点X的成本 g(X)是由X到达一个答案结点所需做的附加工作的估计函数LC-限界检索：选择c()值最小的活结点作为下一个E-结点BFS：g(X)0；f(h(X)X的级数D-Search：f(h(X)0；每当Y是X的一个儿子时，总有g(X)=g(Y)。LC分枝-限界检索：伴之有限界函数的LC-检索,23,例：15-谜问题,a,b,c,问题描述：在一个分成16格的方形棋盘上，放有15块编了号码的牌（见下

9、图）。对这些牌给定一种初始排列如图7.2(a)，要求通过一系列的合法移动将这一初始排列转换成图7.2(b)所示的那样的目标排列。,图7.2 15-谜的排列图,24,例：15-谜问题,图7.2(a)所示的初始排列有四种可能的移动，可以将编号为2,3,5或6的任何一块牌移到空格。在作了这次移动之后，可作其他的移动。每移动一次，就产生一种新的排列。这些排列称为这个谜问题的状态。初始排列和目标排列叫做初始状态和目标状态。若由初始状态到某状态存在一系列合法的移动，则称该状态可由初始状态到达。一种初始状态的状态空间由所有可从初始状态到达的状态构成。,25,例：15-谜问题,可以看出棋盘上这些牌有16！种不

10、同的排列，所以这个问题的状态空间是相当庞大的。有必要在具体求解问题之前判定目标状态是否在这个初始状态的状态空间中。对此有一个非常简单的判定方法：我们先给棋盘的方格位置编上116的号码。位置i 是在图7.2(b)所示的目标排列中放i 号牌的方格位置，位置16是空格的位置。假设POSITION(i)是编号为i的那块牌在初始状态下的位置号，1 i 16；POSITION(16)表示空格的位置。,26,对于任意一种状态，设LESS(i)是使牌j 小于牌i，且使POSITION(j)POSITION(i)的数目。例如，对于图7.2(a)所示的状态，有LESS(1)=0，LESS(4)=1和LESS(12

11、)=6。在初始状态下，如果空格在图7.2的阴影位置中的某一格处，则令X=1；否则X=0。于是有定理7.1：当且仅当LESS(i)+X（1 i16)是偶数时，图7.2(b)所示的目标状态可由此初始状态到达。可以用定理7.1来判定目标状态是否在初始状态的状态空间中。若在，就可以着手确定导致目标状态的一系列移动。,例：15-谜问题,27,为了实现这一检索，可以将此状态空间构造成一棵树。在这棵树中，每一个结点的儿子表示由状态X通过一次合法的移动可到达的状态。不难看出，移动牌与移动空格实质上是等效的，而且在作实际移动时，因此以后都将父状态到子状态的一次转换看成是空格的一次合法移动。,例：15-谜问题,2

12、8,15-谜问题(宽度优先),29,15-谜问题(宽度优先前十步),30,例：15-谜问题,按照FIFO检索方法不管开始格局如何，总是采取由根开始的那条最左路径，因而检索是呆板而盲目的。我们所期望的是：有一个具有一定“智能”的检索方法。这就需给状态空间树的每个结点X赋予一定的成本值c(X)，可将由根出发到最近目标结点路径上的每个结点X赋予这条路径长度作为他们的成本值。切合实际的做法是：给出一个便于计算成本估计值的函数c(X)=f(X)+g(X)，其中f(X)是由根到结点X的路径长度,31,例：15-谜问题,g(X)是以X为根的子树中由X到目标状态的一条最短路径长度的估计值。因此，g(X)至少应

13、是能把状态X转换成目标状态所需的最小移动数。一种可能的选择是：g(X)=不在其目标位置的非空白牌数目使用c(X)图7.3(a)的LC-检索将结点1作为E-结点的开始。结点1在生成它的儿子结点2,3,4和5之后死去。变成E-结点的下一个结点是具有最小c(X)的活结点。,32,15-谜问题（使用C(X)的LC-检索）,33,例：15-谜问题,c(2)=1+4，c(3)=1+4，c(4)=1+2，c(5)=1+4，所以结点4成为E-结点。生成结点4的儿子结点，此时的活结点是2,3,5,10,11,12。c(10)=2+1，c(11)=2+3，c(12)=2+3，具有最小c值的活结点10成为下一个E-

14、结点。接着生成结点22和23，结点23被判定是目标结点，此次检索结束。,34,分支限界法的基本思想,分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。,35,分支限界法的基本思想,在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入到活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为

15、空时为止。,36,LC-检索的抽象化控制,设T是一棵状态空间树，C(.)是T中结点的成本函数。如果，C(X)是其根为X的子树中任一答案结点的最小成本，则C(T)是T中最小成本答案结点的成本。由于函数C(.)不容易实现，所以使用一个对C(.)估值的启发性函数C(.)来代替。这个启发函数应易于计算并具有如下性质：如果X是一个答案结点或者是一个叶结点，则C(X)=C(X)。,37,算法7.1 LC-检索,Procedure LC(T,c)if T是答案结点 then 输出T;return end ifET/E-结点/将活结点表初始化为空loopfor E 的每个儿子X doif X是答案结点 the

16、n 输出从X到T的那条路径return;end ifcall ADD(X)/X是新的活结点/PARENT(X)E repeatif 不在有活结点 then print(no answer node)stop;end ifcall LEAST(E)repeatEnd LC,通常把这个活结点表作成一个min-堆,38,LC-检索说明,只有当有限状态空间树下才能保证LC终止。对于无限状态空间树，在其至少有一个答案结点并假定对成本估计函数C能作出“适当”的选择时，才能保证算法LC终止。实际上LC算法与状态空间树的宽度优先检索算法和D-检索算法基本相同。,39,LC-检索的抽象化控制（vs.BFS,D-

17、Search）,LC算法与BFS及D-Search基本相同活结点表采用队列 vs BFS活节点表采用栈 vs D-Search不同：活结点表的构造，即下一个E-结点的选择规则不同。,40,LC-检索的特性,LC是否一定能找到具有最小成本的答案结点呢？考虑下图所示的状态空间树，方形叶子结点是答案结点。每个结点有两个数，上面的是C的值，下面的是C的值。,41,LC-检索的特性,定理7.2 在有限状态空间树T中，对于每一个结点X，令c(X)是c(X)的估计值且具有以下性质：对于每一个结点Y、Z，当且仅当c(Y)c(Z)时有c(Y)c(Z)。那么在使c()作为c()的估计值时，算法LC到达一个最小的成

18、本答案结点且终止。证明（略）,42,LC-检索的特性,要得到满足定理7.2的要求又易于计算的C(.)通常是不可能的。一般情况下，却不难得到这样的C(.)：C(X)C(X)。如果对于每一个结点X有c(X)c(X)且对于答案结点X有c(X)=c(X)，只要对LC稍作修改就可得到一个在达到某个最小成本答案结点时终止的检索算法LC1。,43,算法7.2 找最小成本答案结点的LC-检索,procedure LC1(T,c)ET置活结点表为空loopif E是答案结点 then 输出从E到T的路径 return end iffor E的每一个儿子X docall ADD(X);PARENT(X)Erepe

19、atif 不再有活结点 then print(No answer node)stopend ifcall LEAST(E)repeatEnd LC1,44,定理7.3 令C(.)是满足如下条件的函数，在状态空间树T中，对于每一个结点X，有C(X)C(X),而对于T中的每一个答案结点X，有C(X)=C(X)。如果算法在第5行终止，则所找到的答案结点是具有最成本的答案结点。,证明：此时，E-结点E是答案结点，对于活结点表中的每一个结点L，C(E)C(L)。由假设C(E)=C(E)且对于一每个活结点L，C(L)C(L)。因此C(E)C(L)，从而E是一个最小成本答案结点。,45,分枝-限界算法,检索

20、状态空间树的各种分枝-限界方法都是在生成当前E-结点的所有儿子之后再将另一个结点变成E-结点。假定每一个答案结点X有一个与其相联系的C(X)，并且假定会找到最小成本的答案结点。使用一个使得 C(X)C(X)的成本估计函数 C(.)来给出可由任一结点X得出的解的下界。采用下界函数使算法具有一定的智能，减少了盲目性。另外还可以通过设置最小成本的上界使算法进一步加速。,46,分枝-限界算法,如果U是最小成本解的上界，则具有 C(X)U的所有活结点X可以被杀死，这是因为由X可以到达的所有答案结点有U C(X)C(X)。在已经到达一个具有成本U的答案结点的情况下，那些有U C(X)的所有活结点都可以被杀

21、死。U的初始值可以用某种启发性方法得到，也可以置为，每当找到一个新的答案结点就可以修改U的值。,47,实例：带限期的作业排序问题,一般化的带限期的作业排序问题假定n个作业和一台处理机作业i对应一个三元组（pi,di,ti）ti表示作业i需要的单位处理时间di表示完成期限pi表示期限内未完成招致的罚款目标：从n个作业选取子集J，要求J中所有作业都能在各自期限内完成并且使得不在J中的作业招致的罚款总额最小。,48,N=4;(p1,d1,t1)=(5,1,1);(p2,d2,t2)=(10,3,2);(p3,d3,t3)=(6,2,1);(p4,d4,t4)=(3,1,1);,图7.7 大小可变的元

22、组表示对应的状态空间树,49,图7.8 大小固定的元组表示对应的状态空间树,N=4;(p1,d1,t1)=(5,1,1);(p2,d2,t2)=(10,3,2);(p3,d3,t3)=(6,2,1);(p4,d4,t4)=(3,1,1);,50,实例：带限期的作业排序问题,图7.7中可将成本函数C(.)定义为，对于圆形结点X，C(X)是根为X的子树中结点的最小罚款；对于方形结点，C(X)=。设SX是在结点X对J所选择的作业的子集。如果m=maxi|i 属于SX，则C(X)等于作业数i 小于m的所有罚款累加和。C(1)=0；C(2)=0；C(3)=5；C(4)=15；C(5)=21；,51,实例

23、：带限期的作业排序问题,根据以上定义，有C(X)C(X)。一个简单上界U(X)可以定义为不在SX中的所有作业的罚款的和。注意，对带限期的作业排序问题而言，U(X)是对应结点X的解SX的成本值。,52,实例：带限期的作业排序问题,作业排序问题的一个FIFO分枝-限界算法开始时可以将最小成本答案结点的成本上界定义为。假定使用图7.7大小可变的元组表示，开始时结点1作为E-结点，于是依次生成结点2,3,4和5。由于u(2)=19,u(3)=14,u(4)=18,u(5)=21,因此在生成结点3时，就将上界U修改为14。因为C(4)和C(5)大于U，所以结点4和5被杀死。,53,实例：带限期的作业排序

24、问题,结点2成为下一个E-结点，生成它的儿子6,7,8。u(6)=9，因此U修改为9；C(7)=10U，所以结点7被杀死；结点8是不可行结点，也被杀死。结点3成为E-结点，生成其儿子结点9和10。u(9)=8，因此U变成8；C(10)=11U，所以10被杀死。结点9只有一个儿子且不可行，因此结点9是最小成本答案结点，其成本值为8。,54,上界U的确定,在实现分枝限界算法时，每修改一次U，在活结点队中那些c(X)U或者在U是已找到的一个成本值情况下有c(X)U的结点应被杀死。必须识别出这个修改了的U是一个已找到的解的成本还是一个不是解成本的单纯上界。这个单纯上界U或者是还没找到一个答案结点，U由

25、处理一可行结点时修改而得；或者是虽然找到一答案结点，但它的成本值大于它的上界值，说明这答案结点的子孙中还有成本更小的答案结点，U取这个上界值。算法实现时，可引进一个很小的正常数来进行这一识别。此要取得足够小，使得对于任意两个可行结点X和Y，如果u(X)u(Y),则u(X)u(X)+u(Y)。当U是由一答案结点的成本值而得时，U就是这个成本值，而当U是由一单纯上界得到时，U等于此上界值u(X)+。,55,找最小成本答案结点的FIFO分枝-限界方法,如何处理c(X)=U的情况为什么要处理？如何处理？引进，当u(X)u(Y)时，u(X)u(X)+u(Y)。在算法中，比较c(X)与U的时候，可以对U作

26、以下处理：当U是成本值，则不变当U由一单纯上界得出，U=u(X)+,56,找最小成本答案结点的FIFO分枝-限界算法,procedure FIFOBB(T,c,u,cost)/为找出最小成本结点检索T。假定T至少包含一个解结点且c(X)c(X)u(X)E=T;PARENT(E)=0if T是解结点 then U=min(cost(T),u(T)+);ans=T else U=u(T)+;ans=0endif将队置初值为空loop for E的每个儿子X do if c(X)0 do print(ans);ans=PARENT(ans)repeat return endif call DELET

27、EQ(X)if c(X)U then exit repeatrepeatend LCBB,57,找最小成本结点的LC分枝限界算法,procedure LCBB(T,c,u,cost)/为找出最小成本结点检索T。假定T至少包含一个解结点且c(X)c(X)u(X)E=T;PARENT(E)=0if T是解结点 then U=min(cost(T),u(T)+);ans=T else U=u(T)+;ans=0endif将活结点表初始化为空loop for E的每个儿子X do if c(X)0 do print(ans)ans=PARENT(ans)repeat return endif call

28、 LEAST(E)repeatend LCBB,58,效率分析,上下界函数的选择是决定分枝-限界算法效率的主要因素。对U选择一个更好的初值是否能减少生成的结点数？（否，根据定理7.4）扩展一些C(.)U的结点是否能减少所生成的结点数？（否，根据定理7.5）假定有两个成本估计函数C1(.)和C2(.)，对于状态空间树的每一个结点X，若有C1(X)C2(X)C(X)，则称C2(.)比C1(.)好。是否用较好的成本估计函数C2(.)比用C1(.)生成的结点数要少呢？（否，根据定理7.6和定理7.7）,59,定理7.4,设U1和U2是状态空间树T中最小成本答案结点的两个初始上界且U1U2。那么FIFO

29、，LIFO和LC分枝-限界算法在以U1为上界初始值时所生成的结点数不会多于以U2为上界初始值时所生成的结点数。,60,定理7.5,设U是状态空间树T最小成本答案结点的当前上界。由FIFO，LIFO和LC分枝-限界算法所生成的结点数不因扩展C(X)U的结点X而减少。,61,定理7.6,在FIFO和LIFO分枝-限界算法中使用一个更好的成本估计函数C(.)不会增加其生成的结点数。,62,定理7.7,在LC分枝-限界算法中使用一个更好的成本估计函数C(.)可能增加所生成的结点的个数。,63,定理7.7的证明,如上图，所有叶子结点都是答案结点，叶结点下面的数是其成本值，从这些值中可以得出C(1)=C(

30、3)=3，C(2)=4。结点1，2和3外面的数是对应的C1、C2（上、下）值显然C2是比C1更好的成本估计函数。如果使用C2，由于C2(2)=C2(3)，因此结点2会在结点3之前变成E-结点,于是所有9个结点都将被生成，而使用C1将不会生成结点4，5和6。,64,7.2 0/1背包问题,用函数-pixi来代替目标函数pixi，从而将背包问题由一个极大问题转换成一个极小化问题。本节只计论在大小固定的元组表示下如何求解0/1背包问题。状态空间树中那些pixiM(1 i n)的装包方案的每一个叶结点是答案结点，其它的叶结点均不可行。,65,上界函数,算法7.5 背包问题的上界函数u(.)Proced

31、ure UBOUND(p,w,k,M)global W(1:n),P(1:n);integer i,k,nb=p;c=wfor i=k+1 to n do if c+w(i)M then c=c+W(i);b=b-P(i)endifrepeatreturn(b)end UBOUND,66,估价函数C(X)的定义,令C(X)=-BOUND，其中BOUND函数是算法6.11（见教材P210）。显然有C(x)C(X)u(X)。,67,7.2.1 LC分枝-限界求解,例7.2 LCBB考虑背包问题：n=4(p1,p2,p3,p4)=(10,10,12,18)(w1,w2,w3,w4)=(2,4,6,9

32、)M=15,68,例7.2 LCBB考虑背包问题：n=4(p1,p2,p3,p4)=(10,10,12,18)(w1,w2,w3,w4)=(2,4,6,9)M=15,69,例7.2 LCBB,在找到答案结点8的情况下，无论哪一个结点变成下一个E-结点都要有C(E)U，因此，终止检索，这时打印出值-38和路径8,7,4,2,1，算法结束。要指出的是，由路径8,7,4,2,1并不能得出由哪些物品装入背包才得到-pixi=U，即看不出这些Xi的取值情况。因此在实现过程LCBB时应保留一些能反映Xi取值情况的附加信息。,70,例7.2 LCBB,一种解决办法是每一个结点增设一个位信息段TAG。若该结点

33、为左孩子，则TAG(X)=1；若该结点为右孩子，则TAG(X)=0。于是，对此问题将有：TAG(2)=TAG(4)=TAG(6)=TAG(8)=1；TAG(3)=TAG(5)=TAG(7)=TAG(9)=0。,71,LCBB求解背包问题分析,状态空间树中结点的结构如何生成一给定结点的儿子如何识别答案结点如何表示活结点表,72,状态空间树中结点的结构,PARENT父结点链接指针LEVEL状态空间树中的级数TAGXi的取值CU背包的剩余空间PE已装入物品的效益值的和UBc(X),73,如何生成一给定结点的儿子,左儿子生成PARENT(Y)=XLEVEL(Y)=LEVEL(X)+1CU(Y)=CU(

34、X)WLEVEL(X)PE(Y)=PE(X)+P LEVEL(X)TAG=1UB(Y)=UB(X),74,如何识别答案结点,当且仅当LEVEL(X)=n 1X是答案结点,75,如何表示活结点表,Min-堆测试活结点表是否为空常量时间加结点到活结点表 log(n)删除最小UB值的结点 log(n),76,计算上界和下界的算法,line procedure LUBOUND(P,W,rw,cp,N,k,LBB,UBB)1 LBB cp;c rw;2 for i k to N do 3 if c=W(j)then c c-W(j)6 LBB LBB+P(j)7 endif8 repeat9 retur

35、n10 endif11 c c-W(i);LBB LBB+P(i)12 repeat13 UBB LBB14 end LUBOUND,77,生成一个新结点,line procedure NEWNODE(par,lev,t,cap,prof,ub)1 call GETNODE(I)2 PARENT(I)par；LEVEL(i)lev；TAG(I)t3 CU(I)cap；PE(I)prof；UB(I)ub4 call ADD(I)5 end NEWNODE,78,背包问题的LC分枝-限界算法,line procedure LCKNAP(P,W,M,N,)/大小固定元组表示状态空间树/假设P(1)/

36、W(1)=P(2)/W(2)=P(N)/W(N)real P(N),W(N),M,L,LBB,UBB,cap,prof int ANS,X,N1 call INIT2 call GETNODE(E)3 PARENT(E)0;LEVEL(e)1;CU(E)M;PE(E)04 call LUBOUND(P,W,M,N,0,1,LBB,UBB)5 L LBB-;UB(E)UBB 6 loop7 i LEVEL(E);cap CU(E);prof PE(E),79,背包问题的LC分枝-限界算法,8 case9:i=N+1:10 if profL then L prof;ANS E11 endif12:

37、else:13 if cap=W(i)then14 call NEWNODE(E,i+1,1,cap-W(i),prof+P(1)UB(E)15 endif16 call LUBOUND(P,W,cap,prof,N,i+1,LBB,UBB)17 if UBBL then18 call NEWNODE(E,i+1,0,cap,prof,UBB)19 L max(L,LBB-)20 endif21 endcase,80,背包问题的LC分枝-限界算法,22 if 不再有活结点 then exit endif23 call LARGEST(E)24 until UB(E)=L repeat25 ca

38、ll FINISH(L,ANS,N)26 end LCKNAP,81,7.2.2 FIFO分枝-限界求解,例7.3 FIFOBB考虑背包问题：n=4(p1,p2,p3,p4)=(10,10,12,18)(w1,w2,w3,w4)=(2,4,6,9)M=15,82,例7.3 FIFOBB考虑背包问题：n=4(p1,p2,p3,p4)=(10,10,12,18)(w1,w2,w3,w4)=(2,4,6,9)M=15,83,背包问题FIFO分枝-限界算法,line procedure FIFOKNAP(P,W,M,N)/大小固定元组表示状态空间树/假设P(1)/W(1)=P(2)/W(2)=P(N)

39、/W(N)real P(N),W(N),M,L,LBB,UBB,E,cap,prof int ANS,X,N1 call INIT;i 12 call LUBOUND(P,W,M,0,N,1,L,UBB)3 call NNODE(0,0,M,0,UBB)4 call ADDQ(#)5 while i=N do6 loop7 call DELETEQ(E),84,背包问题FIFO分枝-限界算法,8 case9:E=#:exit10:UB(E)=L:11 cap CU(E);prof PE(E)12 if cap=W(i)then13 call NNODE(E,1,cap-W(i),prof+P(

40、i),UB(E)14 endif15 call LUBOUND(P,W,cap,prof,N,i+1,LBB,UBB)16 if UBB=L then17 call NNODE(E,0,cap,prof,UBB)18 L max(L,LBB)19 endif20 endcase21 repeat22 call ADDQ(#)23 i i+124 repeat25 ANS PE(X)=L的活结点X26 call FINISH(L,ANS,N)27 end FIFOKNAP,85,7.3 货郎担问题,问题描述：某售货员要到若干个村庄售货，各村庄之间的路程是己知的，为了提高效率，售货员决定从所在商店

41、出发，到每个村庄售一次货然后返回商店，问他应选择一条什么路线才能使所走的总路程最短?设G(V,E)是一个具有边成本cij的有向图。G的一条周游路线是包含V中每个结点的一个有向环。周游路线的成本是此路线上所有边的成本之和，货郎担问题(traveling salesperson problem)是求取具有最小成本的周游路线问题。,86,货郎担问题的状态空间树,87,用LC分枝-限界法检索货郎担问题的状态空间树,成本函数C(.)的定义：（1）若X是叶结点，则C(X)为由根到X的路径确定的周游路线成本。（2）若X不是叶结点，子树X中最小成本叶结点的成本。,88,归约矩阵,如果矩阵的一行（列）至少包含一

42、个零且其余无素均非负，则此行（列）称为已归约行（列）。所有行和列均已归约行和列的矩阵称为归约矩阵。可以通过对一行（列）中每个元素都减去同一个常数t（称为约数）将该行（列）变为已归约行（列）。逐行逐列施行归约就可得到原矩阵的归约矩阵。,89,矩阵约数,假设第i行的约数ti，第j列的约数为rj，那么各行、列的约数之和L=ti+ri，其中1i,j n.,在上例中，C的归约成本矩阵C，矩阵约数L=25,90,估计函数C(.)的定义,在成本矩阵中，若对i行（或j列）施行归约，即将此行（列）的每个元素减去该行（列）的最小元素t，则此次周游成本减少t。显然是此问题的最小周游成本的一个下界值，于是可以将它取作

43、状态空间树根结点的C值。,91,估计函数C(.)的定义,为了定义函数C(.)，在货郎担问题的状态空间树中对每个结点都附以一个归约成本矩阵。设A是结点R的归约成本矩阵，S是R的儿子且树边(R,S)对应这条周游路线中的边(i,j)。,92,估计函数C(.)的定义,在S是非叶子结点的情况下，S的归约成本矩阵可按以下步骤求得：（1）为保证这条周游路线采用边(i,j)，而不采用其它由i出发或者进入j的边，将A中i行和j列的元素置为；（2）为防止采用边(j,1)（因为在已选定的路线上加入边(i,j)之后若再采用边(j,1)就会构成一个环而得不到这条周游路线），将A(j,1)置为；（3）对于那些不全为的行和

44、列施行归约则得到S的归约成本矩阵，令其为B，矩阵约数为r。非叶结点S的C值可定义为C(S)=C(R)+A(i,j)+r 如果S是叶结点，由于一个叶结点确定一条唯一的周游路线，因此可用这条周游路线的成本作为S的C值，即C(S)=C(S)。,93,上界函数u(.)的定义,可以将其定义为：对于树中每个结点R，u(R)=。由以上定义，显然有：c(X)c(X)u(X)。,94,用LC分枝-限界法求解货郎担问题,95,用LC分枝-限界法求解货郎担问题,20 30 10 1115 16 4 2 3 5 2 419 6 18 316 4 7 16,10 17 0 112 11 2 0 0 3 0 215 3

45、12 011 0 0 12,C=,结点1对应的归约成本矩阵,11 2 0 0 0 215 12 011 0 12,结点2对应的归约成本矩阵,c(2)=25+10+0=35,96,用LC分枝-限界法求解货郎担问题,20 30 10 1115 16 4 2 3 5 2 419 6 18 316 4 7 16,10 17 0 112 11 2 0 0 3 0 215 3 12 011 0 0 12,C=,结点1对应的归约成本矩阵,1 2 0 3 0 2 4 3 0 0 0 12,结点3对应的归约成本矩阵,c(2)=25+17+11=53同理可求其它结点。(见教材P239)最小成本周游路是：1,4,2,5,3,1,