算法分析与设计基本检索与周游方法.ppt

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