《计算机算法设计与分析总复习.ppt》由会员分享，可在线阅读，更多相关《计算机算法设计与分析总复习.ppt（87页珍藏版）》请在金锄头文库上搜索。
1、计算机算法设计与分析1.1 算法的定义和特征算法的定义和特征1)什么是算法？什么是算法？算法是求解某一特定问题特定问题的一组的一组有有穷规则穷规则的集合，它是由若干条指令组成是由若干条指令组成的有穷符号串的有穷符号串。2 2） 算法的五个重要特性算法的五个重要特性确定性确定性、可实现性可实现性、输入输入、输出输出、有穷性有穷性3 3） 算法设计的质量指标算法设计的质量指标正确性，可读性，健壮性，效率与存储量正确性，可读性，健壮性，效率与存储量算法和程序的区别算法和程序的区别n程序：一个计算机程序是对一个算法使用某种程序设计语言的具体实现n任何一种程序设计语言都可以实现任何一个算法n算法的有穷性
2、意味着不是所有的计算机程序都是算法问题求解问题求解(Problem Solving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法 一般只考虑三种情况下的时间性一般只考虑三种情况下的时间性:最坏情况、最坏情况、最好情况和平均情况下的复杂性，分别记为最好情况和平均情况下的复杂性，分别记为Tmax(n)、 Tmin(n)和和Tavg(n)算法复杂性算法复杂性 = 算法所需要的计算机资源算法所需要的计算机资源 =时间复杂性时间复杂性+空间复杂性空间复杂性算法渐近复杂性算法渐近复杂性1）上界函数）上界函数定义定义1如果存在两个正常数c和n0，对于所有的nn0，有 |f
3、(n)| c|g(n)| 则记作f(n) = (g(n) 含义：含义：n如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个上界函数。 f(n)的数量级就是g(n)。nf(n)的增长最多像g(n)的增长那样快n试图求出最小的g(n)，使得f(n) = (g(n)。 算法分类（计算时间）算法分类（计算时间）多项式时间算法多项式时间算法：可用多项式（函数）对其计算时间限界的算法。常见的多项式限界函数常见的多项式限界函数有： (1) (logn) (n) (nlogn) (n2) (n3)指数时间算法指数时间算法：计算时间
4、用指数函数限界的算法。常见的指数时间限界函数常见的指数时间限界函数： (2n) (n！) (nn)说明说明：当n取值较大时，指数时间算法和多项式时间算法在计算时间上非常悬殊。典型的计算时间函数曲线典型的计算时间函数曲线定义定义1.2如果存在两个正常数c和n0，对于所有的nn0，有 |f(n)| c|g(n)| 则记作f(n) = (g(n)含义：含义：n如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于|g(n)|的一个常数倍。所以g(n)是计算时间f(n)的一个下界函数。nf(n)的增长至少像g(n)的增长那样快n试图求出“最大”的g(n)，使得f(n) = (g(n)。
5、2）下界函数下界函数定义定义1.3如果存在正常数c1，c2和n0，对于所有的nn0，有 c1|g(n)| |f(n)| c2|g(n)| 则记作含义含义：n算法在最好和最坏情况下的计算时间就一个常数因子范围内而言是相同的。可看作： 既有f(n) = (g(n)，又有f(n) = (g(n)n 记号表明算法的运行时间有一个较准确的界3）“平均情况平均情况”限界函数限界函数最优算法最优算法n问题的计算时间下界为(f(n)，则计算时间复杂性为O(f(n)的算法是最优算法。n例如，排序问题的计算时间下界为(nlogn)，计算时间复杂性为O(nlogn)的排序算法是最优算法。第2章 递归与分治策略2.1
6、 递归的概念直接或间接地调用自身的算法称为递归算法递归算法。函数自身给出定义的函数称为递归函数递归函数。n基于归纳法归纳法的递归n基于分治法分治法的递归2.1 递归的概念例例 FibonacciFibonacci数列数列无穷数列1，1，2，3，5，8，13，21，34，55，称为Fibonacci数列。它可以递归地定义为：边界条件边界条件递归方程递归方程第n个Fibonacci数可递归地计算如下：intfibonacci(intn)if(n=1)return1;returnfibonacci(n-1)+fibonacci(n-2);分治算法总体思想分治法分治法的的设计思想设计思想是，是，将一个
7、难以直接解决的大将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。个击破，分而治之。分治法的适用条件分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：n该问题的规模缩小到一定的程度就可以该问题的规模缩小到一定的程度就可以容易地解决容易地解决；n该问题可以分解为若干个规模较小的相同问题，即该问题该问题可以分解为若干个规模较小的相同问题，即该问题具有具有最优子结构性质最优子结构性质n利用该问题分解出的子问题的
8、解利用该问题分解出的子问题的解可以合并可以合并为该问题的为该问题的解；解；n该问题所分解出的各个子问题是该问题所分解出的各个子问题是相互独立相互独立的，即子问的，即子问题之间不包含公共的子问题。题之间不包含公共的子问题。分治法的基本步骤分治法的基本步骤 （1）分解分解分解分解：将原问题分解为若干个规模较小，：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；相互独立，与原问题形式相同的子问题； （2）解决解决解决解决：若子问题规模较小而容易被解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；则直接解，否则递归地解各个子问题； （3）合并合并合并合并：将各个子问
9、题的解合并为原问题：将各个子问题的解合并为原问题的解。的解。分治法的复杂性分析一个分治法将规模为n的问题分成k个规模为nk的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：通过迭代法求得方程的解：二分搜索技术给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找出一特定元素出一特定元素x。据此容易设计出二分搜索算法二分搜索算法：templatei
10、ntBinarySearch(Typea,constType&x,intl,intr)while(r=l)intm=(l+r)/2;if(x=am)returnm;if(xam)r=m-1;elsel=m+1;return-1;算法复杂度分析：算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。合并排序基本思想：基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排
11、好序的集合。publicstaticvoidmergeSort(Comparablea,intleft,intright)if(leftright)/至少有2个元素inti=(left+right)/2;/取中点mergeSort(a,left,i);mergeSort(a,i+1,right);merge(a,b,left,i,right);/合并到数组bcopy(a,b,left,right);/复制回数组a复杂度分析复杂度分析T(n)=O(nlogn)渐进意义下的最优算法算法算法消去递归的合并排序算法消去递归的合并排序算法输入：输入：具有个元素的数组A输出：输出：按递增顺序排序的数组A1
12、.template2.voidmerge_sort(TypeA,intn)3.4.inti,s,t=1;5.while(tn)6.s=t; t=2*s;i=0;7.while(i+tn)8.merge(A,i,i+s-1,i+t-1,t);9.i=i+t;10.11.if(i+sn)12.merge(A,i,i+s-1,n-1,n-i);13.14.合并排序算法mergeSort的递归过程可以消去。初始序列49 38 65 97 76 13 2738 49 65 97 13 76 27第一步第二步38 49 65 97 13 27 76第三步13 27 38 49 65 76 97快速排序pr
13、ivatestaticvoidqSort(intp,intr)if(pr)intq=partition(p,r);/以ap为基准元素将ap:r划分成3段ap:q-1,aq和aq+1:r，使得ap:q-1中任何元素小于等于aq，aq+1:r中任何元素大于等于aq。下标q在划分过程中确定。qSort(p,q-1);/对左半段排序qSort(q+1,r);/对右半段排序templateint Partition (Type a, int p, int r) int i = p, j = r + 1; Type x=ap; while (true) while (a+i x & ir); / 将将x)
14、; / 将将 x的元素交换到右边区的元素交换到右边区域域 if (i = j) break; Swap(ai,aj); ; ap = aj; aj= x; return j; 快速排序线性时间选择问题线性时间选择问题n问题描述问题描述：给定线性集中n个元素和一个整数k,要求找出这n个元素中第k小的元素，即如果将这n个元素依其线性序排列时，排在第k个位置的元素即为我们要找的元素。n当k=1时，即找最小元素；当k=n时，即找最大元素；当k=(n+1)/2时，称为找中位数。线性时间选择templateTypeRandomizedSelect(Typea,intp,intr,intk)if(p=r)r
15、eturnap;inti=RandomizedPartition(a,p,r),j=i-p+1;if(k=j)returnRandomizedSelect(a,p,i,k);elsereturnRandomizedSelect(a,i+1,r,k-j);线性时间选择问题算法线性时间选择问题算法n上述Partition算法可用来求选择问题的有效解。如果划分元素v测定在A（j）的位置上，则有j-1个元素小于或等于A(j),且有n-j个元素大于或等于A(j)。因此，若kj,则第k小元素在A（j+1:n)中，再对之进一步划分。在最坏情况下，算法randomizedSelect需要O(n2)计算时间但可
16、以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。l将n个输入元素划分成n/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。l递归调用select来找出这n/5个元素的中位数。如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。线性时间选择TypeSelect(Typea,intp,intr,intk)if(r-p75)用某个简单排序算法对数组ap:r排序;returnap+k-1;for(inti=0;i=(r-p-4)/5;i+)将ap+5*i
17、至ap+5*i+4的第3小元素与ap+i交换位置;/找中位数的中位数，r-p-4即上面所说的n-5Typex=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);inti=Partition(a,p,r,x),j=i-p+1;if(k=j)returnSelect(a,p,i,k);elsereturnSelect(a,i+1,r,k-j);复杂度分析复杂度分析T(n)=O(n)32n n基本思想基本思想：n 把求解的问题把求解的问题分成许多阶段或多个子问题分成许多阶段或多个子问题，然后然后按顺序求解各个子问题按顺序求解各个子问题。前一个子问题的。前一个子问题的解为后一个子问
18、题的求解提供了有用的信息。解为后一个子问题的求解提供了有用的信息。在求解任何一子问题时，列出各种可能的局部在求解任何一子问题时，列出各种可能的局部解，解，通过决策保留那些有可能达到最优的局部通过决策保留那些有可能达到最优的局部解，丢弃其他局部解解，丢弃其他局部解，依次解决各子问题，最，依次解决各子问题，最后一个子问题就是问题的解。后一个子问题就是问题的解。动态规划算法动态规划算法的两个基本要素动态规划算法的两个基本要素对于一个多阶段过程问题，最优决策是否存在，不仅依赖于该问题是否有最优子结构性质，而能否采用动态规划的方法，还要看该问题的子问题是否具有重叠性质。最优子结构性质最优子结构性质：原问
19、题的最优解包含了其子问题的最优解。子问题重叠性质子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。34动态规划基本步骤n找出最优解的性质，并刻划其结构特征。找出最优解的性质，并刻划其结构特征。n递归递归地定义最优值。地定义最优值。n以以自底向上自底向上的方式计算出最优值。的方式计算出最优值。n根据计算最优值时得到的信息，构造最根据计算最优值时得到的信息，构造最优解。优解。35矩阵连乘问题u穷举法穷举法u动态规划动态规划将矩阵连乘积 简记为Ai:j ，这里ij 考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方
20、式为计算量：Ai:k的计算量加上Ak+1:j的计算量，再加上Ai:k和Ak+1:j相乘的计算量建立递归关系建立递归关系 令令mij , 1i, jn，为计算为计算Ai, j 的最少数的最少数乘次数，则原问题为乘次数，则原问题为m1n。n当i = j时，Ai, j为单一矩阵， mij = 0；n当ij时，利用最优子结构性质有： mij = minmik + mk+1j + pi1pkpjikj其中矩阵Ai ，1in，的维数为pi1pi。n根据此递归式就可以直接用递归程序来实现。消除重复的矩阵连乘算法消除重复的矩阵连乘算法nVoid MatrixChain(int p, int n, int *m
21、, int *s)n for (int i = 1; i = n; i+) mii = 0; n /将对角线元素赋值为零，即单个矩阵计算量为0n for (int r = 2; r = n; r+) n for (int i = 1; i = n r +1; i+) n int j = i + r 1;n(5) mij = mi+1j + pi1*pi*pj;n /计算Ai, j = Ai: i Ai+1: jn sij = i; /记下断点in(7) for (int k = i + 1; k j; k+) n int t = mik + mk+1j + pi1*pk*pj; n /对ikj
22、, 逐个计算Ai, j = Ai: k Ak+1: jn if (t mij) mij = t; sij = k;n /记下较小的mij及相应的断点k n 算法时间复杂性的上界为O(n3)39子问题的递归结构由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中，和 当i=0或j=0时，空序列是A和B的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：40计算最优值由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上自底向上自底向上自底向上地计算最优值能提高算法的效率。vo
23、idLCSLength(intm，intn，char*x，char*y，int*c，int*b)inti，j;for(i=1;i=m;i+)ci0=0;for(i=1;i=n;i+)c0i=0;for(i=1;i=m;i+)for(j=1;j=cij-1)cij=ci-1j;bij=2;elsecij=cij-1;bij=3;构造最长公共子序列构造最长公共子序列voidLCS(inti，intj，char*x，int*b)if(i=0|j=0)return;if(bij=1)LCS(i-1，j-1，x，b);coutxi;elseif(bij=2)LCS(i-1，j，x，b);elseLCS(
24、i，j-1，x，b);410-1背包问题给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。420-1背包问题设所给0-1背包问题的子问题的最优值为的最优值为m(i，j)，即，即m(i，j)是背包容量为是背包容量为j，可选择物品为，可选择物品为i，i+1，n时时0-1背包问题的最优值。由背包问题的最优值。由0-1背包问题的最优子背包问题的最优子结构性质，可以建立计算结构性质，可以建立计算m(i，j)的递归式如下。的递归式如下。43templatevoidKnapsack(Ty
25、pev,intw,intc,intn,Type*m)intjMax=min(wn-1,c);for(intj=0;j=jMax;j+)mnj=0;for(intj=wn;j=c;j+)nnj=vn;for(inti=n-1;i1;i-)jMax=min(wi-1,c);for(intj=0;j=jMax;j+)mij=mi+1j;for(intj=wi;j=w1)m1c=max(m1c,m2c-w1+v1);贪心算法贪心算法n贪心算法总是作出在贪心算法总是作出在当前看来最好的选当前看来最好的选择择，即所作的选择只是，即所作的选择只是局部最优选择局部最优选择。n希望从希望从局部的最优选择局部的最
26、优选择得到得到整体最优解整体最优解。n采用逐步构造最优解的方法。在每个阶采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不一定的标准下）。决策一旦作出，就不可再更改。可再更改。贪心方法描述量度标准A(1)A(2)A(n)A(1)A(2)A(n)S(1)S(2)这种量度意义下的部分最优解原问题的n个输入排序后的n个输入A (j)贪心算法的基本要素贪心算法的基本要素贪心算法的基本要素贪心算法的基本要素n可用贪心算法求解的问题的基本要素可用贪心算法求解的问题的基本要素最优子结构性质最优子结构性质贪心选择性质贪心选择
27、性质。贪心算法的基本要素贪心算法的基本要素贪心算法与动态规划算法的差异贪心算法与动态规划算法的差异n相同点：都具有最优子结构性质相同点：都具有最优子结构性质n区别：动态规划算法每步所作的选择往往依赖区别：动态规划算法每步所作的选择往往依赖于相关子问题的解。只有解出相关子问题才能于相关子问题的解。只有解出相关子问题才能作出选择。作出选择。贪心算法仅在当前状态下作出最好选择，即局贪心算法仅在当前状态下作出最好选择，即局部最优选择，但不依赖于子问题的解部最优选择，但不依赖于子问题的解贪心：贪心：自顶向下自顶向下动态规划：动态规划：自底向上自底向上贪心算法的基本要素贪心算法的基本要素活动安排问题活动安
28、排问题 已知已知n个活动个活动 E = 1, 2, , n 要求使用同要求使用同一资源，第一资源，第k个活动要求的开始和结束时间个活动要求的开始和结束时间为为sk , fk , 其中其中sk fk , k = 1, 2, , n 。活。活动动k与活动与活动j称为相容的如果称为相容的如果sk fj 或者或者sj fk。活动安排问题就是要在所给的活动集合中活动安排问题就是要在所给的活动集合中选出最大的相容活动子集。选出最大的相容活动子集。问题提出：问题提出：基本思路基本思路n在安排时应该将在安排时应该将结束时间早的活动结束时间早的活动尽量往前安排，尽量往前安排，好给后面的活动安排留出更多的空间，从
29、而达到好给后面的活动安排留出更多的空间，从而达到安排最多活动的目标。安排最多活动的目标。n贪心准则应当是：贪心准则应当是：在未安排的活动中挑选结束时在未安排的活动中挑选结束时间最早的活动安排。间最早的活动安排。活动安排问题活动安排问题n首先将安排的首先将安排的11个活动的开始时间和结束时间个活动的开始时间和结束时间按结束时间的按结束时间的非减次序排列非减次序排列如下：如下：k1234567891011sk130535688212fk4567891011121314活动安排问题活动安排问题0123456789 101112 13 141isifi1142353064575386597610881
30、198121021311121421314141461471481489148101481114811活动安排问题活动安排问题5阴影长条阴影长条表示的表示的活动是已选入集合活动是已选入集合A的活动，而的活动，而空白空白长条长条表示的活动是表示的活动是当前正在检查相容当前正在检查相容性的活动。性的活动。52活动安排问题nPublicstaticvoidgreedySelector(ints,intf,booleana)nintn=s.length-1;na0=true;nintj=0;intcount=1;nfor(inti=1;i=fj)ai=true;j=i;count+;nelseai=f
31、alse;nnreturncount;n下面给出解活动安排问题的贪心算法下面给出解活动安排问题的贪心算法GreedySelectorGreedySelector : :各活动的起始时间和结各活动的起始时间和结束时间存储于数组束时间存储于数组s s和和f f中且按结束时间的非减中且按结束时间的非减序排列序排列53n n0-10-1背包问题：背包问题： 给定给定n n种物品和一个背包。物品种物品和一个背包。物品i i的重量是的重量是W Wi i，其价值，其价值为为V Vi i，背包的容量为，背包的容量为C C。应如何选择装入背包的物品，使得。应如何选择装入背包的物品，使得装入背包中物品的总价值最大
32、装入背包中物品的总价值最大? ? 在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i i只有只有2 2种选择，即种选择，即装入背包或不装入背包。不能将物品装入背包或不装入背包。不能将物品i i装入背包多次，也不能只装入背包多次，也不能只装入部分的物品装入部分的物品i i。54n背包问题：背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品可以选择物品i i的一部分的一部分，而不一定要全部装入背包，1in。形式化描述为： 这2类问题都具有最优子结构最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。 其中C0
33、为背包容量，wi0,vi0，(x1,x2,xn)为最优解。55 首先计算每种物品单位重量的价值首先计算每种物品单位重量的价值v vi i/ /w wi i，然后，依贪心，然后，依贪心选择策略，将尽可能多的选择策略，将尽可能多的单位重量价值最高单位重量价值最高( (即即v vi i/ /w wi i尽可大尽可大的的) )的物品装入背包。若将这种物品全部装入背包后，背包的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过内的物品总重量未超过C C，则选择单位重量价值次高的物品，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背并尽可能多地装入背包。依此
34、策略一直地进行下去，直到背包装满为止。若最后一个物品不能全部装入时，仅装其一部包装满为止。若最后一个物品不能全部装入时，仅装其一部分使背包装满即可。分使背包装满即可。 具体算法可描述如下页：用贪心算法解背包问题的基本思想：贪心解背包问题贪心解背包问题n首先计算每种物品单位重量的价值首先计算每种物品单位重量的价值vi / wi，然后，将尽可能，然后，将尽可能多的单位重量价值最高的物品装入背包。多的单位重量价值最高的物品装入背包。 voidKnapsack(intn,floatM,floatv,floatw,floatx)Sort(n,v,w);/将各种物品按单位重量价值排序将各种物品按单位重量价
35、值排序inti;for(i=1;i=n;i+)xi=0;/将解向量初始化为零将解向量初始化为零floatc=M;/是背包剩余容量初始化为是背包剩余容量初始化为Mfor(i=1;i=n;i+)if()break;xi=1;c;if(ic-=wixi=c/wi算法复杂度算法复杂度该算法的主要计算时间在于将各种物品该算法的主要计算时间在于将各种物品依其单位重量的价值从大到小顺序。因依其单位重量的价值从大到小顺序。因此算法的计算时间上界为此算法的计算时间上界为O(nlogn)。58单源最短路径给定带权有向图给定带权有向图G =(V,E)G =(V,E)，其中每条边的权是非负实数。，其中每条边的权是非负
36、实数。另外，还给定另外，还给定V V中的一个顶点，称为中的一个顶点，称为源源。现在要计算从源到所。现在要计算从源到所有其它各顶点的有其它各顶点的最短路径长度最短路径长度。这里径路的长度是指路径上。这里径路的长度是指路径上各边权之和。这个问题通常称为各边权之和。这个问题通常称为单源最短路径问题单源最短路径问题。1、Dijkstra算法基本思想 Dijkstra算法是解单源最短路径问题的贪心算法。其基本基本思想思想是: 设置顶点集合S(初始仅含源源)并不断地作贪心选择贪心选择清华大学出版社59单源最短路径来扩充这个集合；一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知已知。具体而言：初始时
37、，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路径称为从源到u的特殊路径，并用数组dist记录当前每个顶点当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u添加到S中，同时根据S中顶点的最短路径对数组dist作必要的修改。一旦S包含了V中所有顶点，则dist就记录了从源到其它所有顶点的最短路径的长度。清华大学出版社v0v2v1v3v4v5204550101515201035303迭代迭代选取选取结点结点SDIST(1)(2)(3)(4)(5)置初值置初值-0501045120,250102545230,2,345102
38、545310,2,3,145102545440,2,3,1,445102545550,2,3,1,4,545102545考虑需要哪些存储结构？考虑需要哪些存储结构？算法如何实现？算法如何实现？循环需要几次？循环需要几次？每次循环做什么工作？每次循环做什么工作？首先为第一行赋初值；首先为第一行赋初值；循环循环n-1次；次；每次根据新加进来的每次根据新加进来的结点修改可以修改的结点修改可以修改的路径，并选择最短的路径，并选择最短的61最小生成树 设G =(V,E)是无向连通带权图，即一个网络网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树
39、上各边权的总和称为该生成树的耗费耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成最小生成树树。62最小生成树1、最小生成树性质用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的PrimPrim算法算法和KruskalKruskal算法算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性质最小生成树性质：设G=(V,E)是连通带权图，U是V的非空真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中(即断集中)，(u,v)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一
40、条边。这个性质有时也称为MSTMST性质性质。证明略。63最小生成树PrimPrim算法算法 设G=(V,E)是连通带权图，V=1,2,n。构造G的最小生成树的Prim算法的基本思想基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的贪贪心选择心选择：选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最最小生成树小生成树。 清华大学出版社64最小生成树利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合边集合T T始终始终包含包含G G的某棵最小生成树中的某棵最小生成树中的边的边。因此，在
41、算法结束时，T中的所有边构成G的一棵最小生成树。例如例如，对于右图中的带权图，按PrimPrim算法算法选取边的过程如下页图所示。清华大学出版社654.6 最小生成树清华大学出版社66最小生成树3 3、KruskalKruskal算法算法Kruskal算法构造G的最小生成树的基本思想基本思想是，首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接并按下述方法连接2 2个不同个不同的连通分支：的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)
42、将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。 清华大学出版社67最小生成树例如，例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示。清华大学出版社问题的解向量问题的解向量：一个一个n n元式元式(x1,x2,(x1,x2, ,xnxn) )的形式。的形式。显约束：对分量显约束：对分量xi i的取值限定。的取值限定。隐约束：为满足问题的解而对不同分量之间施加的隐约束：为满足问题的解而对不同分量之间施加的约束。约束。解空间：解空间：问题的解空间
43、一般用问题的解空间一般用解空间树解空间树（Solution Space Trees,也称状态空间树）的方式组织也称状态空间树）的方式组织， 其中，树的根结点位于第其中，树的根结点位于第1层层，表示搜索的初始状态，表示搜索的初始状态，第第2层的结点表示对解向量的第一个分量做出选择后到达的状态层的结点表示对解向量的第一个分量做出选择后到达的状态，第第1层到第层到第2层的边上标出对第一个分量选择的结果，层的边上标出对第一个分量选择的结果，依此类依此类推，推，从树的根结点到叶子结点的路径就构成了解空间的一个从树的根结点到叶子结点的路径就构成了解空间的一个可能解。可能解。回溯法回溯法回溯法的基本思想回溯
44、法的基本思想n回溯法从回溯法从根结点出发根结点出发，按照，按照深度优先深度优先策略策略搜索搜索（遍历）解空间树（遍历）解空间树，搜索满足约束条件的解。，搜索满足约束条件的解。n初始时，根结点成为一个初始时，根结点成为一个活结点活结点，同时也称为当，同时也称为当前的前的扩展结点扩展结点。在当前扩展结点处，搜索向纵深。在当前扩展结点处，搜索向纵深方向移至一个新结点。这个新结点成为一个新的方向移至一个新结点。这个新结点成为一个新的活结点，并成为当前的扩展结点。如果在当前的活结点，并成为当前的扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩扩展结点处不能再向纵深方向移动，则当前的扩展结
45、点就成为一个展结点就成为一个死结点死结点（即不再是一个活节点）（即不再是一个活节点）。此时，应往回移动（回溯）至最近的一个活结。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。点处，并使这个活结点成为当前的扩展结点。回溯法的求解过程回溯法的求解过程(1) (1) 针对所给问题，定义问题的解空间；针对所给问题，定义问题的解空间；(2) (2) 确定易于搜索的解空间结构；确定易于搜索的解空间结构；(3) (3) 深度优先搜索解空间，并在搜索中用剪枝函数避深度优先搜索解空间，并在搜索中用剪枝函数避免无效搜索。免无效搜索。需需要要注注意意的的是是，问问题题的的解解空空间
46、间树树是是虚虚拟拟的的，并并不不需需要要在在算算法法运运行行时时构构造造一一棵棵真真正正的的树树结结构构。在在任任何何时时刻刻，算算法法只只保保存存从从根根结结点点到到当当前前扩扩展展结结点点的的路路径径。如如果果解解空空间间树树中中从从根根结结点点到到叶叶结结点点的的最最长长路路径径的的长长度度为为h(n)，则则回回溯溯法法所所需需的的计计算算空空间间通通常常为为O(h(n)。而而显显式式地地存存储储整整个个解解空空间间则则需需要要O(2h(n)或或O(h(n)!)内存空间。内存空间。回溯法的基本思想回溯法的基本思想n在搜索过程中，通常采用两种策略避免无效搜索：在搜索过程中，通常采用两种策略
47、避免无效搜索：（1）用）用约束条件约束条件剪去得不到可行解的子树；剪去得不到可行解的子树；（2）用）用限界函数限界函数剪去得不到最优解的子树。剪去得不到最优解的子树。这两类函数统称为这两类函数统称为剪枝函数剪枝函数（Pruning Function）。n在搜索至树中任一结点时，先判断该结点对应的部在搜索至树中任一结点时，先判断该结点对应的部分解是否满足分解是否满足约束条件约束条件，或者是否超出，或者是否超出限界函数限界函数的界，也就是判断该结点是否的界，也就是判断该结点是否包含包含问题的（最优）问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的解，如果肯定不包含，则跳过对以该结点为根的子
48、树的搜索，即所谓子树的搜索，即所谓剪枝剪枝（Pruning）；否则，进否则，进入以该结点为根的子树，继续按照深度优先策略入以该结点为根的子树，继续按照深度优先策略搜索。搜索。子集树与排列树子集树与排列树n当所给问题是从当所给问题是从n个元素的集合个元素的集合S中找出满足某中找出满足某种性质的种性质的子集子集时，解空间为时，解空间为子集树子集树。n当所给问题是从当所给问题是从n个元素的集合个元素的集合S中找出满足某中找出满足某种性质的种性质的排列排列时，解空间为时，解空间为排列树排列树。遍历子集树需O(2n)计算时间遍历排列树需要O(n!)计算时间voidbacktrack(intt)if(tn
49、)output(x);elsefor(inti=0;in)output(x);elsefor(inti=t;i当前最优载重量当前最优载重量bestw1 10 01 11 11 11 10 00 00 0不满足不满足约束函数约束函数1 1不满足不满足上界函数上界函数0 00 01 1装载问题算法描述装载问题算法描述n n 集装箱数；集装箱数； ww集装箱重量数组；集装箱重量数组； c c第一艘轮船载重量；第一艘轮船载重量；cwcw 在遍历结点处的当前载重量在遍历结点处的当前载重量 bsetwbsetw 当前最优载重量当前最优载重量privatestaticvoidbacktrack(inti)/
50、搜索第搜索第i层结点层结点if(in)/到达叶结点到达叶结点if(cwbestw)bestw=cw;return;if(cw+win)/到达叶结点更新最优解bestx,bestw;return;r-=wi;if(cw+wibestw)/搜索右子树xi=0;backtrack(i+1);r+=wi;复杂度分析复杂度分析算法算法backtrack在最坏情况下在最坏情况下可能需要更新当前最优解可能需要更新当前最优解O(2n)次，每次更新次，每次更新bestx需计需计算时间算时间O(n)，从而整个算法的从而整个算法的计算时间复杂性为计算时间复杂性为O(n2n)。进一步改进算法，可降低时间进一步改进算法
51、，可降低时间复杂性为复杂性为O(2n)。N-皇后问题定义皇后问题定义n4皇后问题：*n8皇后问题：1Q2Q3Q4Q5Q6 Q7Q8Q1 2 3 4 5 6 7 8经典的回溯算法，该算法的思路如下经典的回溯算法，该算法的思路如下：依次在棋盘的每一行上摆放一个皇后。每次摆放都要检查当前摆放是否可行。如果当前的摆放引发冲突，则把当前皇后摆放到当前行的下一列上，并重新检查冲突。如果当前皇后在当前行的每一列上都不可摆放，则回溯到上一个皇后并且将其摆放到下一列上，并重新检查冲突。如果所有皇后都被摆放成功，则表明成功找到一个解，记录下该解并且回溯到上一个皇后。求解N后问题中的数据表示6543211 2 3
52、4 5 6i-j=k-l6543211 2 3 4 5 6i+j=k+l问题分析问题分析n解向量解向量：(x1,x2,xn)，xi表示皇后i放在棋盘的第i行的第xi列。n显约束显约束：xi=1,2,nn隐约束隐约束：1)不同列：xixj (ij)2)不处于同一正、反对角线：|i-j|xi-xj|n解空间解空间：排列树n约束函数约束函数：xixj (ij) and |i-j|xi-xj|算法描述算法描述/place函数测试若将皇后k放在xk列是否与前面已放置的k-1个皇后都不在同一列，而且都不在同一斜线上。boolQueen:Place(intk)for(intj=1;jn)sum+;/sum记
53、录当前已找到的可行方案数。elsefor(inti=1;i=n;i+)xt=i;if(Place(t)Backtrack(t+1);N后问题的时间复杂性n如果只要找出N后问题的一个解，那么这是一个求路径的问题。n求路径：只需要找到一条路径便可以得到解。设每个状态有k个后继，其搜索树为K叉树，其结点总数为kn+11，遍历的时间为O(kn)，这里n为找到解的路径长度。nN后问题的路径深度为n，可选择的后继有n个，所以时间复杂性为O(nn)。分支限界法的基本思想分支限界法的基本思想分支限界法与回溯法分支限界法与回溯法（1 1 1 1）求解目标：）求解目标：）求解目标：）求解目标：回溯法的求解目标是找
54、出解空回溯法的求解目标是找出解空回溯法的求解目标是找出解空回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法间树中满足约束条件的所有解，而分支限界法间树中满足约束条件的所有解，而分支限界法间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，的求解目标则是找出满足约束条件的一个解，的求解目标则是找出满足约束条件的一个解，的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下或是在满足约束条件的解中找出在某种意义下或是在满足约束条件的解中找出在某种意义下或是在满足约束条件的解中找出在某种意义下的最优解。的最优解。的最优解。的最优
55、解。 （2 2 2 2）搜索方式的不同：）搜索方式的不同：）搜索方式的不同：）搜索方式的不同：回溯法以深度优先的方回溯法以深度优先的方回溯法以深度优先的方回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先式搜索解空间树，而分支限界法则以广度优先式搜索解空间树，而分支限界法则以广度优先式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。或以最小耗费优先的方式搜索解空间树。或以最小耗费优先的方式搜索解空间树。或以最小耗费优先的方式搜索解空间树。 （3）从活结点表中取下一结点成为当前扩展结点，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一
56、直持续到找并重复上述结点扩展过程。这个过程一直持续到找到到所需的解所需的解或或活结点表为空活结点表为空时为止。时为止。（2）每一个活结点只有每一个活结点只有一次机会一次机会成为扩展结点。活成为扩展结点。活结点一旦成为扩展结点，就结点一旦成为扩展结点，就一次性产生一次性产生其所有儿子其所有儿子结点。在这些儿子结点中，导致不可行解或导致非结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被最优解的儿子结点被舍弃舍弃，其余儿子结点被加入活，其余儿子结点被加入活结点表中。结点表中。分支限界法的基本思想分支限界法的基本思想（1）以以广度优先广度优先或以或以最小耗费最小耗费（最大效益）优先（最大效益）优先的方式搜索；的方式搜索；常见的两种分支限界法常见的两种分支限界法（1 1）队列式队列式( (FIFO)FIFO)分支限界法分支限界法 按照队列按照队列先进先出先进先出（FIFOFIFO）原则选取下一原则选取下一个节点为扩展节点。个节点为扩展节点。 （2 2）优先队列式分支限界法）优先队列式分支限界法 按照优先队列中按照优先队列中规定的优先级规定的优先级选取优先级选取优先级最高的节点成为当前扩展节点。最高的节点成为当前扩展节点。
