东北大学数据结构期末复习ppt课件.ppt

《东北大学数据结构期末复习ppt课件.ppt》由会员分享，可在线阅读，更多相关《东北大学数据结构期末复习ppt课件.ppt（134页珍藏版）》请在三一办公上搜索。

1、期末复习,题型,选择题（10分）填空题（10分）算法应用题（算法填空，简单问题回答）（3-4个题，35-40分）算法设计（按照已知条件设计算法或为算法补充完整）（3个题，45-50分）,第1章,算法的性质及其与程序的区别算法复杂性分析渐进意义下的四种记号简单的程序段的复杂度分析,算法的五个重要特征,输入 有零个或多个由外部提供的量作为算法的输入输出 算法产生至少一个量作为输出.确定性 组成算法的每条指令是清晰的,无歧义的.有限性 在执行了有穷步骤后运算终止可行性 运算都是基本运算，原理上能在有限时间内完成。,渐进意义下的记号：O,f(N)和g(N)是定义在正整数上的正函数定义1.1 如果存在两

2、个正常数c和N0,对于所有的NN0，有f(N) Cg(N)，则记作：f(N)= O(g(N)。,N0,f(N),g(N),当说一个算法具有O(g(n)的计算时间时，指的就是如果此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于g(n)的一个常数倍。g(n)是计算时间f(n)的一个上界函数，f(n)的数量级就是g(n),符号的定义,定义1.2 如果存在两个正常数C和自然数N0，使得当N N0时有f(N)Cg(N)，则称函数f(N)当N充分大时下有界；且g(N)是它的一个下界，记为f(N)=(g(N)。这时我们说f(N)的阶不低于g(N)的阶。, ，o 的定义, 定义f(N)= (

3、g(N)当且仅当f(N)=O(g(N)且f(N)=(g(N)。这时，我们说f(N)与g(N)同阶o 如果对于任意给定的0，都存在正整数N0，使得当N N0时有f(N)/g(N)，则称函数f(N)当N充分大时的阶比g(N)低，记为f(N)=o(g(N)例如：4NlogN+7=o(3N2+4NlogN+7),1.2 算法分析初步,多项式时间算法(polynomial time algorithm):可用多项式来对其计算时间限界的算法O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间算法(exponential time algorithm):计算时间用指数函数限界的算法O(

4、2n)O(n!)O(nn),作业1-7,第2章,递归分治法基本思想二分搜索算法Strassen矩阵乘法合并排序和快速排序,递归复杂度分析,汉诺塔移动次数,M(1)=1M(n)=2M(n-1)+1 = 22M(n-2)+1+1 = 22M(n-2)+2+1 = 23M(n-3)+22+2+1 = =2iM(n-i)+2i-1+2i-2+2+1 =2iM(n-i)+2i - 1令i= n -1 则M(n)= 2n-1 + 2n-1-1=2n-1,2.1 递归,分治法的基本思想,分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以： 把它分成两个或多个更小的问题； 分别解决每个小问

5、题； 把各小问题的解答组合起来，即可得到原问题的解答。小问题通常与原问题相似，可以递归地使用分而治之策略来解决。,例2-6 在9,12,15,27,39中分别查找27，12，14,mid = (left+right)/2=(0+4)/2=2,mid =(3+4)/2=3,查找27成功返回3，leftright,查找12成功返回1,left=right,查找14失败返回-1,leftright,template int BinarySearch( T a, const T /未找到x,n-1,0,left=right,(left+right)/2,middle+1,middle 1,当n1时，T

6、w(n)= Tw(n/2)+1, T(1) = 1Tw(n) = Tw(n/2) + 1 = Tw(n/4) +1 +1 =Tw(1)+1+.+1=1+k=1+logn,二分搜索的时间复杂度,最坏情况下的成功检索计算时间(logn) 最坏情况下的不成功检索计算时间(logn) 最好情况下的成功检索计算时间(1) 最好情况下的不成功检索计算时间(logn) 每种不成功的检索时间都为(logn),2.2二分搜索技术,作业：,P34，2-2 中第二个和第五个算法的正确性，错误的说明原因或者给出反例2. P35, 2-3,2-3：二分搜索中当程序停止时，左右指针或者指向同一个元素，此时该元素等于待查找

7、元素或者left=right+1，此时right指向的为比待找元素小的元素，left为比待找元素大的元素,归并排序主程序伪代码,templatevoid MergeSort(Type a , int left, int right)/ Aleft:right是一个全程数组，含有 right-left+1个待排序的元素。 if ( ) /至少有2个元素 int mid = (left+right)/2; /求当前数组的分割点 MergeSort(a，left, mid); MergeSort(a，mid+1, right); Merge(a，b，left, mid ,right); copy（a

8、，b，left，right）； ,left right,递归调用，分别对分解出来的两个子问题排序,合并两个排好序的子问题，放入另一个数组b中,2.4合并排序,考虑数组a的两段为1, 7, 8, 9和2, 3, 4, 5,1,1,2,1,2,3,1,2,3,4,1,2,3,4,5,数组a的两部分,数组b,1,2,3,4,5,7,1,2,3,4,5,7,8,1,2,3,4,5, 7,8,9,在移动扫描指针的同时，要判断其是否已经到达数组的尾部，如到达，则停止扫描，把未参加排序的数全部放入备用数组中,2.4合并排序,合并函数,templatevoid Merge( Type a , Type b ,

9、 int l, int m, int r)/合并al:m和am+1:r到bl:r int i=l; j=m+1, k=l; while( ( ),把al:m和am+1:r中的数据进行比较，按顺序放入b中,如果前一段数据小于后一段的多，则先排完，把后段剩余数赋给bn,否则将前段数据赋给bn,前半段指针,后半段指针,数组b的下标指针,i=m,j=r,2.4合并排序,作业,分析merge函数最好与最坏的键值比较次数。,最好比较1次最差比较m+n-1，m和n分别为两段数组的长度,快速排序,Templatevoid QuickSort(Type a , int p,int r) if(pr) int q

10、=Partition(a,p,r); QuickSort(a,p,q-1);/对左半段排序 QuickSort(a,q+1,r);/对右半段排序 ,a的起始位置,A的终止位置,Partition函数负责将a进行一次分割，返回分割元素的位置,快速排序问题,划分程序,templateint Partition(Type a ,int p,int r) int i = , j = ; Type x = ; while( true ) while( a +i x ); if( ) break; Swap( a i , a j ); a p = ; a j = ; return j;,快速排序问题,p,

11、r+1,a p ,i = j,a j ,x,左侧扫描指针起始,右侧扫描指针起始,中轴元素,移动左侧扫描指针,移动右侧扫描指针,算法分析,最坏情况：划分的两个区域分别包含n1个元素和1个元素，如果每一步都出现这种情况，其复杂性T(n) O(1) n1 T(n)= T(n-1)+O(n) n1解得：T(n)=O(n2),快速排序问题,最好情况每次划分所取的基准都恰好为中值，即每次划分都产生两个大小为n/2的区域， O(1) n1 T(n)= 2T(n/2)+O(n) n1T(n)=O(nlogn),快速排序问题,2-19将算法Partition中的不等号反向,第3章,动态规划思想，基本要素矩阵连乘

12、算法及最优解构造0-1背包问题最优值及最优解最优二叉搜索树（通过具体实例弄清每个算法的流程及算法的具体实现）,动态规划算法,将待求解的问题分解成若干个子问题，先求解子问题，并存储子问题的解而避免计算重复的子问题，再由子问题的解得到原问题的解。,算法思想,动态规划算法的基本要素,1 最优子结构性质2 重叠子问题性质,1. 最优子结构,当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。分析最优子结构性质时，一般假设由问题的最优解导出的子问题不是最优的，然后再设法说明在这个假设下可以构造出一个比原问题更优解更好的解，从而导出矛盾。,动态规划算法的基本要素,2.重叠子问题,在用递归算

13、法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法对每个问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，用常数时间查看一下结果。因此，用动态规划算法通常只需要多项式时间。,动态规划算法的基本要素,动态规划与分治的联系区别,都是分解成子问题，由子问题的解得到原问题的解。分治中子问题相互独立，而动态规划中子问题互相有联系，且存在重复计算，即存在重叠子问题。,动态规划算法设计步骤,（1）找出最优解的性质，刻画其结构特征（2）递归地定义最优值（3）以自底向上的方式计算出最优值（4）根据计算最优值时得到的信息，构造一个最优解,矩阵连乘问题,给定n

14、个矩阵A1, A2, , An，其中Ai 是一个ri-1ri 矩阵( 1in)，即AiAi+1是可乘的，求出n个矩阵相乘的最优计算次序，使得计算量最小。,问题提出,设三个矩阵A1, A2, A3大小分别为10100，1005，550，考虑(A1( A2 A3), (A1A2) A3的结果与相乘的次数。,最优子结构特征,计算A1:n的一个最优次序所包含的计算矩阵子链A1:k和Ak+1:n的次序也是最优的矩阵连乘积计算次序问题的最优解包含着其子问题的最优解，也就是最优子结构性质。,矩阵连乘问题,考虑A1:k 和Ak+1:n相乘所需的计算量，A i: k 和A k+1:j 相乘呢,A1:k 的结果为

15、r0*rk的矩阵，Ak+1:n的结果为rk*rn的矩阵，则它们相乘的计算量为p0*pk*pn,2.建立递归关系,设计算A i: j 所需的最少次数为mij,原问题的最优解为m1n。当 i = j 时，A i : j = Ai ,m i i = 0,i=1,2,n。 当 i j 时m i j =m i k + m k+1 j + pi-1pkpj k i, i+1, , j-1 ,矩阵连乘问题,采用递归方法计算,int RecurMatrixChain( int i, int, j, int p) if ( ) return 0; int u=RecurMatrixChain(i, i)+Rec

16、urMatrixChain(i+1,j,p) +pi-1*pi*pj; sij=i; for(int k=i+1; kj; k+) int t=RecurMatrixChain(i,k)+RecurMatrixChain(k+1,j,p) +pi-1*pi*pj; if (tu) u=t; sij=k; return u;,参加运算矩阵链起始位置,矩阵链终止位置,i=j,取第一个断开位置时计算量,记录当前断开位置,循环取k的可取断开位置,矩阵连乘问题,递归树,14,11,24,12,34,13,44,22,34,23,44,11,22,33,44,11,23,12,33,33,44,22,33

17、,22,33,11,22,矩阵连乘问题,24,22,34,12,33,44,11,14,13,23,矩阵连乘问题,3.计算最优值,3.计算最优值,置所有只有一个矩阵的矩阵链计算量为0，即mii=0， i=1,2,n。通过上一步的结果可以得到所有矩阵链长度为2的子问题的最优计算量。通过上两步的结果可以得到所有矩阵链长度为3的子问题的最优计算量 ,矩阵连乘问题,计算m i j 时，只用到已计算出的m i k 和m k+1 j ,A1 A2 A3 A4 A5 A6 3035 3515 155 510 1020 2025,例32,设要计算矩阵连乘积A1A2A3A4A5A6 ,其中各矩阵的维数分别为,1

18、 2 3 4 5 6,15750,2625,750,1000,5000,m11 + m23+p0p1p3=7875m13=min m12 + m33 + p0p2p3=15750,9375,11875,15125,4375,7125,10500,2500,5375,3500,7875,i,j,3.计算最优值,void MatrixChain(int p, int n, int * *m, int * *s) for (int i=1; i=n; i+) mii= ;/单个矩阵的计算量 for (int r=2; r=n; r+)/r为每次循环矩阵链的长度 for (int i=1; i= ;

19、i+) int j=i+r-1; mij= mi+1j+pi-1*pi*pj; sij=i; for (int k=i+1; kj; k+) int t= mik+ mk+1j+ ; if (t mij) mij=t; sij=k; ,矩阵连乘问题,0,n r + 1,取第一个可取位置，即断开位置为i,循环取k的可取位置,pi-1*pk*pj,算法复杂度,算法MatrixChain 的主要计算量取决于程序中对r, i 和k 的三重循环，循环体内的计算量为O(1)，三重循环的总次数是O(n3)，所以，算法的计算时间上界为O(n3)。,4. 构造最优解,上述算法只是明确给出了矩阵最优连乘次序所用的

20、数乘次数m1n，并未明确给出最优连乘次序，即完全加括号方法。但是以sij为元素的2 维数组却给出了足够的信息。事实上，sij=k说明，计算连乘积Ai:j的最佳方式应该在矩阵Ak 和Ak+1 之间断开，即最优加括号方式为(Ai:k)(Ak+1:j)。,1 2 3 4 5 60 1 1 3 3 3 0 2 3 3 3 0 3 3 3 0 4 5 0 5 0,考虑计算A16时的顺序,S16,(A1A3) (A4A6),S13,A1(A2A3),S46,(A4A5) A6,S11=0,S23=0,A1(A2)(A3),S22= S33= 0,S66=0,S45=0,(A4)(A5) A6,S44= S

21、55= 0,根据最优值算法构造最优解,Void Traceback(int i, int j, int * * s) if (i=j) return; Traceback(i, sij, s); Traceback(sij+1, j, s); cout “Multiply A” i “,” sij; cout “and A” (sij +1) “,” j; endl; ,调用Traceback(1, n, s)即可得到A1:n,作业 1 当A1 A2 A3 A4 A5 分别为2025， 2510，105，515，1520的矩阵时，填写相应的mij和sij，并给出最优计算次序。,备忘录方法,用一

22、个表格来保存已解决的子问题的答案，用的时候查表即可。采用的递归方式是自顶向下，动态规划是自低向上控制结构与直接递归相同，区别在于备忘录方式为每个解过的子问题建立备忘录。初始化为每个子问题的记录存入一个特殊的值，表示并未求解。在求解过程中，查看相应记录如果是特殊值，表示未求解，否则只要取出该子问题的解答即可。,动态规划算法的基本要素,备忘录方法解矩阵乘,int MemoizedMatrixChain(int n,int *m,int *s) for(int i=1;i=n;i+) for(int j=i;j=n;j+) mij=0; return LookupChain(1,n);,动态规划算法

23、的基本要素,int LookupChain(int i, int j) if(mij0) return mij; if(i=j) return 0; int u=LookupChain(i,i)+LookupChain(i+1,j) +pi-1*pk*pj; sij=i; for(int k=i+1;kj;k+) int t=LookupChain(i,k) +LookupChain(k+1,j) +pi-1*pk*pj; if(tu) u=t; sij=k; mij=u; return u;,动态规划算法的基本要素,表示该子问题已经求解,递归求解断开位置为i时的计算量,循环每个可取断开位置求

24、计算量,作业：请写出利用备忘录方法计算A1:4时都计算了哪些子问题,动态规划算法的基本要素,备忘录采用自顶向下的计算，将计算结果存入矩阵后返回，每个子问题仅在第一次被调用时计算。mij共有O(n2)个备忘记录项，初始化需要O(n2)时间，每个记录项只填入一次，共耗费O(n)时间，所以备忘录方法耗时O(n3)。,当一个问题的所有子问题都至少要解一次时，则用动态规划算法比备忘录方法好当子问题空间中的部分子问题可不必求解时，用备忘录方法则较有利，因为从其控制结构可以看出，该方法只解哪些确实需要求解的子问题。,动态规划算法的基本要素,0-1背包问题,给定n种物品和一背包。物品i的重量是wi0，其价值为

25、vi0，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？,1. 最优子结构性质,证明0/1 背包问题具有最优子结构性质即若背包容量为c时，(y1, y2, yn )为待选物品为1到n时knap(1, n, c)的最优解，则(y2, yn )将是物品1作出选择后的子问题 的最优解,当第一个物品做出决策后，有两种状态 y1=0，则背包容量没有影响，(y2, yn )是 的最优解 y1=1，则背包减少w1，价值增长v1，(y2, yn )是 的最优解,x1,vixi,knap(2, n, c- w1*y1),knap(2, n,c),knap(2, n,c w1),2.

26、递归关系,设背包问题的子问题的最优值为m( i, j ),即m( i, j)是背包容量为j，可选择物品为i，i1，, n时的最优值。当选择第i个物品时， 。 如果不选择第i个物品，则 。由问题的最优子结构性质，我们可以建立计算m( i, j)的递归式如下：,m( i, j) = m(i + 1, j - wi) + vi,m( i, j) = m(i + 1, j),例: 四个物品，背包容积为5，w4=2, 1, 3, 2，v4=12, 10, 20, 15，求最大价值m1c及选取的物品编号,4,3,2,1,4,3,2,1,0,5,0,0,0,0,0,10,15,15,15,15,15,15,

27、20,20,35,35,30,25,37,i,j,x4 X3 X2 X1,1,m15m25所以物品1被选,c w1= 3,查看m23m33,1,j w2= 2,查看m32=m42,0,查看m420,1,3.算法描述,templatevoid Knapsack(Type v, int w, int c, int n, Type *m) int jMax = min( wn - 1, c ); for( int j = 0; j 1; i - ) jMax = min( w i - 1, c ); for(int j = 0; j = w1 ) m1c=max(m1c,m2c-w1+v1);,0,

28、vn,m i+1 j ,m 2 c ,初始化mnj,只剩下第一个物品时，如果剩余背包容积大于w1时，要进行选择,m15 m25,4,3,2,1,4,3,2,1,0,5,0,0,0,0,0,10,10,15,15,15,15,15,20,20,35,35,30,25,37,i,j,构造最优解,x1=1 c= 5- w1=3,m23 m33,x2=1 c= 3- w2=2,m32 = m42,x3=0 c= 2,m42 0,x4=1,构造最优解,TemplateVoid Traceback(Type *m,int w,int c,int n,int x) for(int i=1;in;i+) if

29、(mic=mi+1c)xi=0; else xi=1; c-=wi; xn=(mnc)?1:0;,4.计算复杂性分析,上述算法需要O(nc)计算时间，构造最优结构需要O(n)的计算时间缺点:算法要求每个物品的重量为整数,当背包容量c很大时，算法需要的计算时间较多。例如，c2n时，算法需要(n2n),n=3, (w1, w2, w3)=(2, 3, 4), v1, v2, v3=(1, 2, 5), c=5,3-4 钱币问题,3.5 最优二叉搜索树Optimal Binary Search Trees,最优二叉搜索树,利用动态规划构造对标识符集合a1, a2, , an的最优二叉搜索树算法包括成

30、功检索和不成功检索）。,最优二叉搜索树,3、最优二叉搜索树问题,对于有序集S及其存取概率分布 （a0, b1, a1, , bn, an），在所有表示有序集S的二叉搜索树中找出一棵具有最小平均路长的二叉搜索树。 结点在二叉搜索树中的层次越深，需要比较的次数就越多，因此要构造一棵最小二叉树，一般尽量把搜索概率较高的结点放在较高的层次。,最优二叉搜索树问题,4、最优子结构性质,假设选择 k为树根，则 1, 2, , k-1 和a0, a1, , ak-1 都将位于左子树 L 上，其余结点 (k+1, , n 和 ak, ak+1, , an)位于右子树 R 上。,k,L,R,1, 2, , k-1

31、 a0, a1, , ak-1,k+1, , n ak, ak+1, , an,最优子结构性质,4、最优子结构性质,二叉搜索树T 的一棵含有顶点xi , , xj和叶顶点 (xi-1 , xi ) , , ( xj , xj+1)的子树可以看作是有序集 xi , , xj 关于全集为 xi-1 , xj1 的一棵二叉搜索树（T 自身可以看作是有序集) 。根据S 的存取分布概率，在子树的顶点处被搜索到的概率是,最优子结构性质,左子树的搜索概率,右子树的搜索概率,设Tij是有序集xi , , xj关于存储概率分布为ai-1, bi, , bj, aj 的一棵最优二叉搜索树Pij ：平均路长xm ：

32、Tij的根顶点存储的元素pl和pr: 左子树Tl和右子树Tr的平均路长,构造最优二叉搜索树时，可以选择先构造其左右子树，使其左右子树最优，然后构造整棵树,最优子结构性质,5、递归计算最优值,最优二叉搜索树Tij的平均路长为pij，则所求的最优值为p1,n。由二叉树的花费公式根据最优二叉搜索树问题的最优子结构性质可建立计算pij的递归式如下,初始时,递归计算最优值,记wi,j pi,j为m( i, j ),递归计算最优值,例,给出标识符集1, 2, 3do, if, stop存取概率若P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.

33、05构造一棵最优二叉搜索树,递归计算最优值,P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05,T12,w12=0.9m12=0.9+ m11+m32 =1.65,w12=0.9m12=0.9+ m10+m22 =1.15,P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05,T12,w12=0.9m12=0.9+ m11+m32 =1.65,w12=0.9m12=0.9+ m10+m22 =1.15,T23w23=0. 5,m23=0.5,m23=0.6,P1=0

34、.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05,T12,w12=0.9m12=0.9+ m11+m32 =1.65,w12=0.9m12=0.9+ m10+m22 =1.15,T23w23=0. 5,m23=0.5,m23=0.6,P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05,T12m12=1.15,T23m23=0.5,T13W13=1,m13=1.5,m13=1.9,m13=2.15,P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=

35、0.1, q2=0.05, q3=0.05,T12m12=1.15,T23m23=0.5,2,3,q2,q3,1,q0,q1,T13W13=1,m13=1.5,2,3,q2,q3,1,q0,q1,m13=1.9,2,3,q2,q3,1,q0,q1,m13=2.15,P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05,0,1,2,3,1,2,3,0,0,0,0,4,0 1 2 3,1234,W(i, j),0 1 2 3,1234,0,0,0,0,0.15,0.1,0.05,0.05,0.75,0.75,1,0.25,0.15,0

36、.25,0.15,2,3,0.9,1.15,1,0.35,1,0. 5,2,1.5,1,m(i, j),s(i, j),void OptimalBinarySearchTree( int a, int b,int n, int *m, int *s, int *w) for( int i=0; i=n; i+) wi+1i=ai; mi+1i=0; for(int r=0; rn; r+) for(int i =1; i= n - r; i+) int j= j + r; wij=wij-1+aj+bj; mij=mi+1j; sij = i;,for(int k = i+1; k=j; k+

37、) int t=mik-1+mk+1j; if (tmij) mij=t; sij=k; mij+=wij; ,初始化对角线赋值,i为起始元素下标,j为终止元素下标,加第j个结点后，权值w改变,如第i个结点作根的值,取第k个结点作根,练习,设n=4，且 (1, 2, 3, 4) = (do, if, read, while)。又设b(1 : 4)=(3, 3, 1, 1)和a(0 : 4)=(2,3,1,1,1)(这些b,a都乘了16。)写出数组wij,mij,sij及最后的最优二叉搜索树,作业,P84 3-15,第4章,贪心算法的基本要素，思想，与动态规划的区别联系活动安排问题最优装载单源最

38、短路径多机调度问题,什么是贪心方法,如果硬币面值为1角1分、7分、5分、和1分。要找给顾客2角6分钱， 按贪心方法找出的硬币个数是：2个1角1分和四个1分，共6枚，这比1个1角1分和3个5分多了2枚；因此，从局部的最优选择得到的解并不总是问题的最优解。,贪心算法总是作出在当前看来最好的选择。 也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。,虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路径问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是

39、最优解的很好近似。,贪心算法通过一系列的选择来得到一个问题的解。它所做的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。希望通过每次所做的选择导致最终结果是问题的一个最优解。希望从局部的最优选择得到整体最优解。,贪心算法的基本要素,贪心算法的基本要素,贪心算法的基本要素,可用贪心算法求解的问题的基本要素 用贪心算法求解的问题，具有两个重要的性质：最优子结构性质贪心选择性质。,贪心算法的基本要素,1. 最优子结构性质,最优子结构性质整体最优解包含它的子问题的最优解。具有最优子结构性质是一个问题可用动态规划算法或贪心算法求解的一个关键特征。,贪心算法的基本要素,最优子结构性质,例： 活动安

40、排问题中最优子结构性质表现为：若A是对于E的活动安排问题包含活动1的一个最优解，则相容活动集合A= A 1是对于E =iE: sif1的活动安排问题的一个最优解,2.贪心选择性质,贪心选择性质:所求问题的整体最优解可以通过一系列局部最优的选择来完成即贪心选择来达到。这是贪心算法可行的要素。也是贪心算法与动态规划算法的主要区别。如找顾客钱币问题和图的染色问题不具有贪心选择性质。,贪心算法的基本要素,3.贪心算法与动态规划算法的差异,相同点：都具有最优子结构性质区别：动态规划算法每步所作的选择往往依赖于相关子问题的解。只有解出相关子问题才能作出选择。 贪心算法仅在当前状态下作出最好选择，即局部最优

41、选择，但不依赖于子问题的解 贪心：自顶向下 动态规划：自低向上,贪心算法的基本要素,贪心算法与动态规划算法的差异,对于一个具有最优子结构的问题应该选用贪心算法还是动态规划算法？是不是能用动态规划算法求解的问题也能用贪心算法来求解？,活动安排问题,已知n个活动 E = 1, 2, , n 要求使用同一资源，第k个活动要求的开始和结束时间为sk , fk , 其中sk fk , k = 1, 2, , n 。活动k与活动j称为相容的如果sk fj 或者sj fk。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集。,问题提出：,基本思路,在安排时应该将结束时间早的活动尽量往前安排，好给后面

42、的活动安排留出更多的空间，从而达到安排最多活动的目标。 贪心准则应当是：在未安排的活动中挑选结束时间最早的活动安排。,活动安排问题,活动安排贪心算法伪代码,templatevoid GreedySelector(int n, Type starttime , Type fintime ,bool A ) ,A1 = true; /用集合A来存储所选择的活动，活动i在集合A中， /当且仅当Ai的值为true,int join=1; /变量join用以记录最近一次加入到A中的活动,for(int i =2; i=finishtimejoin) /如果第i个任务和第j个相容 Ai = true; j

43、oin = i ; else Ai = false; ,活动安排问题,4.3 最优装载,有一艘大船用来装载货物。假设有n个货箱，它们的体积相同，重量分别是 货船的最大载重量是c。目标是在船上装最多货箱该怎样装？如果用 表示装第i个货箱，而 表示不装第i个货箱，则上述问题是解优化问题：求x1, x2,， xn，,问题提出,满足,使得,1.算法描述,采用重量最轻者先装的贪心选择策略. template void Loading ( int x , Type w ,Type c, int n) int *t = new int n + 1; sort ( w, t, n ); for ( int i

44、 = 1; i = n; i +) x i = 0; for( int i =1;i = n ,例,物品重量分别为15，10，27，18，船载重为50w =15, 10, 27, 18T = 1 , 0, 3, 2C=50wT0=10c,templatevoid Dijkstra(int n,int v, Type dist,int prev,Type*c) bool smaxin; for(int i = 1; i=n; i+) disti = cvi; si = false; if ( disti = maxint) previ = 0; else previ = v; distv = 0

45、; sv =true; for(int i =1; in; i+) int temp = maxint; int u = v;,将集合S初始化为空，初始化DIST数组,确定从结点v开始出发的n-1条路,确定前驱结点，初始时前驱为0或者源点,for( int j =1;j=n;j+) if(!sj) ,在n个结点中寻找路径最小者，如果第j个结点没有加进集合，且其路径长度小于当前的temp值，修改temp，最短的结点加进s,新加进结点u后，则所有和u相连的且没有加进s中的结点，其路径的值都可能有改变，如果改变后比原来的值小，则替换原来的值，且前驱改为u,多机调度问题,采用最长处理时间作业优先的贪心

46、选择策略可以设计出解多机调度问题的较好的近似算法。按此策略，当 时，只要将机器i的0,ti 时间区间分配给作业i即可当 时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。,class JobNode friend void Greedy( JobNode *, int, int ); friend void main( void ); public: operator int ( ) const return time; private: int ID, time; ;class Machine Node friend void Greedy( JobNo

47、de *, int, int ); public: operator int( ) const return avail; private: int ID, avail; ;,ID为作业的编号time为该作业需要的时间,ID为机器的编号avail记录该机器何时空闲,templatevoid Greedy(Type a,int n,int m) if( n H( m ); MachineNode x; for( int i = 1; i = m; i + ) x. avail = 0; x. ID = i; H. Insert( x ); ,for( int i = n; i = 1; i -

48、-) H.DeleteMin( x ); cout“将机器”x.ID“从” x.avail“到”(x.avail+ai.time) “的时间段分配给作业”ai.IDendl; x.avail + = a i . time; H. Insert( x ); ,如果作业数小于机器数，给每个作业分配一台机器,建立一个小堆，堆中每个结点存有一台机器的状态,初始化每台机器，开始都空闲，所以avail （记录该机器何时空闲）都为0，并把该机器插入堆中,取到堆中最早空闲的机器来处理第i个任务，把它从堆中删去，使得下一个最早空闲的机器在堆顶,将第i个任务占用的机器的空闲时间加上该任务的时间，并插入堆中,例如，

49、设7个独立作业1,2,3,4,5,6,7由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为2,14,4,16,6,5,3。按算法greedy产生的作业调度如下图所示，所需的加工时间为17。,第5章,回溯法的基本思想两种回溯方式及两种解空间树装载问题0-1背包问题图的M着色问题,回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种以深度优先的方式系统地搜索问题的解的方法称为回溯法。适用于解一些组合数相当大的问题。,回溯法在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯

50、定不包含问题的解，如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则进入该子树，继续按深度优先的策略进行搜索。,用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。用来求问题的任一解时，只要搜索到问题的一个解就可结束。回溯法适用于解一些组合数较大的问题。,回溯法的基本步骤,(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。,常用剪枝函数：用约束函数在扩展结点处剪去不满足约束的子树；用限界函数剪去得不到最优解的子树。,用回溯法解题的一个显著特征是在搜索过程中