《(算法几何和设计）贪心算法》由会员分享，可在线阅读，更多相关《(算法几何和设计）贪心算法（46页珍藏版）》请在金锄头文库上搜索。
1、第四章.贪心算法(Greed method) 适用问题 具备贪心选择和最优子结构性质的最优化问题将问题的求解过程看作是一系列选择,每次选择一个输入,每次选择 都是当前状态下的最好选择(局部最优解).每作一次选择后,所求问 题会简化为一个规模更小的子问题.从而通过每一步的最 优解逐步达到整体的最优解。例 题算法优点求解速度快,时间复杂性有较低的阶.整体的最优解可通过一系列局部最优 解达到.每次的选择可以依赖以前作 出的选择,但不能依赖于后面的选择问题的整体最优解中 包含着它的子问题的 最优解.算法缺点需证明是最优解.常见应用背包问题,最小生成树,最短路径,作业调度等等4.1 基本思想用以求解最优
2、化问题算法设计与分析 贪心算法算法思路将n个活动按结束时间非减序排列,依次考虑活动i, 若i与 已选择的活动相容,则添加此活动到相容活动子集.4.2.活动安排问题 问题陈述设有n个活动E=1,2,n要使用同一资源,同一时间内只 允许一个活动使用该资源. 设活动i的起止时间区间si, fi ) ,如果选择 了活动i,则它在时间区间si, fi )内占用该资源;若区间si, fi )与sj, fj ) 不相交, 则称活动i与j是相容的. 求解目标是在所给的活动集合 中选出最大相容活动子集.算法设计与分析 贪心算法1 2 3 4 5 6 7 8 9 10 11例1 3 0 5 3 5 6 8 8 2
3、 124 5 6 7 8 9 10 11 12 13 14i sifi设待安排的11个活动起止时间按结束时间的非减序排列最大相容活动子集(1, 4, 8, 11), 也可表示为等长n元数组:(1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1)活动安排问题贪心算法template void GreedySelector(int n, Type s , Type f , bool A ) A 1 = true;int j = 1;/从第二个活动开始检查是否与前一个相容for (int i=2;i=fj) Ai = true;j=i;else A i = false; T(n)=O(n
4、logn) (未排序时)算法分析 T(n)=O(n) (已排序时)算法设计与分析 贪心算法算法证明 算法达到最优解.4复杂性分析 由于输入的活动以其完成时间的非减序排列， 所以算法greedySelector每次总是选择具有最早 完成时间的相容活动加入集合A中。直观上， 按这种方法选择相容活动为未安排活动留下尽 可能多的时间。也就是说，该算法的贪心选择 的意义是使剩余的可安排时间段极大化，以便 安排尽可能多的相容活动。 算法greedySelector的效率极高。当输入的活动 已按结束时间的非减序排列，算法只需O(n)的 时间安排n个活动，使最多的活动能相容地使 用公共资源。如果所给出的活动未
5、按非减序排 列，可以用O(nlogn)的时间重排。5图示 算法greedySelector 的计算过程如右图 所示。图中每行相 应于算法的一次迭 代。阴影长条表示 的活动是已选入集 合A的活动，而空 白长条表示的活动 是当前正在检查相 容性的活动。6说明 若被检查的活动i的开始时间Si小于最近 选择的活动j的结束时间fi，则不选择活 动i，否则选择活动i加入集合A中。 贪心算法并不总能求得问题的整体最优 解。但对于活动安排问题，贪心算法 greedySelector却总能求得的整体最优解 ，即它最终所确定的相容活动集合A的规 模最大。这个结论可以用数学归纳法证 明。71.贪心选择性质 所谓贪心
6、选择性质是指所求问题的整体最优解 可以通过一系列局部最优的选择，即贪心选择 来达到。这是贪心算法可行的第一个基本要素 ，也是贪心算法与动态规划算法的主要区别。 贪心算法则通常以自顶向下的方式进行，以迭 代的方式作出相继的贪心选择，每作一次贪心 选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选 择性质，必须证明每一步所作的贪心选择最终 导致问题的整体最优解。 0-1背包问题 背包问题82.最优子结构性质 当一个问题的最优解包含其子问题的最 优解时，称此问题具有最优子结构性质 。问题的最优子结构性质是该问题可用 动态规划算法或贪心算法求解的关键特 征。问题描述 输
7、入:(x1,x2,.xn), xi=0,货箱i不装船; xi=1,货箱i装船可行解: 满足约束条件 c 的输入优化函数:最优解:使优化函数达到最大值的一种输入.4.3 最优装载算法设计与分析 贪心算法例设n=8，w1，w8=100, 200, 50, 90, 150, 50, 20, 80，c=400。所考察货箱的次序为 :7, 3, 6, 8, 4, 1, 5, 2。货箱7, 3, 6, 8, 4, 1的总重量为390个单位且已被装载, 剩下的装载能力为10 ,小于任意货箱.所以得到解x1,.x8= 1, 0, 1, 1, 0, 1, 1, 1算法思路 将装船过程划为多步选择，每步装一个货箱
8、，每次从 剩下的货箱中选择重量最轻的货箱.如此下去直到所有货箱均装上 船或船上不能再容纳其他任何一个货箱。最优装载的贪心算法算法设计与分析 贪心算法template void Loading(int x, Type w, Type c, int n ) int *t = new int n + 1; /t记录顺序映射Sort(w, t, n) ; /按货箱重量排序/for (int i = 1; i 0 , 1 i n4-4 背包问题 (Knapsack Problem)算法思路1).将各物体按单位价值由高到低排序. 2).取价值最高者放入背包.3).计算背包剩余空间.4).在剩余物体中取价值
9、最高者放入背包.若背包剩余容量=0或物体全部装入背包为止约 束 条 件优化函数 例 n=3,c=20 (v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10) x1,x2,x3 0,2/3,1 0,1,1/2.1,2/15,020202028.23131.5. .算法设计与分析 贪心算法void Knapsack(int n,float M,float v ,float w ,float x ) Sort(n, v, w); /按单位价值排序/int i;for (i =1;i c) break; /可能是最后一个xi= 1;c-= wi; if(i 贪心算法0-
10、1背包问题算法设计与分析 贪心算法10203050物体1物体2物体3背包价值=$60 单位价值 =$60价值=$100 单位价值 =$50价值=$120 单位价值 =$401020贪心算法结果 =$1602030实际最优 结果=$220*旅行商问题(货郎担问题) 问题: 设一个由N个城市v1,v2,vn组成的网络, ci,j 为从vi 到vj的代价 不妨设ci,j = cj,i ,且ci,i= .一推销员要从某城市出发经过每城市一次 且仅一次后返回出发地问如何选择路线使代价最小。5143173422算法设计与分析 贪心算法抽象描述:将城市以及之间的道路抽象为一个无向图G, G中每边的 权值表示
11、这段线路的代价. 问题转化为求一条最佳周游路线:从一点 出发,经过每点一次且仅一次并返回原点,且该路线的总代价最小.v1v5v2v4v3C=输入:城市的数目n,代价矩阵c=c(1n,1n). 输出: 最小代价路线 1. tour:=0; / tour 纪录路线/ 2. cost:=0; / cost 纪录到目前为止的花费/ 3. v:=N; / N为起点城市, v为当前出发城市/ 4. for k:=1 to N-1 do 5. tour:= tour+(v,w) /(v,w)为从v到其余城市代价中值最小的边/ 6. cost:= cost+c(v,w) 7 v:=w 8 tour:= tou
12、r+(v,N) 9 cost:= cost+c(v,N) print tour, cost 算法的最坏时间复杂性为O(n2)*该算法不能求得最优解.算法设计与分析 贪心算法该问题为NP难问题.算法设计与分析 贪心算法问题:设有n个独立的作业1, 2, , n, 由m台相同的机器进行加工 处理. 作业i所需时间为t i. 约定:任何作业可以在任何一台机器上 加工处理, 但未完工前不允许中断处理,任何作业不能拆分成更小 的子作业。要求给出一种作业调度方案，使所给的n 个作业在尽 可能短的时间内 由m台机器加工处理完成。 4.7 多机调度问题贪心近似算法: 采用最长处理时间作业优先的贪心策略: 当n
13、m时, 只要将机器i的0, ti时间区间分配给作业i即可。 当nm时, 将n个作业依其所需的处理时间从大到小排序,然后依次 将作业分配给空闲的处理机。该问题为NP完全问题.7个独立作业1, 2, 3, 4, 5, 6, 7 由M1,M2和M3来加工处理 各作业所需时间间分别为 2, 14, 4, 16, 6, 5, 3。(16) (14) (6)(5)(4)(2)(3)算法设计与分析 贪心算法class JobNode friend void Greedy(JobNode * , int, int);friend void main(void);public:operator int () c
14、onst return time; private:int ID, time; ;class MachineNode friend void Greedy(JobNode *, int, int);public:operator int( ) const return avail; private:int ID, avail; /机器可被使用的最早时间 多机调度问题的贪心近似算法算法设计与分析 贪心算法多机调度问题的贪心近似算法template void Greedy(Type a，int n，int m) if (nH(m)； MachineNode x； for(int：i=1；i=1；i-)HDeleteMin(x)； /从Heap中将x取出cout 贪心算法分析:nm时, 排序耗时O(nlogn). 初始化堆耗时O(m). 堆的 DeleteMin和insert 共需O(nlogm).因此算法Greedy 所需时间 :O(nlogn)。算法设计与分析 贪心算法堆结构堆结构是一种数组对象，可以被视为一棵完全二叉树。数中每 个节点与数组中存放该点中值的那个元素对应。完全二叉树(Complete Binary Tree) 若设二叉树的高度为h，除第 h 层外，其它各层 (1h-1) 的结 点数都达到最大个数，第 h 层所有的节点都连续集中在最左边，这 就是完全二叉
