Ch-5贪心策略.doc

第5章 贪心策略5.1 概述问题导入：找零钱问题有4 种硬币，面值分别为2角5分、1角、5分和1分。现在要求以最少的硬币个数找给顾客6角3分。通常做法是：先拿2个2角5 分的 1个1角 3个一分这种找法所拿出的硬币个数最少。这种算法其实就是贪心算法。（考虑动态规划法如何求解？）顾名思义，该算法总是做出在当前看来最好的选择，并且不从整体上考虑最优问题，所做出的每一步选择只是在某种意义上的局部最优选择，逐步扩大解的规模。当然，希望贪心算法得到的最终结果也是整体最优的（上面的解法得到的恰好是最优解）。但未必总是得到最优解。假如，面值有1角1分、5分和1分，要找给顾客1角5分。如果还是使用上述贪心算法，得到的解是：1个1角1分 4个1分。而实际上最优解是3个5分。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解，例如：单源最短路径问题、最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心法的难点在于它的正确性证明。5.1 单源最短路径问题G = (V, E) 是一个有向图，每条边上有一个非负整数表示长度值，其中有一个顶点称为源节点。所谓的单源最短路径问题就是：求解该源节点到所有任一节点的最短路径的长度。不失一般性，假设V = 1,2,3,.,n 并且s = 1。那么该问题可以使用Dijkstra算法来求解，该算法是一种贪心算法，并且能求得最优解。开始时，我们将所有的顶点划分为两个集合X = 1, Y = 2,3,4,.,n。所有已经计算好的顶点存放在X中，Y中表示还没有计算好的。Y中的每个顶点y有一个对应的量 y，该值是从源顶点到y (并且只经由X中的顶点) 的最短路径的长度。Dijkstra算法假设V = 1,2,3,.,n 并且s = 1。1) 选择一个y 最小顶点yY，并将其移动到X 中。2) 若 y 被从Y 移动到X 中，Y 中每个和y 相邻的顶点w 的w都要更新(表示经由y 到w 的一条更短的路径被发现)41513945312112101234564151394531214101012345641513945312117134810123456415139453121171348101234564151394531211917481012345619415139453121134810123456Dijkstra算法1. X=1; YV-1; 102. for y2 to n3. if y 相邻于1 then ylength1,y /Q(n)4. else y /O(n)5. end if6. end for7. for j1 to n-18. 令yY, 使得y为最小的 /(n-i)i=1,n-1= Q(n2)9. XXy /Q(n)10. YY - y /Q(n)11. for 每条边(y,w) /每条边恰好检查一次，Q(m), m=|E|12. if wY and y+lengthy,w w then13. w y+lengthy,w /Q(m)14. end if15. end for16. end for算法的时间复杂度Q(n)+ O(n)+ Q(n2)+ Q(n)+ Q(n)+ Q(m)+ Q(m) = Q(m+n2)对于任意一个顶点 vV, 假如我们使用v表示源顶点到顶点v 的最短路径的长度，可以证明, 上述的贪心法结束后有v = v下面来证明使用该方法得到的是最优解，也就是y = y。证明: 归纳法1) 显然1 = 1 = 02) 假设当前将 y 移动到X 中，并且在y 之前移动到X 中的任何一个顶点c，都有c = c。（第二数学归纳法）由于y 是有限的，也就是说必定存在一条从1 到y 路径，长度为 y（我们需要来证明 y = y）。那么这条路径总可以写作：1 y在上述序列中，我们总是可以找到一个顶点，不妨称之为x (x X), 使得x 之后的顶点均属于Y。所以有以下两种情形：1 xy (A)或：1 x y (B)对于情形(A)，y x+lengthx, y /算法要求=x+length(x, y) /归纳假设=y /是最短路径对于情形(B)，我们将x之后的顶点不妨称之为w (wY)，即：1 x wy (B)于是有： y w /由于y在w之前离开Y x + length(x,w) /算法要求，原因同(A)=x + length(x,w) /归纳假设=w /因为是最短路径y /因为是最短路径综合(A)(B)情况，总是有 y y. 我们已经说了，y是最短路径了，因此y = y。因此，Dijkstra算法得到的是最优解。 5.1.1 稠密图的线性时间算法 (pp.149-150)5.2 最小生成树设G =(V,E)是连通无向带权图，(V,T)是G的一个子图，并且T是一颗树，那么称(V,T)是G的生成树。如果T的权之和是所有生成树中最小的，那么则称之为最小生成树。网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v 和城市w 之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。我们假定G 是连通的，如果G 是非连通的，那么，可以对G 的每个子图应用求解最小生成树的算法。5.2.1 Kruskal算法1. 对G的边E按权重以非降序排列2. 初始时输出数T=;对于排序表中的每条边，若加入T不形成回路，则加入T;否则将其丢弃；3. 不断重复步骤2，直到树T包含n-1条边，算法结束。437691311211234561123456112345623112345624311234562643112345627431123456294311234562Kruskal算法1. 对E中的边按权重以非降序排列 /O(mlogm)2. for 每个顶点 vV /Q(n)3. MAKESET(v) /why?4. end for5. T=6. while |T|n-17. 令(x,y)为E中的下一条边 /取每条边试探, 最多m次8. if FIND(x) FIND(y) then /最多2m次查找，原因如上9. 将(x,y)加入T /刚好n-1次, Q(n)10. UNION(x,y) /如上, n-1次11. end if12. end while Kruskal算法复杂度O(mlogm)+ Q(n)+O(m)+O(m)+Q(n)+ Q(n)= O(mlogm+n)由于图边数mn-1, 则O(mlogm+n) = O(mlogm)Kruskal 算法的正确性证明证明：我们只要证明，使用Kruskal 算法过程中，每次循环所得到的T (从空集增至最小生成树)总是图G 的最小生成树的子集即可。证明使用归纳法反证法。(1) G总是具有一个最小生成树，不妨记为T*(2) 当前要加入的边为e= (x,y) (3) 包含x的那棵子树的所有顶点用X表示，有x X, yV X(4) 假设在e= (x,y)加入之前得到的T均满足TT*令T =Te，下面我们要证明T 也是图G 的最小生成树的子集。依据归纳假设，有TT* 。i) 如果eT*, 显然有TT*ii) 如果 e T*, 我们知道T*中必定包含这样一条边e =(w,z) ,且wX, zVX , 且cost( e ) cost( e )。（否则若cost(e)cost( e ), 则e 将被选择加入(而不是e)）下面我们来研究：如果eT*会带来什么结果。定义T* =T*ee，那么T*也是图的一个生成树，并且cost(T* )=cost(T* ) - cost(e) + cost(e) cost(T* )。也就是说，T*不是最小生成树，矛盾。所以e 必定是属于T* 的。也就必定有TT*，证毕。5.2.2 Prim算法设G=(V,E)是连通无向带权图，V=1,2,n。构造G 的最小生成树的Prim算法的基本思想是：首先置X=1，然后，只要X是V的真子集，就作如下的贪心选择：选取权重最小的边(x,y), 其中xX，yY，将边(x,y)加入当前的最小生成树，将顶点 y 从Y 移到X 中，这个过程一直进行到X=V时为止。在这个过程中选取到的所有边恰好构成G 的一棵最小生成树。13437691121123456C4=cost(4,2)=1143769131121123456C4=cost(4,3)=943769131121123456437691311211234564376913112112345643769131121123456算法设计要点：寻找(x,y), 使得xX, yY, 且cost(x,y)最小.候选边(x,y)对应的顶点yY, 可考察y在X中的邻居.邻居就是X中离y最近的那个点x*, 即cost(x*, y)=mincost(x, y)| xX 且 (x,y)存在记x*=Ny, 定义 Cy= cost(x*, y) = cost(y, Ny).X,Y可用n维0,1向量表示, 例Xi=1表示顶点iX.Prim算法1. T; X1; YV-1 2. for y2 to n 3. if y 邻接于1 then 4. Ny 15. Cy cost1,y6. else Cy 7. end if8. end for9. for j1 to n-1 /寻找MST的n-1条边10. 令 yY, 使得Cy最小 11. TT(y, Ny) 12. XXy 13. YY - y 14. for 每个邻接于y的顶点wY 15. if costy,w Cw then /w有了更近的邻居，即yX16. Nw y17. Cw costy,w18. end if19. end for20. end forPrim算法复杂度分析1. T; X1; YV-1 /Q(n)2. for y2 to n /Q(n)3. if y 邻接于1 then /第36步, O(n)4. Ny 15. Cy cost1,y6. else Cy 7. end if8. end for9. for j1 to n-1 /寻找MST的n-1条边10. 令 yY, 使得Cy最小 /每次Q(n), 共n-1次, 计Q(n2)11. TT(y, Ny) /Q(1)(n-1)= Q(n)12. XXy /Q(1)(n-1)= Q(n)13. YY - y /.14. for 每个邻接于y的顶点wY /Q(m)15. if costy,w Cw then /每条边执行1次，共m次16. Nw y /最多m次，Q(m)17. Cw costy,w /Q(m)18. end if/每条边y,w被扫描1次：现在是y移向X时被扫描1次，目的是更新Cw，便于下次从Y中挑选顶点；下一轮只需比较Y中的Cy值，即可挑中某一顶点并将其移向X，无需第二次扫描边1343769112112345643769131121123456/2移入X后,(2,3)和(2,4)被扫描一次； 3移入X之前,(2,3)和(2,4)无需扫描19. end for20. end forPrim算法的时间复杂度：Q(n)+ Q(n2)+ Q(m)= Q(m+n2)比较：Kruskal算法复杂度为O(mlogm). 当m=W(n2)时，Kruskal算法O(mlogm)=O(n2logn),Prim算法Q(m+n2)= Q(n2); Kruskal算法较差。当m=o(n2)时，Kruskal算法O(mlogm)=o(nlogn), Prim算法Q(m+n2)= Q(n2); Kruskal算法较好。Kruskal算法适合于稀疏图；而Prim算法适合于稠密图。5.3 Huffman编码5.3.1 数学基础-排序不等式设有两组数a1, a2, , an和b1, b2, , bn，满足a1a2 an 和 b1b2 bn则有a1bn+ a2bn-1+ anb1 a1bt1+ a2bt2+ anbtn a1b1+ a2b2+ anbn式中t1, t2,tn是1, 2,n的任意一个排列。当且仅当 a1=a2= =an 或 b1=b2= =bn时，等号成立。以上排序不等式也可简记为： 反序和 乱序和 同序和证明时可采用逐步调整法例如，其余不变时，将a1b1+ a2b2调整为a1b2+ a2b1，易知(a1b1+ a2b2) - (a1b2+ a2b1) = (a1-a2)(b1-b2) 0即a1b2+ a2b1 a1b1+ a2b2;依次类推，根据逐步调整法，排序不等式得证。 例：有10人各拿一只水桶去接水，水龙头只有一个，灌满这些水桶需要ai分钟。假设ai大小不同，不妨设a1a2a10。问：应该如何安排这10人的顺序，使得他们等待的总时间最少？ e a c b d182010741820101174182010117421b de a c11110000101174211820385910117421182038贪心性质当前要合并的总是两棵最小频率的树；先考虑的节点深度比较大，对应的编码比较长。与排序不等式的关系：频度小的编码长，频度大的编码短（即反序和，为最小），这样编码后，总编码长度最小。算法实现：由于总是在C=c1,cn中寻找最小频度对应的节点c和c，删除c和c，生成新节点v，再将v插入集合C，（节点数减1）再寻找最小频度对应的节点；（直到最后只有一个节点时，Huffman树构造完成。）因此，最小堆结构是最佳选择。（上述过程重复n-1次）Huffman输入：n个字符的集合C=c1,cn及其频度 c1,cn 输出：C的Huffma