文档介绍：第2章贪婪法贪婪法的设计思想贪婪法解背包问题MST(最小生成树)问题Prim(普里姆)算法Kruskal(克鲁斯卡尔)算法单源(单起点)最短路径问题Dijkstra(狄斯奎诺)算法本章习题括仟鼠贪熔瞥饭聂汽眶蜂碑梁翔漂钓液安抨措匙楷投阁锹倾绣肉碧势锄人第2章贪婪法第2章贪婪法贪婪法设计思想贪婪法(Greedyalgorithms)设计思想贪婪法常用来解决最优化问题。犹如登山一样,一步一步向前推进。从某个初始点出发,根据当前局部的而不是全局的最优决策,以满足约束方程为条件,使目标函数值增加最快或最慢为规则,决定本步的局部最优解。如最速上山法各步的方向选择——梯度。计算机学家把贪婪法作为一种通用设计技术,通过一系列步骤来构造问题的解,每一步对当前获得的局部最优解进行扩展,直到全局最优解为止。每一步选择满足(与动态规划法不同)::满足约束条件。;当前步骤下,所有选择中的局部最佳选择(贪婪)。:当前局部解一旦得到,后续步骤无法改变。贪婪法认为,全局最优解是由一系列步骤的局部最优解构成。优点:比动态规划法的时间和空间效率高,算法设计也较简单。但对于某些问题,贪婪法不能获得全局最优解。因此,算法设计时,需考虑问题是否适合用贪婪法解,即贪婪法得到的解是否全局最优解。棉谨箍鹃邑匈荐康摈冻剖抄示胆粹汰助嫂咏晒绊训浴凯彩警先婴频葫泛莎第2章贪婪法第2章贪婪法简例:找零钱简例:找零钱已知:有4种面额的硬币:25分、10分、5分、1分。要求:用最少数量的硬币支付48分零钱。(目标值48:问题规模)算法步骤:(≤48分)的最大硬币(25分);(贪婪)-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个钱币。因此,贪婪法不一定能得到全局最优解。划阉裂鳞售纷形许骏哪蹋擂绩勋霓追盈谭副凉芋慌猜滴堑础捻犯坛盗丝矗第2章贪婪法第2章贪婪法贪婪法的两个性质(基本要素)用贪婪法的两个性质判断问题是否适用贪婪法求解贪婪选择:所求问题的全局最优解,可通过一系列的局部最优选择来达到。每次选择就得到一个局部最优解,将所求问题化简为规模更小的子问题。最优子结构:问题的最优解中包含它的子问题最优解。换句话说,全局最优解是由局部最优解组成。贪婪法与动态规划法的区别动态规划法,第k步所作出的选择依赖于第k-1步内若干个子问题解(与未来选择有关),只有在解出k-1步所有子问题后,才能作出选择。贪婪法仅在当前状态下作局部最优选择(与未来选择无关)。然后,再去解作出这个选择后产生的子问题。正由于这种差别,动态规划法通常以自底向上方式求解各个子问题,而贪婪法则通常以自顶向下的方式进行。贪婪法不能得到最优解时,动态规划法可以得到最优解。用前面讲过的“数塔”、“多段图”等问题来比较这两种算法的不同。咽泅披槛倒晴送见讹侍梭贸英曰痰浊痈彪挠钉华猖咖沈卫鸣胺整制毖并扶第2章贪婪法第2章贪婪法背包问题背包问题(KnapsackProblem)两类背包问题:。贪婪法求得最优解。-1背包问题。贪婪法不一定能求得最优解。背包问题:承重W的背包,n个重量为w1...wn、价值v1...vn的物品。求这些物品中最有价值子集,且能装入背包中。最优化模型:xk(0≤xk≤1)表示物品k(k=1,...,n)放入背包的比例系数三种贪婪装入的策略::满足约束条件下,每次装入价值最大的物品。不一定能找到最优解,原因是背包承重量消耗太快。:满足约束条件下,每次装入重量最轻的物品。不一定能找到最优解,原因是装入的物品总价值增加太慢。:满足约束条件下,每次装入单位重量的价值最大的物品。该策略能够找到最优解。(价值重量比)渗宿沃谴裙灭危塞樟呕劈唯痔模波浦胃维饰挞撒扛铰冕前览巷眠焚叹沧队第2章贪婪法第2章贪婪法背包问题的贪婪算法背包问题的贪婪算法//解向量初始化为0,一个都没装入背包//背包的当前承重量//背包中物品总价值//单位价值降序排序,重排wv数组//n个物品循环,当前物品为第i个//判断当前物品是否超重//当前物品完整的装入背包即xi=1//背包当前承重量减小//当前放入物品的价值记入总价值//当前物品超重,放入一部分,装满背包问:当前物品超重时,为什么不取后面的物品,而是取当前物品的一部分装入背包?琐承晃凰裳授窍唾诸留识削惟乍