贪心算法演讲.ppt

贪心算 法 孙道伟 2015年11月16日 定义 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。 基本要素 1.贪心选择性质 指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。 2.最优子结构性质 即一个问题的最优解包含其子问题的最优解 1.建立数学模型来描述问题 ⒉把求解的问题分成若干个子问题 ⒊对每一子问题求解，得到子问题的局部最优解 ⒋把子问题的解局部最优解合成原来解问题的一个解 贪心算法的基本思路 存在的问题 1、不能保证求得最后的解是最佳的 2、不能用来求得最大或者最小解问题 3、只能求满足某些约束条件的可行解的范围 实现算法的过程 从问题的某一初始解出发逐步逼近给定的目标 while 能朝给定总目标前进一步 Do 求出可行解的一个解元素 由所有解元素组合成问题的一个可行解 问题原型 贪心算法 — 背包问题 即求X=(x1,x2,…,xn)，满足上述优化方程。 背包问题的数学描述 1. 价值最大 — 贪心选择价值大者 例：背包重量10 物体1：重量9 价值5 物体2：重量4 价值4 物体3：重量3 价值2 ①选物体1，x1=1；剩余可装重量1，价值5 ②选物体2，x2=0.25；剩余0，价值6 但若令X=(1/3,1,1);则背包价值为7.667 因此此贪心选择不一定达到最大价值。 贪心法解背包问题解法1 2. 价值最大 — 贪心选择价值/重量大者 例：背包重量10 物体1：重量9 价值5 物体2：重量4 价值4 物体3：重量3 价值2 贪心法解背包问题解法2 √ ③贪心选择物体2 w2≤m, 故x2=1; m=m-w2=6 p=p+p2=4 ④贪心选择物体3 w3≤m, 故x3=1; m=m-w3=3 p=p+p3=6 ⑤贪心选择物体1 w1m, 故x1=m/w1=1/3 p=p+p1*x1=7.667 最优解为：X=(1/3，1，1）。 ①初始：背包剩余重量m=M=10 背包当前价值p=0 ②对物体按价值/重量的降序排序，得2 3 1 时间复杂性分析：排序O(nlogn)，贪心选择O(n)， 故时间复杂性为O(nlogn)。 贪心法解背包问题算法分析 问题原型 某售货员要到若干个城市销售货物，已知各城市之间的距离，要求售货员选择出发的城市及旅行路线，使每个城市经过一次，最后回到原出发城市，而总路程最短。 贪心算法 — 货郎担问题 货郎担问题数学描述 求距离最短的哈密尔顿回路，需求从各城市出发的 最短回路，再对n条回路求极小值。 回路最短—贪心选择距离短的路线 贪心法解货郎担问题 例：假设5个城市的费用矩阵为： ∞ 3 3 2 6 3 ∞ 7 3 2 3 7 ∞ 2 5 2 3 2 ∞ 3 6 2 5 3 ∞ 1 2 3 4 5 1 2 3 4 5 从城市1出发：1-4-3-5-2-1，总距离14 从城市2出发：2-5-4-1-3-2，总距离17 其它城市同理，再在5条回路中选择最小距离。 时间复杂性分析： 从一个城市出发的最短回路计算为 O(n2)，共n个城市，故时间复杂度为O(n3)，远小于穷举法的 n!。 最优解分析： 从城市1出发最优路线：1-2-5-4-3-1，距离13 贪心法求解货郎担问题不具有贪心选择性质和最优子结构性质。只能得到近似解，不能得到最优解 。 贪心法解货郎担问题算法分析 单源点最短路径 最小生成树 — prim和Kruskal Huffman编码 数据结构中的贪心算法