计算机算法设计与

1、计算机算法设计与分析中 国 地 质 大 学研究生课程论文课程名称: 算法设计与分析 教师姓名: 戴光明 研究生姓名: 研究生学号: 120161* 研究生专业: * 所在院系: 计算机学院 类别: A.博士 B.硕士 C.进修生 日期: 2017.01.13 评 语对课程论文的评语：平时成绩：课程论文成绩：总 成 绩：评阅人签名：注：1、无评阅人签名成绩无效；2、必须用钢笔或圆珠笔批阅，用铅笔阅卷无效；3、 如有平时成绩，必须在上面评分表中标出，并计算入总成绩。目录第一章算法导引4一、算法及其特性4二、算法分析4第二章分治法6一、一般方法6二、二分检索法6三、归并分类7四、特斯拉森矩阵乘法8五

2、、总结8第三章贪心算法9一、一般方法9二、背包问题9三、最小生成树10四、单源点最短路径11第四章动态规划12一、优化问题12二、一般原理12三、多段图12四、每对结点间的最短路径14五、最优二分检索树14六、0-1背包问题16七、调度问题16八、TSP问题17第五章基本检索与周游算法18一、一般方法18二、双连通图和深度优先检索19三、决策树（博弈树）21第六章回溯法22第七章分支限界法22一、一般方法22二、回溯法解0-1背包问题22三、分支限界法解0-1背包问题23第八章总结24第一章 算法导引课前题目：编写程序：1、 编写两个矩阵相乘的程序；2、 如图，菱形ABCD中，E是AD的中点，

3、EF垂直于AC交CB的延长线于F，求证四边形AFBE是平行四边形。AEDFBNMC图1-1 平行四边形一、 算法及其特性1、算法是什么？ 算法是计算的方法。2、什么是计算？1) 计算是基于规则的符号串的变换；2) 计算是基于规则的物理信息的变换；3) 计算是基于规则的信息的变换。为了使计算机械化，图灵提出了图灵模型，在此基础上将理论进行技术实现，1946年诞生了第一台计算机（读写头、纸带、四元组），在内存条上进行输入输出。3、 算法的特性？4) 无二义性：由于算法是由机器执行的，所以算法的每一步都必须是确定的。5) 能行性（可计算性与不可计算性）：算法的每一步机器都能够执行（计算机能够解决的问

4、题是有限的）。6) 有限性（可计算性与计算复杂性）。二、 算法分析算法分析就是分析算法的复杂性。1、 算法分析的计算机模型：1） 冯诺依曼计算机：串行执行的计算机。2） 均匀存储：假设存储量是够的。3） 基本运算的时间为整数。2、 两个重要的量：1） 问题的规模n。2） 频率的计数f(n)。3、求时间复杂度：1） 冒泡排序：Bubblesort A(1->n)do i->1 to ndo j->i+1 to nif Aj < Aj then exchange Aj and Aj;continue j;continue I;print A(i->n); 计算过程：f

5、(n) = nC1 + n(n+1)C2/2 + nC3f(n) = n(C1 + C2/2 + C3) + n2C2/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 (int n,char left,char middle,char right) if (n=1) printf (left-> right) else hanoi (n-1, left, ri

6、ght, 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)对算法进行分类：两类：1） 多项式时间复杂度算法P（理论可行实际也可行）：O(c) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3)2） 指数时间复杂度算法NP（理论可行实际不可行，需要限制规模或用近似解）：O(2n) <

7、; O(n!) <O(nn)3） P->NP方法：智能算法(GA)、随机过程。第二章 分治法算法设计的三个基础技术：1. 由难到易的校正技术例，泰勒公式：求2的值，每次取两项，经过多次泰勒公式展开可以得到方程中无线趋近合理的解。2. 由粗到细的松弛技术例，割圆术求圆的面积，超松弛迭代：3. 由大到小的分治技术（加权的方法）一、 一般方法procedure DAN(p,q)globalif Small (p,q)then return G(p,q)else m<-DIVIDE(p,q)return (Combine(DAN(p,m),DAN(m+1,q)endifend DAN

8、设算法规模为n=q-p+1， T(n)=gn ,n足够小2Tn2+fn ，n为其它二、 二分检索法输入n个有序数，输出x把n个数输入，放到二叉树，使构造的二叉树树的高度最小。Procedure BINSRCH(A, n, x, j) integer low, high, mid, j, n; low1; highn. while low high do midlow+high/2 case : x<A(mid): highmid-1 : x>A(mid): highmid+1 :else: jmid; return endcase repeatj0end BINSRCH设树的高度为

9、k，2k+1>=n，k=log(n-1)，所以k=O(logn)三、 归并分类procedure MERGESORT(low, high)integerif low < highthen mid <- (low+ high)/2call MERGESORT(low, mid)call MERGESORT(mid+1,high)call MERGE(low, mid, high)end ifend 设规模为n，则fn=a ,n=12fn+nc ,n>1设n=2kfn=2fn2+nc=22fn22+2nc=2kf1+knc=an+nlogC例：输入a，b，c进行排序输出结果

10、：图3-1 排序树由于n个关键字有n!种排列，而每种排列可以是某种特定输入下的分类结果，因此比较树必定至少有n!个外结点，每个外结点表示一种可能的分类序列。设树的高度为h，则2h>=n!设比较树的最小高度为T(n)，则：n!2T(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，方程个数和自变量的个数关系：当方程个数多于自变量个数时：超定；当方程个数少于自变量个数时：欠定；当方程

11、个数等于自变量个数是：适定。矩阵相乘：Cnl=AnmBmlCij=k=1maikbkjT(n)=b n比较小7Tn/2+an2 n比较大其中，b和d是常数。根据斯特拉森的设计推理：T(n)=b n27Tn/2+dn2 n>2其中，a，b是常数。求解此递推关系式，得：Tn=an21+74+742+74k-1+7kT1=cn274logn=c+1nlog7=Onlog7On2.81五、 总结分治法作用：1、 由大化小求解（并行算法，空间换时间）；2、 能有效的降低算法的时间复杂度。（O(n)-> O(logn)，O(n2)-> O(nlogn)，O(n3)-> O(n2.8

12、1)）第三章 贪心算法一、 一般方法给定n个输入，找n个输入的一个子集，这个子集要满足一些约束条件，满足约束条件的子集可能会很多，把满足约束条件的子集都可以叫可行解。我们根据要求去定义一个目标函数，根据目标函数，使目标函数取得的极值的可行解叫最优解。例：给定图（V，E）->树->树的边权值为最小->最小生成树根据问题的特性去找一个量度标准，算法证明包括：证明量度标准、算法正确性证明。一般方法：Procedure GREEDY(A,n) solution for i1 to n do xSELECT(A) if FEASIBLE(solution,x) then solutio

13、nUNION(solution,x) endifrepeatreturn(solution)end二、 背包问题有一个背包，容量为M，现有物品N件，物品的质量为W1，W2，.，Wn，权值分别为P1，P2，.，Pn。1、问题分类设有N件物品分别装入X1，X2，.，Xn（代表物品装入的比例）。其中有，此时问题变为0、1背包问题，也就是该物品要么全部放入到背包中，要么不放入到背包中，此时为NP问题。若有，此时该问题变为部分背包问题，也就是该问题可以把物品只放入一部分到背包中，利用W/M进行排序，按排序从大到小放入到背包中，直到背包容量装满，此时为P问题。2、函数表示约束条件：目标函数：利用上述的两个

14、表达函数，在满足约束函数条件的前提下，求取目标函数的最大值，实现背包问题的求解。例：n=3，M=20，（P1，P2，P3）=（25，24，15），（W1，W2，W3）=（18，15，10），（X1，X2，X3）=？量度标准：X1，X2，X3属在01之间。可能的可行解如下： (x1,x2,x3) (1/2,1/3,1/4) 16.5 24.25 /没有放满背包/ (1,2/15,0 ) 20 28.2 /效益由大到小顺序装包 (0,2/3,1) 20 31 /质量由大到小顺序装包 (0,1,1/2) 20 31.5 单位质量的效益值从大到小顺序装包（最优）三、 最小生成树定义：设G(V,E)是一

15、个无向连通图。如果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，直至所有顶点全部被加入V，此时就构建出了一颗MST。普里姆算法：procedure PRIM(E,COST,n,T,mincost) /E是G的边集。COST(n,

16、n)是n结点图G的成本邻接矩阵，矩阵元素COST(i,j)是一个正实数，如果不存在边(i,j)，则为。计算一棵最小生成树并把它作为一个集合存放到数组T(1:n-1,2)中(T(i,1),T(i,2)是最小成本生成树的一条边。最小成本生成树的总成本最后赋给mincost。NEAR(j)是树中使得COST(j,NEAR(j)是对NEAR(j)所有选择中的最小值/ real COST(n,n), mincost integer NEAR(n), n, i, j,k, l, T(1:n-1,2) (k,l)具有最小成本的边 mincostCOST(k,l) (T(l,1),T(l,2) (k,l) f

17、or i1 to n do /将NEAR置初值/ if COST(i,l) COST(i,k) then NEAR(i)l else NEAR(i) k endif repeatNEAR(k)NEAR(l)0 for i2 to n-1 do /找T的其余n-2条边/ 设j是NEAR(j)0 且COST(j,NEAR(j)最小的下标 (T(i,1),T(i,2)(j,NEAR(j) mincostmincost+COST(j,NEAR(j) NEAR(j)0 for k1 to n do /修改NEAR/ if NEAR(k)0 and COST(k,NEAR(k)COST(k,j) then

18、 NEAR(k)j endif repeat repeat if mincost then print(no spanning tree) endifend PRIM计算复杂性：O(n2)四、 单源点最短路径即一直的一个n结点有向图G=（V,E）和边的权函数C(e)，求由G中某指定结点V0到其他各个点的最短路径。生成最短路径的贪心算法：Procedure SHORTEST (V,COST,DIST,n)/G是一个有n个结点的有向图，它由其邻接矩阵COST（n，n）表示，DIST（n，n）表示，DIST（j）被置以结点V到结点j的最短路径的长度，这里1<jn;DIST(v)被置为0/Boo

19、lean S(1:n); real COST(1:n,1:n),DIST(1:n)Integer u,v,n,num,i,wFor i1 to n do S(i) 0; DIST(i) COST(v,i)RepeatS(v) 1; DIST(v) 0For sum2 to n-1 do S(u) 1 For 所有S(w)=0的结点w do DIST(w) min(DIST(w), DIST(w)+ COST(u,w) RepeatRepeatEnd 生成最短路径的贪心算法的计算时间是O（n2）。第四章 动态规划一、 优化问题1、分类(1) 线性优化与非线性优化(2) 约束优化和无约束优化(3)

20、 确定性优化和随意性优化(4) 动态优化和静态优化(5) 单目标优化与多目标优化（最值与平衡解）2、优化问题求解难度上可分为(1) 函数优化：目标函数(2) 参数优化(3) 模型优化：模型是什么样的，建立模型二、 一般原理用来求解优化问题。特点：(1) 多阶段决策(2) 满足最优解原理：不论初始决策是什么样的，后面的决策相对初始决策产生一个最优的决策。三、 多段图最优性原理对多段图问题成立，在多段图中求从s到t的一条最小成本的路径，可以看作是在k-2个段作出某种决策的结果，其中第i（1ik-2）次决策决定Vi+1中的哪个结点在这条路径上。令源点s编号为1，然后依次对V2、V3Vk-1中的结点编

21、号，汇点t编号为n。如下图所示： 图4-1 一个5段图1、由前向后推 设BP(i, j)是一条从源点s到Vi中的结点j的最小成本路径，BCOST(I ,j)是这条路径的成本则向后递推式为 对图中所示的多段图采用向后策略递推：第2段 BCOST(2,2) = 9 BCOST(2,3) = 7 BCOST(2,4) = 3 BCOST(2,5) = 2第3段 BCOST(3,6) = minBCOST(2,2)+4,BCOST(2,3)+2 = 9 BCOST(3,7) = minBCOST(2,2)+2,BCOST(2,3)+7, BCOST(2,5)+11 = 11 BCOST(3,8) =

22、minBCOST(2,4)+11, BCOST(2,5)+8 = 10第4段 BCOST(4,9) = minBCOST(3,6)+6,BCOST(3,7)+4 = 15 BCOST(4,10) = minBCOST(3,6)+5,BCOST(3,7)+3, BCOST(3,8)+5 = 14 BCOST(4,11) = minBCOST(3,8)+6 = 16第5段 BCOST(5,12) = minBCOST(4,9)+4,BCOST(4,10)+2, BCOST(4,11)+5= 16S到t的最小成本路径的成本 16最小路径的求取： 记 BD(i, j)每一COST(i, j)的决策，即

23、使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的最小成本路径是：12710122、由后向前推 设P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径，COST(i,j)是这条路径的成本

24、。设i表示Vi，j表示Vi中的结点号向前递推式为对图中所示的多段图采用向前策略递推：第4段 COST(4,9) = c(9,12) = 4 COST(4,10) = c(10,12) = 2 COST(4,11) = c(11,12) = 5第3段 COST(3,6) = min6+COST(4,9),5+COST(4,10) = 7 COST(3,7) = min4+COST(4,9),3+COST(4,10) = 5 COST(3,8) = min5+COST(4,10),6+COST(4,11) = 7第2段 COST(2,2) = min4+COST(3,6) , 2+COST(3,7

25、), 1+COST(3,8) = 7 COST(2,3) = 9 COST(2,4) = 18 COST(2,5) = 15第1段 COST(1,1) = min9+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)

26、 = 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的最小成本路径是：1271012四、 每对结点间的最短路径设G=(V,E)是一个有n个结点的有向图，C是G的成本邻接矩阵，1i，jn，则C中元素有：则每对结点之间的最短路径问题即是求满足下述条件的矩阵A，A中的任一元素A(i,j)代表结点i到结点j的最短路径长度。若利用单源最短路径算法求解，那么计算n个结点的单源最短路径的时间复杂度为O（n3）。若利用动态规划策略求解，可以将求解G中每对结点之间

27、的最短路径问题转化成一个多阶段决策过程。设Ak (i,j)表示从i到j并且不经过比k还大的结点的最短路径长度，则A(i,j) = Ak (i,j)，即由i到j的最短路径不通过比编号k还大的结点。若该路径经过结点k，则Ak (i,j) Ak-1 (i,k) + Ak-1 (k,j)，若该路径不经过结点k，则Ak (i,j) Ak-1 (i,j)，故可得Ak(i,j) = min Ak-1 (i,j)，Ak-1 (i,k) + Ak-1 (k,j)。每对结点间的最短路径长度算法描述如下：procedure ALL-PATHS(COST,A,n) /COST(n,n)是n结点图的成本邻接矩阵；A(i

28、,j)是结点vi到vj的最短路 径的成本；COST(i,i)=0,1in/ integer I,j,k,n; real COST(n,n),A(n,n) for i1 to n do for j1 to n do A(i,j) COST(i,j) /用COST(i,j)对A0赋初值/ repeat repeat for k1 to n do for i1 to n do for j1 to n do A (i,j) minA (i,j) ，A (i,k) + A (k,j) repeat repeat repeat end ALL-PATHS计算时间为O（n3）。五、 最优二分检索树设给定的标

29、识符集合是a1,a2,an，并假定a1a2 an 。设P(i)是对ai检索的概率，Q(i)是正被检索的标识符X恰好满足ai Xai+1，0in（设a0=-,an+1=+)时的概率，即一种不成功检索情况下的概率，则所有成功检索的概率为 ，所有不成功检索的概率为 ，考虑所有可能的成功和不成功检索共2n+1种可能的情况，则有 。设Ei为不成功检索的等价类，则预期总的成本表示如下：其中左子树、右子树成本分别为：记 则原二分检索树的预期成本可表示为： COST(T)=P(k)+COST(L)+COST(R)+W(0,k-1)+W(k,n)若T最优二分检索树，则COST(L)和COST(R)将分别是包含a

30、1,a2,ak-1和E0,E1,Ek-1及ak1, ak+2, ,an和Ek,Ek+1,En的最优二分检索(子)树。如图：akLR 图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(i,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，总计算时间为例：设P(4) = (3,

31、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)=8 c(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)=7 c(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)=3 c(2,3)= min c(2,2)+ c(3,3) + w(2,3) = 3R(2,3)=3w(3,4)

32、=P(4)+Q(5) +w(3,3)=3 c(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 , i)=0，R(i ,i )的总时间：1mnnm-m2=O(n3)六、 0-1背包问题n件物品，背包容量为M， P1，P2，.，Pn 为价值，W1，W2，.，Wn为容量。装包方法：目标函数： 约束条件： 解答方法1：真值表方法（穷举法）。解答方法2：设fn-1(x)代表包容量为x，装W1，W2，.，Wn-1后的最大效益值。当将Wn装入背包时：fn (X)=fn-1(X-wn)+pn

33、fn(X) = maxfn-1(X),fn-1(X -wn)+pnj代表1到n之间的数：fi(X) = maxfj-1(X),fj-1(X-wj)+pj。例： n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,3)，M=6，其递推计算过程：由fi=fi-1(x-wi)+pi可得：f1(x)=maxf0(x),f0(x-2)+1 f2=maxf1(x),f1(x-3)+2七、 调度问题相同处理机调度PVM：n个作业，每个作业需时（t1，t2，tn），设有两个相同的处理机，给出最优调度方案，最优调度方案所需时间为（t1+t2+tn）/2。其实是子集和数的问题，是一个NP

34、 hard问题。流水线调度：例：n+2个作业，m=3，t1,i=ai，t2,i=0，t3,i= ai，1in；t1,n+1=T/2，t2,n+1=T，t3,i= 0;t1,n+2=0，t2,n+2=T，t3,n+2= T/2。其中，T=i=1nai。t1,i表示第i个任务在第一台机器上的时间。以长为标准，最好的调度方案是2T。P1t1,i ,T/2t1 ,n+1t1,i ,T/2P2t2 ,n+2t2 ,n+1P3tn ,T/2t3 ,n+1t1,i ,T/2第一台机器所需时间:i=1nai+T2=T+T2=3T2第一台机器所需时间:T+T=2T第一台机器所需时间:i=1nai+T2=3T2例

35、：有n=4个作业，每个作业两个任务：（a1，a2，a3，a4）=（3，4，8，10）（b1，b2，b3，b4）=（6，2，9，15）（b2 a1a2 b1 a3 b3 a4 b4），即t1t3t4t2。八、 TSP问题这是一个NP hard问题，时间复杂度为O（n!）。令g（i，S）为从i出发，经过S（S图中点集的子集），g（i，S）表示从i点出发，经过S中所有的结点一次且仅一次，回到出发点i的最短路径。g（i，1,2,3，n）=mincik+ g（k，S-k）。例如对于矩阵：C4,4=0101520509106130128890g（2，）=C21=5；g（3，）=C31=6；g（4，）=C4

36、1=8；g（2，3）=minC23+ g（3，）=15；g（2，4）=minC24+ g（4，）=18；g（3，2）=minC32+ g（2，）=18；g（3，4）=minC34+ g（4，）=20；g（4，2）=minC42+ g（2，）=13；g（4，3）=minC43+ g（3，）=15；g（2，3，4）=minC23+ g（3，4），C24+ g（4，3）=25；g（3，2，4）=minC32+ g（2，4），C34+ g（4，2）=25；g（4，2，3）=minC42+ g（2，3），C43+ g（4，2）=23；g（1，2，3，4）=minC12+ g（2，3，4），C13+ g（

37、3，2，4），C14+ g（4，2，3）=35；所以路径为1à2à4à3à1，时间复杂度O（2nn2）。第五章 基本检索与周游算法一、 一般方法1、 树的三种遍历方式 IABCDEGHF图5-1 给定二叉树中根：FDHGIBEAC先根：ABDFGHIEC后根：FHIGDEBCA2、图的生成树12345678图5-2 给定连通图12345678图5-3 宽度优先生成树12345678 图5-4 深度优先生成树：二、 双连通图和深度优先检索图5-5双连通分图双连通分图深度优先检索树：图5-6 双连通分图深度优先检索树深度优先生成树中的虚线条代表逆边，实线条代

38、表树边，结点旁的数代表深度优先树用DFN表示。最低深度优先数L（u）=minDFN（u），min（L(w)|w是u的儿子），minDFN（w）|（ u,w）是一条逆边，而且当且仅当u有一个使得L（w）>=DFN(u)的儿子w时，u是一个关节点。按后根的次序去各结点的最低深度优先数DFN(u)是：L(10)=4 L(9)=5 L(6)=8 L(8)=6 L(7)=6 L(5)=6 L(2)=1 L(3)=1 L(4)=1 L(1)=1 对于关节点：除根结点以外的其它结点，L（w）DFN（u）且w是u的儿子的结点是关节点，当然叶子结点不用考虑。 结点3：儿子结点10有L(10)4而DFN(3

39、)=3。 结点2：儿子结点5有L(5)=6而DFN(2)6结点5：儿子结点6有L(6)8而DFN(5)7由连通图的分类可知分为单连通分图、双连通分图两种类型，每一个图上都有一定的关节点，要识别出图上所有的关节点，根据各个关节点的连通性，找到符合条件的通路。对于宽度优先搜索和深度优先搜索，在这里，首先要对各个关节点之间的连接是单连通还是双连通的关系进行确定，再找到在一个连通图中关结点之间是有实边连接时，还有没有逆边连接，实边用实线来表示，逆边用虚线来表示，再根据DFS算法和BFS算法进行实现，找出符合条件的最优路径。三、 决策树（博弈树）对策树类问题的本质思想，是起源于博弈类游戏，比如，在一盘棋

40、赛中，对弈各方都要根据当前的局势，分析和预见以后可能出现的局面，决定自己要采取的各种对策，以争取更好的结果，博弈类问题是一种竞争，终局是表示为胜局、负局或者和局的情况的棋局，其它的都是非终止棋局。博弈过程在计算机里表示为对策树，对棋局进行判断的评价函数E（X）是maxßàmin的过程，该过程可采用剪枝策略，如-截断。截断：如果一个求最小值位置的值判断为小于或等于它父亲的值，那么可以停止生成这个求最小值位置其余儿子的值，在这种规则下终止生成结点值的行动称为截断。截断：如果一个求最大值位置的值判断为大于或等于它父亲的值，那么可以停止生成这个求最大值位置其余儿子的值，在这种规则下终止生成结点值的行动称为截断。第六章 回溯法第七章 分支限界法回溯法：深度优先搜索+限界函数分支限界法：宽度优先搜索+限界函数+LC（最小成本）一、 一般方法回溯法其实是求n元组的问题。所要求的解必须能表示成一个n-元组（x1，x2，xn），其中x1是取自某个有穷集Si。|Si|= mi，m1*m2mn。例：8-皇后问题8-皇后问题实际上是一个8元组问题。计算本质上是基于规划的一组符号的变换过程，是物理状态的变迁，而其中的状态及状态的转移（深度优化和宽度优化）本质上就是离散状