贪心法专题.doc

算法设计技术——贪心法专题 1一、贪心法的设计思想 1例1埃及分数 1例2TSP问题 2例3图着色问题 3例4最小生成树问题——prim算法 4例5最小生成树问题——Kruskal算法 5例6背包问题 6例7活动安排问题 7例8多机调度问题 8算法设计技术——贪心法专题一、贪心法的设计思想正如其名字一样,贪心法(greedymethod)在解决问题的策略上目光短浅,只根据当前已有的信息做出选择,而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。考虑用贪心法求解付款问题(paymentproblem)。假设有面值为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角。由于贪心法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优,这种局部最优选择并不总能获得整体最优解(optimalsolution),但通常能获得近似最优解(near-optimalsolution)。如果一个问题的最优解只能用蛮力法穷举得到,则贪心法不失为寻找问题近似最优解的一个较好办法。例1埃及分数【问题】埃及同中国一样,也是世界文明古国之一。古埃及人只用分子为1的分数,在表示一个真分数时,将其分解为若干个埃及分数之和,例如:7/8表示为1/2+1/3+1/24。埃及分数问题(Egyptfraction)要求把一个真分数表示为最少的埃及分数之和的形式。【想法】一个真分数的埃及分数表示不是唯一的,例如: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/(C+1)即1/(C+1)即为真分数A/B包含的最大埃及分数。设E=C+1,由于A/B–1/E=((A×E)–B)/(B×E)则真分数减去最大埃及分数后,得到真分数((A×E)–B)/B×E,该真分数可能存在公因子,需要化简,可以将分子和分母同时除以最大公约数。【算法】设函数EgyptFraction实现埃及分数问题,算法用伪代码描述如下::埃及分数EgyptFraction输入:真分数的分子A和分母B输出:=B/A+1;;=A*E–B;B=B*E;,如果R不为1,则将A和B同时除以R;,则输出1/B,算法结束;否则转步骤1重复执行;例2TSP问题【问题】TSP问题是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短。【想法1】TSP问题的贪心策略可以采用最近邻点策略:从任意城市出发,每次在没有到过的城市中选择最近的一个,直到经过了所有的城市,最后回到出发城市。(a)所示是一个无向图的代价矩阵,从顶点1出发,按照最近邻点的贪心策略,得到的路径是1→4→3→5→2→1,总代价是14,(b)~(f)所示。(d)顶点3→顶点5(e)顶点5→顶点2(f)顶点2→=∞33263∞73237∞25232∞36253∞(a)一个无向图的代价矩阵(b)顶点1→顶点4(c)顶点4→顶点3214221432521543252215432需要说明的是,用最近邻点贪心策略求解TSP问题所得的结果不一定