第2章 贪婪法.ppt

《第2章 贪婪法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章贪婪法贪婪法的设计思想贪婪法解背包问题MST（最小生成树）问题Prim（普里姆）算法Kruskal（克鲁斯卡尔）算法单源（单起点）最短路径问题Dijkstra（狄斯奎诺）算法本章习题贪婪法设计思想贪婪法（Greedyalgorithms）设计思想贪婪法常用来解决最优化问题。犹如登山一样，一步一步向前推进。从某个初始点出发，根据当前局部的而不是全局的最优决策，以满足约束方程为条件，使目标函数值增加最快或最慢为规则，决定本步的局部最优解。如最速上山法各步的方向选择——梯度。计算机学家把贪婪法作为一种通用设计技术，通过一系列步骤来构造问题的解，每一步对当前获得的局部最优解进行扩展

2、，直到全局最优解为止。每一步选择满足（与动态规划法不同）：1.可行解：满足约束条件。2.局部最优；当前步骤下，所有选择中的局部最佳选择（贪婪）。3.不可取消：当前局部解一旦得到，后续步骤无法改变。贪婪法认为，全局最优解是由一系列步骤的局部最优解构成。优点：比动态规划法的时间和空间效率高，算法设计也较简单。但对于某些问题，贪婪法不能获得全局最优解。因此，算法设计时，需考虑问题是否适合用贪婪法解，即贪婪法得到的解是否全局最优解。简例：找零钱简例：找零钱已知：有4种面额的硬币：25分、10分、5分、1分。要求：用最少数量的硬币支付48分零钱。（目标值48：问题规模）算法步骤：1.支付面

3、额满足约束条件（≤48分）的最大硬币（25分）；（贪婪）2.计算目标函数值48-25=23；判断是否达到要求（0分）：若是，算法停止，否则，返回1步。计算结果：25，10，10，1，1，1。——6个钱币算法策略：总是作出当前最佳选择——局部最优。每一步选择最大硬币，是为了把余下的数量减到最小。结果讨论：针对这4种面额，贪婪法的确能给出全局最优解。现在换为3种面额：7分、5分、1分，找零钱11分。贪婪法结果：7,1,1,1,1共5个钱币。最优解：5,5,1共3个钱币。因此，贪婪法不一定能得到全局最优解。贪婪法的两个性质（基本要素）用贪婪法的两个性质判断问题是否适用贪婪法求解贪婪选择

4、：所求问题的全局最优解，可通过一系列的局部最优选择来达到。每次选择就得到一个局部最优解，将所求问题化简为规模更小的子问题。最优子结构：问题的最优解中包含它的子问题最优解。换句话说，全局最优解是由局部最优解组成。贪婪法与动态规划法的区别动态规划法，第k步所作出的选择依赖于第k-1步内若干个子问题解（与未来选择有关），只有在解出k-1步所有子问题后，才能作出选择。贪婪法仅在当前状态下作局部最优选择（与未来选择无关）。然后，再去解作出这个选择后产生的子问题。正由于这种差别，动态规划法通常以自底向上方式求解各个子问题，而贪婪法则通常以自顶向下的方式进行。贪婪法不能得到最优解时，动态规划法

5、可以得到最优解。用前面讲过的“数塔”、“多段图”等问题来比较这两种算法的不同。背包问题背包问题（KnapsackProblem）两类背包问题：1.物品可以分割的背包问题。贪婪法求得最优解。2.物品不可以分割的0-1背包问题。贪婪法不一定能求得最优解。背包问题：承重W的背包，n个重量为w1...wn、价值v1...vn的物品。求这些物品中最有价值子集，且能装入背包中。最优化模型：xk(0≤xk≤1)表示物品k(k=1,...,n)放入背包的比例系数三种贪婪装入的策略：1.价值最大：满足约束条件下，每次装入价值最大的物品。不一定能找到最优解，原因是背包承重量消耗太快。2.重量最小：满

6、足约束条件下，每次装入重量最轻的物品。不一定能找到最优解，原因是装入的物品总价值增加太慢。3.单位价值最大：满足约束条件下，每次装入单位重量的价值最大的物品。该策略能够找到最优解。（价值重量比）背包问题的贪婪算法背包问题的贪婪算法//解向量初始化为0，一个都没装入背包//背包的当前承重量//背包中物品总价值//单位价值降序排序，重排wv数组//n个物品循环，当前物品为第i个//判断当前物品是否超重//当前物品完整的装入背包即xi=1//背包当前承重量减小//当前放入物品的价值记入总价值//当前物品超重，放入一部分，装满背包问：当前物品超重时，为什么不取后面的物品，而是取当前物品的

7、一部分装入背包？有限期的计算机作业调度给定n个作业j1,j2,…,jn。对于每一个作业ji，有一个与联系的限期di>0和收益p≥0，di，pi均为整数，1≤i≤n。对于作业ji，只有在限期di内完成，才能得到收益pi。假定只有一台处理机为这批作业服务，处理机每次只能处理一个作业，并且完成任一作业需一个单位时间。可行解：这批作业的一个子集J，且J中每一作业均能在限期内完成，调度的总收益是该子集J中各作业收益的和。最优解：具有最大收益的可行解称为最优解。本问题的目标函数∑pi可以作为