计算机算法设计与分析

中国地质大学

研究生课程论文课程名称：算法设计与分析教师姓名:戴光明研究生姓名:研究生学号:**********研究生专业：***********所在院系:计算机学院类别：A.博士B.硕士yC进修生日期：2017.01.13

平时成绩：课程论文成绩：总成绩：评阅人签名：注：1、无评阅人签名成绩无效；2、必须用钢笔或圆珠笔批阅，用铅笔阅卷无效；3、如有平时成绩，必须在上面评分表中标出，并计算入总成绩。目录TOC\o"1-5"\h\z\o"CurrentDocument"第一章算法导引.4一、算法及其特性4\o"CurrentDocument"二、算法分析4\o"CurrentDocument"第二章分治法6\o"CurrentDocument"一、一般方法6\o"CurrentDocument"二、二分检索法6\o"CurrentDocument"三、归并分类.7\o"CurrentDocument"四、特斯拉森矩阵乘法8\o"CurrentDocument"五、总结8\o"CurrentDocument"第三章贪心算法9\o"CurrentDocument"一、一般方法9\o"CurrentDocument"二、背包问题9三、最小生成树10\o"CurrentDocument"四、单源点最短路径11\o"CurrentDocument"第四章动态规划12\o"CurrentDocument"一、优化问题12\o"CurrentDocument"二、一般原理12\o"CurrentDocument"三、多段图12\o"CurrentDocument"四、每对结点间的最短路径14\o"CurrentDocument"五、最优二分检索树14\o"CurrentDocument"六、0-1背包问题16\o"CurrentDocument"七、调度问题16\o"CurrentDocument"八、TSP问题17\o"CurrentDocument"第五章基本检索与周游算法18\o"CurrentDocument"一、一般方法18\o"CurrentDocument"二、双连通图和深度优先检索19\o"CurrentDocument"三、决策树（博弈树）21第六章回溯法22第七章分支限界法22一、一般方法22\o"CurrentDocument"二、回溯法解0-1背包问题22\o"CurrentDocument"三、分支限界法解0-1背包问题23\o"CurrentDocument"第八章总结24第一章算法导引课前题目:编写程序:1、编写两个矩阵相乘的程序;2、如图，菱形ABCD中，E是AD的中点，EF垂直于AC交CB的延长线于F，求证四边形AFBE是平行四边形。一、图1-1平行四边形一、图1-1平行四边形算法及其特性1、算法是什么？算法是计算的方法。2、什么是计算？1）计算是基于规则的符号串的变换；2）计算是基于规则的物理信息的变换；3）计算是基于规则的信息的变换。为了使计算机械化，图灵提出了图灵模型，在此基础上将理论进行技术实现，1946年诞生了第一台计算机（读写头、纸带、四元组），在内存条上进行输入输出。3、算法的特性？4）无二义性：由于算法是由机器执行的，所以算法的每一步都必须是确定的。5）能行性（可计算性与不可计算性）：算法的每一步机器都能够执行（计算机能够解决的问题是有限的）。6）有限性（可计算性与计算复杂性）。二、算法分析算法分析就是分析算法的复杂性。1、算法分析的计算机模型：1）冯诺依曼计算机：串行执行的计算机。2）均匀存储：假设存储量是够的。3）基本运算的时间为整数。2、两个重要的量：1）问题的规模n。2）频率的计数f（n）。3、求时间复杂度：1）冒泡排序：BubblesortA(1->n)doi->1tondoj->i+1tonifA[j]<A[j]thenexchangeA[j]andA[j];continuej;continueI;printA(i->n);计算过程：f(n)=nC1+n(n+1)C2/2+nC3f(n)=n(C1+C2/2+C3)+mC2/2对以上公式进行简化，表示如下：f(n)=n2C4+nC5(其中C4=C1+C2/2+C3，C5=C2/2)进行分析后可知，运算的上界为：g(n)=O(n2)当n>=n0时，若n足够大，f(n)<=Cn2。2)汉诺塔：hanoi(intn,charleft,charmiddle,charright){if(n==1)printf(left->right)else{hanoi(n-1,left,right,middle)print(left->right)hanoi(n-1,middle,left,right)}}设时间为f(n),规模为n:f(n)=2f(n-1)+C1=2(f(n-2)+C1)+C1=……=C12n所以g(n)=O(2n)。3、根据算法的时间界g(n)对算法进行分类：两类：多项式时间复杂度算法P(理论可行实际也可行)：O(c)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指数时间复杂度算法NP(理论可行实际不可行，需要限制规模或用近似解)：O(2n)<O(n!)<O(nn)P->NP方法：智能算法(GA)、随机过程。第二章分治法算法设计的三个基础技术:由难到易的校正技术例，泰勒公式：f(X)*(X0)+广(X0)(x-X0)+f"(X0)(x-X0)2+求V2的值，每次取两项，经过多次泰勒公式展开可以得到方程中无线趋近合理的解。由粗到细的松弛技术例，割圆术求圆的面积，超松弛迭代：S=S--^6(S-S)307219210519296由大到小的分治技术(加权的方法)一、一般方法procedureDAN(p,q)globalifSmall(p,q)thenreturnG(p,q)elsem<-DIVIDE(p,q)return(Combine(DAN(p,m),DAN(m+1,q)))endifendDAN设算法规模为n=q-p+1，T(n)g(n),几足够小2T(?+f㈤，n为其它二、二分检索法输入n个有序数，输出x把n个数输入，放到二叉树，使构造的二叉树树的高度最小。设算法规模为n=q-p+1，T(n)g(n),几足够小2T(?+f㈤，n为其它ProcedureBINSRCH(A,n,x,j)integerlow,high,mid,j,n;low—1;high—n.whilelow<highdomid—[low+high]/2case:x<A(mid):high—mid-1:x>A(mid):high—mid+1:else:j—mid;returnendcaserepeatendBINSRCH设树的高度为k,2k+1>=n,k=log(n-1)，所以k=O(logn)三、归并分类procedureMERGESORT(low,high)integeriflow<highthenmid<-[(low+high)/2]callMERGESORT(low,mid)callMERGESORT(mid+1,high)callMERGE(low,mid,high)endifend设规模为n，则fE={a,n=1一(2f(n)+nc,n>1设n=2knnf(n)=2f(-)+nc=22f(—)+2nc=…=2^/(1)+knc=an+nlogC2较树必定至少有n!个外结点，每个外结点表示一种可能的分类序列。设树的高度为h，则2h>=n!设比较树的最小高度为T(n)，则：n!M2T(n)而当n>1时有：n!>n(n-1)(n-2)…([n/2])>(n/2)n/2因此，对于n>=4有：T(n)>(n/2)log(n/2)>(n/4)logn故以比较为基础的分类算法的最坏情况的时间下界为O(nlogn)。四、特斯拉森矩阵乘法工程计算Ax=B，方程个数和自变量的个数关系:当方程个数多于自变量个数时：超定;当方程个数少于自变量个数时：欠定;当方程个数等于自变量个数是：适定。矩阵相乘：CrAnmBmiCij=z^u%Ajfbn比较小其中，b和d其中，b和d是常数。(7T(n/2)+an2n比较大根据斯特拉森的设计推理：T(n)={7T(3)+席>2其中，a，b是常数。求解此递推关系式，得：T(n)=an2(1+7+(7)2+…+(7)k1)+7叮(1)=444<cn2(Z)logn=(c+I)nlog7=O(nlog7)次O(n2.81)4五、总结分治法作用：1、由大化小求解(并行算法，空间换时间)；2、能有效的降低算法的时间复杂度。(O(n)->O(logn)，O(n2)->O(nlogn)，O(n3)->O(n2.8i))第三章贪心算法一、一般方法给定n个输入，找n个输入的一个子集，这个子集要满足一些约束条件，满足约束条件的子集可能会很多，把满足约束条件的子集都可以叫可行解。我们根据要求去定义一个目标函数，根据目标函数，使目标函数取得的极值的可行解叫最优解。例：给定图（V，E）-＞树-＞树的边权值为最小-＞最小生成树根据问题的特性去找一个量度标准，算法证明包括：证明量度标准、算法正确性证明。一般方法：ProcedureGREEDY（A,n）solution—fori—1tondox—SELECT（A）ifFEASIBLE（solution,x）thensolution—UNION（solution,x）endifrepeatreturn（solution）end二、背包问题有一个背包，容量为M，现有物品N件，物品的质量为W1，W2,....，Wn，权值分别为P1，P2，...，Pn。1、问题分类设有N件物品分别装入X1，X2,...，Xn（代表物品装入的比例）。其中有七f'0’1｝，此时问题变为0、1背包问题，也就是该物品要么全部放入到背包中，要么不放入到背包中，此时为NP问题。若有Xf"'」，此时该问题变为部分背包问题，也就是该问题可以把物品只放入一部分到背包中，利用W/M进行排序，按排序从大到小放入到背包中，直到背包容量装满，此时为P问题。l^XW<M

ii

i=l^XW<M

ii

i=1max^XW

ii

i=1约束条件：目标函数：利用上述的两个表达函数，在满足约束函数条件的前提下，求取目标函数的最大值，实现背包问题的求解。例：n=3，M=20，（P1，P2，P3）=（25，24，15），（W1，W2，W3）=（18，15，10），（X1，X2,X3)=?量度标准：X1,X2,X3属在0~1之间。可能的可行解如下：一一(x1,x2,x3)£wxii16.5£px24.25ii〃没有放满背包〃①(1/2,1/3,1/4)②(1,2/15,0)2028.2〃效益由大到小顺序装包③(0,2/3,1)2031〃质量由大到小顺序装包④(0,1,1/2)2031.5单位质量的效益值从大到小顺序装包(最优)三、最小生成树定义：设G(V,E)是一个无向连通图。如果G的生成子图T=(V,E,)是一棵生成树，则称T是G的一棵生成树。当树的各边权重之和达到最小时，则称之为最小生成树。Prim算法的基本思想是：设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加AV，此时就构建出了一颗MST。普里姆算法：procedurePRIM(E,COST,n,T,mincost)//E是G的边集。COST(n,n)是n结点图G的成本邻接矩阵，矩阵元素COST(i,j)是一个正实数，如果不存在边(i,j)，则为+8。计算一棵最小生成树并把它作为一个集合存放到数组T(1:n-1,2)中(冷1)冲,2))是最小成本生成树的一条边。最小成本生成树的总成本最后赋给mincostoNEAR(j)是树中使得COST(j,NEAR(j))是对NEAR(j)所有选择中的最小值〃realCOST(n,n),mincostintegerNEAR(n),n,i,j,k,l,T(1:n-1,2)(k,l)-具有最小成本的边mincost—COST(k,l)(T(l,1),T(l,2))-(k,l)fori—1tondo//将NEAR置初值//ifCOST(i,l)<COST(i,k)thenNEAR(i)—lelseNEAR(i)—kendifrepeatNEAR(k)—NEAR(l)—0fori—2ton-1do//找T的其余n-2条边〃设j是NEAR(j)N0且COST(j,NEAR(j))最小的下标(T(i,1),T(i,2))—(j,NEAR(j))mincost—mincost+COST(j,NEAR(j))NEAR(j)—0fork—1tondo//修改NEAR//ifNEAR(k)^0andCOST(k,NEAR(k))>COST(k,j)thenNEAR(k)—jendifrepeatrepeatifmincost^8thenprint(‘nospanningtree’)endifendPRIM计算复杂性：O(n2)四、单源点最短路径即一直的一个n结点有向图G=(V,E)和边的权函数C(e),求由G中某指定结点V。到其他各个点的最短路径。生成最短路径的贪心算法：ProcedureSHORTEST(V,COST,DIST,n)//G是一个有n个结点的有向图，它由其邻接矩阵COST(n,n)表示，DIST(n,n)表示，DIST(j)被置以结点V到结点j的最短路径的长度，这里1<j<n;DIST(v)被置为0//BooleanS(1:n);realCOST(1:n,1:n),DIST(1:n)Integeru,v,n,num,i,wFori—1tondoS(i)-0;DIST(i)-COST(v,i)RepeatS(v)-1;DIST(v)-0Forsum—2ton-1doS(u)—1For所有S(w)=0的结点wdoDIST(w)—min(DIST(w),DIST(w)+COST(u,w))RepeatRepeatEnd生成最短路径的贪心算法的计算时间是O(n2)。第四章动态规划一、优化问题1、分类线性优化与非线性优化约束优化和无约束优化确定性优化和随意性优化⑷动态优化和静态优化⑸单目标优化与多目标优化(最值与平衡解)2、优化问题求解难度上可分为⑴函数优化：目标函数⑵参数优化(3)模型优化：模型是什么样的，建立模型二、一般原理用来求解优化问题。特点：⑴多阶段决策(2)满足最优解原理：不论初始决策是什么样的，后面的决策相对初始决策产生一个最优的决策。三、多段图最优性原理对多段图问题成立，在多段图中求从s到t的一条最小成本的路径，可以看作是在k-2个段作出某种决策的结果，其中第i(1WiWk-2)次决策决定Vi+1中的哪个结点在这条路径上。令源点s编号为1，然后依次对V2、V3・・・Vk-1中的结点编号，汇点t编号为n。如下图所示：图4-1一个5段图1、由前向后推设BP(i,j)是一条从源点s到Vi中的结点j的最小成本路径，BCOST(I,j)是这条路径的成本则向后递推式为BCOST(i,j)=min{BCOST(i—1,l)+c(l,j)}心(i,j)^e对图中所示的多段图采用向后策略递推：第2段BCOST(2,2)=9BCOST(2,3)=7BCOST(2,4)=3BCOST(2,5)=2第3段BCOST(3,6)=min{BCOST(2,2)+4,BCOST(2,3)+2}=9BCOST(3,7)=min{BCOST(2,2)+2,BCOST(2,3)+7,BCOST(2,5)+11}=11BCOST(3,8)=min{BCOST(2,4)+11,BCOST(2,5)+8}=10第4段BCOST(4,9)=min{BCOST(3,6)+6,BCOST(3,7)+4}=15BCOST(4,10)=min{BCOST(3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5}=14BCOST(4,11)=min{BCOST(3,8)+6}=16第5段BCOST(5,12)=min{BCOST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5}=16S到t的最小成本路径的成本=16最小路径的求取：记BD(i,j)=每一COST(i,j)的决策，即使COST(i-1,l)+c(l,j)取得最小值的l值。例：BD(3,6)=3,BD(3,7)=2,BD(3,8)=5,BD(4,9)=6,BD(4,10)=7,BD(4,11)=8,BD(5,12)=10根据D(5,12)的决策值向前递推求取最小成本路径：v4=BD(5,12)=10,v3=BD(4,BD(5,12))=7,v2=BD(3,BD(4,BD(5,12)))=BD(3,7)=2，故由s到t的最小成本路径是：1-2-7-10-122、由后向前推设P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径，COST(i,j)是这条路径的成本。设i表示Vi,j表示Vi中的结点号向前递推式为COST(i,j)=min{c(j,l)+COST(i+1,l)}lEV.(j,l%E对图中所示的多段图采用向前策略递推：第4段COST(4,9)=c(9,12)=4COST(4,10)=c(10,12)=2COST(4,11)=c(11,12)=5第3段COST(3,6)=min{6+COST(4,9),5+COST(4,10)}=7COST(3,7)=min{4+COST(4,9),3+COST(4,10)}=5COST(3,8)=min{5+COST(4,10),6+COST(4,11)}=7第2段COST(2,2)=min{4+COST(3,6),2+COST(3,7),1+COST(3,8)}=7COST(2,3)=9COST(2,4)=18COST(2,5)=15第1段COST(1,1)=min{9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)}=16S到t的最小成本路径的成本=16最小路径的求取：记D(i,j)=每一COST(i,j)的决策即，使c(j,l)+COST(i+1,l)取得最小值的l值。例：D(3,6)=10,D(3,7)=10,D(3,8)=10,D(2,2)=7,D(2,3)=6,D(2,4)=8,D(2,5)=8,D(1,1)=2,根据D(1,1)的决策值向后递推求取最小成本路径：v2=D(1,1)=2,v3=D(2,D(1,1))=7,v4=D(3,D(2,D(1,1)))=D(3,7)=10,故由s到t的最小成本路径是：1-2-7-10-12四、每对结点间的最短路径设G=(V,E)是一个有n个结点的有向图，C是G的成本邻接矩阵，1Wi,jWn，则C中元素有：1^。『i=jc(ij)=边知》的成本』i¥=jfi<ij>EE(G)8m由且则每对结点之间的最短路径问题即是求满足下述条件的矩阵A，A中的任一元素A(i,j)代表结点i到结点j的最短路径长度。若利用单源最短路径算法求解，那么计算n个结点的单源最短路径的时间复杂度为O(n3)。若利用动态规划策略求解，可以将求解G中每对结点之间的最短路径问题转化成一个多阶段决策过程。设Ak(i,j)表示从i至Uj并且不经过比k还大的结点的最短路径长度，则A(i,j)=Ak(i,j)，即由i到j的最短路径不通过比编号k还大的结点。若该路径经过结点k，则Ak(i,j)=Ak-i(i,k)+Ak-i(k,j)，若该路径不经过结点k，则Ak(i,j)=Ak-i(i,j)，故可得Ak(i,j)=min{Ak-i(i,j)，Ak-i(i,k)+Ak-i(k,j)}。每对结点间的最短路径长度算法描述如下：procedureALL-PATHS(COST,A,n)//COST(n,n)是n结点图的成本邻接矩阵；A(i,j)是结点vi到vj的最短路径的成本；COST(i,i)=0,1WiWn//integerI,j,k,n;realCOST(n,n),A(n,n)fori—1tondoforj—1tondoA(i,j)—COST(i,j)〃用COST(i,j)对A0赋初值//repeatrepeatfork—1tondofori—1tondoforj—1tondoA(i,j)—min{A(i,j)，A(i,k)+A(k,j)}repeatrepeatrepeatendALL-PATHS计算时间为O(n3)。五、最优二分检索树设给定的标识符集合是{a1,a2,…,an}，并假定a1<a2<…<an。设P(i)是对ai检索的概率，Q(i)是正被检索的标识符X恰好满足ai<X<ai+1，0WiWn(设a0=-^,an+1=+^)时的概率，即一种不成功检索情况下的概率，则所有成功检索的概率为EP⑺，所有不成功检索的概率为ZQ(i)，考虑所有可能的成功和不成功检索共2n+1种可能1的"情况，则有ZP(i)+ZQ(iT=1。设Ei为不成功检索的等价类，则预期总的成本表示如下：1缶n0<i<nZP(i)*level(a)+ZQ(i)*(level(Ei)-1)i1<i<n其中左子树、右子树成本分别为：TOC\o"1-5"\h\zCOST(L)=SP(i)*level(a)+2Q(i)*(level(E)-1)ii1^i<k05^kCOST(R)=乙P(i)*level(a)+乙Q(i)*(level(E)-1)iik<i<nk<i<nw(i,j)=Q(i)+Zj1(Q(l)+P(l))则原二分检索树的预期成本可表示为：COST(T)=P(k)+COST(L)+COST(R)+W(0R1)+W(k,n)若T最优二分检索树，则COST(L)和COST(R)将分别是包含③容)…,ak-1和E0,E1,-,Ek_1及ak±,ak+2,…,an和Ek,Ek+1，…,En的最优二分检索(子)树。如图：图4-1二分检索树记由ai+1,ai+2,…,aj和Ei,Ei+1,…,Ej构成的二分检索树的成本为C(i,j)，则对于最优二分检索树T有，COST(L)=C(0,k-1),COST(R)=C(k,n),则C(0,n)=min{C(0,k-1)+C(k,n)+P(k)+W(0,k-1)+W(k,n)}对任何C(i,j)有1<k<nC(i,j)=min{C(i,k-1)+C(k,j)+P(k)+W(i,k-1)+W(k,j)}i<k<j=min{C(i,k-1)+C(k,j)}+W(i,j)i<k<j当j-i=m时，有n-m+1个C(i,j)要计算，C(i,j)的计算O(m)，每个C(i,j)要求找出m个量中的最小值，则n-m+1个C(i,j)的计算时间为O(nm-m2)，对所有可能的m，总计算时间为2(nm一m2)=0(n3)1<m<n例：设P(4)=(3,3,1,1)，Q(4)=(2,3,1,1,1),w(i,i)=Q(i)，c(i,i)=0，R(i,i)=0。w(0,1)=P(1)+Q(0)+Q(1)+w(0,0)=8c(0,1)=min{c(0,1)+c(1,1)}+w(0,1)=8R(0,1)=1w(1,2)=P(2)+Q(1)+Q(2)+w(1,1)=7c(1,2)=min{c(1,1)+c(2,2)}+w(1,2)=7R(1,2)=2w(2,3)=P(3)+Q(4)+w(2,2)=3c(2,3)=min{c(2,2)+c(3,3)}+w(2,3)=3R(2,3)=3w(3,4)=P(4)+Q(5)+w(3,3)=3c(3,4)=min{c(3,3)+c(4,4)}+w(3,4)=3R(3,4)=4最后计算可以得出w(0,4)，c(0,4)，R(0,4)。

计算所有的c(i计算所有的c(i,i)=0,R(i,i)的总时间:>(nm—m2)=0(睥)1mn六、0-1背包问题n件物品，背包容量为M，P1，P2，...，Pn为价值，W1，W2，....，Wn为容量。装包方法：目标函数：Zpx£Wx<X..iiii1<1<j1<i<j约束条件：x.=0或1,p>0,w>0,1<i<j解答方法1：真值表方法(穷举法)。'11解答方法2：设fn-1(x)代表包容量为x，装W1，W2,....，Wn-1后的最大效益值。当将Wn装入背包时：fn(X)=fn-1(X-wn)+pnfn(X)=max{fn-1(X),fn-1(X-wn)+pn}j代表1到n之间的数：fi(X)=max{fj-1(X),fj-1(X-wj)+pj}。例：n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(123)，M=6,其递推计算过程：由fi=fi-1(x-wi)+pi可得：f1(x)=max{f0(x),f0(x-2)+1}f2=max{f1(x),f1(x-3)+2}七、调度问题f2=max{f1(x),f1(x-3)+2}相同处理机调度PVM：n个作业，每个作业需时(Jt2，…，tn)，设有两个相同的处理机，给出最优调度方案，最优调度方案所需时间为("、+•••+“,2。其实是子集和数的问题，是一个NPhard问题。流水线调度：例：n+2个作业，m=3，t1i=a.，t2i=0，t3.=a.，1WiWn；t1,n+1=T/2，t2,n+1=T，t3,i=0；t1,n+2=0，京2=T，t3,n+2=T/2。其中，t=2=j印。m表示第i个任务在第一台机器上的时间。以长为标准，最好的调度方案是2T。七，T/2ti，n+1t1,i，T/2t2,n+2t2，n+1tn，T/2t3，n+1方案是2T。七，T/2ti，n+1t1,i，T/2t2,n+2t2，n+1tn，T/2t3，n+1t1，i，T/2P1P2P33T2T+二2第一台机器所需时间:z&印+2第一台机器所需时间:T+T2T第一台机器所需时间:z&缶+2例：有n=4个作业，每个作业两个任务：(a1,a2,a3,a4)=(3,(b1,b2,b3,b4)=(6,—3T24,8,10)2,9,15)(b2a1a2b1a3b3a4b4),即t1t3t4t2。八、TSP问题这是一个NPhard问题，时间复杂度为O(n!)。令g(i，S)为从i出发，经过S(S图中点集的子集)，g(i,S)表示从i点出发，经过S中所有的结点一次且仅一次，回到出发点i的最短路径。S-{k})}。g(i,{1,2,3，，n})=min{cik+g(k例如对于矩阵：r°1°152°5°91°613°12.889°,C(4,4)ggggggggggggg(2(3(4(2(2(3(3(4(4(2(3(4(10)0)0){3}){4}){2}){4}){2}){3}){3{2{2{2,=C21=5；=C31=6；=C41=8；=min{C23+g=min{C24+g=min{C32+g=min{C34+g=min{C42+g=min{C43+g(3(4(2(4(2(30)0)0)0)0)0)(3(2(2}=15；}=18；}=18；}=20；}=13；}=15；4})=min{C23+g4})=min{C32+g3})=min{C42+g3,4})=min{C12+g(2{4}),C24+g{4}),C34+g{3}),C43+g{3,4}),C13+g(4,(4,(4,}=25；}=25；}=23；{3}){2}){2})(3,{2,4}),C14+g(4,{2,3})}=35；所以路径为132343331,时间复杂度O(2nn2)。第五章基本检索与周游算法一、一般方法1、树的三种遍历方式图5-1给定二叉树中根：FDHGIBEAC先根：ABDFGHIEC后根：FHIGDEBCA2、图的生成树图5-2给定连通图二、双连通图和深度优先检索图5-5双连通分图双连通分图深度优先检索树:图5-6双连通分图深度优先检索树深度优先生成树中的虚线条代表逆边，实线条代表树边，结点旁的数代表深度优先树用DFN表示。最低深度优先数L(u)=min｛DFN(u)，min(L(w)|w是u的儿子)｝，min｛DFN(w)|(u,w)是一条逆边｝｝，而且当且仅当u有一个使得L(w)>=DFN(u)的儿子w时，u是一个关节点。按后根的次序去各结点的最低深度优先数DFN(u)是：L(10)=4L(9)=5L(6)=8L(8)=6L(7)=6L(5)=6L(2)=1L(3)=1L(4)=1L(1)=1对于关节点：除根结点以外的其它结点，L(w)NDFN(u)且w是u的儿子的结点是关节点，当然叶子结点不用考虑。结点3：儿子结点10有L(10)=4而DFN(3)=3。结点2：儿子结点5有L(5)=6而DFN(2)=6结点5：儿子结点6有L(6)=8而DFN(5)=7由连通图的分类可知分为单连通分图、双连通分图两种类型，每一个图上都有一定的关节点，要识别出图上所有的关节点，根据各个关节点的连通性，找到符合条件的通路。对于宽度优先搜索和深度优先搜索，在这里，首先要对各个关节点之间的连接是单连通还是双连通的关系进行确定，再找到在一个连通图中关结点之间是有实边连接时，还有没有逆边连接，实边用实线来表示，逆边用虚线来表示，再根^FS算法和BFS算法进行实现，找出符合条件的最优路径。三、决策树（博弈树）对策树类问题的本质思想，是起源于博弈类游戏，比如，在一盘棋赛中，对弈各方都要根据当前的局势，分析和预见以后可能出现的局面，决定自己要采取的各种对策，以争取更好的结果，博弈类问题是一种竞争，终局是表示为胜局、负局或者和局的情况的棋局，其它的都是非终止棋局。博弈过程在计算机里表示为对策树，对棋局进行判断的评价函数E（X）是maxmin的过程，该过程可采用剪枝策略，如a邛截断。a截断：如果一个求最小值位置的值判断为小于或等于它父亲的a值，那么可以停止生成这个求最小值位置其余儿子的值，在这种规则下终止生成结点值的行动称为a截断。P截断：如果一个求最大值位置的值判断为大于或等于它父亲的P值，那么可以停止生成这个求最大值位置其余儿子的值，在这种规则下终止生成结点值的行动称为0截断。第六章回溯法第七章分支限界法回溯法：深度优先搜索+限界函数分支限界法：宽度优先搜索+限界函数+LC（最小成本）一、一般方法回溯法其实是求n元组的问题。所要求的解必