《算法设计与分析》第06章

《《算法设计与分析》第06章》由会员分享，可在线阅读，更多相关《《算法设计与分析》第06章（96页珍藏版）》请在金锄头文库上搜索。

1、第6章 贪心法 Greedy Algorithm找零问题假如售货员需要找给小孩67美分的零钱。现在，售货员手中只有25美分、10美分、5美分和1美分的硬币。在小孩的催促下，售货员想尽快将钱找给小孩。她的做法是：先找不大于67美分的最大硬币25美分硬币 ，再找不大于672542美分的最大硬币25美分硬币，再找 不大于422517美分的最大硬币10美分硬币，再找不大于 17107美分的最大硬币5美分硬币，最后售货员再找出两 个1美分的硬币。至此，售货员共找给小孩6枚硬币。售货员 的原则是拿尽可能少的硬币个数找给小孩。从另一个角度看 ，如果售货员将捡出的硬币逐一放在手中，最后一起交给小 孩，那么售货

2、员想使自己手中的钱数增加的尽量快些，所以 每一次都尽可能地捡面额大的硬币。2l贪心法就是只顾眼前利益，每次都选最好的。l总是作出在当前看来是最好的选择。也就 是说，不从整体最优上加以考虑，它所做 出的仅是在某种意义上的局部最优解。l贪心算法不是对所有问题都能得到整体最 优解，但对范围相当广泛的许多问题它能 产生整体最优解。但其解必然是最优解的 很好近似解。 36.1 6.1 一般方法一般方法6.2 6.2 背包问题背包问题6.3 6.3 带时限的作业排序带时限的作业排序6.4 6.4 最佳合并模式最佳合并模式6.5 6.5 最小代价生成树最小代价生成树 6.6 6.6 单源最短路径单源最短路径

3、6.7 6.7 磁带最优存储磁带最优存储6.8 6.8 贪心法的基本要素贪心法的基本要素 * *贪心法的应用贪心法的应用46.1 一般方法 5l最优化问题（optimization problems）是指这样一类问题，问题给定某些约束条件（ constraint），满足这些约束条件的问题解 称为可行解（feasible solution）。通常满足约束条件的解不是惟一的。为了衡量可行 解的好坏，问题还给出了某个数值函数，称 为目标函数（objective function），使目标函数取最大（或最小）值的可行解称为最 优解（optimal solution）。6贪心法是通过分步决策分步决策（s

4、tepwise decision）的方法来求解问题的。 贪心法每一步上用作决策依据的选择准则被称为 最优量度标准最优量度标准（optimization criterion）。 在根据最优量度标准选择分量的过程中，还需要 使用一个可行解判定函数可行解判定函数。 贪贪心策略并不是从整体上加以考虑虑的，它所做出 的选择选择 只是当前看似最佳选择选择 ，必须进须进 一步证证明 该该算法最终导终导 致问题问题 的一个整体最优优解。7【程序程序6 61 1】贪心法贪心法 SolutionType Greedy(SType a,int n) SolutionType solution=; for(int i

5、=0;i0，pi0，0i class Knapsack public:Knapsack(int mSize,float cap,float *wei,T *prof); void GreedyKnapsack(float* x); private:float m,*w; T *p; int n; ;14template void Knapsack:GreedyKnapsack(float* x) /前置条件：wi已按pi/wi的非增次序排列float u=m; for (int i=0;iu) break; xi=1.0;u=u-wi; if (i0 ，di为整数。如果作业能够在截止期限之内完

6、成， 可获得pi0的收益。问题要求得到一种作业调度方案，该方案给出作业的一个子集和该作业子集的一 种排列，使得若按照这种排列次序调度作业运行， 该子集中的每个作业都能如期完成，并且能够获得 最大收益。也就是说这种作业调度是最优的。 186.3.2 贪心法求解例例6 62 2 设有4个作业，每个作业的时限为 (d0,d1,d2,d3)=(2,1,2,1),收益为 (p0,p1,p2,p3)=(100,10,15,27)。 1920【程序63】带时带时 限作业业排序的贪贪心算法void GreedyJob(int d, Set X, int n) /前置条件：p0p1,pn-1 X=0;for (

7、int i=1;i=0 if(rr+1) for (int i=k;i=r+1;i-) xi+1=xi; xr+1=j; k+; return k;286.3.6 一种改进算法l本小节节将介绍绍一种带时带时 限作业业排序的快速算法， 它采用不同于前者的可行解判定方法，可使算法 的时间时间 从(n2)减少到接近O(n)。2930例例6 63 3 设n=5个作业， 作业的时限为:(d0,d1,d2,d3,d4)=(2,2,1,3,3), 收益为: (p0,p1,p2,p3,p4)=(20,15,10,5,1)。3132【程序程序6 65 5】使用并查集的带时限作业排序使用并查集的带时限作业排序 i

8、nt FJS(int *d,int *x,int n) UFSet s(n); int b,k=-1,*f=new intn+1;for (int i=0;i struct HNode /优先权队列中的元素的类型operator T()const return weight;BTNode *ptr;T weight; ;42template BTNode* CreateHfmTree (T* w,int n) /w 为一维数组保存n个权值 PrioQueue pq(2*n-1); BTNode*p;HNode a,b; for (int i=0;i(wi); a.ptr=p;a.weight=

9、wi; pq.Append(a); 43for (i=1;i(a.weight,a.ptr,b.ptr); a.ptr=p;pq.Append(a); pq.Serve(a); return a.ptr; 446.4.3 算法正确性 l 定理64 设有n个权值W=w0,w1 ,wn1作为外结点的权值，构造两路合并树的贪心算法将 生成一棵具有最小带权外路径长度的二叉 树。 45466.5 最小代价生成树476.5.1 问题描述问题问题 一个无向连通图的生成树生成树是一个极小连通子图 ，它包括图中全部结点，并且有尽可能少的边。 一棵生成树的代价生成树的代价是树中各条边上的代价之和 。一个网络的各生

10、成树中，具有最小代价的生成 树称为该网络的最小代价生成树最小代价生成树（minimum-cost spanning tree）。486.5.2 贪心法求解l 最优量度标准选择使得迄今为止已入选S中边的代价之和增量 最小的边克鲁斯卡尔算法的贪心准则是：按边代价的非减 次序考察E中的边，从中选择一条代价最小的边 e=(u,v)。普里姆算法的贪心准则是：在保证S所代表的子图 是一棵树的前提下选择一条最小代价的边e=(u,v) 。49【程序程序6 67 7】最小代价生成树的贪心算法最小代价生成树的贪心算法 ESetType SpanningTree(ESetType E, int n) /G=(V,E

11、)为无向图 ESetType S=; int u,v,k=0; EType e; while (k struct ENode /带权图的边结点 int adjVex; T w;ENode* nextArc; ;51template class Graph public:Graph (int mSize);void Prim(); protected:void Prim(int k,int* nearest,T* lowcost);ENode* a;int n; ;52template void Graph:Prim(int s) /公有成员函数 int* nearest=new intn,*l

12、owcost=new intn; Prim(s,nearest,lowcost); for(int j=0;j void Graph:Prim(int k,int* nearest,T* lowcost) /私有成员函数bool* mark=new booln; ENode *p;if (kn-1) throw OutofBounds;for (int i=0;inextArc) int j= p-adjVex;if (!markj ) nearestj=k; T min=INFTY; for (int j=0;jstruct eNode operator T ()const return w

13、; int u,v; T w; ;5758【程序程序6 69 9】克鲁斯卡尔算法克鲁斯卡尔算法 template void Graph:Kruskal(PrioQueue UFSet s(n); int u,v,k=0; 59while (k class MGraph public:MGraph(int mSize);void Dijkstra(int s,T*67private:int Choose(int* d, bool* s); T*a; int n; ; 68template int MGraph:Choose(int* d, bool* s) int i,minpos; T min;min=INFTY; minpos=-1;for (i=1;i void MGraph:Dijkstra(int s,T*if (sn-1) throw OutOfBounds;bool *inS=new booln; d=new Tn;path=new intn;for (i=0;i1条磁带T0,T1,Tm1和n个程序。要求将此 n个程序分配到这m条磁带上，令