算法分析与设计基本检索与周游方法ppt课件Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望一般方法n n 许多问题的解法涉及到对二元树、树和图的处理。这种处理往拄要求我们确定满足某一性质的那些给定数据对象中的一个结点或结点子集。n n这通常在数据对象中以检索的方式来进行。n n当这种检索必须包括对检索的数据对象的每一个结点进行检查时就把它称之为周游。代码优化n n编译程序的作用是,把高级语言程序翻译成一个等效的机器语言程序。n n假定有一个模型机A，其只有一个累加器寄存器。n n讨论只限于四个双目运算符：+、-、*、/n n相应的汇编语言指令：LOAD X LOAD X 将内存单元将内存单元X X的内容装入累加器。的内容装入累加器。STORE X STORE X 将累加器的内容不得存入内存将累加器的内容不得存入内存X X单无。单无。OP X OPOP X OP可以是可以是ADDADD，SUBSUB，MPYMPY或或DIVDIV。例1相关定义n n定义定义5.1 5.1 表达式表达式E E翻译成某给定机器的机器语言翻译成某给定机器的机器语言或汇编语言是最优的，当且仅当这一翻译有最或汇编语言是最优的，当且仅当这一翻译有最少的指令条数。少的指令条数。n n定义5.2 运算符的交换律。n n定义5.3 运算符的分配律。n n定义5.4 运算符的结合律。例2例3MPY c例4怎样获取最优代码段？n n首先将讨论局限于模型机首先将讨论局限于模型机A A。然后，再考察更一般的机。然后，再考察更一般的机器模型。器模型。n n用二叉树表示算术表达式，非叶子结点表示一个运算用二叉树表示算术表达式，非叶子结点表示一个运算符，称为内部结点。叶子结点或者表示一个变量或者符，称为内部结点。叶子结点或者表示一个变量或者表示一个常数。这样的二叉树称为表达式树。表示一个常数。这样的二叉树称为表达式树。n n假定所有的运算符既不可交换，也不可分配或结合。假定所有的运算符既不可交换，也不可分配或结合。n n易于证明在任何没有冗余指令的代码段中，除了第一易于证明在任何没有冗余指令的代码段中，除了第一条以外的每条装入指令都必须紧接在一条存放指令之条以外的每条装入指令都必须紧接在一条存放指令之后。因此，装入指令数总比存放指令数多后。因此，装入指令数总比存放指令数多1 1。所以只要。所以只要产生使装入指令数或存放指令数为最小值的代码段就产生使装入指令数或存放指令数为最小值的代码段就是最优的代码。是最优的代码。表达式树计算LR注：条件的代码段比条件的要少些，所以应被采用。生成代码段的算法CODE1procedure CODE1(T)procedure CODE1(T)if Tif T是叶子是叶子 then print (“LOAD”,DATA(T) then print (“LOAD”,DATA(T) return returnendifendifF=0 /F=0 /如果如果RCHILDRCHILD（T T）不是叶子，则将）不是叶子，则将F F置成置成1 1if RCHILD(T) if RCHILD(T) 不是叶子不是叶子 then then call CODE1(RCHILD(T) / call CODE1(RCHILD(T) /生成生成C CR R call TEMP(i); print(“STORE”, i); F=1 call TEMP(i); print(“STORE”, i); F=1endifendifcall CODE1(LCHILD(T) /call CODE1(LCHILD(T) /生成生成C CL Lif F=1 then print(DATA(T),i)if F=1 then print(DATA(T),i) call RETEMP(i) call RETEMP(i) else print(DATA(T),DATA(RCHILD(T) else print(DATA(T),DATA(RCHILD(T)endifendifend CODE1end CODE1例5更一般的情况n n现将机器A推广到另一种机器B。B有N1个可以执行算术运算的寄存器。n n对于B，有四种类型的机器指令：（1）LOAD M，R（2）STORE R，M（3）OP R1，M，R2（4）OP R1，R2，R3例 6(1)当N=1时，必须生成一条存放指令，而当N=2时，则 不需要生成存放指令。(2)LOAD的条数不再需要正好比STORE的条数多1。因此，为了最优化而只考虑LOAD数或STORE数就不够了。而要使它们的和取最小值。如何在机器B上生成最优代码段n n给定一个表达式E1、不用任何STORE指令可以算出E的值吗？2、不用任何STORE指令而计算E的值所需要寄存器的最小数量是多少？n n第一个问题答案是肯定的。n n下面讨论第二个问题。函数MR(P)的定义例 7机器B的代码生成器line procedure CODE2(T,i)line procedure CODE2(T,i)if Tif T是叶子是叶子 then then print(LOAD,DATA(T),R,i) print(LOAD,DATA(T),R,i) return returnendifendifL=LCHILD(T); R=RCHILD(T)L=LCHILD(T); R=RCHILD(T)casecase :MR(R)=0: /R :MR(R)=0: /R是叶子是叶子/ / call CODE2(L,i) call CODE2(L,i) print(DATA(T),R,i,DATA(R),R,i)print(DATA(T),R,i,DATA(R),R,i) :MR(L)=N and MR(R)=N: :MR(L)=N and MR(R)=N: call CODE2(R,i) call CODE2(R,i) call TEMP(S) call TEMP(S) print(STORE,R,i,S) print(STORE,R,i,S) call CODE2(L,i) call CODE2(L,i) print(DATA(T),R,i,S,R,i) print(DATA(T),R,i,S,R,i) call RETEMP(S) call RETEMP(S):MR(L)MR(R): /MR(L)N,:MR(L)MR(R): /MR(L)N,先计算先计算R R call CODE2(R,i) call CODE2(R,i) call CODE2(L,i+1) call CODE2(L,i+1) print(DATA(T),R,i+1,R,i,R,i) print(DATA(T),R,i+1,R,i,R,i):else:else: call CODE2(L,i) call CODE2(L,i) call CODE2(R,i+1) call CODE2(R,i+1) print(DATA(T),R,i,R,i +1,R,i) print(DATA(T),R,i,R,i +1,R,i)endcaseendcaseend CODE2end CODE2例 8LOAD d,R1LOAD e,R2ADD R2,f,R2MPY R1,R2,R1STORE R1,T1LOAD a,R1LOAD b,R2ADD R2,c,R2DIV R1,R2,R1ADD R1,T1,R1 N=2LOAD a,R1LOAD b,R2ADD R2,c,R2DIV R1,R2,R1LOAD d,R2LOAD e,R3ADD R3,f,R3MPY R2,R3,R2ADD R1,R2,R1N=3定理5.8n n对每一棵表达式树T， CODE2都生成正确的代码段。定义5.5n n已知寄存器数目为N，如果一个结点的两个儿子的MR值都至少为N，则称该结点为大结点(major)。n n如果一个结点是没有父亲的叶子，或者是它父亲的左儿子叶子，则称该结点为小结点(minor)。引理5.1n n设n是表达式树T中的大结点数。当表达式树T没有可交换的运算符且在运算符和运算量之间不存在任何关系（即不允许可结合和可分配的运算符以及公共子表达式）时，为了计算T的值至少需要n条STORE型指令。引理5.2n n对于任何一棵表达式树T，由CODE2所生成的代码段中的STORE型指令条数等于表达式树T中的大结点数。引理5.3n n设m是T中的小结点数，在引理5.1的假设下，计算T的代码段必须至少有m条LOAD指令。引理5.4n n对于任一表达式树T，由CODE2所生成的代码段中的LOAD指令条数等于T中的小结点数。定理5.9n n在引理5.1的条件下，算法CODE2生成最优代码段。5.3 双连通分图与深度优先检索n n本节重点双连通图的概念双连通图的概念关节点的概念关节点的概念深度优先检索深度优先检索n n本节难点关节点识别算法关节点识别算法双连通图的构造算法双连通图的构造算法连通图与双连通图14231095678图5.11一个连通图1243图5.12一个双连通图n n通信网通信网：图中结点表示通信站，边表示通信线路。图中结点表示通信站，边表示通信线路。n n下面两个图显然都是无向连通图下面两个图显然都是无向连通图, ,但却有不同的特性。但却有不同的特性。n n出现差异的原因在于这两个图的连通程度不同。出现差异的原因在于这两个图的连通程度不同。几个基本概念n n关节点：如果把无向连通图如果把无向连通图G G中某结点中某结点a a以及与以及与a a相关联相关联的所有边删去，得到二个或二个以上的非空分的所有边删去，得到二个或二个以上的非空分图，那么结点图，那么结点a a就称为就称为G G的关节点。的关节点。n n双连通图：如果无向连通图如果无向连通图G G根本不包含关节点，则称根本不包含关节点，则称G G为双连通图。为双连通图。n n双连通分图：最大双连通子图最大双连通子图双连通分图14231095678图5.13一个连通图142352785639310图5.14 连通分图下面我们的任务n n设计一个算法，测试某个连通图G是否双连通；n n若G不是双连通的，找出所有的关节点；n n确定一个适当的边集加到G上，将其变为一个双连通图。双连通分图性质n n连通图中，两个双连通分图至多有一个公共结点，且这个结点是关节点。n n任何一条边不可能同时在两个不同的双连通分图中（因为这需要两个公共结点）。n n由此，可得到把图G变成双连通图的算法。把连通图G变成一个双连通图1 for 每一个关节点 a do2 设B1,B2,Bk是包含结点a的双连通 分图;3 设vi是Bi的一个结点,且vi a,1i k4 将(vi,vi+1)加到G;5 repeat把连通图G变成一个双连通图10941325876关节点和双连通分图的识别n n怎么识别出关节点？n n怎么在识别出关节点后，识别出所有的双连通分图？n n几个概念：深度优先数（深度优先数（DFNDFN）树边树边逆边逆边交叉边交叉边关节点和双连通分图的识别14231095678图5.15一个连通图123456789101431092567812345678910图5.16中图的一棵深度优先生成树几个概念n n深度优先数（DFN）：DFN(1)=1,DFN(2)=6n n树边：实线边，代表生成树的边n n逆边：虚线边，代表不在生成树中的边关节点的识别n n深度优先生成树的两条重要的性质：深度优先生成树的两条重要的性质： 若若(u,v)(u,v)是是G G中任一条边，则相对于深度优先生成树中任一条边，则相对于深度优先生成树T T，或者，或者u u是是v v的祖先，或者的祖先，或者v v是是u u的祖先。即的祖先。即没有交叉边没有交叉边。（u,vu,v）是一条相对于生成树）是一条相对于生成树T T的交叉边指的是的交叉边指的是u u不是不是v v的祖先，的祖先，v v也不是也不是u u的祖先。的祖先。 当且仅当一棵深度优先生成树的根结点至少有两个儿当且仅当一棵深度优先生成树的根结点至少有两个儿子时，此根结点是关节点，如果子时，此根结点是关节点，如果u u是除根外的任一结点，是除根外的任一结点，那么当且仅当由那么当且仅当由u u的每一个儿子的每一个儿子w w出发，若只通过出发，若只通过w w的的子孙组成的一条路径和一条逆边就可到达子孙组成的一条路径和一条逆边就可到达u u的某个祖先的某个祖先时，则时，则u u就不是关节点。就不是关节点。关节点的识别n n对每个结点对每个结点u u，有，有L(u)L(u)定义如下：定义如下： L(u) = min L(u) = min DFN(u) DFN(u) , , min L(w) | wmin L(w) | w是是是是u u的儿子的儿子的儿子的儿子 , , min DFN(w) | (u,w)min DFN(w) | (u,w)是一条逆边是一条逆边是一条逆边是一条逆边 n n显然，显然，L(u)L(u)是是u u通过一条子孙路径且至多后随一通过一条子孙路径且至多后随一条逆边所可能到达的最低深度优先数。条逆边所可能到达的最低深度优先数。n n由上述讨论可知，如果由上述讨论可知，如果u u不是根，则当且仅当不是根，则当且仅当u u有一个使得有一个使得L(w)L(w) DFN(u)DFN(u)的儿子的儿子w w时，时，u u是一个是一个关节点。关节点。计算DFN和L的算法n n计算计算L(u)的方法的方法：按后根次序访问深度优先生成树的结点。n n确定G的关节点的工作： 1、完成对G的深度优先搜索，产生G的深度优先生成树T； 2、按后根次序访问树T的结点。算法5.11 计算DFN和L的算法line procedure ART(u,v)line procedure ART(u,v) /u /u是深度优先检索的开始结点。在深度优先生成树中，是深度优先检索的开始结点。在深度优先生成树中，u u若有父亲，若有父亲，那么那么v v就是它的父亲。假设数组就是它的父亲。假设数组DFNDFN是全局量，并将其初始化为是全局量，并将其初始化为0 0，numnum是全局变量，被初始化为是全局变量，被初始化为1 1。n n是是G G的结点数。的结点数。ARTART的初始调的初始调用是用是call ART(1,0)call ART(1,0)。/ / global DFN(n), L(n), num, n global DFN(n), L(n), num, n1 DFN(u)=num; L(u)=num; num=num+11 DFN(u)=num; L(u)=num; num=num+12 for 2 for 每一个邻接于每一个邻接于u u的结点的结点w dow do3 if DFN(w)=0 then call ART(w,u)3 if DFN(w)=0 then call ART(w,u)4 L(u)=min(L(u),L(w)4 L(u)=min(L(u),L(w)5 else if wv then L(u)=min(L(u),DFN(w)5 else if wv then L(u)=min(L(u),DFN(w)6 endif6 endif7 endif7 endif8 repeat8 repeat9 end ART9 end ART关节点的识别各结点的最低深度优先数是L(1:10)(1,1,1,1,6,8,6,6,5,4)关节点： 结点3：它的儿子结点10有L(10)4而DFN(3)=3。 结点2：儿子结点5有L(5)=6而DFN(2)6 结点5：儿子结点6有L(6)8而DFN(5)71431092567812345678910算法分析n n设图G有n个结点和e条边，G由邻接表表示，那么ART的计算时间为O(n+e)。因此L(1:n)可在时间O(n+e)内算出。n n一旦算出L(1:n)，G的关节点就能在O(n)时间内识别出来。n n因此识别关节点的总时间不超过O(n+e)。连通分图的识别n n要是在第3行调用ART之后，有L(w) DFN(u)，就可断定u或者是根，或者是关节点。n n不管u是否为根，也不管u有一个或是多个儿子，将边(u，w)和对ART的这次调用期间遇到的所有树边和逆边加在一起(除了包含在子树w中其它双连通分图的边以外)，构成一个双连通分图。连通分图的识别line procedure ART(u,v)line procedure ART(u,v) global DFN(n),L(n),num,n global DFN(n),L(n),num,n1 DFN(u)=num; L(u)=num; num=num+11 DFN(u)=num; L(u)=num; num=num+12 for 2 for 每一个邻接于每一个邻接于u u的结点的结点w dow do2.1 if vw and DFN(w)DFN(u) then 2.1 if vw and DFN(w)DFN(u) then 将将(u,w)(u,w)加到全程栈加到全程栈S S的顶部的顶部 endif endif3 if DFN(w)=0 then call ART(w,u)3 if DFN(w)=0 then call ART(w,u)3.1 if L(w) 3.1 if L(w) DFN(u) then DFN(u) then print(new bi-connected component) print(new bi-connected component)3.2 loop3.2 loop3.3 3.3 从栈从栈S S的顶部删去一条边的顶部删去一条边3.4 3.4 设这条边是设这条边是(x,y)(x,y)3.5 print(,x,y,)3.5 print(,x,y,)3.6 until(x,y)=(u,w) or (x,y)=(w,u) repeat3.6 until(x,y)=(u,w) or (x,y)=(w,u) repeat3.7 endif3.7 endif4 L(u)=min(L(u),L(w)4 L(u)=min(L(u),L(w)5 else if wv then 5 else if wv then L(u)=min(L(u),DFN(w) L(u)=min(L(u),DFN(w)6 endif6 endif7 endif7 endif8 repeat8 repeat9 end ART9 end ART定理5.10 当连通图G至少有两个点时，增加了2.1和3.13.7行的算法，ART正确地生成G的双连通分图。5.4 与/或图n n很多复杂问题很难或没法直接求解，但可以分解成一很多复杂问题很难或没法直接求解，但可以分解成一系列（类型不同）的子问题，而这些子问题又可反复系列（类型不同）的子问题，而这些子问题又可反复细分成一些更小的子问题，一直到分成一些可普通求细分成一些更小的子问题，一直到分成一些可普通求解的，相当与基本的问题为止。然后让这些分解成的解的，相当与基本的问题为止。然后让这些分解成的子问题的全部或部分解在导出原问题的解。子问题的全部或部分解在导出原问题的解。n n例：洗衣服问题例：洗衣服问题 某人一星期洗一次衣服，要做的事可以分为收集某人一星期洗一次衣服，要做的事可以分为收集脏衣服、洗衣服、干燥、熨衣服、叠好衣服并放入衣脏衣服、洗衣服、干燥、熨衣服、叠好衣服并放入衣柜。其中，某些事可采用不同的方法，如洗衣服可以柜。其中，某些事可采用不同的方法，如洗衣服可以是手洗或者是机器洗。干燥可以是晾干或者机器烘干。是手洗或者是机器洗。干燥可以是晾干或者机器烘干。与/或图n对于上述问题，可以用与/或图来表示。n与/或图是一个有向图：结点表示问题，一个结点的子孙代表与其相关联的子问题。用一条弧将那些可以联合导出其解的子结点连结在一起。如下图(a)中表示问题A可以通过求解子问题B和C来解出，或者可由单个求解子问题D或E来解出。n为使结点含义单一化，即它的解或者需要求解它所有的子孙得到，或者求解它的一个子孙便可得到，通过引入图(b)中虚结点可达到此目的。前一类结点称为与结点，后一类结点称为或结点。ABCDE(a)AAABCDE(b)洗衣服问题对应的与/或图下图为洗衣服问题的与/或图。图中，没有子孙的结点是终结点，它代表基本问题并标记上可解或不可解。可解的终结点用方框表示。洗衣服问题收集脏衣服洗干燥熨叠好并归堆手洗机器洗适当的更换装入并开始晾干机器烘干适当的更换装入并开始图5.17洗衣服问题对应的与/或图概念n n根据问题的与/或树判断该问题是否可解方法：对与对与/ /或树作后根次序周游就可得出答案。或树作后根次序周游就可得出答案。在算法执行过程中，一旦发现某与结点的一个儿在算法执行过程中，一旦发现某与结点的一个儿子结点不可解，或者发现某或结点的一个儿子结子结点不可解，或者发现某或结点的一个儿子结点可解，就立即终止该算法，这可减少算法的工点可解，就立即终止该算法，这可减少算法的工作量且对结果无任何影响。作量且对结果无任何影响。判断与/或树是否可解算法procedure SOLVE(T)procedure SOLVE(T)case case :T :T是终结点：是终结点：if Tif T可解可解 then return(1) then return(1) else return(0) else return(0) endif endif :T :T是与结点：是与结点： for T for T的每个儿子的每个儿子S doS do if SOLVE(S)=0 then return(0) if SOLVE(S)=0 then return(0) endif endif repeat repeat return(1) return(1) :else: for T :else: for T的每个儿子的每个儿子S doS do if SOLVE(S)=1 then return(1) endif if SOLVE(S)=1 then return(1) endif repeat repeat return(0) return(0)endcaseendcaseend SOLVE end SOLVE 生成问题的解树n n对于一个给定的复杂问题，不仅需要知道此问题是否对于一个给定的复杂问题，不仅需要知道此问题是否可解，而且希望求出问题的解树。可解，而且希望求出问题的解树。n n解树的结点可按宽度优先也可按深度优先的次序来生解树的结点可按宽度优先也可按深度优先的次序来生成。成。n n需要指出的是，一棵与需要指出的是，一棵与/ /或树可能有无穷的深度，在使或树可能有无穷的深度，在使用解树的深度优先生成算法的情况下，即使已知解树用解树的深度优先生成算法的情况下，即使已知解树存在，算法也可能导致所有生成的结点都在一条由根存在，算法也可能导致所有生成的结点都在一条由根出发的无穷深度的路径上，从而根本就不能确定出一出发的无穷深度的路径上，从而根本就不能确定出一棵解树，这一点可通过对生成深度作出某种限制获得棵解树，这一点可通过对生成深度作出某种限制获得解决。解决。n n宽度生成算法没有这样的缺点。宽度生成算法没有这样的缺点。宽度优先生成解树line procedure BFGEN(T,F)/F生成T中的儿子结点；T是根结点。终止时，若存在解树，则T是这解树的根/1 将队列Q初始化为空；VT2 loop3用F生成V的那些儿子 /检测V/4if V没有儿子 then 标记V为不可解 else 将V的所有不是叶子结点的儿子放入队列Q，将那些叶子结点 分别标上可解或不可解； 把V的所有儿子加入树T；5endif6call ASOLVE(T) /后序遍历T，将结点标是可解、不可解或可能可解的标记/7从树T删去所有标记为不可解的结点8if 根结点T标记为可解 then return(T) endif9从队列Q中删去以下的所有结点：它们在T中曾有一个祖先被标记为不可解或者在T中有一个标记为可解的祖先10if Q为空 then print(no solution); stop endif11删去队列Q的第一个元素；设此结点是V12 repeat13 end BFGEN 5.5 对策树n n拾火柴棍游戏假定盘上放有假定盘上放有n n支火柴，由奕者支火柴，由奕者A A和和B B两个人两个人参加比赛。参加比赛。比赛规则是：两名奕者轮流从盘中取走火柴，比赛规则是：两名奕者轮流从盘中取走火柴，每次从盘中取走每次从盘中取走1,21,2或或3 3支火柴均为合法着。支火柴均为合法着。否则，为非法着；拿走盘中最后一支火柴的否则，为非法着；拿走盘中最后一支火柴的奕者则负了这一局，当然另一名奕者则胜这奕者则负了这一局，当然另一名奕者则胜这一局。一局。对策树n n任何时刻盘中剩下的火柴数表示此时刻的棋局。任何时刻盘中剩下的火柴数表示此时刻的棋局。n n拾火柴棍游戏在任一时刻的状态则由此时的棋拾火柴棍游戏在任一时刻的状态则由此时的棋局和轮到走下一着的奕者一起所决定。局和轮到走下一着的奕者一起所决定。n n结局是表示胜局、负局或和局情况的棋局。其结局是表示胜局、负局或和局情况的棋局。其它棋局都是非终止棋局。它棋局都是非终止棋局。n n棋局序列棋局序列C C1 1,C,C2 2,C,Cmm称为有效期局序列：称为有效期局序列： C C1 1是开始棋局；是开始棋局； C Ci i(0im)(0im)是非终止棋局；是非终止棋局； 由由C Ci i得到得到C Ci+1i+1是走下述棋着实现的：若是走下述棋着实现的：若i i是奇数，则是奇数，则A A者走一合法棋着；若者走一合法棋着；若i i是偶数，则是偶数，则B B者走一合法棋着。者走一合法棋着。n=6的拾火柴棍游戏的完整对策树对策树n n估价函数估价函数E(X)E(X) E(X)E(X)以数值形式表示弈者在棋局以数值形式表示弈者在棋局X X下获胜机会的大小。下获胜机会的大小。 对于对策树结点比较少的搏弈游戏，对于对策树结点比较少的搏弈游戏，E(X)E(X)为：为： E(X)=1,-1| E(X)=1,-1| 若若X X为胜局，为胜局，E(X)=1E(X)=1， 若若X X为负局，为负局， E(X)=-1 E(X)=-1 一般情况：一般情况：V(X)=maxV(ci) 若X是方形结点，1id minV(ci) 若X是圆形结点，1id 一种假想博弈游戏的部分对策树对策树n n在具有大对策树的博弈游戏中，确定当前的对策时，采用了弈者通常所使用的办法，即预先向前看几着棋。n n在对策树中就是通过考察这一棋局下面几级的这一部分对策树，用估价函数E(X)来求取这棵子对策树叶子结点的值，然后得到其余结点的值，从而确定下一步要走的那着棋。对策树的后序遍历求值首先将最大最小过程的定义改写成如下形式： e(X) e(X) 若若X X是所生成子树的叶子结点是所生成子树的叶子结点V(X)= max-V(ci) 若若X X不是所生成子树的叶子结点且不是所生成子树的叶子结点且c ci(1id)(1id)是的儿子是的儿子式中，若是由走子的位置，则e(X)=E(X)；否则e(X)=-E(X)对策树的后序遍历求值procedure VE(X,L)procedure VE(X,L) if X if X是终局是终局 or L=0 then return(e(X) endif or L=0 then return(e(X) endif ans=-VE(c ans=-VE(c1 1,L-1),L-1) for i=2 to d do for i=2 to d do ans=max(ans,-VE(c ans=max(ans,-VE(ci i,L-1),L-1) repeat repeat return(ans) return(ans)end VEend VE-剪枝术-剪枝术n n通过对例子的进一步考察将会发现即使不生成图通过对例子的进一步考察将会发现即使不生成图5.205.20中的所中的所有的结点仍可精确计算出有的结点仍可精确计算出V(pV(p1111) )n n定义一个求最大值位置的定义一个求最大值位置的 值值, ,它是该位置迄今最大的可能值它是该位置迄今最大的可能值. .n n如果一个求最小值位置的值被判断为小于或等于它父亲的如果一个求最小值位置的值被判断为小于或等于它父亲的如果一个求最小值位置的值被判断为小于或等于它父亲的如果一个求最小值位置的值被判断为小于或等于它父亲的值值值值, , , ,那么那么那么那么, , , ,可以停止生成这个求最小值位置其余儿子的值可以停止生成这个求最小值位置其余儿子的值可以停止生成这个求最小值位置其余儿子的值可以停止生成这个求最小值位置其余儿子的值.(.(.(.(即即即即截断截断截断截断) ) ) )n n定义一个求最小值位置的定义一个求最小值位置的 值值, ,它是该位置迄今最小的可能值它是该位置迄今最小的可能值. .n n如果一个求最大值位置的值被判断为大于或等于它父亲的如果一个求最大值位置的值被判断为大于或等于它父亲的如果一个求最大值位置的值被判断为大于或等于它父亲的如果一个求最大值位置的值被判断为大于或等于它父亲的值值值值, , , ,那么那么那么那么, , , ,可以停止生成这个求最大值位置其余儿子的值可以停止生成这个求最大值位置其余儿子的值可以停止生成这个求最大值位置其余儿子的值可以停止生成这个求最大值位置其余儿子的值.(.(.(.(即即即即截断截断截断截断) ) ) )n n定义一个位置的定义一个位置的B B值是该位置迄今最大的可能值值是该位置迄今最大的可能值. .n n对于任一结点对于任一结点对于任一结点对于任一结点X,X,X,X,设设设设B B B B是该结点父亲的是该结点父亲的是该结点父亲的是该结点父亲的B B B B值且值且值且值且D=-B,D=-B,D=-B,D=-B,那么那么那么那么, , , ,如果如果如果如果X X X X的的的的值判断为大于或等于值判断为大于或等于值判断为大于或等于值判断为大于或等于D,D,D,D,则可以停止生成则可以停止生成则可以停止生成则可以停止生成X X X X的其它儿子的其它儿子的其它儿子的其它儿子.(.(.(.(即即即即-截断截断截断截断) ) ) )使用使用-截断规则对一棵对策树作后根次序求值截断规则对一棵对策树作后根次序求值procedure VEB(X,L,D)/使用-截断规则并只向前看L步/ if X是终点 or L=0 then return(e(X) endif ans-VEB(C1,L-1,) /V(X)迄今可能的最大值/ for i 2 to d do if ansD then return(ans) endif /使用-截断规则/ ans max(ans,-VEB(Ci,L-1,-ans) repeat return(ans)end VEB