数据结构第十章.优秀PPT.ppt

《数据结构第十章.优秀PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构第十章.优秀PPT.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 10.3 回溯法回溯法 有很多问题，当须要找出它的解集或者要求回答有很多问题，当须要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要运用什么解是满足某些约束条件的最佳解时，往往要运用回溯法。回溯法。回溯法的基本做法是搜寻，或是一种组织得井井有回溯法的基本做法是搜寻，或是一种组织得井井有条的、能避开不必要搜寻的穷举式搜寻法。这种方法条的、能避开不必要搜寻的穷举式搜寻法。这种方法适用于解一些组合数相当大的问题。适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，回溯法在问题的解空间树中，按深度优先策略，从根结点动身搜寻解空间树。算法搜寻至解空间树的从根结点

2、动身搜寻解空间树。算法搜寻至解空间树的随意一点时，先推断该结点是否包含问题的解：假如随意一点时，先推断该结点是否包含问题的解：假如确定不包含，则跳过对该结点为根的子树的搜寻，逐确定不包含，则跳过对该结点为根的子树的搜寻，逐层向其祖先结点回溯；否则，进入该子树，接着按深层向其祖先结点回溯；否则，进入该子树，接着按深度优先策略搜寻。度优先策略搜寻。一、回溯法的算法框架一、回溯法的算法框架1.1.问题的解空间：应用回溯法解问题时，首先应明确定义问题问题的解空间：应用回溯法解问题时，首先应明确定义问题的解空间。问题的解空间应至少包含问题的一个的解空间。问题的解空间应至少包含问题的一个(最优最优)解。解

3、。例如：例如：0 01 1背包问题：给定背包问题：给定n n种物品和一个背包，物品种物品和一个背包，物品i i的重量的重量是是wiwi，其价值为，其价值为vivi，背包的最大负重量是，背包的最大负重量是C C：如何选择装入背包：如何选择装入背包的物品，可以使得背包中物品的总价值最大？的物品，可以使得背包中物品的总价值最大？对于有对于有n n种可选物品的种可选物品的0-10-1背包问题，其解空间由长度为背包问题，其解空间由长度为n n的的0-10-1向量组成。当向量组成。当n n3 3时，解空间为：时，解空间为：000000、001001、010010、011011、100100、101101、

4、110110、111111；为了能够便利的运用回溯法解决问题，；为了能够便利的运用回溯法解决问题，我们一般将解空间组织成树或图的形式；我们一般将解空间组织成树或图的形式；2 2生成解空间的方法生成解空间的方法（1 1）扩展结点）扩展结点:一个正在产生儿子的结点称为扩展结点一个正在产生儿子的结点称为扩展结点;（2 2）活结点）活结点:一个自身已生成但其儿子还没有全部生成的节一个自身已生成但其儿子还没有全部生成的节 点称做活结点点称做活结点;（3 3）死结点）死结点:一个全部儿子已经产生的结点称做死结点一个全部儿子已经产生的结点称做死结点;深深度度优优先先的的问问题题状状态态生生成成法法：假假如如

5、对对一一个个扩扩展展结结点点R R，一一旦旦产产生生了了它它的的一一个个儿儿子子C C，就就把把C C当当做做新新的的扩扩展展结结点点。在在完完成成对对子子树树C C（以以C C为为根根的的子子树树）的的穷穷尽尽搜搜寻寻之之后后，将将R R重重新新变变成成扩展结点，接着生成扩展结点，接着生成R R的下一个儿子（假如存在）的下一个儿子（假如存在）.回回溯溯法法：为为了了避避开开生生成成那那些些不不行行能能产产生生最最佳佳解解的的问问题题状状态态，要要不不断断地地利利用用限限界界函函数数(bounding(bounding function)function)来来处处死死那那些些事事实实上上不不行

6、行能能产产生生所所需需解解的的活活结结点点，以以削削减减问问题题的的计计算算量量。具有限界函数的深度优先生成法称为回溯法。具有限界函数的深度优先生成法称为回溯法。3 3避开无效搜寻的方法：避开无效搜寻的方法：例例1 1：对对于于n n3 3的的0 01 1背背包包问问题题，考考虑虑：重重量量W W（1616，1515，1515）；价值价值p p（4545，2525，2525）；背包承重）；背包承重C C3030；起先搜寻解空间；起先搜寻解空间；最优解X=(0,1,1)，最优值V=50例例2 2：旅行售货员问题：某售货员要到若干个城市去推销商品，已：旅行售货员问题：某售货员要到若干个城市去推销商

7、品，已知各城市之间的路程（或旅费）。他要选定一条从驻地动身，经知各城市之间的路程（或旅费）。他要选定一条从驻地动身，经过每个城市一次，最终回到驻地的路途，使总的路程（或旅费）过每个城市一次，最终回到驻地的路途，使总的路程（或旅费）最短；最短；4123206305410 回溯法搜寻解空间树时，通常接受两种策略避开无效搜寻，提高搜寻效率：（1）用约束函数在扩展结点处剪去不满足约束的子树；（2）用限界函数剪去得不到最优解的子树。这两类函数通称为剪枝函数；最优解(1,3,2,4,1)，最优值2544 4子集树与排列树：子集树与排列树：（1 1）子子集集树树：当当所所给给的的问问题题从从n n个个元元素

8、素的的集集合合S S中中找找出出S S满满足足某某种种性性质质的的子子集集时时，相相应应的的解解空空间间称称为为子子集集树树；（n n个个元元素素，有有2n2n个叶子结点，满二叉树；个叶子结点，满二叉树；0 01 1背包问题）背包问题）用回溯法搜寻子集树的一般算法：用回溯法搜寻子集树的一般算法：void backtrack(int t)void backtrack(int t)if(tn)output(x);if(tn)output(x);else else for(int i=0;i=1;i+)for(int i=0;in)output(x);if(tn)output(x);else els

9、e for(int i=t;i=n;i+)for(int i=t;i=n;i+)swap(xt,xi);swap(xt,xi);if(legal(t)backtrack(t+1);if(legal(t)backtrack(t+1);swap(xt,swap(xt,xi);xi);遍遍历历排排列列树须要树须要O(n!)O(n!)计算时间计算时间 44 4回溯法解题步骤：回溯法解题步骤：(1)(1)针对所给问题，定义问题的解空间；针对所给问题，定义问题的解空间；(2)(2)确确定定易易于于搜搜寻寻的的解解空空间间结结构构(子子集集树或排列树树或排列树)；(3)(3)以以深深度度优优先先方方式式搜搜

10、寻寻解解空空间间，并并在在搜寻过程中用剪枝函数避开无效搜寻。搜寻过程中用剪枝函数避开无效搜寻。实实现现方方法法：回回溯溯法法对对解解空空间间作作深深度度优优先先搜搜寻寻，因因此此，在在一一般般状状况况下下用用递递归归方方法法实实现现回回溯溯法法。也也可可将将回回溯溯法法表表示为一个非递归迭代过程。示为一个非递归迭代过程。注注：用用回回溯溯法法解解题题的的一一个个显显著著特特征征是是在在搜搜寻寻过过程程中中动动态态产产生生问问题题的的解解空空间间。在在任任何何时时刻刻，算算法法只只保保存存从从根根结结点点到到当当前前扩扩展展结结点点的的路路径径。假假如如解解空空间间树树中中从从根根结结点点到到叶

11、叶结结点点的的最最长长路路径径的的长长度度为为n n，则则回回溯溯法法所所需需的的计计算算空空间间通通常常为为O(n)O(n)。而而显显式式地地存存储储整整个个解解空空间间则则须须要要O(2n)O(2n)或或O(n!)O(n!)内存空间。内存空间。1 10 01 1背包问题：背包问题：解空间：解空间：子集树子集树 可行性约束函数：可行性约束函数：上界函数：上界函数：解解：设设n n件件物物品品的的重重量量分分别别为为w w0 0，w w1 1，w wn n1 1，物物品品的的价价值值为为v v0 0，v v1 1，v vn n1 1；用用optionoption数数组组存存放放最最优优解解，其

12、其中中每每个个元元素取素取1 1或或0 0；include include#define MaxSize 100#define MaxSize 100 /最多物品数最多物品数 int limitw;/限制的总重量限制的总重量 int maxwv=0;/存放最优解的总价值存放最优解的总价值 int maxw;int n;/实际物品数实际物品数 int optionMaxSize;/存放最终解存放最终解 int opMaxSize;/存放临时解存放临时解struct int weight;int value;AMaxSize;/存放物品数组存放物品数组 void Knap(int i,int tw

13、,int tv)/考虑第考虑第i个物品个物品int j;if(i=n)/找到一个叶子结点找到一个叶子结点 if(twmaxv)/找到一个满足条件地更优解，保存它找到一个满足条件地更优解，保存它 maxv=tv;maxw=tw;for(j=0;jn;j+)optionj=opj;else opi=1;/选取第选取第i个物品个物品 Knap(i+1;tw+ai.weight,tv+ai.value);Opi=0;/不选取第不选取第i个物品，回溯个物品，回溯 Knap(i+1,tw,tv);void main()int j;n=4;/4种物品种物品 a0.weight=5;a0.value=4;a1

14、.weight=3;a1.value=4;a2.weight=2;a2.value=3;a3.weight=1;a3.value=1;limitw=7;/限制重量不超过限制重量不超过7 knap(0,0,0);cout”最佳装填方案是：最佳装填方案是：“endl;for(j=0;jn;j+)if(optionj=1)cout”第第”j”种物品种物品”endl;cout”总重量总重量“maxw”,总价值总价值“maxvendl;2.2.全排列问题：全排列问题：描述：输入描述：输入n n个不同的字符，给出他们全部的个不同的字符，给出他们全部的n n个字符的全排列；个字符的全排列；void perm

15、(char str,int k;int n)void perm(char str,int k;int n)int i;char tmp;int i;char tmp;if(k=n-1)if(k=n-1)for(int i=0;in;i+)coutstri”;for(int i=0;in;i+)coutstri”;coutendl;coutendl;else for(i=k;in;i+)else for(i=k;in;i+)tmp=strk;strk=stri;stri=tmp;tmp=strk;strk=stri;stri=tmp;perm(str,k+1,n);perm(str,k+1,n)

16、;tmp=stri;tmp=stri;stri=strk;strk=tmp;stri=strk;strk=tmp;3 3旅行售货员问题：旅行售货员问题：解空间：排列树解空间：排列树#define Max 32767#define n 4main()int n;/图顶点数图顶点数 int xn+1;/当前解当前解 int bestxn+1;/当前最优解当前最优解 float bestc;/当前最优值当前最优值 float cc=0;/当前费用当前费用 float an+1n+1;/图邻接矩阵图邻接矩阵 for(i=1;i=n;i+)xi=i;bestc=Max;backtrack(2);cout

17、”最优结果为最优结果为“bestcendl;Void backtrack(int i)if(i=n)if(axn-1xn MAX&axn1 MAX&(bestc=MAX|cc+axn-1xn+axn1bestc)for(int j=1;j=n;j+)bestxj=xj;bestc=cc+axn-1xn+axn1;else for(int j=i;j=n;j+)/是否可进入是否可进入xj子树子树?if(axi-1xj MAX&(bestc=MAX|cc+axi-1xj0)/while(k0)/对全部列执行以下语句；对全部列执行以下语句；qk=qk+1;/qk=qk+1;/移到下一行移到下一行 W

18、hile(qk=n&!Place(k)/While(qk=n&!Place(k)/找合适位置找合适位置 qk=qk+1;qk=qk+1;if(qk=n)if(qk=n)if(k=n)print(n);if(k=n)print(n);else k+;/else k+;/转向下一列转向下一列 qk=0;/qk=0;/从行头起先找从行头起先找 else k-;/else k-;/回溯上一列；回溯上一列；10.5 贪心算法贪心算法一、基本思想一、基本思想 例：找硬币问题：假设有例：找硬币问题：假设有4种硬币，面值分别为二角五分、一种硬币，面值分别为二角五分、一角、五分、一分。现要找给顾客六角三分钱，如

19、何找拿出的硬币角、五分、一分。现要找给顾客六角三分钱，如何找拿出的硬币个数最少？个数最少？解：一种方法：首先选一个不超过解：一种方法：首先选一个不超过0.63的硬币（的硬币（0.25），然后），然后剩下剩下0.38，再找一个不超过，再找一个不超过0.38的硬币（的硬币（0.25），剩下），剩下0.13，这种方法就是贪心算法。这种方法就是贪心算法。顾名思义，贪心算法总是作出在当前看来最好的选择。也就顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心

20、算法得到的最终结果也意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。具有最优子结构性质的问题也可以用动态规划法是整体最优的。具有最优子结构性质的问题也可以用动态规划法解决，但是贪心算法更简洁、更干脆，且解体效率更高；解决，但是贪心算法更简洁、更干脆，且解体效率更高；但上述算法利用了硬币面值得特殊性，假如把硬币的面值改为3种：0.01、0.05、0.11，要找顾客0.15元钱。用贪心算法得到的解为:实际的最优解是:虽然贪心算法不能对全部问题都得到整体最优解，但对很多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些状况下，即使贪心算法不能得到整体最优解，其

21、最终结果却是最优解的很好近似。二、活动支配问题二、活动支配问题 活动支配问题就是要在所给的活动集合中选出最活动支配问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地支配一系列争用某一公很好例子。该问题要求高效地支配一系列争用某一公共资源的活动。贪心算法供应了一个简洁、美丽的方共资源的活动。贪心算法供应了一个简洁、美丽的方法使得尽可能多的活动能兼容地运用公共资源。法使得尽可能多的活动能兼容地运用公共资源。设有设有n n个活动的集合个活动的集合E=1,2,nE=1,2,n，其中每个活动，其中每个活

22、动都要求运用同一资源，如演讲会场等，而在同一时间都要求运用同一资源，如演讲会场等，而在同一时间内只有一个活动能运用这一资源。每个活动内只有一个活动能运用这一资源。每个活动i i都有一个都有一个要求运用该资源的起始时间要求运用该资源的起始时间sisi和一个结束时间和一个结束时间fi,fi,且且si fi si fi。假如选择了活动。假如选择了活动i i，则它在半开时间区间，则它在半开时间区间si,fi)si,fi)内占用资源。若区间内占用资源。若区间si,fi)si,fi)与区间与区间sj,sj,fj)fj)不相交，则称活动不相交，则称活动i i与活动与活动j j是相容的。也就是说，是相容的。也

23、就是说，当当sifjsifj或或sjfisjfi时，活动时，活动i i与活动与活动j j相容。相容。在下面所给出的解活动支配问题的贪心算法在下面所给出的解活动支配问题的贪心算法greedySelector:greedySelector:int greedySelector(int s,int f,boolean a)int greedySelector(int s,int f,boolean a)/设输入的活动以完成时间设输入的活动以完成时间 f f 的非减序排列的非减序排列 int n;/int n;/活活动个数动个数 a1=true;a1=true;int j=1,count=1;int

24、j=1,count=1;for(i=2;i=n;i+)for(i=2;i=fj)if(si=fj)ai=true;ai=true;j=i;j=i;count+;count+;else ai=false;else ai=false;return count;return count;由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未支配活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可支配时间段极大化，以便支配尽可能多的相容活动。算法greedySelector的效率

25、极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间支配n个活动，使最多的活动能相容地运用公共资源。假如所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。例：设待支配的例：设待支配的11个活动的起先时间和结束时间按结束时间的个活动的起先时间和结束时间按结束时间的非减序排列如下：非减序排列如下：若被检查的活动i的起先时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。贪心算法并不总能求得问题的整体最优解。但对于活动支配问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可

26、以用数学归纳法证明。i1234567891011Si130535688212Fi4567891011121314三、贪心算法的基本要素三、贪心算法的基本要素 对于一个具体的问题，怎么知道是否可用贪心算对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢法解此问题，以及能否得到问题的最优解呢?这个问这个问题很难赐予确定的回答。题很难赐予确定的回答。但是，从很多可以用贪心算法求解的问题中看到但是，从很多可以用贪心算法求解的问题中看到这类问题一般具有这类问题一般具有2 2个重要的性质：贪心选择性质和个重要的性质：贪心选择性质和最优子结构性质。最优子结构性质。1.1.贪心选

27、择性质贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区分。与动态规划算法的主要区分。动态规划算法通常以自底向上的方式解各子问题，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所方式作出相继的贪心选择，每作一次贪

28、心选择就将所求问题简化为规模更小的子问题。求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择对于一个具体问题，要确定它是否具有贪心选择性质，必需证明每一步所作的贪心选择最终导致问题性质，必需证明每一步所作的贪心选择最终导致问题的整体最优解。的整体最优解。2.2.最优子结构性质最优子结构性质 当一个问题的最优解包含其子问题的最优解时，当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键质是该问题可用动态规划算法或贪心算法求解的关键特征。特征。3.3

29、.贪心算法与动态规划算法的差异贪心算法与动态规划算法的差异 贪心算法和动态规划算法都要求问题具有最优子贪心算法和动态规划算法都要求问题具有最优子结构性质，这是结构性质，这是2 2类算法的一个共同点。但是，对于具类算法的一个共同点。但是，对于具有最优子结构的问题应当选用贪心算法还是动态规划有最优子结构的问题应当选用贪心算法还是动态规划算法求解算法求解?是否能用动态规划算法求解的问题也能用贪是否能用动态规划算法求解的问题也能用贪心算法求解心算法求解?下面探讨下面探讨2 2个经典的组合优化问题，并以个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。此说明贪心算法与动态规划算法的主要差

30、别。（1）0-1背包问题：背包问题：给定给定n种物品和一个背包。物品种物品和一个背包。物品i的重量是的重量是Wi，其价值为，其价值为Vi，背包的容量为背包的容量为C。应如何选择装入背包的物品，使得装入背包。应如何选择装入背包的物品，使得装入背包中物品的总价值最大中物品的总价值最大?在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i只有只有2种选择，即装种选择，即装入背包或不装入背包。不能将物品入背包或不装入背包。不能将物品i装入背包多次，也不能只装装入背包多次，也不能只装入部分的物品入部分的物品i。（2）背包问题：）背包问题：与与0-1背包问题类似，所不同的是在选择物品背包

31、问题类似，所不同的是在选择物品i装入背包时，装入背包时，可以选择物品可以选择物品i的一部分，而不确定要全部装入背包，的一部分，而不确定要全部装入背包，1in。这这2类问题都具有最优子结构性质，极为相像，但背包问题类问题都具有最优子结构性质，极为相像，但背包问题可以用贪心算法求解，而可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。背包问题却不能用贪心算法求解。（3 3）用贪心算法解背包问题的基本步骤：）用贪心算法解背包问题的基本步骤：首先计算每种物品单位重量的价值首先计算每种物品单位重量的价值Vi/WiVi/Wi，然后，依贪心选择，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物

32、品装入背包。若将这策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过种物品全部装入背包后，背包内的物品总重量未超过C C，则选择单，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略始终地位重量价值次高的物品并尽可能多地装入背包。依此策略始终地进行下去，直到背包装满为止。进行下去，直到背包装满为止。具体算法可描述如下具体算法可描述如下:float knapsack(float*p,float*w,float*x,float m,int n)float knapsack(float*p,float*w,float*x,float m,i

33、nt n)/p/p存放物品价格；存放物品价格；ww存放重量；物品已经按存放重量；物品已经按pi/wipi/wi降序降序 存放；存放；m m为背包内物品总重；为背包内物品总重；n n为物品件数；为物品件数；x x存放解向量；存放解向量；int i;float s=0;int i;float s=0;for(i=0;in;i+)xi=0;for(i=0;in;i+)xi=0;i i0 0；while(in&wim)while(in&wim)m=m-wi;s=s+pi;m=m-wi;s=s+pi;xi=1;xi=1;i+;i+;if(i0)xi=m/wi;s+=pi*xi;i+;return s;算

34、法knapsack的时间代价为O（n），但该方法的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，此方法的计算时间上界为O（nlogn）。当然，为了证明算法的正确性，还必需证明背包问题具有贪心选择性质。对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种状况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出很多相互重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。事实上也是如此，动态规划算法的确可以有效地解0-1背包问题

35、。四、最优装载问题：四、最优装载问题：有一批集装箱要装上一艘载重量为有一批集装箱要装上一艘载重量为c c的轮船。其中集装箱的轮船。其中集装箱i i的重量为的重量为WiWi。最优装载问题要求确定在装载体积不受限制的状。最优装载问题要求确定在装载体积不受限制的状况下，将尽可能多的集装箱装上轮船。况下，将尽可能多的集装箱装上轮船。1.1.算法描述算法描述 最优装载问题可用贪心算法求解。接受重量最轻者先装的最优装载问题可用贪心算法求解。接受重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解贪心选择策略，可产生最优装载问题的最优解 float loading(float c,float w,int

36、 x )float loading(float c,float w,int x )int n;int n;for(int i=0;i n;i+)for(int i=0;i n;i+)di=new Element(wi,i);di=new Element(wi,i);MergeSort.mergeSort(d);MergeSort.mergeSort(d);float opt=0;float opt=0;for(int i=0;i n;i+)xi=0;for(int i=0;i n;i+)xi=0;for(int i=0;i n&di.w=c;i+)xdi.i=1;opt+=di.w;c-=di

37、.w;return opt;2.贪心选择性质贪心选择性质 可以证明最优装载问题具有贪心选择性质。可以证明最优装载问题具有贪心选择性质。3.最优子结构性质最优子结构性质 最优装载问题具有最优子结构性质。最优装载问题具有最优子结构性质。由最优装载问题的贪心选择性质和最优子结构性质，简洁证由最优装载问题的贪心选择性质和最优子结构性质，简洁证明算法明算法loading的正确性。算法的正确性。算法loading的主要计算量在于将集的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。五、最小生成树问题：五、最小生成树问题：

38、设设G=(V,E)G=(V,E)是无向连通带权图，即一个网络。是无向连通带权图，即一个网络。E E中每条边中每条边(v,w)(v,w)的权为的权为cvwcvw。假如。假如G G的子图的子图GG是一棵包含是一棵包含G G的全部顶的全部顶点的树，则称点的树，则称GG为为G G的生成树。生成树上各边权的总和称为的生成树。生成树上各边权的总和称为该生成树的耗费。在该生成树的耗费。在G G的全部生成树中，耗费最小的生成树称的全部生成树中，耗费最小的生成树称为为G G的最小生成树。的最小生成树。1.1.最小生成树性质最小生成树性质 用贪心算法设计策略可以设计出构造最小生成树的有效用贪心算法设计策略可以设计

39、出构造最小生成树的有效算法。本节介绍的构造最小生成树的算法。本节介绍的构造最小生成树的PrimPrim算法和算法和KruskalKruskal算法算法都可以看作是应用贪心算法设计策略的例子。尽管这都可以看作是应用贪心算法设计策略的例子。尽管这2 2个算法个算法做贪心选择的方式不同，它们都利用了下面的最小生成树性做贪心选择的方式不同，它们都利用了下面的最小生成树性质：质：设设G=(V,E)G=(V,E)是连通带权图，是连通带权图，U U是是V V的真子集。假如的真子集。假如(u,v)(u,v)E E，且，且u u U U，v v V-UV-U，且在全部这样的边中，且在全部这样的边中，(u,v)(

40、u,v)的的权权cuvcuv最小，那么确定存在最小，那么确定存在G G的一棵最小生成树，它以的一棵最小生成树，它以(u,v)(u,v)为其中一条边。这特性质有时也称为为其中一条边。这特性质有时也称为MSTMST性质。性质。2 2PrimPrim算法：算法：利用最小生成树性质和数学归纳法简洁证明，上述算法中利用最小生成树性质和数学归纳法简洁证明，上述算法中的边集合的边集合T T始终包含始终包含G G的某棵最小生成树中的边。因此，在算法的某棵最小生成树中的边。因此，在算法结束时，结束时，T T中的全部边构成中的全部边构成G G的一棵最小生成树。的一棵最小生成树。3.Kruskal3.Kruskal算法算法 Kruskal Kruskal算法构造算法构造G G的最小的最小生成树的基本思想生成树的基本思想:当图的边数为当图的边数为e e时，时，KruskalKruskal算法所需的计算时间算法所需的计算时间是是O O（elogeeloge）。当）。当en2en2时，时，KruskalKruskal算法比算法比PrimPrim算法差，算法差，但当但当e en2n2时，时，KruskalKruskal算法却算法却比比PrimPrim算法好得多。算法好得多。