计算机算法基础课件.ppt

1、计算机算法基础计算机算法基础分枝限界法分枝限界法0 预备知识预备知识问题状态问题状态解状态解状态状态空间状态空间答案状态答案状态状态空间树状态空间树活结点活结点E-结点结点死结点死结点等等等等本节主要目的本节主要目的通过对n-皇后问题的分析，学习以上概念，并且了解回溯法解空间树结构的术语解空间树结构的术语树中每个结点确定求解问题的一个树中每个结点确定求解问题的一个问题状态(problem state)由根结点到其它结点的所有路径确定了这个由根结点到其它结点的所有路径确定了这个问题的问题的状态空间(state space)解状态(solution states)是这样一些问题状是这样一些问题状态

2、态S，对于这些问题状态，由根到，对于这些问题状态，由根到S的那条路的那条路径确定了这解空间中的一个元组（满足显式径确定了这解空间中的一个元组（满足显式约束）约束）答案状态(solution states)是这样一些解状是这样一些解状态态S，由根到，由根到S的路径确定了问题的一个解的路径确定了问题的一个解（满足隐式约束）（满足隐式约束）解空间的树结构为解空间的树结构为状态空间树(state space tree)利用状态空间树解题利用状态空间树解题1 设想状态空间树设想状态空间树2 生成问题状态生成问题状态3 确定问题状态中哪些是解状态确定问题状态中哪些是解状态4 哪些解状态是答案状态哪些解状态

3、是答案状态生成问题状态生成问题状态 构造状态空间树构造状态空间树状态空间树术语状态空间树术语l活结点：自己已经生成而其所有的儿子结点还没有全部生成的结点。lE-结点（正在扩展的结点）：当前正在生成其儿子结点的活结点。l死结点：不再进一步扩展或者其儿子结点已全部生成的生成结点。静态树静态树(static trees)：树结构与所要解：树结构与所要解决的问题的实例无关。决的问题的实例无关。动态树动态树(dynamic trees)：根据不同的：根据不同的实例而使用不同的树结构。实例而使用不同的树结构。构造状态空间树的两个方法构造状态空间树的两个方法回溯法回溯法l当前当前E-结点结点R，生成一个新的

4、儿子，生成一个新的儿子C，则则C就变成一个新的就变成一个新的E-结点，对子树结点，对子树C完全检测后，完全检测后，R结点再次成为结点再次成为E-结点结点分枝分枝-限界方法限界方法l一个一个E-结点一直保持到变成死结点为止结点一直保持到变成死结点为止限界函数限界函数l以上两种方法都使用以上两种方法都使用限界函数杀死还没杀死还没有全部生成其儿子结点的那些活结点有全部生成其儿子结点的那些活结点分枝限界法分枝限界法在生成当前在生成当前E-结点全部儿子之后再生结点全部儿子之后再生成其它活结点的儿子成其它活结点的儿子并且，用限界函数帮助避免生成不包并且，用限界函数帮助避免生成不包含答案结点子树的状态空间含

5、答案结点子树的状态空间FIFO检索：活结点表采用检索：活结点表采用队队LIFO检索：活结点表采用检索：活结点表采用栈栈LC检索：最小成本检索检索：最小成本检索FIFO分枝限界法分枝限界法例例9.1（4-皇后问题）皇后问题）394-皇后问题皇后问题回溯回溯 vs FIFO分枝分枝-限界限界回溯回溯Win！LC-检索（检索（Least Cost）分枝分枝-限界失败的原因限界失败的原因l对下一个对下一个E-结点的选择规则过于死板结点的选择规则过于死板如何解决？如何解决？l排序，让答案结点排在前面！排序，让答案结点排在前面！l寻找一种寻找一种“有智力有智力”的排序函数的排序函数C()，该函数，该函数能

6、够让答案结点尽早生成能够让答案结点尽早生成排序的标准排序的标准l下一个下一个E-结点应当是生成答案结点花费成本结点应当是生成答案结点花费成本最小的结点，因此最小的结点，因此C()又称作又称作结点成本函数结点成本函数。lLC：Least CostLC-检索（结点成本的两个标检索（结点成本的两个标准）准）一：在生成一个答案结点之前，子树一：在生成一个答案结点之前，子树X需要需要生成的结点数。生成的结点数。二：在子树二：在子树X中离中离X最近的那个答案结点到最近的那个答案结点到X的路径长度。以的路径长度。以图图9.1为例为例l节点节点1、18和和34、29和和35、30和和38的代价分的代价分别是别

7、是4，3，2，1l其他其他2，3，4级上的点代价应分别大于级上的点代价应分别大于3，2，1l生成结点（生成结点（12 18 34 5019 24 2930 3231）39LC-检索（结点成本函数）检索（结点成本函数）C()定义定义如果如果X是答案结点，则是答案结点，则C(X)是由状态空是由状态空间树的根结点到间树的根结点到X的成本（即花费的代的成本（即花费的代价，可以是级数、计算复杂度等）价，可以是级数、计算复杂度等）如果如果X不是答案结点且子树不是答案结点且子树X不包含任不包含任何答案结点，则何答案结点，则C(X)如果如果X不是答案结点但子树不是答案结点但子树X包含答案包含答案结点，则结点，

8、则C(X)等于子树等于子树X中具有最小成中具有最小成本的答案结点的成本本的答案结点的成本LC-检索（成本估计函数）检索（成本估计函数）从前面的两个成本度量标准看，从前面的两个成本度量标准看，计算计算C()的工的工作量与原问题的解具有相同复杂度。这是因为作量与原问题的解具有相同复杂度。这是因为计算一个结点的代价通常要检索包含一个答案计算一个结点的代价通常要检索包含一个答案结点的子树才能确定，而这正是解决此问题所结点的子树才能确定，而这正是解决此问题所要作的检索工作，因此要得到精确的成本函数要作的检索工作，因此要得到精确的成本函数一般是不现实的一般是不现实的因此需要成本估计函数因此需要成本估计函数

9、g(X)出现的新问题出现的新问题l仅利用仅利用g(X)会导致算法偏向纵深检查，无法会导致算法偏向纵深检查，无法有效处理下面这种情况：即有效处理下面这种情况：即g(W)=g(Y)，LC分枝分枝-限界检索：伴之有限界函数的限界检索：伴之有限界函数的LC-检检索索15-谜问题（问题描述）谜问题（问题描述）1341525127611 148910 13123456789101112131415通过一系列合法移动将初始排列转换成目标排列。合法移动：将邻接于空格的牌移动到空格。目标排列一种初始排列15-谜问题（是否有解）谜问题（是否有解）棋盘存在棋盘存在16！种不同排列！种不同排列任一初始状态，可到达的状

10、态为这些任一初始状态，可到达的状态为这些排列中的一半排列中的一半在求解问题前，需要判定目标状态是在求解问题前，需要判定目标状态是否在初始状态的状态空间中否在初始状态的状态空间中15-谜问题（判定方法）谜问题（判定方法）按目标状态给牌编号，空格为按目标状态给牌编号，空格为16用用POSITION(i)记录编号为记录编号为i的牌在初始状的牌在初始状态中的位置；态中的位置；POSITION(16)表示空格表示空格l图图9.2(a)的的POSITIONl(1 5 2 3 7 10 9 13 14 15 11 8 16 12 4 6)LESS(i)是使得牌是使得牌j小于牌小于牌i且且POSITION(j

11、)POSITION(i)的数目的数目lLESS(1)=0;LESS(4)=1;LESS(12)=615-谜问题（判定方法）谜问题（判定方法）定理定理7.1 当且仅当当且仅当sum(LESS(i)+X)是偶是偶数时，目标状态可由此数时，目标状态可由此初始状态到达初始状态到达X1：空格恰好在上图：空格恰好在上图棋盘中的蓝色格子上棋盘中的蓝色格子上X0：空格在棋盘中的：空格在棋盘中的白色格子上白色格子上15-谜问题谜问题(宽度优先宽度优先)15-谜问题谜问题(深度优先深度优先)15-谜问题（谜问题（“智能智能”方法）方法）针对不同实例用相同规则检索，过于呆板和针对不同实例用相同规则检索，过于呆板和盲

12、目盲目是否能够找到一种是否能够找到一种“智能智能”方法，给每个结方法，给每个结点赋予成本值点赋予成本值:l如果结点在根结点到最近目标结点路径上，如果结点在根结点到最近目标结点路径上，则成本为这条路径的长度：则成本为这条路径的长度：C(1)=C(4)=C(10)=C(23)=3l否则，成本为否则，成本为l检索时杀死成本为检索时杀死成本为的结点的结点该方法的实际可操作性？该方法的实际可操作性？15-谜问题谜问题（成本估计值函数）（成本估计值函数）C(X)=f(X)+g(X)f(X)：根到结点：根到结点X的路径长度的路径长度1）g(X)：是子树：是子树X中，由中，由X到目标状态的到目标状态的最短路径

13、长度的估计值最短路径长度的估计值2）状态）状态X转换成目标状态所需的最小移动数转换成目标状态所需的最小移动数3）g(X)=不在其目标位置的非空白牌数目；不在其目标位置的非空白牌数目；该值应该比该值应该比2）要小）要小 C(X)是是C(X)的下界的下界15-谜问题（使用谜问题（使用C(X)的的LC-检索）检索）123456891071113 14 15 12123456891071113 14 15 12123456891071113 14 15 1212345689 1071113 14 15 12123456891071113 14 15 121 2 345 689 1071113 14 1

14、5 1212345689 1071113 141512123456891071113 14 15 121 2345689 1071113 14 15 1212345689 1071113 14 15125553553结点结点1为为E-结点，生结点，生成其儿子结点成其儿子结点C(2)=1+4C(3)=1+4C(4)=1+2C(5)=1+4所以结点所以结点4成为成为E-结结点点LC-检索的抽象化控制检索的抽象化控制line procedure LC(T,c)/为找答案结点检索为找答案结点检索T0 if T是答案结点是答案结点 then 输出输出T;return endif1 E T2 将活结点表初

15、始化为空将活结点表初始化为空3 loop4 for E的每个儿子的每个儿子X do5 if X是答案结点是答案结点 then 输出从输出从X到到T的路径的路径6 return7 endif8 call ADD(X)/X是新的活结点是新的活结点9 PARENT(X)E/指示到根的路径指示到根的路径10 repeat (Continue)X加入到活结点表中LC-检索的抽象化控制检索的抽象化控制 loop11 if 不再有活结点不再有活结点 then print(“no answer code”)12 stop13 endif14 call LEAST(E)15 repeat16 end LC从活结

16、点表中删除具有最小c值的活结点，并且将该结点赋给ELC-检索的抽象化控制检索的抽象化控制（正确性证明）（正确性证明）过程略过程略结论结论l对于有限状态空间树，以及存在答案结对于有限状态空间树，以及存在答案结点的无限状态空间树，算法能够终止点的无限状态空间树，算法能够终止l对于没有答案结点的无限状态空间树，对于没有答案结点的无限状态空间树，LC不会终止不会终止l检索局限在寻找估计成本不大于某个给检索局限在寻找估计成本不大于某个给定的限界定的限界C的答案结点是可取的的答案结点是可取的LC-检索的抽象化控制检索的抽象化控制（vs.BFS,D-Search）LC算法与算法与BFS及及D-Search基

17、本相同基本相同活结点表采用队列活结点表采用队列 vs BFS活节点表采用栈活节点表采用栈 vs D-Search不同：活结点表的构造，即下一个不同：活结点表的构造，即下一个E-结点的选择规则不同。结点的选择规则不同。LC-检索的特性检索的特性LC是否一定找得到具有最小成本的答案结点呢？是否一定找得到具有最小成本的答案结点呢？否否LC-检索的特性定理检索的特性定理7.2定理定理7.2 在有限状态空间树在有限状态空间树T中，对于中，对于每一个结点每一个结点X，令，令c(X)是是c(X)的估计的估计值且具有以下性质：对于每一对结点值且具有以下性质：对于每一对结点Y、Z，当且仅当，当且仅当c(Y)c(

18、Z)时有时有c(Y)c(Z)。那么在使。那么在使c()作为作为c()的估计值时，算法的估计值时，算法LC到达一个最小的到达一个最小的成本答案结点终止。成本答案结点终止。LC-检索的特性检索的特性 定理定理7.2的证明的证明略略LC-检索的特性检索的特性 找最小成本答案结点找最小成本答案结点line procedure LC1(T,c)/为找最小成本答案结点的为找最小成本答案结点的LC-检检索索0 if T是答案结点 then 输出T;return endif1 E T2 将活结点表初始化为空将活结点表初始化为空3 loop3 if E是答案结点是答案结点 then 输出从输出从E到到T的路径的

19、路径 return end if4 for E的每个儿子的每个儿子X do5 if X是答案结点 then 输出从X到T的路径6 return7 endif8 call ADD(X)/X是新的活结点是新的活结点9 PARENT(X)E/指示到根的路径指示到根的路径10 repeat (Continue)LC-检索的特性检索的特性 找最小成本答案结点找最小成本答案结点 loop11 if 不再有活结点不再有活结点 then print(“no answer code”)12 stop13 endif14 call LEAST(E)15 repeat16 end LC1LC-检索的特性检索的特性

20、定理定理7.3定理定理7.3 令令c()是满足如下条件的函数，是满足如下条件的函数，在状态空间树在状态空间树T中，对于每一个结点中，对于每一个结点X，有有c(X)=c(X)，而对于，而对于T中的每一个中的每一个答案结点答案结点X，有，有c(X)=c(X)。如果算法。如果算法在第在第3行终止，则所找到的答案结点是行终止，则所找到的答案结点是具有最小成本的答案结点。具有最小成本的答案结点。证明略证明略分枝分枝-限界算法限界算法限界的目的限界的目的l减少算法的盲目性，减小搜索空间，从而降减少算法的盲目性，减小搜索空间，从而降低计算量低计算量下界下界l使用使得使用使得c(X)U的所有活结点的所有活结点

21、X可以被杀死可以被杀死分枝分枝-限界算法限界算法(解最优化问题解最优化问题)一般化的带限期的作业排序问题一般化的带限期的作业排序问题l假定假定n个作业和一台处理机个作业和一台处理机l作业作业i对应一个三元组（对应一个三元组（pi,di,ti）lti表示作业表示作业i需要的单位处理时间需要的单位处理时间ldi表示完成期限表示完成期限lpi表示期限内未完成招致的罚款表示期限内未完成招致的罚款目标：从目标：从n个作业选取子集个作业选取子集J，要求，要求J中所有中所有作业都能在各自期限内完成并且使得不在作业都能在各自期限内完成并且使得不在J中的作业招致的罚款总额最小中的作业招致的罚款总额最小分枝分枝-

22、限界算法限界算法(实例实例)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);成本函数成本函数:圆形结点圆形结点X,c(X)是根为是根为X的子树中结点的最小罚款；的子树中结点的最小罚款；方形结点，方形结点，c(X)=下界函数下界函数m=maxi|i SX，SX是在结点是在结点X对对J所选择的作业的子集所选择的作业的子集上界上界XSimiipXc)(XSiipXu)(状态空间树状态空间树元组大小可变元组大小可变其中：圆形结点是答案结点，方形结点代表不可行的子集合状态空间树状态空间树元组

23、大小固定元组大小固定找最小成本答案结点的找最小成本答案结点的FIFO分枝分枝-限界方法限界方法如何处理如何处理c(X)=U的情况的情况l为什么要处理？为什么要处理？l如何处理？引进如何处理？引进，当，当u(X)u(Y)时，时，u(X)u(X)+u(Y)。l在算法中，比较在算法中，比较c(X)与与U的时候，可的时候，可以对以对U作以下处理：作以下处理：l当当U是成本值，则不变是成本值，则不变l当当U由一单纯上界得出，由一单纯上界得出，U=u(X)+FIFO分枝分枝-限界算法限界算法FIFOBBline procedure FIFOBB(T,c,u,cost)/为找出最小成本答案结点检索为找出最小

24、成本答案结点检索T 假定假定T至少包含一个解结点且至少包含一个解结点且 c(X)=c(X)=u(X)1 E T;PARENT(E)0;2 if T是解结点是解结点 then U min(cost(T),u(T)+);ans T3 else U u(T)+;ans 04 Endif5 将队列置初值为空将队列置初值为空 （Continue）FIFO分枝分枝-限界算法限界算法(续续1)6 loop7 for E的每个儿子的每个儿子X do8 if c(X)U then call ADDQ(X);PARENT(X)E 9 case10 :X是解结点是解结点 and cost(X)U:11 U min(

25、cost(T),u(T)+);12 ans X13 :u(X)+U:U u(X)+14 endcase15 endif16 repeat（Continue）FIFO分枝分枝-限界算法限界算法(续续2)17 loop/得到下一个得到下一个E-结点结点18 if 队列为空队列为空 then print(least cost=,U)19 while ans 0 do 20 print(ans)21 ans PARENT(ans)22 repeat23 return24 endif 25 call DELETEQ(X)26 if c(X)=U19 then print(least cost=,U)20

26、 while ans0 do21 print(ans)22 ans PARENT(ans)23 repeat24 return 25 endif26 call LEAST(X)27 repeat28end LCBB效率分析效率分析上下界函数的选择是决定分枝上下界函数的选择是决定分枝-限界算法效率限界算法效率的主要因素的主要因素对对U选择一个更好的初值是否能减少所生成选择一个更好的初值是否能减少所生成的结点数？（的结点数？（否否，根据定理，根据定理7.4）扩展一些扩展一些c()U的结点是否能减少所生成的的结点是否能减少所生成的结点数？（结点数？（否否，根据定理，根据定理7.5）假定有两个成本估计

27、函数假定有两个成本估计函数c1()和和c2()，对，对于状态空间树的每一个结点于状态空间树的每一个结点X，若有，若有c1()=c2()=c(X)，则称，则称c2()比比c1()好。好。是否用较好的成本估计函数生成的结点数要是否用较好的成本估计函数生成的结点数要少呢？（少呢？（否否，根据定理，根据定理7.6和定理和定理7.7）0/1背包问题描述背包问题描述极小化极小化约束条件约束条件 xi=0 或或xi=1，1=i=n niiixp1Mxwniii10/1背包问题的函数定义背包问题的函数定义c(X)=（答案结点）（答案结点）c(X)=（不可行的结点）（不可行的结点）c(X)=minc(LCHIL

28、D(X),c(RCHILD(X)c(X)=-Bound(,j-1,M)U(X)=-Bound(,j-1,M)l其中其中j是结点是结点X所在的层级所在的层级niiixp111jiiixp11jiiixw11jiiixp11jiiixw例例7.2n=4,M=15(p1,p2,p3,p4)=(10,10,12,18)(w1,w2,w3,w4)=(2,4,6,9)例例7.2的的LC分枝分枝 限界树限界树上面的数c下面的数u大小固定元组LCBB求解背包问题分析求解背包问题分析状态空间树中结点的结构状态空间树中结点的结构如何生成一给定结点的儿子如何生成一给定结点的儿子如何识别答案结点如何识别答案结点如何表

29、示活结点表如何表示活结点表状态空间树中结点的结构状态空间树中结点的结构PARENTl父结点链接指针父结点链接指针LEVELl状态空间树中的级数状态空间树中的级数TAGlXi的取值的取值CUl背包的剩余空间背包的剩余空间PEl已装入物品的效益值的和已装入物品的效益值的和UBlc(X)如何生成一给定结点的儿子如何生成一给定结点的儿子左儿子生成左儿子生成lPARENT(Y)=XlLEVEL(Y)=LEVEL(X)+1lCU(Y)=CU(X)WLEVEL(X)lPE(Y)=PE(X)+P LEVEL(X)lTAG=1lUB(Y)=UB(X)如何识别答案结点如何识别答案结点当且仅当当且仅当LEVEL(X

30、)=n 1X是答案结点是答案结点如何表示活结点表如何表示活结点表Min-堆堆测试活结点表是否测试活结点表是否为空为空l常量时间常量时间加结点到活结点表加结点到活结点表l log(n)删除最小删除最小UB值的结值的结点点l log(n)计算上界和下界的算法计算上界和下界的算法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 return10 endif11 c c-W(i);LBB L

31、BB+P(i)12 repeat13 UBB LBB14 end LUBOUND生成一个新结点生成一个新结点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背包问题的背包问题的LC分枝分枝-限界算法限界算法line procedure LCKNAP(P,W,M,N,)/大小固定元组表示状态空间树大小固定元组表示状态空间树/假设假设P(1)/W(1

32、)=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)背包问题的背包问题的LC分枝分枝-限界算法限界算法8 case9 :i=N+1:10 if profL then L prof;ANS E11 endi

33、f12 :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背包问题的背包问题的LC分枝分枝-限界算法限界算法22 if 不再有活结点不再有活结点 then exit endif23 call LARGEST(E)24 until UB

34、(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 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