计算机算法设计与分析第4章 贪心算法.ppt

计算机算法设计与分析 Design and Analysis of Computer Algorithms 第四章 贪心算法 Greedy Algorithm 提纲 一、贪心算法的基本思想 二、活动安排问题 三、最优装载 四、哈夫曼编码 五、单源最短路径 六、最小生成树 七、多机调度问题 提纲 一、贪心算法的基本思想 二、活动安排问题 三、最优装载 四、哈夫曼编码 五、单源最短路径 六、最小生成树 七、多机调度问题 1.1 贪心算法总体思想 1.1 贪心算法总体思想 1.2 贪心算法的基本要素 贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 最优子结构性质 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。 1.3 贪心算法正确性证明方法 证明算法所求解的问题具有贪心选择性； 证明算法所求解的问题具有最优子结构； 证明算法确实按照贪心选择性进行局部优化选择。 1.4 动态规划与贪心算法的比较 相同点： 都具有最优子结构性质。 不同点： 贪心算法具有贪心选择性质； 动态规划算法具有子问题重叠性，子问题空间小； 动态规划算法通常以自底向上的方式解各子问题； 贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 可用贪心算法时，动态规划方法可能不适用； 可用动态规划方法时，贪心算法可能不适用。 1.5 0-1背包问题和背包问题 0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，价值为Vi，背包容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有2种选择，即装入或不装入。 背包问题： 与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。 1.5 0-1背包问题和背包问题 0-1背包问题的定义： 背包问题定义： 1.5 0-1背包问题和背包问题 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页： 1.5 0-1背包问题和背包问题 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w); int i; for (i=1;i=n;i++) x[i]=0; float c=M; for (i=1;i=n;i++) { if (w[i]c) break; x[i]=1; c-=w[i]; } if (i=n) x[i]=c/w[i]; } 对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。 实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。 1.6 贪心算法的步骤 优化解的结构分析 算法设计 算法复杂性分析 算法正确性证明 提纲 一、贪心算法的基本思想 二、活动安排问题 三、最优装载 四、哈夫曼编码 五、单源最短路径 六、最小生成树 七、多机调度问题 2.1 问题定义（ An activity-arranging problem ） 活动 设E={1,2,…,n}是n个活动的集合，各个活动使用同一个资源，资源在同一时间只能为一个活动使用。 每个活动i有起始时间si，终止时间fi，si fi 如果选择了活动i，则它在时间[si ，fi)内占用资源。 相容活动 活动i和j是相容的，若sj?fi或si?fj，即 2.1 问题定义 问题定义： 输入：E={1, 2, …, n}，s=[si] ，f=[fi] ，n?i?1 输出：E的最大相容集合 2.2 贪心选择 2.3贪心算法 将所有活动按结束时间排序，得到活动集合E={e1,e2…en}； 先将e1选入结果集合A中，