算法设计与分析_王红梅_第7章 贪心法.ppt

《算法设计与分析_王红梅_第7章 贪心法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7章贪心法7.1概述7.2图问题中的贪心法7.3组合问题中的贪心法7.4实验项目——哈夫曼编码7.1概述7.1.1贪心法的设计思想7.1.2贪心法的求解过程贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解（OptimalSolution），但通常能获得近似最优解（Near-OptimalSolution）。7.1.1贪心法的设计思想

2、例：用贪心法求解付款问题。假设有面值为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）最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。（2）贪心选择性质所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。动态规划法通常以自底向上的方式求解各个子问题，而贪心法则通常以自顶向下的方式做出一系列的贪心选择。7.1.2贪心法的求解过程用贪心法求解问题应该考虑如下几个方面

4、：（1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。（3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。（4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目

5、标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。（5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。贪心法的一般过程Greedy(C)//C是问题的输入集合即候选集合{S={};//初始解集合为空集while(notsolution(S))//集合S没有构成问题的一个解{x=select(C);//在候选集合C中做贪心选择iffeasible(S,x)//判断集合S中加入

6、x后的解是否可行S=S+{x};C=C-{x};}returnS;}7.2图问题中的贪心法7.2.1TSP问题7.2.2图着色问题7.2.3最小生成树问题7.2.1TSP问题求解TSP问题至少有两种贪心策略是合理的：（1）最近邻点策略：从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。(d)城市3→城市5(e)城市5→城市2(f)城市2→城市1最近邻点贪心策略求解TSP问题的过程25221543225221543232522154327363215432233215432C=∞33

7、263∞73237∞25232∞36253∞(a)5城市的代价矩阵(b)城市1→城市4(c)城市4→城市3算法7.1——最近邻点策略求解TSP问题1．P={};2．V=V-{u0};u=u0;//从顶点u0出发3．循环直到集合P中包含n-1条边3.1查找与顶点u邻接的最小代价边(u,v)并且v属于集合V；3.2P=P+{(u,v)};3.3V=V-{v};3.4u=v;//从顶点v出发继续求解伪代码设图G有n个顶点，边上的代价存储在二维数组w[n][n]中，集合V存储图的顶点，集合P存储经过的边，最近邻点策略求解TSP问题的

8、算法如下：算法7.1的时间性能为O(n2)，因为共进行n-1次贪心选择，每一次选择都需要查找满足贪心条件的最短边。用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解，图7.1(a)中从城市1出发的最优解是1→2→5→4→3→1，总代价只有13。当图中顶点个数较多并且各边的代价值分布比