《算法分析与设计分枝限界法.ppt》由会员分享，可在线阅读，更多相关《算法分析与设计分枝限界法.ppt（96页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第七章第七章 分枝分枝-限界法限界法1上章知识回顾n问题状态n解状态n状态空间n答案状态n状态空间树n活结点nE-结点n死结点n通过对n-皇后问题的分析，复习以上概念和回溯法2n-皇后问题描述n将n个皇后放置在一个nn的棋盘上，要求没有两个皇后可以互相攻击。攻击的定义：两个皇后出现在同一行、或同一列、或者同一条斜线上都视为出现了攻击。38-皇后问题的一个解1 2 3 4 5 6 7 812345678该解的8元组表示:(4,6,8,2,7,1,3,5)4n-皇后问题n用n-元组(x1,x2,xn)表示棋盘上皇后的位置状态下标表示皇后i(i=1,2,n)xi表示放置皇后i所在的列号n显式约束条件
2、：每个xi只从集合Si=1,2,n取值满足显式约束的所有元组确定一个可能的解空间 解空间由nn个n-元组组成n隐式约束条件没有两个xi可以相同，而且没有两个皇后可以在同一条斜线上 由前者得，所有解都是n-元组(1,2,n)的置换，因此，解空间缩小为 n！个元组54-皇后问题解空间的树结构n结点按深度优先检索编号n叶子结点有4！24个 6解空间树结构的术语n树中每个结点确定求解问题的一个问题状态问题状态(problem state)n由根结点到其它结点的所有路径确定了这个问题的状态空间状态空间(state space)n解状态解状态(solution states)是这样一些问题状态S，对于这些
3、问题状态，由根到S的那条路径确定了这解空间中的一个元组（满足显式约束）n答案状态答案状态(solution states)是这样一些解状态S，由根到S的路径确定了问题的一个解（满足隐式约束）n解空间的树结构为状态空间树状态空间树(state space tree)7利用状态空间树解题1 设想状态空间树2 生成问题状态3 确定问题状态中哪些是解状态4 哪些解状态是答案状态生成问题状态 构造状态空间树8状态空间树术语n活结点：自己已经生成而其所有的儿子活结点：自己已经生成而其所有的儿子结点还没有全部生成的结点。结点还没有全部生成的结点。nE-结点（正在扩展的结点）：当前正在结点（正在扩展的结点）：
4、当前正在生成其儿子结点的活结点。生成其儿子结点的活结点。n死结点：不再进一步扩展或者其儿子结死结点：不再进一步扩展或者其儿子结点已全部生成的生成结点。点已全部生成的生成结点。9构造状态空间树的两个方法n回溯法当前E-结点R，生成一个新的儿子C，则C就变成一个新的E-结点，对子树C完全检测后，R结点再次成为E-结点。n分枝-限界方法一个E-结点一直保持到变成死结点为止。n限界函数以上两种方法都使用限界函数限界函数杀死还没有全部生成其儿子结点的那些活结点。104-皇后问题的限界函数限界函数n如果(x1,x2,xi)是到当前E-结点的路径，那么具有父-子标记xi+1的所有儿子结点是一些这样的结点，它
5、们使得(x1,x2,xi+1)表示没有两个皇后正在互相没有两个皇后正在互相攻击的一种棋盘格局攻击的一种棋盘格局。114-皇后问题回溯法vs状态空间树n结点按深度优先检索编号n叶子结点有4！24个 124-皇后问题回溯期间的生成树13分枝限界法n在生成当前E-结点全部儿子之后再生成其它活结点的儿子，并且，用限界函数帮助避免生成不包含答案结点子树的状态空间nFIFO检索：活结点表采用队nLIFO检索：活结点表采用栈14FIFO分枝限界法例7.1（4-皇后问题）3955154-皇后问题回溯 vs FIFO分枝-限界回溯回溯 Win！16LC-检索（Least Cost）n分枝-限界失败的原因对下一个
6、E-结点的选择规则过于死板。n如何解决？排序，让答案结点排在前面！寻找一种“有智力”的排序函数C()，该函数能够让答案结点尽早生成。n排序的标准下一个E-结点应当是生成答案结点花费成本最小的结点，因此C()又称作结点成本函数。LC：Least Cost17分枝分枝-限界策略的种类限界策略的种类n根据对状态空间树中结点检索次序的不根据对状态空间树中结点检索次序的不同，可将分枝同，可将分枝-限界的设计策略分为：限界的设计策略分为：FIFO检索，活结点采用一张先进先出表检索，活结点采用一张先进先出表LIFO检索，活结点采用一张先进后出表检索，活结点采用一张先进后出表LC分枝分枝-限界检索，活结点采用
7、一张易于操限界检索，活结点采用一张易于操作的线性表。作的线性表。18LC-检索（结点成本的两个标准）n一、在生成一个答案结点之前，子树X需要生成的结点数。n二、在子树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）19LC-检索（结点成本函数）nC()定义如果X是答案结点，则C(X)是由状态空间树的根结点到X的成本（即花费的代价，可以是级数、计算复杂度等）。如果X不是答案结点且子树X不包含任何答案结点，则C(X
8、)。如果X不是答案结点但子树X包含答案结点，则C(X)等于子树X中具有最小成本的答案结点的成本。20LC-检索（成本估计函数）n从前面的两个成本度量标准看，计算C()的工作量与原问题的解具有相同复杂度。这是因为计算一个结点的代价通常要检索包含一个答案结点的子树才能确定，而这正是解决此问题所要作的检索工作，因此要得到精确的成本函数一般是不现实的。n因此需要成本估计函数g(X)n出现的新问题仅利用g(X)会导致算法偏向纵深检查，无法有效处理下面这种情况：即g(W)=g(Y)。nLC分枝分枝-限界检索：伴之有限界函数的限界检索：伴之有限界函数的LC-检索检索22例：例：15-谜问题谜问题134152
9、512761114891013123456789101112131415abc问题描述：在一个分成问题描述：在一个分成16格的方形棋盘上，放有格的方形棋盘上，放有15块编了号码的牌（见下图）。对这些牌给定一块编了号码的牌（见下图）。对这些牌给定一种初始排列如图种初始排列如图7.2(a)，要求通过一系列的合法移，要求通过一系列的合法移动将这一初始排列转换成图动将这一初始排列转换成图7.2(b)所示的那样的目所示的那样的目标排列。标排列。图图7.2 15-谜的排列图谜的排列图23例：例：15-谜问题谜问题 图图7.2(a)所示的初始排列有四种可能的移动，可所示的初始排列有四种可能的移动，可以将编号
10、为以将编号为2,3,5或或6的任何一块牌移到空格。的任何一块牌移到空格。在作了这次移动之后，可作其他的移动。每移动在作了这次移动之后，可作其他的移动。每移动一次，就产生一种新的排列。这些排列称为这个一次，就产生一种新的排列。这些排列称为这个谜问题的状态。谜问题的状态。初始排列和目标排列叫做初始状态和目标状态。初始排列和目标排列叫做初始状态和目标状态。若由初始状态到某状态存在一系列合法的移动，若由初始状态到某状态存在一系列合法的移动，则称该状态可由初始状态到达。则称该状态可由初始状态到达。一种初始状态的状态空间由所有可从初始状态到一种初始状态的状态空间由所有可从初始状态到达的状态构成。达的状态构
11、成。24例：例：15-谜问题谜问题 可以看出棋盘上这些牌有可以看出棋盘上这些牌有16！种不同的排列，！种不同的排列，所以这个问题的状态空间是相当庞大的。所以这个问题的状态空间是相当庞大的。有必要在具体求解问题之前判定目标状态是否有必要在具体求解问题之前判定目标状态是否在这个初始状态的状态空间中。在这个初始状态的状态空间中。对此有一个非常简单的判定方法：我们先给棋对此有一个非常简单的判定方法：我们先给棋盘的方格位置编上盘的方格位置编上116的号码。位置的号码。位置i 是在图是在图7.2(b)所示的目标排列中放所示的目标排列中放i 号牌的方格位置，号牌的方格位置，位置位置16是空格的位置。是空格的
12、位置。假设假设POSITION(i)是编号为是编号为i的那块牌在初始状的那块牌在初始状态下的位置号，态下的位置号，1 i POSITION(i)的的数目。数目。例如，对于图例如，对于图7.2(a)所示的状态，有所示的状态，有LESS(1)=0，LESS(4)=1和和LESS(12)=6。在在初始状态下，如果空格在图初始状态下，如果空格在图7.2的阴影位置中的某的阴影位置中的某一格处，则令一格处，则令X=1；否则否则X=0。于是有于是有定理定理7.1：当且仅当当且仅当LESS(i)+X（1 i16)i16)是是偶数时，图偶数时，图7.2(b)7.2(b)所示的目标状态可由此初始状态到达。所示的目
13、标状态可由此初始状态到达。可以用定理可以用定理7.17.1来判定目标状态是否在初始状态的状来判定目标状态是否在初始状态的状态空间中。若在，就可以着手确定导致目标状态的一态空间中。若在，就可以着手确定导致目标状态的一系列移动。系列移动。例：例：15-谜问题谜问题26 为了实现这一检索，可以将此状态空间构造为了实现这一检索，可以将此状态空间构造成一棵树。在这棵树中，每一个结点的儿子表成一棵树。在这棵树中，每一个结点的儿子表示由状态示由状态X通过一次合法的移动可到达的状态。通过一次合法的移动可到达的状态。不难看出，移动牌与移动空格实质上是等效的，不难看出，移动牌与移动空格实质上是等效的，而且在作实际
14、移动时，因此以后都将父状态到而且在作实际移动时，因此以后都将父状态到子状态的一次转换看成是空格的一次合法移动。子状态的一次转换看成是空格的一次合法移动。例：例：15-谜问题谜问题2715-谜问题谜问题(宽度优先宽度优先)2815-谜问题谜问题(宽度优先前十步宽度优先前十步)29例：例：15-谜问题谜问题n按照按照FIFO检索方法不管开始格局如何，总是采检索方法不管开始格局如何，总是采取由根开始的那条最左路径，因而检索是呆板而取由根开始的那条最左路径，因而检索是呆板而盲目的。盲目的。n我们所期望的是：我们所期望的是：有一个具有一定有一个具有一定“智能智能”的检索方法。这就需给的检索方法。这就需给
15、状态空间树的每个结点状态空间树的每个结点X赋予一定的成本值赋予一定的成本值c(X)，可将，可将由根出发到最近目标结点路径上的每个结由根出发到最近目标结点路径上的每个结点点X赋予这条路径长度作为他们的成本值赋予这条路径长度作为他们的成本值。n切合实际的做法是：切合实际的做法是：给出一个便于计算成本估计值的函数给出一个便于计算成本估计值的函数c(X)=f(X)+g(X)，其中，其中f(X)是由根到结点是由根到结点X的路径长度的路径长度30例：例：15-谜问题谜问题ng(X)是以是以X为根的子树中由为根的子树中由X到目标状态的一到目标状态的一条最短路径长度的估计值。条最短路径长度的估计值。n因此，因
16、此，g(X)至少应是能把状态至少应是能把状态X转换成目标状转换成目标状态所需的最小移动数。态所需的最小移动数。n一种可能的选择是：一种可能的选择是：g(X)=g(X)=不在其目标位置的非空白牌数目不在其目标位置的非空白牌数目不在其目标位置的非空白牌数目不在其目标位置的非空白牌数目n使用使用c(X)图图7.3(a)的的LC-检索将结点检索将结点1作为作为E-结点的开始。结点结点的开始。结点1在生成它的儿子结点在生成它的儿子结点2,3,4和和5之后死去。变成之后死去。变成 E-结点的下一个结结点的下一个结点是具有最小点是具有最小c(X)的活结点。的活结点。3115-谜问题（使用C(X)的LC-检索
17、）555355332例：例：15-谜问题谜问题nc(2)=1+4，c(3)=1+4，c(4)=1+2，c(5)=1+4，所以结点，所以结点4成为成为E-结点。结点。n生成结点生成结点4的儿子结点，此时的活结点的儿子结点，此时的活结点是是2,3,5,10,11,12。nc(10)=2+1，c(11)=2+3，c(12)=2+3，具有最小，具有最小c值的活结点值的活结点10成为下一个成为下一个E-结点。结点。n接着生成结点接着生成结点22和和23，结点，结点23被判定被判定是目标结点，此次检索结束。是目标结点，此次检索结束。33分支限界法的基本思想分支限界法的基本思想n分支限界法常以广度优先或以最
18、小耗费分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解（最大效益）优先的方式搜索问题的解空间树。空间树。n在搜索问题的解空间树时，分支限界法在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活方式不同。在分支限界法中，每一个活结点结点只有一次机会只有一次机会成为扩展结点。活结成为扩展结点。活结点一旦成为扩展结点，就一次性产生其点一旦成为扩展结点，就一次性产生其所有儿子结点。所有儿子结点。34分支限界法的基本思想分支限界法的基本思想n在这些儿子结点中，那些导致不可行解在这些儿子结点中，那些导致
19、不可行解或导致非最优解的儿子结点被舍弃，其或导致非最优解的儿子结点被舍弃，其余儿子结点被加入到活结点表中。余儿子结点被加入到活结点表中。n此后，从活结点表中取下一结点成为当此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活这个过程一直持续到找到所求的解或活结点表为空时为止。结点表为空时为止。35LC-检索的抽象化控制检索的抽象化控制n设设T是一棵状态空间树，是一棵状态空间树，C(.)是是T中结点中结点的成本函数。如果，的成本函数。如果，C(X)是其根为是其根为X的的子树中任一答案结点的最小成本，则子树中任
20、一答案结点的最小成本，则C(T)是是T中最小成本答案结点的成本。中最小成本答案结点的成本。n由于函数由于函数C(.)不容易实现，所以使用一个不容易实现，所以使用一个对对C(.)估值的启发性函数估值的启发性函数C(.)来代替。来代替。n这个启发函数应易于计算并具有如下性这个启发函数应易于计算并具有如下性质：如果质：如果X是一个答案结点或者是一个是一个答案结点或者是一个叶结点，则叶结点，则C(X)=C(X)。36算法算法7.1 LC-检索检索Procedure LC(T,c)if T是答案结点是答案结点 then 输出输出T;return end ifET /E-结点结点 /将活结点表初始化为空将
21、活结点表初始化为空loopfor E 的每个儿子的每个儿子X doif X是答案结点是答案结点 then 输出从输出从X到到T的那条路径的那条路径return;end ifcall ADD(X)/X是新的活结点是新的活结点 /PARENT(X)E repeatif 不在有活结点不在有活结点 then print(no answer node)stop;end ifcall LEAST(E)repeatEnd LC将一个活结点加将一个活结点加入到队列中入到队列中找一个具有最小找一个具有最小C值值的活结点并从活结点表的活结点并从活结点表中删除这个结点中删除这个结点保存结点保存结点X的父的父结点结点
22、E通常把这个活结点表作成一个min-堆37LC-检索说明n只有当有限状态空间树下才能保证LC终止。n对于无限状态空间树，在其至少有一个答案结点并假定对成本估计函数C能作出“适当”的选择时，才能保证算法LC终止。n实际上LC算法与状态空间树的宽度优先检索算法和D-检索算法基本相同。38LC-检索的抽象化控制（vs.BFS,D-Search）nLC算法与BFS及D-Search基本相同n活结点表采用队列 vs BFSn活节点表采用栈 vs D-Searchn不同：活结点表的构造，即下一个E-结点的选择规则不同。39LC-检索的特性检索的特性nLC是否一定能找到具有是否一定能找到具有最小成本最小成本
23、的答案结点的答案结点呢？呢？n考虑下图所示的状态空间树，方形叶子结点考虑下图所示的状态空间树，方形叶子结点是答案结点。每个结点有两个数，上面的是是答案结点。每个结点有两个数，上面的是C的值，下面的是的值，下面的是C的值。的值。10020220201041010 40LC-检索的特性检索的特性n定理定理7.2 在有限状态空间树在有限状态空间树T中，对于每一个结点中，对于每一个结点X，令，令c(X)是是c(X)的估计值且具有以下性质：对的估计值且具有以下性质：对于每一个结点于每一个结点Y、Z，当且仅当，当且仅当c(Y)c(Z)时有时有c(Y)U的所有活结点的所有活结点X可以被杀死，这是因为由可以被
24、杀死，这是因为由X可以可以到达的所有答案结点有到达的所有答案结点有UU，所以结点所以结点7被杀死；结点被杀死；结点8是不可行结点，是不可行结点，也被杀死。也被杀死。n结点结点3成为成为E-结点，生成其儿子结点结点，生成其儿子结点9和和10。u(9)=8u(9)=8，因此，因此U U变成变成8 8；C(10)=11U，所以，所以10被杀死。被杀死。n结点结点9只有一个儿子且不可行，因此结点只有一个儿子且不可行，因此结点9是最小成本答案结点，其成本值为是最小成本答案结点，其成本值为8。53上界U的确定n在实现分枝限界算法时，每修改一次在实现分枝限界算法时，每修改一次U，在活结点队中那，在活结点队中
25、那些些c(X)U或者在或者在U是已找到的一个成本值情况下有是已找到的一个成本值情况下有c(X)U的的结点点应被被杀死。死。n必必须识别出出这个修改了的个修改了的U是一个已找到的解的成本是一个已找到的解的成本还是是一个不是解成本的一个不是解成本的单纯上界。上界。n这个个单纯上界上界U或者是或者是还没找到一个答案没找到一个答案结点，点，U由由处理理一可行一可行结点点时修改而得；修改而得；或者是或者是虽然找到一答案然找到一答案结点，点，但它的成本但它的成本值大于它的上界大于它的上界值，说明明这答案答案结点的子点的子孙中中还有成本更小的答案有成本更小的答案结点，点，U取取这个上界个上界值。n算法算法实
26、现时，可引，可引进一个很小的正常数一个很小的正常数来来进进行行这这一一识识别别。此。此要取得足要取得足够够小，使得小，使得对对于任意两个可行于任意两个可行结结点点X X和和Y Y，如果，如果u(X)u(Y),u(X)u(Y),则则u(X)u(X)+u(Y)u(X)u(X)+u(Y)。当。当U U是由一是由一答案答案结结点的成本点的成本值值而得而得时时，U U就是就是这这个成本个成本值值，而当，而当U U是是由一由一单纯单纯上界得到上界得到时时，U U等于此上界等于此上界值值u(X)+u(X)+。54找最小成本答案结点的FIFO分枝-限界方法n如何处理c(X)=U的情况为什么要处理？如何处理？引
27、进，当u(X)u(Y)时，u(X)u(X)+u(Y)。在算法中，比较c(X)与U的时候，可以对U作以下处理：当U是成本值，则不变当U由一单纯上界得出，U=u(X)+55找最小成本答案结点的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)U then call ADD
28、(X);PARENT(X)=E case :X是解结点 and cost(X)U:U=min(cost(X),u(X)+);ans=X :u(X)+U:U=u(X)+endcase endif repeat loop /得到下一个E-结点/if 队为空 then print(least cost=,U)then print(least cost=,U)while ans0 do print(ans);ans=PARENT(ans)repeat return endif call DELETEQ(X)if c(X)U then exit repeatrepeatend LCBB56找最小成本结点
29、的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)U then call ADD(X)PARENT(X)=E case :X是解结点 and cost(X)U:U=min(cost(X),u(X)+)ans=X :u(X)+U:U=u(X)+endcase endif
30、repeat if 不再有活结点 or 下一个E结点有cU then print(least cost=,U)while ans0 do print(ans)ans=PARENT(ans)repeat return endif call LEAST(E)repeatend LCBB57效率分析n上下界函数的选择是决定分枝-限界算法效率的主要因素。n对U选择一个更好的初值是否能减少生成的结点数？（否，根据定理7.4）n扩展一些C(.)U的结点是否能减少所生成的结点数？（否，根据定理7.5）n假定有两个成本估计函数C1(.)和C2(.)，对于状态空间树的每一个结点X，若有C1(X)C2(X)C(X
31、)，则称C2(.)比C1(.)好。是否用较好的成本估计函数C2(.)比用C1(.)生成的结点数要少呢？（否，根据定理7.6和定理7.7）58定理7.4n设U1和U2是状态空间树T中最小成本答案结点的两个初始上界且U1U的结点X而减少。60定理7.6n在FIFO和LIFO分枝-限界算法中使用一个更好的成本估计函数C(.)不会增加其生成的结点数。61定理7.7n在LC分枝-限界算法中使用一个更好的成本估计函数C(.)可能增加所生成的结点的个数。62定理7.7的证明13276333361334 4 495864 如上图，所有叶子结点都是答案结点，叶结点下面的数是其成本值，从这些值中可以得出C(1)=
32、C(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。637.2 0/1背包问题n用函数-pixi来代替目标函数pixi，从而将背包问题由一个极大问题转换成一个极小化问题。n本节只计论在大小固定的元组表示下如何求解0/1背包问题。n状态空间树中那些pixiM(1 i n)的装包方案的每一个叶结点是答案结点，其它的叶结点均不可行。64上界函数算法7.5 背包问题的上界函数u(.)Procedu
33、re 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 UBOUND65估价函数C(X)的定义n令C(X)=-BOUND，其中BOUND函数是算法6.11（见教材P210）。n显然有C(x)C(X)u(X)。667.2.1 LC分枝-限界求解n例7.2 LCBB考虑背包问题：n=4(p1,p2,p3,p4)=(10,10,12,18)(w1,w2,w3,w4)=(2,4,6,9)M=1
34、56713275-38-32-32-224968-38-32-38-32-38-32-36-22-38-38-38-38-20-20上面的数=C下面的数=u例例7.2 LCBB考虑背包问题：n=4(p1,p2,p3,p4)=(10,10,12,18)(w1,w2,w3,w4)=(2,4,6,9)M=1568例7.2 LCBBn在找到答案结点8的情况下，无论哪一个结点变成下一个E-结点都要有C(E)U，因此，终止检索，这时打印出值-38和路径8,7,4,2,1，算法结束。n要指出的是，由路径8,7,4,2,1并不能得出由哪些物品装入背包才得到-pixi=U，即看不出这些Xi的取值情况。n因此在实
35、现过程LCBB时应保留一些能反映Xi取值情况的附加信息。69例7.2 LCBBn一种解决办法是每一个结点增设一个位信息段TAG。n若该结点为左孩子，则TAG(X)=1；n若该结点为右孩子，则TAG(X)=0。n于是，对此问题将有：TAG(2)=TAG(4)=TAG(6)=TAG(8)=1；TAG(3)=TAG(5)=TAG(7)=TAG(9)=0。70LCBB求解背包问题分析n状态空间树中结点的结构n如何生成一给定结点的儿子n如何识别答案结点n如何表示活结点表71状态空间树中结点的结构nPARENT父结点链接指针nLEVEL状态空间树中的级数nTAGXi的取值nCU背包的剩余空间nPE已装入物
36、品的效益值的和nUBc(X)72如何生成一给定结点的儿子n左儿子生成PARENT(Y)=XLEVEL(Y)=LEVEL(X)+1CU(Y)=CU(X)WLEVEL(X)PE(Y)=PE(X)+P LEVEL(X)TAG=1UB(Y)=UB(X)73如何识别答案结点n当且仅当LEVEL(X)=n 1nX是答案结点74如何表示活结点表nMin-堆n测试活结点表是否为空常量时间n加结点到活结点表 log(n)n删除最小UB值的结点 log(n)75计算上界和下界的算法line procedure LUBOUND(P,W,rw,cp,N,k,LBB,UBB)1 LBB cp;c rw;2 for i
37、k to N do 3 if c=W(j)then c c-W(j)6 LBB LBB+P(j)7 endif8 repeat9 return10 endif11 c c-W(i);LBB LBB+P(i)12 repeat13 UBB LBB14 end LUBOUND76生成一个新结点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 NEWNODE77背包问
38、题的LC分枝-限界算法line procedure LCKNAP(P,W,M,N,)/大小固定元组表示状态空间树/假设P(1)/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)78背包问题的LC
39、分枝-限界算法8 case9 :i=N+1:10 if profL then L prof;ANS E11 endif12 :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 endcase79背包问题的LC分枝-限界算法22 if 不再有活结点 t
40、hen exit endif23 call LARGEST(E)24 until UB(E)=P(2)/W(2)=P(N)/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=L:11 cap CU(E);prof PE(E)12 if cap=W(i)then13 call NNODE(E,1,cap-W(i),prof+P(i),UB(E)14
41、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 FIFOKNAP847.3 货郎担问题n问题描述：问题描述：某售货员要到若干个村庄售货，各村庄之间的路程某售货员要到若干个村庄售货，各村庄之间的路程是己知的，为了提
42、高效率，售货员决定从所在商店是己知的，为了提高效率，售货员决定从所在商店出发，到每个村庄售一次货然后返回商店，问他应出发，到每个村庄售一次货然后返回商店，问他应选择一条什么路线才能使所走的总路程最短选择一条什么路线才能使所走的总路程最短?设设G(V,E)是一个具有边成本是一个具有边成本cij的有向图。的有向图。G的一条的一条周游路线是包含周游路线是包含V中每个结点的一个有向环。中每个结点的一个有向环。周游路线的成本是此路线上所有边的成本之和，周游路线的成本是此路线上所有边的成本之和，货货郎担问题郎担问题(traveling salesperson problem)是求是求取具有最小成本的周游路
43、线问题。取具有最小成本的周游路线问题。85货郎担问题的状态空间树12345769812111016151413n=4，i0=i4=1的货郎担问题的状态空间树i1=2i1=3i1=4i2=3i2=4i2=2i2=4i2=2i2=3i3=4i3=3i3=4i3=2i3=3i3=286用LC分枝-限界法检索货郎担问题的状态空间树n成本函数C(.)的定义：（1）若X是叶结点，则C(X)为由根到X的路径确定的周游路线成本。（2）若X不是叶结点，子树X中最小成本叶结点的成本。87归约矩阵n如果矩阵的一行（列）至少包含一个零且其余无素均非负，则此行（列）称为已归约行（列）。n所有行和列均已归约行和列的矩阵称
44、为归约矩阵。n可以通过对一行（列）中每个元素都减去同一个常数t（称为约数）将该行（列）变为已归约行（列）。逐行逐列施行归约就可得到原矩阵的归约矩阵。88矩阵约数n假设第i行的约数ti，第j列的约数为rj，那么各行、列的约数之和L=ti+ri，其中1i,j n.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=C=在上例中，C的归约成本矩阵C，矩阵约数L=2589估计函数C(.)的定义n在成本矩阵中，若对i行（或j列）施行归约，即将此行（列）的每个元素减去该行
45、（列）的最小元素t，则此次周游成本减少t。n显然是此问题的最小周游成本的一个下界值，于是可以将它取作状态空间树根结点的C值。90估计函数C(.)的定义n为了定义函数C(.)，在货郎担问题的状态空间树中对每个结点都附以一个归约成本矩阵。n设A是结点R的归约成本矩阵，S是R的儿子且树边(R,S)对应这条周游路线中的边(i,j)。91估计函数C(.)的定义n在S是非叶子结点的情况下，S的归约成本矩阵可按以下步骤求得：（1）为保证这条周游路线采用边(i,j)，而不采用其它由i出发或者进入j的边，将A中i行和j列的元素置为；（2）为防止采用边(j,1)（因为在已选定的路线上加入边(i,j)之后若再采用边
46、(j,1)就会构成一个环而得不到这条周游路线），将A(j,1)置为；（3）对于那些不全为的行和列施行归约则得到S的归约成本矩阵，令其为B，矩阵约数为r。非叶结点S的C值可定义为C(S)=C(R)+A(i,j)+r n如果S是叶结点，由于一个叶结点确定一条唯一的周游路线，因此可用这条周游路线的成本作为S的C值，即C(S)=C(S)。92上界函数u(.)的定义n可以将其定义为：对于树中每个结点R，u(R)=。n由以上定义，显然有：c(X)c(X)u(X)。93用LC分枝-限界法求解货郎担问题123467109n=5，i0=i4=1的货郎担问题算法LCBB生成的状态空间树i1=2i1=3i1=4i2
47、=2i2=3i3=3i3=55i1=58i2=511i4=33553253128503632282825 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=C=94用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对应的归约成本矩阵 11 2 0 0 0 215 12 011 0 12 结点2对应的归约成本矩阵c(2)=25+10+0=3595用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,196