贪心法专题参考资料.doc

目录
算法设计技术——贪心法专题 1
一、贪心法的设计思想 1
例1 埃及分数 1
例2 TSP问题 2
例3 图着色问题 3
例4 最小生成树问题——prim算法 4
例5 最小生成树问题——Kruskal算法 5
例6 背包问题 6
例7 活动安排问题 7
例8 多机调度问题 8
算法设计技术——贪心法专题
一、贪心法的设计思想
正如其名字一样,贪心法(greedy method)在解决问题的策略上目光短浅,只根据当前已有的信息做出选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。
考虑用贪心法求解付款问题(payment problem)。假设有面值为5元、2元、1元、5角、2角、1角的货币,需要找给顾客4元6角现金,为使付出的货币的数量最少,首先选出1张面值不超过4元6角的最大面值的货币,即2元,再选出1张面值不超过2元6角的最大面值的货币,即2元,再选出1张面值不超过6角的最大面值的货币,即5角,再选出1张面值不超过1角的最大面值的货币,即1角,总共付出4张货币。在付款问题每一步的贪心选择中,在不超过应付款金额的条件下,只选择面值最大的货币,而不去考虑在后面看来这种选择是否合理,而且它还不会改变决定:一旦选出了一张货币,就永远选定。付款问题的贪心选择策略是尽可能使付出的货币最快地满足支付要求,其目的是使付出的货币张数最慢地增加,这正体现了贪心法的设计思想。
上述付款问题应用贪心法得到的是整体最优解,但是如果把面值改为3元、1元、8角、5角、1角,需要找给顾客4元6角现金,则找给顾客的是1个3元、1个1元、1个5角和1个1角共4张货币,但最优解却是3张货币:1个3元和2个8角。由于贪心法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优,这种局部最优选择并不总能获得整体最优解(optimal solution),但通常能获得近似最优解(near-optimal solution)。如果一个问题的最优解只能用蛮力法穷举得到,则贪心法不失为寻找问题近似最优解的一个较好办法。
例1 埃及分数
【问题】埃及同中国一样,也是世界文明古国之一。古埃及人只用分子为1的分数,在表示一个真分数时,将其分解为若干个埃及分数之和,例如:7/8表示为1/2 + 1/3 + 1/24。埃及分数问题(Egypt fraction)要求把一个真分数表示为最少的埃及分数之和的形式。
【想法】一个真分数的埃及分数表示不是唯一的,例如:7/8又可以表示为1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8 + 1/8。显然,把一个真分数表示为最少的埃及分数之和的形式,其贪心策略是选择真分数包含的最大埃及分数,以7/8为例,7/8 > 1/2,则1/2是第一次贪心选择的结果;7/8 – 1/2 = 3/8 > 1/3,则1/3是第二次贪心选择的结果;7/8 – 1/2 – 1/3 = 1/24,则1/24是第三次贪心选择的结果,即7/8 = 1/2 + 1/3 + 1/24。
接下来的问题是:如何找到真分数包含的最大埃及分数?设真分数为A/B,B除以A的整数部分为C,余数为D,则有下式成立:
B = A × C + D
即:
B/A = C + D/A < C + 1
则:
A/B > 1/