搜索
算法设计与分析清华大学出版社第7章贪心法7.1概述7.2图问题中的贪心法7.3组合问题中的贪心法7.4实验项目——哈夫曼编码算法设计与分析清华大学出版社7.1概述7.1.1贪心法的设计思想7.1.2贪心法的求解过程算法设计与分析清华大学出版社贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优。这种局部最优选择并不总能获得整体最优解（OptimalSolution），但通常能获得近似最优解（Near-OptimalSolution）。7.1.1贪心法的设计思想算法设计与分析清华大学出版社例：用贪心法求解付款问题。假设有面值为5元、2元、1元、5角、2角、1角的货币，需要找给顾客4元6角现金，为使付出的货币的数量最少，首先选出1张面值不超过4元6角的最大面值的货币，即2元，再选出1张面值不超过2元6角的最大面值的货币，即2元，再选出1张面值不超过6角的最大面值的货币，即5角，再选出1张面值不超过1角的最大面值的货币，即1角，总共付出4张货币。算法设计与分析清华大学出版社在付款问题每一步的贪心选择中，在不超过应付款金额的条件下，只选择面值最大的货币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定：一旦选出了一张货币，就永远选定。付款问题的贪心选择策略是尽可能使付出的货币最快地满足支付要求，其目的是使付出的货币张数最慢地增加，这正体现了贪心法的设计思想。算法设计与分析清华大学出版社贪心法求解的问题的特征：（1）最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。（2）贪心选择性质所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到。动态规划法通常以自底向上的方式求解各个子问题，而贪心法则通常以自顶向下的方式做出一系列的贪心选择。算法设计与分析清华大学出版社7.1.2贪心法的求解过程用贪心法求解问题应该考虑如下几个方面：（1）候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。（2）解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。算法设计与分析清华大学出版社（3）解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款。（4）选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币。（5）可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款。算法设计与分析清华大学出版社贪心法的一般过程Greedy(C)//C是问题的输入集合即候选集合{S={};//初始解集合为空集while(notsolution(S))//集合S没有构成问题的一个解{x=select(C);//在候选集合C中做贪心选择iffeasible(S,x)//判断集合S中加入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=∞33263∞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问题的算法如下：算法设计与分析清华大学出版社算法7.1的时间性能为O(n2)，因为共进行n-1次贪心选择，每一次选择都需要查找满足贪心条件的最短边。用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解，图7.1(a)中从城市1出发的最优解是1→2→5→4→3→1，总代价只有13。当图中顶点个数较多并且各边的代价值分布比较均匀时，最近邻点策略可以给出较好的近似解，不过，这个近似解以何种程度近似于最优解，却难以保证。例如，在图7.1中，如果增大边(2,1)的代价，则总代价只好随之增加，没有选择的余地。算法设计与分析清华大学出版社（2）最短链接策略：每次在整个图的范围内选择最短边加入到解集合中，但是，要保证加入解集合中的边最终形成一个哈密顿回路。因此，当从剩余边集E'中选择一条边(u,v)加入解集合S中，应满足以下条件：①边(u,v)是边集E'中代价最小的边；②边(u,v)加入解集合S后，S中不产生回路；③边(u,v)加入解集合S后，S中不产生分枝；算法设计与分析清华大学出版社215432215432C=∞33263∞73237∞25232∞36253∞(a)5城市的代价矩阵(b)城市1→城市4(c)城市5→城市22(d)城市4→城市3(e)城市3→城市5(f)城市2回到出发城市1最短链接贪心策略求解TSP问题的过程222154322221543222215432535算法设计与分析清华大学出版社算法7.2——最短链接策略求解TSP问题1．P={};2．E'=E;//候选集合，初始时为图中所有边3．循环直到集合P中包含n-1条边3.1在E'中选取最短边(u,v);3.2E'=E'-{(u,v)};3.3如果(顶点u和v在P中不连通and不产生分枝)则P=P+{(u,v)};设图G有n个顶点，边上的代价存储在二维数组w[n][n]中，集合E'是候选集合即存储所有未选取的边，集合P存储经过的边，最短链接策略求解TSP问题的算法如下：算法设计与分析清华大学出版社在算法7.2中，如果操作“在E'中选取最短边(u,v)”用顺序查找，则算法7.2的时间性能是O(n2)，如果采用堆排序的方法将集合E'中的边建立堆，则选取最短边的操作可以是O(log2n)，对于两个顶点是否连通以及是否会产生分枝，可以用并查集的操作将其时间性能提高到O(n)，此时算法7.2的时间性能为O(nlog2n)。算法设计与分析清华大学出版社7.2.2图着色问题给定无向连通图G=(V,E)，求图G的最小色数k，使得用k种颜色对G中的顶点着色，可使任意两个相邻顶点着色不同。算法设计与分析清华大学出版社12345例如，图7.3(a)所示的图可以只用两种颜色着色，将顶点1、3和4着成一种颜色，将顶点2和顶点5着成另外一种颜色。为简单起见，下面假定k个颜色的集合为{颜色1,颜色2,…,颜色k}。算法设计与分析清华大学出版社贪心策略：选择一种颜色，以任意顶点作为开始顶点，依次考察图中的未被着色的每个顶点，如果一个顶点可以用颜色1着色，换言之，该顶点的邻接点都还未被着色，则用颜色1为该顶点着色，当没有顶点能以这种颜色着色时，选择颜色2和一个未被着色的顶点作为开始顶点，用第二种颜色为尽可能多的顶点着色，如果还有未着色的顶点，则选取颜色3并为尽可能多的顶点着色，依此类推。3451212345算法设计与分析清华大学出版社算法7.3——图着色问题1．color[1]=1;//顶点1着颜色12．for(i=2;i=n;i++)//其他所有顶点置未着色状态color[i]=0;3．k=0;4．循环直到所有顶点均着色4.1k++;//取下一个颜色4.2for(i=2;i=n;i++)//用颜色k为尽量多的顶点着色4.2.1若顶点i已着色，则转步骤4.2，考虑下一个顶点;4.2.2若图中与顶点i邻接的顶点着色与顶点i着颜色k不冲突，则color[i]=k;5．输出k;设数组color[n]表示顶点的着色情况，贪心法求解图着色问题的算法如下：算法设计与分析清华大学出版社15372648图7.4具有8个顶点的双向图考虑一个具有2n个顶点的无向图，顶点的编号从1到2n，当i是奇数时，顶点i与除了顶点i+1之外的其他所有编号为偶数的顶点邻接，当i是偶数时，顶点i与除了顶点i-1之外的其他所有编号为奇数的顶点邻接，这样的图称为双向图（Bipartite）。算法设计与分析清华大学出版社7.2.3最小生成树问题设G=(V，E)是一个无向连通网，生成树上各边的权值之和称为该生成树的代价，在G的所有生成树中，代价最小的生成树称为最小生成树（MinimalSpanningTrees）。算法设计与分析清华大学出版社最小生成树问题至少有两种合理的贪心策略：（1）最近顶点策略：任选一个顶点，并以此建立起生成树，每一步的贪心选择是简单地把不在生成树中的最近顶点添加到生成树中。Prim算法就应用了这个贪心策略,它使生成树以一种自然的方式生长，即从任意顶点开始，每一步为这棵树添加一个分枝，直到生成树中包含全部顶点。算法设计与分析清华大学出版社(d)U={A,F,C,D}(e)U={A,F,C,D,E}(f)U={A,F,C,D,E,B}cost={(A,B)34,(F,E)26}cost={(E,B)12}cost={}Prim算法构造最小生成树的过程示意B251234192646381725251234192646381725251234192646381725AAABBEEEFFFDDD343434171717251219264638252512192646382525121926463825(a)连通网，U={A}(b)U={A,F}(c)U={A,F,C}cost={(A,B)34,(A,C)46,cost={(A,B)34,(F,C)25,cost={(A,B)34,(C,D)17,(F,E)26}(A,D)∞,(A,E)∞,(A,F)19}(F,D)25,(F,E)26}BBBAAAEEEFFFDDDCCCCCC算法设计与分析清华大学出版社设图G中顶点的编号为0～n-1，Prim算法如下：算法7.4——Prim算法1.初始化两个辅助数组lowcost和adjvex；2.U={u0};输出顶点u0;//将顶点u0加入生成树中3.重复执行下列操作n-1次3.1在lowcost中选取最短边，取adjvex中对应的顶点序号k；3.2输出顶点k和对应的权值；3.3U=U+{k}；3.4调整数组lowcost和adjvex；设连通网中有n个顶点，则第一个进行初始化的循环语句需要执行n-1次，第二个循环共执行n-1次，内嵌两个循环，其一是在长度为n的数组中求最小值，需要执行n-1次，其二是调整辅助数组，需要执行n-1次，所以，Prim算法的时间复杂度为O(n2)。算法设计与分析清华大学出版社（2）最短边策略：设G=(V，E)是一个无向连通网，令T=(U，TE)是G的最小生成树。最短边策略从TE={}开始，每一次贪心选择都是在边集E中选取最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，