贪心算法计算机算法设计与分析第.pptx

《贪心算法计算机算法设计与分析第.pptx》由会员分享，可在线阅读，更多相关《贪心算法计算机算法设计与分析第.pptx（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1学习要点理解贪心算法的概念。掌握贪心算法的基本要素（1）最优子结构性质（2）贪心选择性质理解贪心算法与动态规划算法的差异通过应用范例学习贪心设计策略。（1）活动安排问题；（2）最优装载问题；（3）单源最短路径；（4）多机调度问题。第1页/共31页2解决问题类型局部最优问题部分问题的整体近似最优一般问题的整体最优贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似解。贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。第2页/共31页3举例硬币问题一描述4枚硬币：面值分别为0.

2、25、0.1、0.05、0.01，问构成0.63所需硬币数最少，如何选择其？结论：每次都做出最好的选择，即每次确定一枚硬币后，总使剩余金额最少。贪心算法可以得到本问题的最优解。问题二描述3枚硬币：面值分别为0.11、0.05、0.01，问构成0.15所需硬币数最少，如何选择其？贪心算法：1*0.11+4*0.01 共5枚硬币、结论：不是整体最优解，是近似最优解。第3页/共31页44.1 4.1 活动安排问题活动安排问题问题描述 设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si

3、和一个结束时间fi,且si fi。如果选择了活动i，则它在半开时间区间si,fi)内占用资源。若区间si,fi)与区间sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。问题：要在所给的活动集合中选出最大的相容活动子集合。第4页/共31页54.1 4.1 活动安排问题活动安排问题templatevoid GreedySelectorGreedySelector(int n,Type s,Type f,bool A)A1=true;int j=1;for(int i=2;i=fj)Ai=true;j=i;else Ai=false;下面给出解活动

4、安排问题的贪心算法:各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列 第5页/共31页64.1 4.1 活动安排问题活动安排问题 由于输入的活动以其完成时间的非减非减序序排列，所以算法greedySelectorgreedySelector每次总是选择具有最早完成时间具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活未安排活动留下尽可能多的时间动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大使剩余的可安排时间段极大化化，以便安排尽可能多的相容活动以便安排尽可能多的相容活动。算法greedySelectorgree

5、dySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)O(nlogn)的时间重排。第6页/共31页74.1 4.1 活动安排问题活动安排问题 例：例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i12345678910 11si130535688212fi4567891011121314第7页/共31页84.1 4.1 活动安排问题活动安排问题 算法算法greedySelector greedySelector 的的计算过程

6、计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。第8页/共31页94.1 4.1 活动安排问题活动安排问题 若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。贪心算法并不总能求得问题的整体最优解整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。第9页/共31页104.2 4.2 贪心算法的基本要素贪心算法的基本要素 本节着重讨论可以用贪心算法求解的问题的一般特征。

7、对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质：贪心选择性质贪心选择性质和最优子结构性质最优子结构性质。第10页/共31页114.2 4.2 贪心算法的基本要素贪心算法的基本要素-贪心选择性质贪心选择性质贪心选择性质:指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。与动态规划算法的区别：（1）是否依赖子问题的解；（2）求解过程（自下向上还是自上向下）判断问题是否所具此性质：对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作

8、的贪心选择最终导致问题的整体最优解。第11页/共31页124.2 4.2 贪心算法的基本要素贪心算法的基本要素-最优子结构性质最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。第12页/共31页134.2 4.2 贪心算法的基本要素贪心算法的基本要素相同点：最优子结构性质不同点：通过组合优化问题实例说明二者差别。贪心算法与动态规划算法的差异贪心算法与动态规划算法的差异第13页/共31页144.2 4.2 贪心算法的基本要素贪心算法的基本要素0-10-1背包问题：背包问题：问题描述 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如

9、何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。最优子结构设第j个物品放入了背包中，原问题最优解包含其中一个子问题的最优解，即：集合：Aj=A-j，背包容量：c-wj第14页/共31页154.2 4.2 贪心算法的基本要素贪心算法的基本要素背包问题：背包问题：问题描述 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品可以选择物品i i的一部分的一部分，而不一定要全部装入背包，1in。最优子结构设第j个物品放入了背包中，原问题最优解包含其中一个子

10、问题的最优解，即：集合:Ajw=A-w，背包容量：c-w 结论：结论：背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。第15页/共31页164.2 4.2 贪心算法的基本要素贪心算法的基本要素（1）计算每种物品单位重量的价值Vi/Wi，（2）依贪心选择策略，将尽可能多的单位重量价单位重量价值最高值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。用贪心算法解背包问题的基本步骤：第16页/共31页174.2 4.2 贪心算法的基本要素贪心算法的基本要素void

11、Knapsack(int n,float M,float v,float w,float x)Sort(n,v,w);int i;for(i=1;i=n;i+)xi=0;float c=M;for(i=1;ic)break;xi=1;c-=wi;if(i=n)xi=c/wi;算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（nlogn）。第17页/共31页184.2 4.2 贪心算法的基本要素贪心算法的基本要素 实例如P107图4-2对于0-10-1背包问题背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背

12、包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法动态规划算法求解的另一重要特征。实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。第18页/共31页194.3 4.3 最优装载最优装载1 1、问题描述、问题描述有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。2 2、算法描述、算法描述最优装载问题可用贪心算法求解。采用重量最轻者

13、先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下页。第19页/共31页204.3 4.3 最优装载最优装载templatevoid Loading(int x,Type w,Type c,int n)int*t=new int n+1;Sort(w,t,n);for(int i=1;i=n;i+)xi=0;for(int i=1;i=n&wti=c;i+)xti=1;c-=wti;第20页/共31页214.3 4.3 最优装载最优装载3 3、贪心选择性质、贪心选择性质 证明省略。思想：每处理完一个集装箱，都要使得船的剩余容量尽可能大。即原问题的最优解通过局部问题的最优解得到。4

14、 4、最优子结构性质、最优子结构性质原问题的最优解包含了子问题的最优解，具有最优子结构性质。算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为 O(nlogn)。第21页/共31页224.5 4.5 单源最短路径单源最短路径问题描述：给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源源。现在要计算从源到所有其它各顶点的最短路长度最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题单源最短路径问题。第22页/共31页234.5 4.5 单源最短路径单源最短路径Dijkstra算法基本思想基本思想：

15、基本思想：设置一初始为仅含源的顶点集合S，通过不断地作贪心选择贪心选择扩充此集合，直至S包含所有顶点。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了V中所有顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。第23页/共31页244.5 4.5 单源最短路径单源最短路径例如例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表

16、中。第24页/共31页254.5 4.5 单源最短路径单源最短路径迭代迭代S Su udist2dist2 dist3dist3 dist4dist4 dist5dist5 初始初始1-10maxint301001 11,221060301002 21,2,44105030903 31,2,4,33105030604 41,2,4,3,5510503060Dijkstra算法的迭代过程：第25页/共31页264.5 4.5 单源最短路径单源最短路径算法P113 第26页/共31页274.7 4.7 多机调度问题多机调度问题问题描述：有n个独立的作业1，2，n，由m台相同的机器进行加工处理。作业

17、i所需的处理时间为ti。任何作业可以在任何一台机器上加工处理，但未完工前不允许中断处理。任何作业不能拆分成更小的子作业。要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。第27页/共31页284.7 4.7 多机调度问题多机调度问题算法思想：采用最长处理时间作业优先最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。按此策略，当 时，只要将机器i的0,ti时间区间分配给作业i即可，算法只需要O(1)时间。当 时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。第28页/共31页294.7 4.7 多机调度问题多机调度问题例如，例如，设7个独立作业1,2,3,4,5,6,7由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为2,14,4,16,6,5,3。按算法greedygreedy产生的作业调度如下图所示，所需的加工时间为17。第29页/共31页30算法P120第30页/共31页31感谢您的观看！第31页/共31页