贪婪算法

贪婪算法 中国数学建模-编程交流-贪婪算法 feifei7 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 >> VC++,C,Perl,Asp...编程学习,算法介绍. 我的收件箱 (0) 中国数学建模 ? 学术区 ? 编程交流 ? 贪婪算法 您是本帖的第 672 个阅读者 * 贴子主:贪婪算法 b 等级:职业侠客 文章:472 积分:951 门派:黑客帝国 注册:2003-8-28 第 11 楼 1.3.6 最小耗费生成树 在例1 - 2及1 - 3中已考察过这个问题。因为具有n 个顶点的无向网络G的每个生成树刚好具有n-1条边，所以问题是用某种选择n-1条边使它们形成G的最小生成树。至少可以采用三种不同的贪婪策略来选择这n-1条边。这三种求解最小生成树的贪婪算法策略是: K r u s k a l算法，P r i m算法和S o l l i n算法。 1. Kruskal算法 (1) 算法思想 K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是:从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。 考察图1-12a 中的网络。初始时没有任何边被选择。图13-12b 显示了各节点的当前状态。边( 1 , 6)是最先选入的边，它被加入到欲构建的生成树中，得到图1 3 - 1 2 c。下一步选择边( 3，4)并将其加入树中(如图1 3 - 1 2 d所示)。然后考虑边( 2，7 )，将它加入树中并不会产生环路，于是便得到图1 3 - 1 2 e。下一步考虑边( 2，3)并将其加入树中(如图1 3 - 1 2 f所示)。在其余还未考虑的边中，(7，4)具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。此后将边( 5，4)加入树中，得到的树如图13-12g 所示。下一步考虑边( 7，5)，由于会产生环路，将其丢弃。最后考虑边( 6，5)并将其加入树中，产生了一棵生成树，其耗费为9 9。图1 - 1 3给出了K r u s k a l算法的伪代码。 / /在一个具有n 个顶点的网络中找到一棵最小生成树 令T为所选边的集合，初始化T= 令E 为网络中边的集合 w h i l e(E? )&&(| T |?n- 1 ) { 令(u,v)为E中代价最小的边 E=E- { (u,v) } / /从E中删除边 i f( (u,v)加入T中不会产生环路)将( u,v)加入T } i f(| T | = =n-1) T是最小耗费生成树 e l s e 网络不是互连的，不能找到生成树 图13-13 Kruskao算法的伪代码 (2) 正确性证明 利用前述装载问题所用的转化技术可以证明图1 3 - 1 3的贪婪算法总能建立一棵最小耗费生成树。需要证明以下两点: 1) 只要存在生成树，K r u s k a l算法总能产生一棵生成树; 2) 产生的生成树具有最小耗费。令G为任意加权无向图(即G是一个无向网络)。从1 2 . 11 . 3节可知当且仅当一个无向图连通时它有生成树。而且在Kruskal 算法中被拒绝(丢弃)的边是那些会产生环路的边。删除连通图环路中的一条边所形成的图仍是连通图，因此如果G在开始时是连通的，则T与E中的边总能形成一个连通图。也就是若G开始时是连通的，算法不会终止于E= 和| T |< n- 1。 现在来证明所建立的生成树T具有最小耗费。由于G具有有限棵生成树，所以它至少具有一棵最小生成树。令U为这样的一棵最小生成树， T与U都刚好有n- 1条边。如果T=U, 则T就具有最小耗费，那么不必再证明下去。因此假设T?U，令k(k >0) 为在T中而不在U中的边的个数，当然k 也是在U中而不在T中的边的数目。 通过把U变换为T来证明U与T具有相同的耗费，这种转化可在k 步内完成。每一步使在T而不在U中的边的数目刚好减1。而且U的耗费不会因为转化而改变。经过k 步的转化得到的U将与原来的U具有相同的耗费，且转化后U中的边就是T中的边。由此可知， T具有最小耗费。每步转化包括从T中移一条边e 到U中，并从U中移出一条边f。边e 与f 的选取按如下方式进行: 1) 令e 是在T中而不在U中的具有最小耗费的边。由于k >0，这条边肯定 存在。 2) 当把e 加入U时，则会形成唯一的一条环路。令f 为这条环路上不在T中的任意一条边。 由于T中不含环路，因此所形成的环路中至少有一条边不在T中。 从e 与f 的选择方法中可以看出， V=U+ {e} -{ f } 是一棵生成树，且T中恰有k- 1条边不在V中出现。现在来证明V的耗费与U的相同。显然，V的耗费等于U的耗费加上边e 的耗费再减去边f 的耗费。若e 的耗费比f 的小，则生成树V的耗费比U的耗费小，这是不可能的。如果e 的耗费高于f，在K r u s k a l算法中f 会在e 之前被考虑。由于f 不在T中，Kruskal 算法在考虑f 能否加入T时已将f 丢弃，因此f 和T中耗费小于或等于f 的边共同形成环路。通过选择e，所有这些边均在U中，因此U肯定含有环路，但是实际上这不可能，因为U是一棵生成树。e 的代价高于f 的假设将会导致矛盾。剩下的唯一的可能是e 与f 具有相同的耗费，由此可知V与U的耗费相同。 (3) 数据结构的选择及复杂性 为了按耗费非递减的顺序选择边，可以建立最小堆并根据需要从堆中一条一条地取出各边。当图中有e 条边时，需花(e) 的时间初始化堆及O ( l o ge) 的时间来选取每一条边。边的集合T与G中的顶点一起定义了一个由至多n 个连通子图构成的图。用顶点集合来描述每个子图，这些顶点集合没有公共顶点。为了确定边( u,v)是否会产生环路，仅需检查u,v 是否在同一个顶点集中(即处于同一子图)。如果是，则会形成一个环路;如果不是，则不会产生环路。因此对于顶点集使用两个F i n d操作就足够了。当一条边包含在T中时，2个子图将被合并成一个子图，即对两个集合执行U n i o n操作。集合的F i n d和U n i o n操作可利用8 . 1 0 . 2节的树(以及加权规则和路径压缩)来高效地执行。F i n d操作的次数最多为2e，Un i o n操作的次数最多为n- 1(若网络是连通的，则刚好是n- 1次)。加上树的初始化时间，算法中这部分的复杂性只比O (n+e) 稍大一点。 对集合T所执行的唯一操作是向T中添加一条新边。T可用数组t 来实现。添加操作在数组 的一端进行，因为最多可在T中加入n- 1条边，因此对T的操作总时间为O (n)。 总结上述各个部分的执行时间，可得图1 3 - 1 3算法的渐进复杂性为O (n+el o ge)。 (4) 实现 利用上述数据结构，图1 - 1 3可用C + +代码来实现。首先定义E d g e N o d e 类(见程序1 3 - 6 )，它是最小堆的元素及生成树数组t 的数据类型 ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); 2004-5-27 19:42:37 b 等级:职业侠客 文章:472 积分:951 门派:黑客帝国 注册:2003-8-28 第 12 楼 程序13-6 Kruskal算法所需要的数据类型 template class EdgeNode { p u b l i c : operator T() const {return weight;} p r i v a t e : T weight;//边的高度 int u, v;//边的端点 } ; 为了更简单地使用8 . 1 0 . 2节的查找和合并策略，定义了U n i o n F i n d类，它的构造函数是程序8 - 1 6的初始化函数，U n i o n是程序8 - 1 6的加权合并函数，F i n d是程序8 - 1 7的路径压缩搜索函数。 为了编写与网络描述无关的代码，还定义了一个新的类U N e t Wo r k，它包含了应用于无向网络的所有函数。这个类与U n d i r e c t e d类的差别在于U n d i r e c t e d类中的函数不要求加权边，而U N e t Wo r k要求边必须带有权值。U N e t Wo r k中的成员需要利用N e t w o r k类中定义的诸如B e g i n和N e x t Ve r t e x的遍历函数。不过，新的遍历函数不仅需要返回下一个邻接的顶点，而且要返回到达这个顶点的边的权值。这些遍历函数以及有向和无向加权网络的其他函数一起构 成了W N e t w o r k类(见程序1 3 - 7)。 程序13-7 WNetwork类 template class WNetwork : virtual public Network { public : virtual void First(int i, int& j, T& c)=0; virtual void Next(int i, int& j, T& c)=0; } ; 象B e g i n和N e x t Ve r t e x一样，可在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h类中加入函数F i r s t与N e x t。现在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h类都需要从W N e t Wo r k中派生而来。由于A d j a c e n c y W G r a p h类和L i n k e d W G r a p h类需要访问U N e t w o r k的成员，所以这两个类还必须从U N e t Wo r k 中派生而来。U N e t Wo r k : : K r u s k a l的代码见程序1 3 - 8，它要求将Edges() 定义为N e t Work 类的虚成员，并且把U N e t Wo r k定义为E d g e N o d e的友元)。如果没有生成树，函数返回f a l s e，否则返回t r u e。注意当返回true 时，在数组t 中返回最小耗费生成树。 程序13-8 Kr u s k a l算法的C + +代码 template bool UNetwork::Kruskal(EdgeNode t[]) {// 使用K r u s k a l算法寻找最小耗费生成树 // 如果不连通则返回false // 如果连通，则在t [ 0 : n - 2 ]中返回最小生成树 int n = Ve r t i c e s ( ) ; int e = Edges(); / /设置网络边的数组 InitializePos(); // 图遍历器 EdgeNode *E = new EdgeNode [e+1]; int k = 0; // E的游标 for (int i = 1; i <= n; i++) { // 使所有边附属于i int j; T c; First(i, j, c); while (j) { // j 邻接自i if (i < j) {// 添加到达E的边 E[++k].weight = c; E[k].u = i; E[k].v = j;} Next(i, j, c); } } // 把边放入最小堆 MinHeap > H(1); H.Initialize(E, e, e); UnionFind U(n); // 合并/搜索结构 // 根据耗费的次序来抽取边 k = 0; // 此时作为t的游标 while (e && k < n - 1) { // 生成树未完成，尚有剩余边 EdgeNode x; H.DeleteMin(x); // 最小耗费边 e - - ; int a = U.Find(x.u); int b = U.Find(x.v); if (a != b) {// 选择边 t[k++] = x; U . U n i o n ( a , b ) ; } } D e a c t i v a t e P o s ( ) ; H . D e a c t i v a t e ( ) ; return (k == n - 1); } 2. Prim算法 与Kr u s k a l算法类似，P r i m算法通过每次选择多条边来创建最小生成树。选择下一条边的贪婪准则是:从剩余的边中，选择一条耗费最小的边，并且它的加入应使所有入选的边仍是一棵树。最终，在所有步骤中选择的边形成一棵树。相反，在Kruskal 算法中所有入选的边集合最终形成一个森林。 P r i m算法从具有一个单一顶点的树T开始，这个顶点可以是原图中任意一个顶点。然后往T中加入一条代价最小的边( u , v)使TÈ{ (u , v) }仍是一棵树，这种加边的步骤反复循环直到T中包含n- 1条边。注意对于边( u , v)，u、v 中正好有一个顶点位于T中。P r i m算法的伪代码如图1 -1 4所示。在伪代码中也包含了所输入的图不是连通图的可能，在这种情况下没有生成树。图1 - 1 5显示了对图1-12a 使用P r i m算法的过程。把图1 - 1 4的伪代码细化为C + +程序及其正确性的证明留作练习(练习3 1)。 / /假设网络中至少具有一个顶点 设T为所选择的边的集合，初始化T= 设T V为已在树中的顶点的集合，置T V= { 1 } 令E为网络中边的集合 w h i l e(E< > ) & & (| T | < > n-1) { 令(u , v)为最小代价边，其中u T V, v T V i f(没有这种边) b re a k E=E- { (u,v) } / /从E中删除此边 在T中加入边( u , v) } if (| T | = =n- 1 ) T是一棵最小生成树 else 网络是不连通的，没有最小生成树 图13-14 Prim最小生成树算法 如果根据每个不在T V中的顶点v 选择一个顶点n e ar (v)，使得n e ar (v) Î TV 且c o st (v, n e ar (v) )的值是所有这样的n e ar (v) 节点中最小的，则实现P r i m算法的时间复杂性为O (n2 )。下一条添加到T中的边是这样的边:其cost (v, near (v)) 最小，且v T V。 3. Sollin算法 S o l l i n算法每步选择若干条边。在每步开始时，所选择的边及图中的n个顶点形成一个生成树的森林。在每一步中为森林中的每棵树选择一条边，这条边刚好有一个顶点在树中且边的代价最小。将所选择的边加入要创建的生成树中。注意一个森林中的两棵树可选择同一条边，因此必须多次复制同一条边。当有多条边具有相同的耗费时，两棵树可选择与它们相连的不同的边，在这种情况下，必须丢弃其中的一条边。开始时，所选择的边的集合为空。若某一步结束时仅剩下一棵树或没有剩余的边可供选择时算法终止。 图1 - 6给出了初始状态为图1-12a 时，使用S o l l i n算法的步骤。初始入选边数为0时的情形如图13-12a 时,森林中的每棵树均是单个顶点。顶点1，2，.，7所选择的边分别是(1.6), (2,7),(3,4), (4,3), (5,4), (6,1), (7,2)，其中不同的边是( 1 , 6 )，( 2 , 7 )，(3,4) 和( 5 , 4 )，将这些边加入入选边的集合后所得到的结果如图1 3 - 1 6 a所示。下一步具有顶点集{ 1 , 6 }的树选择边( 6 , 5 )，剩下的两棵树选择边( 2 , 3 )，加入这两条边后已形成一棵生成树，构建好的生成树见图1 3 - 6 b。S o l l i n算法的C + +程序实现及其正确性证明留作练习(练习3 2 )。 ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); 2004-5-27 19:42:54 b 等级:职业侠客 文章:472 积分:951 门派:黑客帝国 注册:2003-8-28 第 13 楼 练习 8. 针对装载问题，扩充贪婪算法，考虑有两条船的情况，算法总能产生最优解吗, 9. 已知n 个任务的执行序列。假设任务i 需要ti 个时间单位。若任务完成的顺序为1，2，.，n，则任务i 完成的时间为ci =i åj = 1tj 。任务的平均完成时间(Av e rge Completion Time, ACT) 为1–nn åi = 1ci 。 1) 考虑有四个任务的情况，每个任务所需时间分别是( 4，2，8，1)。若任务的顺序为1，2，3，4，则A C T是多少, 2) 若任务顺序为2，1，4，3，则A C T是多少, 3) 创建具有最小A C T的任务序列的贪婪算法分n 步来构造该任务序列，在每一步中，从剩下的任务里选择时间最小的任务。对于1 )，利用这种策略获得的任务顺序为4，2，1，3，这种顺序的A C T是多少, 4) 写一个C + +程序实现3) 中的贪婪策略，程序的复杂性应为O (nl o gn)，试证明之。 5) 证明利用3) 中的贪婪算法获得的任务顺序具有最小的A C T。 10. 若有两个工人执行练习9中的n个任务，需将任务分配给他们，同时他们具有自己的任务执行顺序。任务完成时间及A C T的定义同练习9。使A C T最小化的一种可行的贪婪算法是:两个工人轮流选择任务，每次从剩余的任务中选择时间最小的任务。每个人按照自己所选任务的顺序执行任务。对于练习9中的例子，假定工人1首先选择任务4，然后工人2选择任务2，工人1选择任务1，最后工人2选择任务3。 1) 利用C + +程序实现这种策略，其时间复杂性为多少, 2) 上述的贪婪策略总能获得最小的A C T吗,证明结论。 11. 1) 考虑有m 个人可以执行任务，扩充练习1 0中的贪婪算法。 2) 算法能保证获得最优解吗,证明结论。 3) 用C + +程序实现此算法，其复杂性是多少, 12. 考虑例4 - 4的堆栈折叠问题。 1) 设计一个贪婪算法，将堆栈折叠为最小数目的子堆栈，使得每个子堆栈的高度均不超过H。 2) 算法总能保证得到数目最少的子堆栈吗,证明结论。 3) 用C + +代码实现1) 的算法。 4) 代码的时间复杂性是多少, 13. 编写C + +程序实现0 / 1背包问题，使用如下启发式方法:按价值密度非递减的顺序打包。 14. 根据k= 1的性能受限启发式方法编写一个C + +程序来实现0 / 1背包问题。 15. 对于k= 1的情况证明用性能受限的启发式方法求解0 / 1背包问题会发生边界错误。 16. 根据k= 2的性能受限启发式方法编写一个C + +程序来实现0 / 1背包问题。 17. 考虑0?xi ?1而不是xi Î{ 0 , 1 }的连续背包问题。一种可行的贪婪策略是:按价值密度非递减的顺序检查物品，若剩余容量能容下正在考察的物品，将其装入;否则，往背包中装入此物品的一部分。 1) 对于n=3, w=[100,10,10], p= [ 2 0 , 1 5 , 1 5 ]及c= 1 0 5 ,上述装入方法获得的结果是什么, 2) 证明这种贪婪算法总能获得最优解。 3) 用一个C + +程序实现此算法。 18. 例1 3 - 1的渴婴问题是练习1 7中连续背包问题的一般化，将练习1 7的贪婪算法用于渴婴问题，算法能保证总能得到最优解吗,证明结论。 19. 1) 证明当且仅当二分图没有覆盖时，图1 3 - 7的算法找不到覆盖。 2) 给出一个具有覆盖的二分图，使得图1 3 - 7的算法找不到最小覆盖。 20. 当第一步选择了顶点1时，给出图1 3 - 7的工作过程。 21. 对于二分图覆盖问题设计另外一种贪婪启发式方法，可使用如下贪婪准则:如果B中的某一个顶点仅被A中一个顶点覆盖，选择A中这个顶点;否则，从A中选择一个顶点，使得它所覆盖的未被覆盖的顶点数目最多。 1) 给出这种贪婪算法的伪代码。 2) 编写一个C + +函数作为U n d i r e c t e d类的成员来实现上述贪婪算法。 3) 函数的复杂性是多少, 4) 验证代码的正确性。 22. 令G为无向图，S为G中顶点的子集，当且仅当S中的任意两个顶点都有一条边相连时，S为完备子图(c l i q u e)，完备子图的大小即S中的顶点数目。最大完备子图( maximum clique)即具有最大项点数目的完备子图。在图中寻找最大完备子图的问题(即最大完备子图问题)是一个N P-复杂问题。 1) 给出最大完备子图问题的一种可行的贪婪算法及其伪代码。 2) 给出一个能用1) 中的启发式算法求解最大完备子图的图例，以及不能用该算法求解的一个图例。 3) 将1) 中的启发式算法实现为Undirected::Clique(int C, int m) 共享成员，其中最大完备子图的大小返回到m中，最大完备子图的顶点返回到C中。 4) 代码的复杂性是多少, 23. 令G为一无向图，S为G中顶点的子集，当且仅当S中任意两个顶点都无边相连时， S为无关集(independent set)。最大无关集即是顶点数目最多的无关集。在一幅图中寻找最大无关集是一个N P-复杂问题。按练习2 2的要求解决最大无关集问题。 24. 对无向图G着色的方法是:为G中的顶点编号({ 1 , 2 ,.})，使得由一条边相连的两个顶点具有不同的编号。在图的着色问题中， 要求利用最少的相互不同的颜色(编号)来给图G着色。图的着色问题也是一个N P-复杂问题。按练习2 2的要求解决图着色问题。 25. 证明当按路径长度的顺序产生一条最短路径时，所产生的下一条最短路径总是由已产生的一条最短路径扩充一条边得到。 26. 证明对于具有一条或多条具有负长度的边，图1 3 - 11的贪婪算法不一定能正确地计算出最短路径的长度。 27. 编写一个P a t h ( p , s , i )函数，利用函数S h o r t e s t P a t h s计算出的p 值，输出从顶点s到顶点i的一条最短路径。函数的复杂性是多少, 28. 若把有向图作为L i n k e d w D i g r a p h类的一个成员，重写程序1 3 - 5，函数应作为该类的一个成员。函数的复杂性是多少, 29. 若把有向图作为L i n k e d W D i g r a p h类的一个成员且仅有O (n)条边，重写程序1 3 - 5，L用最小堆来实现。函数的复杂性是多少, 30. 从N e t w o r k类(见程序1 2 - 1 5)派生出一个新的模板类D N e t w o r k(有向网络)，这个类仅包含应用于有向网络的所有函数。为该类定义一个S h o r t e s t P a t h s函数，使得它与有向网络的描述形式无关，尤其适用于耗费邻接矩阵及邻接链表描述方法。在函数的实现过程中可利用原来的遍历函数，也可根据需要定义新的遍历函数。函数的复杂性应为O (n2 )，其中n 是顶点的数目，试证明之。 *31. 1) 给出P r i m算法(如图1 3 - 1 4所示)的一种正确性证明。 2) 将图1 3 - 1 4细化为一个C + +程序U N e t w o r k : : P r i m，其复杂性应为O (n2 )。 3) 证明程序的复杂性确实是O(n2 )。 *32. 1) 证明对于任意连通无向图，S o l l i n算法总能找到一个最小耗费生成树。 2) 在S o l l i n算法中，最大的步骤数是多少,试用图中顶点数n 来表示。 3) 编写一个C + +程序U N e t w o r k : : S o l l i n，使用S o l l i n算法找到一棵最小生成树。 4) 程序的复杂性是多少, *33. 令T为一棵每条边均带有长度的树(不一定是二叉树)。令S为T中顶点的子集，并令T / S为从T中删除S中的顶点所得到的森林。我们希望能找到具有最小走势的子集S，使得T / S中没有从根到叶的距离大于d的森林。 1) 给出一种寻找最小走势子集S的贪婪算法(提示:从叶节点开始向根移动)。 2) 证明算法的正确性。 3) 算法的复杂性是多少,如果它不是T中顶点数的线性函数，则重新设计算法，使其复杂性是线性的。 *34. 令T / S表示将S中的每个顶点复制两份而获得的森林，其中父节点的指针指向一个复本，而另一复本的指针指向其儿子。针对这种情况再做练习3 3。 ( 说明:本资料是根据《数据结构、算法与应用》(美，Sartaj Sahni著)一书第13-17章编辑、改写的。考虑到因特网传输速度等因素， 大部分插图和公式不得不被删除。对于内容不连贯之处，请网友或读者参阅该书，敬请原谅。 ) ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); 2004-5-27 19:43:19 lantian3 等级:新手上路 文章:2 积分:52 门派:?nudter? 注册:2004-6-5 第 14 楼 怎么没人顶, 我先来 2004-6-5 10:49:29 jolin 等级:新手上路 文章:22 积分:101 注册:2004-3-26 第 15 楼 虽然我还没看，但是还是要顶一顶 2004-6-5 18:12:35 afliboy 等级:新手上路 文章:1 积分:51 门派:?nudter? 注册:2004-6-5 第 16 楼 狂顶 2004-6-5 23:41:53 king8egg 等级:新手上路 文章:2 积分:53 门派:?nudter? 注册:2004-6-3 第 17 楼 不错不错,看你发了这么多,不顶不好意思啊,以后有时间再慢慢看吧 2004-6-6 21:49:31 寒枫 等级:新手上路 文章:8 积分:64 门派:?nudter? 注册:2004-6-8 第 18 楼 练习做完了是不是直接跟帖就行, 2004-6-8 21:15:26 本主题贴数 18 分页:9 1 2 : 跳转论坛至...?数学建模 ?数模竞赛 ?新手入门 ?数学工具 ?资源与检索?学术区 ?数学思想 ?编程交流 ?学术杂谈 ?English Fans?休闲专区 ?灌水搞笑专区 ?神秘园?本站站务 ?站务讨论 ?数模管理区 *快速回复:贪婪算法 发贴表情 段落格式 普通格式标题 1标题 2标题 3标题 4标题 5标题 6标题 7已编排格式地址 字体宋体黑体楷体仿宋隶书幼圆新宋体细明体ArialArial BlackCourierVerdanaWide LatinWingdings 字号1234567 第 1 页,共 7 页， 49 个 显示签名 内容限制:字节. 管理选项: 专题管理 | 修复 | 锁定 | 解锁 | 提升 | 跟贴管理 | 删除 | 移动 | 设置固顶 | 奖励 | 惩罚 | 发布公告 Copyright ©2002 - 2004 Shumo.Com 执行时间:156.25000毫秒。查询数据库9次。 当前模板样式:[默认模板] 中国数学建模-编程交流-贪婪算法 wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 >> VC++,C,Perl,Asp...编程学习,算法介绍. 我的收件箱 (0) 中国数学建模 ? 学术区 ? 编程交流 ? 贪婪算法 您是本帖的第 889 个阅读者 * 贴子主题:贪婪算法 b 等级:职业侠客 文章:470 积分:956 门派:黑客帝国 注册:2003-8-28 鲜花(0) 鸡蛋(0) 楼主 贪婪算法 第 1 章 贪婪算法 虽然设计一个好的求解算法更像是一门艺术，而不像是技术，但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。 本章首先引入最优化的概念，然后介绍一种直观的问题求解方法:贪婪算法。最后，应用该算法给出货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解

方案

气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载

。 1.1 最优化问题 本章及后续章节中的许多例子都是最优化问题( optimization problem)，每个最优化问题都包含一组限制条件( c o n s t r a i n t)和一个优化函数( optimization function)，符合限制条件的问题求解方案称为可行解( feasible solution)，使优化函数取得最佳值的可行解称为最优解(optimal solution)。 例1-1 [ 渴婴问题] 有一个非常渴的、聪明的小婴儿，她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水，即婴儿可得到n 种不同的饮料。根据以前关于这n 种饮料的不同体验，此婴儿知道这其中某些饮料更合自己的胃口，因此，婴儿采取如下方法为每一种饮料赋予一个满意度值:饮用1盎司第i 种饮料，对它作出相对评价，将一个数值si 作为满意度赋予第i 种饮料。 通常，这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满足她解渴的需要，但是不幸的是:具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设ai是第i 种饮料的总量(以盎司为单位)，而此婴儿需要t 盎司的饮料来解渴，那么，需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求呢, 设各种饮料的满意度已知。令xi 为婴儿将要饮用的第i 种饮料的量，则需要解决的问题是: 找到一组实数xi(1?i?n)，使n åi = 1si xi 最大，并满足:n åi=1xi =t 及0?xi?ai 。 需要指出的是:如果n åi = 1ai < t，则不可能找到问题的求解方案，因为即使喝光所有的饮料也不能使婴儿解渴。 对上述问题精确的数学描述明确地指出了程序必须完成的工作，根据这些数学公式，可以对输入/ 输出作如下形式的描述: 输入:n，t，si ，ai(其中1?i?n，n 为整数，t、si 、ai 为正实数)。 输出:实数xi(1?i?n)，使n åi= 1si xi 最大且n åi=1xi =t(0?xi?ai)。如果n åi = 1ai k。寻找[ 1 ,n]范围内最小的整数j，使得xj?yj 。若没有这样的j 存在，则n åi= 1xi =n åi = 1yi 。如果有这样的j 存在，则j?k，否则y 就不是一个可行解，因为xj?yj ，xj = 1且yj = 0。令yj = 1，若结果得到的y 不是可行解，则在[ j+ 1 ,n]范围内必有一个l 使得yl = 1。令yl = 0，由于wj?wl ，则得到的y 是可行的。而且，得到的新y 至少与原来的y 具有相同数目的1。 经过数次这种转化，可将y 转化为x。由于每次转化产生的新y 至少与前一个y 具有相同数目的1，因此x 至少与初始的y 具有相同的数目1。货箱装载算法的C + +代码实现见程序1 3 - 1。由于贪婪算法按货箱重量递增的顺序装载，程序1 3 - 1首先利用间接寻址排序函数I n d i r e c t S o r t对货箱重量进行排序(见3 . 5节间接寻址的定义)，随后货箱便可按重量递增的顺序装载。由于间接寻址排序所需的时间为O (nl o gn)(也可利用9 . 5 . 1节的堆排序及第2章的归并排序)，算法其余部分所需时间为O (n)，因此程序1 3 - 1的总的复杂性为O (nl o gn)。 程序13-1 货箱装船 template void ContainerLoading(int x[], T w[], T c, int n) {// 货箱装船问题的贪婪算法 // x[i] = 1 当且仅当货箱i被装载， 1<=i<=n // c是船的容量, w 是货箱的重量 // 对重量按间接寻址方式排序 // t 是间接寻址表 int *t = new int [n+1]; I n d i r e c t S o r t ( w, t, n); // 此时, w[t[i]] <= w[t[i+1]], 1<=i0时总的时间开销为O (nk+1 )。实际观察到的性能要好得多。 ---------------------------------------------- plot(100+t+15*cos(3.05*t),t=0..200,coords=polar,axes=none,scaling=constrained); 2004-5-27 19:39:53 b 等级:职业侠客 文章:470 积分:956 门派:黑客帝国 注册:2003-8-28 第 6 楼 1.3.3 拓扑排序 一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成。例如，汽车装配工程可分解为以下任务:将底盘放上装配线，装轴，将座位装在底盘上，上漆，装刹车，装门等等。任务之间具有先后关系，例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示——称为顶点活动( Activity On Vertex, AOV)网络。有向图的顶点代表任务，有向边(i, j) 表示先后关系:任务j 开始前任务i 必须完成。图1 - 4显示了六个任务的工程，边( 1 , 4)表示任务1在任务4开始前完成，同样边( 4 , 6)表示任务4在任务6开始前完成，边(1 , 4)与(4 , 6)合起来可知任务1在任务6开始前完成，即前后关系是传递的。由此可知，边(1 , 4)是多余的，因为边(1 , 3)和(3 , 4)已暗示了这种关系。 在很多条件下，任务的执行是连续进行的，例如汽车装配问题或平时购买的标有“需要装配”的消费品(自行车、小孩的秋千装置，割草机等等)。我们可根据所建议的顺序来装配。在由任务建立的有向图中，边( i, j)表示在装配序列中任务i 在任务j 的前面，具有这种性质的序列称为拓扑序列(topological orders或topological sequences)。根据任务的有向图建立拓扑序列的过程称为拓扑排序(topological sorting)。图1 - 4的任务有向图有多种拓扑序列，其中的三种为1 2 3 4 5 6，1 3 2 4 5 6和2 1 5 3 4 6，序列1 4 2 3 5 6就不是拓扑序列，因为在这个序列中任务4在3的前面，而任务有向图中的边为( 3 , 4)，这种序列与边( 3 , 4)及其他边所指示的序列相矛盾。可用贪婪算法来建立拓扑序列。算法按从左到右的步骤构造拓扑序列，每一步在排好的序列中加入一个顶点。利用如下贪婪准则来选择顶点:从剩下的顶点中，选择顶点w，使得w 不存在这样的入边( v,w)，其中顶点v 不在已排好的序列结构中出现。注意到如果加入的顶点w违背了这个准则(即有向图中存在边( v,w)且v 不在已构造的序列中)，则无法完成拓扑排序，因为顶点v 必须跟随在顶点w 之后。贪婪算法的伪代码如图1 3 - 5所示。while 循环的每次迭代代表贪婪算法的一个步骤。 现在用贪婪算法来求解图1 - 4的有向图。首先从一个空序列V开始，第一步选择V的第一个顶点。此时，在有向图中有两个候选顶点1和2，若选择顶点2，则序列V = 2，第一步完成。第二步选择V的第二个顶点，根据贪婪准则可知候选顶点为1和5，若选择5，则V = 2 5。下一步，顶点1是唯一的候选，因此V = 2 5 1。第四步，顶点3是唯一的候选，因此把顶点3加入V 得到V = 2 5 1 3。在最后两步分别加入顶点4和6 ，得V = 2 5 1 3 4 6。 1. 贪婪算法的正确性 为保证贪婪算法算的正确性，需要证明: 1) 当算法失败时，有向图没有拓扑序列; 2) 若 算法没有失败，V即是拓扑序列。2) 即是用贪婪准则来选取下一个顶点的直接结果， 1) 的证明见定理1 3 - 2，它证明了若算法失败，则有向图中有环路。若有向图中包含环qj qj + 1.qk qj , 则它没有拓扑序列，因为该序列暗示了qj 一定要在qj 开始前完成。 定理1-2 如果图1 3 - 5算法失败，则有向图含有环路。 证明注意到当失败时| V |记录

混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载