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

1、OP X OP可以是ADD，SUB，MPY或DIV。MPY c注：条件的代码段比条件的要少些，所以应被采用。(1)当N=1时，必需生成一条存放指令，而当N=2时，那么 不需求生成存放指令。(2)LOAD的条数不再需求正好比STORE的条数多1。因此，为了最优化而只思索LOAD数或STORE数就不够了。而要使它们的和取最小值。LOAD 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,R

2、2DIV R1,R2,R1LOAD d,R2LOAD e,R3ADD R3,f,R3MPY R2,R3,R2ADD R1,R2,R1N=314231095678图5.11一个连通图1243图5.12一个双连通5.13一个连通图142352785639310图5.14 连通分图1094132587614231095678图5.15一个连通图123456789101431092567812345678910图5.16中图的一棵深度优先生成树各结点的最低深度优先数是L(1:10)(1,1,1,1,6,8,6,6,5,4)关节点： 结点3：它的儿子结点10有L(10)4而DF

3、N(3)=3。 结点2：儿子结点5有L(5)=6而DFN(2)6 结点5：儿子结点6有L(6)8而DFN(5)71431092567812345678910定理5.10 当连通图G至少有两个点时，添加了2.1和3.13.7行的算法，ART正确地生成G的双连通分图。n对于上述问题，可以用与/或图来表示。n与/或图是一个有向图：结点表示问题，一个结点的子孙代表与其相关联的子问题。用一条弧将那些可以结合导出其解的子结点连结在一同。如以下图(a)中表示问题A可以经过求解子问题B和C来解出，或者可由单个求解子问题D或E来解出。n为使结点含义单一化，即它的解或者需求求解它一切的子孙得到，或者求解它的一个子

4、孙便可得到，经过引入图(b)中虚结点可到达此目的。前一类结点称为与结点，后一类结点称为或结点。ABCDE(a)AAABCDE(b)以下图为洗衣服问题的与/或图。图中，没有子孙的结点是终结点，它代表根本问题并标志上可解或不可解。可解的终结点用方框表示。洗衣服问题搜集脏衣服洗枯燥熨叠好并归堆手洗机器洗适当的改换装入并开场晾干机器烘干适当的改换装入并开场图5.17洗衣服问题对应的与/或图line procedure BFGEN(T,F)/F生成T中的儿子结点；T是根结点。终止时，假设存在解树，那么T是这解树的根/1 将队列Q初始化为空；VT2 loop用F生成V的那些儿子 /检测V/if V没有儿子

5、 then 标志V为不可解 else 将V的一切不是叶子结点的儿子放入队列Q，将那些叶子结点 分别标上可解或不可解； 把V的一切儿子参与树T；endifcall ASOLVE(T) /后序遍历T，将结点标是可解、不可解或能够可解的标志/从树T删去一切标志为不可解的结点if 根结点T标志为可解 then return(T) endif从队列Q中删去以下的一切结点：它们在T中曾有一个祖先被标志为不可解或者在T中有一个标志为可解的祖先if Q为空 then print(no solution); stop endif删去队列Q的第一个元素；设此结点是V12 repeat13 end BFGEN V(X)=maxV(ci) 假设X是方形结点，1id minV(ci) 假设X是圆形结点，1id 式中，假设是由走子的位置，那么e(X)=E(X)；否那么e(X)=-E(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