《数据结构第十章(2)..ppt》由会员分享，可在线阅读，更多相关《数据结构第十章(2)..ppt（33页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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、110110、
4、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 function)(bounding 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 1）用）用约束函数约束函数在扩展结点处剪去不满足约束的子树；在扩展结点处剪去不满足约束的子树；（2 2）用）用限界函数限界函数剪去得不到最优解的子树。剪去得不到最优解的子树。这两类函数通称为剪枝函数；这两类函
8、数通称为剪枝函数；最优解(1,3,2,4,1)，最优值2544 4子集树与排列树：子集树与排列树：（1 1）子子集集树树：当当所所给给的的问问题题从从n n个个元元素素的的集集合合S S中中找找出出S S满满足足某某种种性性质质的的子子集集时时，相相应应的的解解空空间间称称为为子子集集树树；（n n个个元元素素，有有2 2n n个叶子结点，满二叉树；个叶子结点，满二叉树；0 01 1背包问题）背包问题）用回溯法搜索子集树的一般算法：用回溯法搜索子集树的一般算法：void backtrack(int t)if(tn)output(x);else for(int i=0;in)output(x);
9、else for(int i=t;i=n;i+)swap(xt,xi);if(legal(t)backtrack(t+1);swap(xt,xi);遍历排列树需要遍历排列树需要O(n!)计算时间计算时间 44 4回溯法解题步骤：回溯法解题步骤：(1)(1)针对所给问题，针对所给问题，定义问题的解空间定义问题的解空间；(2)(2)确确定定易易于于搜搜索索的的解解空空间间结结构构(子子集集树树或或排排列树列树)；(3)(3)以以深深度度优优先先方方式式搜搜索索解解空空间间，并并在在搜搜索索过程中用过程中用剪枝函数剪枝函数避免无效搜索。避免无效搜索。实实现现方方法法：回回溯溯法法对对解解空空间间作作
10、深深度度优优先先搜搜索索，因因此此，在在一一般般情情况况下下用用递递归归方方法法实实现现回回溯溯法法。也也可可将将回溯法表示为一个非递归迭代过程。回溯法表示为一个非递归迭代过程。注注：用用回回溯溯法法解解题题的的一一个个显显著著特特征征是是在在搜搜索索过过程程中中动动态态产产生生问问题题的的解解空空间间。在在任任何何时时刻刻，算算法法只只保保存存从从根根结结点点到到当当前前扩扩展展结结点点的的路路径径。如如果果解解空空间间树树中中从从根根结结点点到到叶叶结结点点的的最最长长路路径径的的长长度度为为n n，则则回回溯溯法法所所需需的的计计算算空空间间通通常常为为O(nO(n)。而而显显式式地地存
11、存储储整整个个解解空空间间则则需需要要O(2O(2n n)或或O(nO(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数数组组存存放放最最优优解解，其其中中每每个个元元素取素取1 1或或0 0；include include#define#define MaxSizeMaxSize 100 10
12、0 /最多物品数最多物品数 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,int tv)/考虑第考虑第i个物品个物品int j;if(i=n)/找到一个叶子结点找到一个叶子结点 if(twmaxv)/找到一个满足条件地更
13、优解，保存它找到一个满足条件地更优解，保存它 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.weight=3;a1.value=4;a2.weight=2;a2.value=3;a3.weight=1;a3.value=1;limitw=
14、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(char str,int k;int n)int i;char tmp;if(k=n-1)for(int i=0;in;i+)coutstri”;
15、coutendl;else for(i=k;in;i+)tmp=strk;strk=stri;stri=tmp;perm(str,k+1,n);tmp=stri;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(
16、i=1;i=n;i+)xi=i;bestc=Max;backtrack(2);cout”最优结果为最优结果为“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)/对所有列执行以下语句；对所有列执行以下
17、语句；qk=qk+1;/移到下一行移到下一行 While(qk=n&!Place(k)/找合适位置找合适位置 qk=qk+1;if(qk=n)if(k=n)print(n);else k+;/转向下一列转向下一列 qk=0;/从行头开始找从行头开始找 else k-;/回溯上一列；回溯上一列；10.5 10.5 贪心算法贪心算法一、基本思想一、基本思想 例：找硬币问题：假设有例：找硬币问题：假设有4 4种硬币，面值分别为二角五分、一种硬币，面值分别为二角五分、一角、五分、一分。现要找给顾客六角三分钱，如何找拿出的硬币角、五分、一分。现要找给顾客六角三分钱，如何找拿出的硬币个数最少？个数最少？解
18、：一种方法：首先选一个不超过解：一种方法：首先选一个不超过0.630.63的硬币（的硬币（0.250.25），），然后剩下然后剩下0.380.38，再找一个不超过，再找一个不超过0.380.38的硬币（的硬币（0.250.25），剩下），剩下0.130.13，这种方法就是贪心算法。，这种方法就是贪心算法。顾名思义，贪心算法总是作出在当前看来最好的选择。也就顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也意义上的局部最优选择。
19、当然，希望贪心算法得到的最终结果也是整体最优的。具有最优子结构性质的问题也可以用动态规划法是整体最优的。具有最优子结构性质的问题也可以用动态规划法解决，但是贪心算法更简单、更直接，且解体效率更高；解决，但是贪心算法更简单、更直接，且解体效率更高；但上述算法利用了硬币面值得特殊性，如果把硬但上述算法利用了硬币面值得特殊性，如果把硬币的面值改为币的面值改为3 3种：种：0.010.01、0.050.05、0.110.11，要找顾客，要找顾客0.150.15元钱。元钱。用用贪心算法贪心算法得到的解为得到的解为:实际的实际的最优解最优解是是:虽然贪心算法不能对所有问题都得到整体最优解，虽然贪心算法不能
20、对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。优解的很好近似。二、活动安排问题二、活动安排问题 活动安排问题活动安排问题就是要在所给的活动集合中选出最大就是要在所给的活动集合中选出最大的的相容活动子集合相容活动子集合，是可以用贪心算法有效求解的很，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共好例子。该问题要
21、求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。使得尽可能多的活动能兼容地使用公共资源。设有设有n n个活动的集合个活动的集合E=1,2,nE=1,2,n，其中每个活动，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动内只有一个活动能使用这一资源。每个活动i i都有一个都有一个要求使用该资源的起始时间要求使用该资源的起始时间sisi和一个结束时间和一个结束时间fifi,且且sisi fif
22、i 。如果选择了活动。如果选择了活动i i，则它在半开时间区间，则它在半开时间区间 sisi,fifi)内占用资源。若区间内占用资源。若区间 sisi,fifi)与区间与区间 sjsj,fjfj)不相交不相交，则称活动，则称活动i i与活动与活动j j是相容的。也就是说，是相容的。也就是说，当当sifjsifj或或sjfisjfi时，活动时，活动i i与活动与活动j j相容。相容。在下面所给出的解活动安排问题的贪心算法在下面所给出的解活动安排问题的贪心算法greedySelectorgreedySelector:int greedySelector(int s,int f,boolean a)
23、/设输入的活动以完成时间设输入的活动以完成时间 f 的非减序排列的非减序排列 int n;/活动个数活动个数 a1=true;int j=1,count=1;for(i=2;i=fj)ai=true;j=i;count+;else ai=false;return count;由于输入的活动以其完成时间的非减序排列，所由于输入的活动以其完成时间的非减序排列，所以算法以算法greedySelectorgreedySelector每次总是选择具有最早完成时每次总是选择具有最早完成时间的相容活动加入集合间的相容活动加入集合A A中。直观上，按这种方法选中。直观上，按这种方法选择相容活动为未安排活动留下
24、尽可能多的时间。也就择相容活动为未安排活动留下尽可能多的时间。也就是说，是说，该算法的贪心选择的意义是使剩余的可安排时该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动间段极大化，以便安排尽可能多的相容活动。算法算法greedySelectorgreedySelector的效率极高。当输入的活动的效率极高。当输入的活动已按结束时间的非减序排列，算法只需已按结束时间的非减序排列，算法只需O(nO(n)的时间安的时间安排排n n个活动，使最多的活动能相容地使用公共资源。个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用如果所给出的活动未按非
25、减序排列，可以用O(nlognO(nlogn)的时间重排。的时间重排。例：设待安排的例：设待安排的11个活动的开始时间和结束时间按结束时间的个活动的开始时间和结束时间按结束时间的非减序排列如下：非减序排列如下：若被检查的活动若被检查的活动i i的开始时间的开始时间SiSi小于最近选择的活动小于最近选择的活动j j的结束时间的结束时间fifi，则不选择活动，则不选择活动i i，否则选择活动，否则选择活动i i加入集加入集合合A A中。中。贪心算法并不总能求得问题的整体最优解。但对于贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，贪心算法活动安排问题，贪心算法greedySelector
26、greedySelector却总能求得的却总能求得的整体最优解，即它最终所确定的相容活动集合整体最优解，即它最终所确定的相容活动集合A A的规模最的规模最大。这个结论可以用数学归纳法证明。大。这个结论可以用数学归纳法证明。i1234567891011Si130535688212Fi4567891011121314三、贪心算法的基本要素三、贪心算法的基本要素 对于一个具体的问题，怎么知道是否可用贪心算法解此问对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢题，以及能否得到问题的最优解呢?这个问题很难给予肯定的这个问题很难给予肯定的回答。回答。但是，从许多可以用贪心
27、算法求解的问题中看到这类问题但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有一般具有2 2个重要的性质：个重要的性质：贪心选择性质和最优子结构性质。贪心选择性质和最优子结构性质。1.1.贪心选择性质贪心选择性质 所谓所谓贪心选择性质贪心选择性质是指所求问题的整体最优解可以通过一是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。的第一个基本要素，也是贪心算法与动态规划算法的主要区别。动态规划算法动态规划算法通常以自底向上的方式解各子问题，而
28、贪心通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。须证明每一步所作的贪心选择最终导致问题的整体最优解。2.2.最优子结构性质最优子结构性质 当一个问题的最优解包含其子问题的最优解时，当一个问题的最优解包含其子问题的最优解时，
29、称此问题具有最优子结构性质。问题的最优子结构性称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键质是该问题可用动态规划算法或贪心算法求解的关键特征。特征。3.3.贪心算法与动态规划算法的差异贪心算法与动态规划算法的差异 贪心算法和动态规划算法都要求问题具有最优子贪心算法和动态规划算法都要求问题具有最优子结构性质，这是结构性质，这是2 2类算法的一个共同点。但是，对于具类算法的一个共同点。但是，对于具有最优子结构的问题应该选用贪心算法还是动态规划有最优子结构的问题应该选用贪心算法还是动态规划算法求解算法求解?是否能用动态规划算法求解的问题也能用贪是否能用
30、动态规划算法求解的问题也能用贪心算法求解心算法求解?下面研究下面研究2 2个经典的组合优化问题，并以个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。此说明贪心算法与动态规划算法的主要差别。（1）0-1背包问题：背包问题：给定给定n n种物品和一个背包。物品种物品和一个背包。物品i i的重量是的重量是WiWi，其其价值为价值为ViVi，背包的容量为背包的容量为C C。应如何选择装入背包的应如何选择装入背包的物品，使得装入背包中物品的总价值最大物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i i只有只有2 2种种选择，即
31、装入背包或不装入背包。不能将物品选择，即装入背包或不装入背包。不能将物品i i装入装入背包多次，也不能只装入部分的物品背包多次，也不能只装入部分的物品i i。（2 2）背包问题：背包问题：与与0-10-1背包问题类似，所不同的是在选择物品背包问题类似，所不同的是在选择物品i i装装入背包时，可以选择物品入背包时，可以选择物品i i的一部分，而不一定要全的一部分，而不一定要全部装入背包，部装入背包，1in1in。这这2 2类问题都具有最优子结构性质，极为相似，类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而但背包问题可以用贪心算法求解，而0-10-1背包问题却背包问题却不能
32、用贪心算法求解。不能用贪心算法求解。（3 3）用贪心算法解背包问题的基本步骤：）用贪心算法解背包问题的基本步骤：首先计算每种物品首先计算每种物品单位重量的价值单位重量的价值Vi/Vi/WiWi，然后，依贪心选择然后，依贪心选择策略，将尽可能多的策略，将尽可能多的单位重量价值最高单位重量价值最高的物品装入背包。若将这的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过种物品全部装入背包后，背包内的物品总重量未超过C C，则选择单则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。进行下
33、去，直到背包装满为止。具体算法可描述如下具体算法可描述如下:float knapsack(float*p,float*w,float*x,float float knapsack(float*p,float*w,float*x,float m,intm,int n)n)/pp存放物品价格；存放物品价格；ww存放重量；物品已经按存放重量；物品已经按pi/wipi/wi降序降序 存放；存放；m m为背包内物品总重；为背包内物品总重；n n为物品件数；为物品件数；xx存放解向量；存放解向量；intint i;float s=0;i;float s=0;for(i=0;in;i+)xi=0;for(i
34、=0;in;i+)xi=0;i i0 0；while(in&wim)m=m-wi;s=s+pi;xi=1;i+;if(i0)xi=m/wi;s+=pi*xi;i+;return s;算法算法knapsack的的时间代价为时间代价为O（n），），但该方法的主但该方法的主要计算时间在于将各种物品依其单位重量的价值从大到小要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，此方法的计算时间上界为排序。因此，此方法的计算时间上界为O（nlogn）。）。当然，当然，为了证明算法的正确性，还必须证明背包问题具有贪心选为了证明算法的正确性，还必须证明背包问题具有贪心选择性质择性质。对于对于0-10
35、-1背包问题，贪心选择之所以不能得到背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它最优解是因为在这种情况下，它无法保证最终能将无法保证最终能将背包装满背包装满，部分闲置的背包空间使每公斤背包空间，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑的价值降低了。事实上，在考虑0-10-1背包问题时，背包问题时，应比较选择该物品和不选择该物品所导致的最终方应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解叠的子问题。这正是该问题可用动态规划算法求解
36、的另一重要特征。实际上也是如此，动态规划算法的另一重要特征。实际上也是如此，动态规划算法的确可以有效地解的确可以有效地解0-10-1背包问题。背包问题。四、最优装载问题：四、最优装载问题：有一批集装箱要装上一艘载重量为有一批集装箱要装上一艘载重量为c c的轮船。其中集装箱的轮船。其中集装箱i i的重量为的重量为WiWi。最优装载问题要求确定在装载体积不受限制的情最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。况下，将尽可能多的集装箱装上轮船。1.1.算法描述算法描述 最优装载问题可用贪心算法求解。采用重量最轻者先装的最优装载问题可用贪心算法求解。采用重量最轻者先装的
37、贪心选择策略，可产生最优装载问题的最优解贪心选择策略，可产生最优装载问题的最优解 float loading(float c,float w,int x )int n;for(int i=0;i n;i+)di=new Element(wi,i);MergeSort.mergeSort(d);float opt=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.w;return opt;2.2.贪心选择性质贪心选择性质 可以证明最优装载问题具有贪心选择性质。可以证明最优装载问题具有贪心选择性质
38、。3.3.最优子结构性质最优子结构性质 最优装载问题具有最优子结构性质。最优装载问题具有最优子结构性质。由最优装载问题的贪心选择性质和最优子结构性由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法质，容易证明算法loadingloading的正确性。算法的正确性。算法loadingloading的的主要计算量在于将集装箱依其重量从小到大排序，故主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为算法所需的计算时间为 O(nlognO(nlogn)。五、最小生成树问题：五、最小生成树问题：设设G=(V,E)G=(V,E)是无向连通带权图，即一个网络。是无向连通带权图，即一个
39、网络。E E中每条边中每条边(v,w)(v,w)的权为的权为cvwcvw。如果如果G G的子图的子图GG是一棵包含是一棵包含G G的所有顶的所有顶点的树，则称点的树，则称GG为为G G的生成树。生成树上各边权的总和称为的生成树。生成树上各边权的总和称为该生成树的耗费。在该生成树的耗费。在G G的所有生成树中，耗费最小的生成树称的所有生成树中，耗费最小的生成树称为为G G的最小生成树。的最小生成树。1.1.最小生成树性质最小生成树性质 用贪心算法设计策略可以设计出构造最小生成树的有效用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的算法。本节介绍的构造最小生成树的P
40、rimPrim算法和算法和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)(u,v)的的权权cuvcuv最小，那么一定存在最小，那么一定存在G G的一棵最小生成树，
41、它以的一棵最小生成树，它以(u,v)(u,v)为其中一条边。这个性质有时也称为为其中一条边。这个性质有时也称为MSTMST性质。性质。2 2PrimPrim算法：算法：利用最小生成树性质和数学归纳法容易证明，上述算法中利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合的边集合T T始终包含始终包含G G的某棵最小生成树中的边。因此，在算法的某棵最小生成树中的边。因此，在算法结束时，结束时，T T中的所有边构成中的所有边构成G G的一棵最小生成树。的一棵最小生成树。3.Kruskal3.Kruskal算法算法 KruskalKruskal算法构造算法构造G G的最小的最小生成树的基本思想生成树的基本思想:当图的边数为当图的边数为e e时，时，KruskalKruskal算法所需的计算时间算法所需的计算时间是是O O（elogeeloge）。当）。当en2en2时，时，KruskalKruskal算法比算法比PrimPrim算法差，算法差，但当但当e en2n2时，时，KruskalKruskal算法却算法却比比PrimPrim算法好得多。算法好得多。