Ch-5贪心策略

《Ch-5贪心策略》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5章贪心策略5.1概述问题导入：找零钱问题有4种硬币，面值分别为2角5分、1角、5分和1分。现在要求以最少的硬币个数找给顾客6角3分。通常做法是：先拿2个2角5分的＋1个1角＋3个一分这种找法所拿出的硬币个数最少。这种算法其实就是贪心算法。（考虑动态规划法如何求解？）顾名思义，该算法总是做出在当前看来最好的选择，并且不从整体上考虑最优问题，所做出的每一步选择只是在某种意义上的局部最优选择，逐步扩大解的规模。当然，希望贪心算法得到的最终结果也是整体最优的（上面的解法得到的恰好是最优解）。但未必总是得到最优解。假如，面值有1角1分、5分和1分，要找给顾客1角

2、5分。如果还是使用上述贪心算法，得到的解是：1个1角1分＋4个1分。而实际上最优解是3个5分。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解，例如：单源最短路径问题、最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心法的难点在于它的正确性证明。5.1单源最短路径问题G=(V,E)是一个有向图，每条边上有一个非负整数表示长度值，其中有一个顶点称为源节点。所谓的单源最短路径问题就是：求解该源节点到所有任一节点的最短路径的长度。不失一般性，假设V={1,2,3,...,n}并且s=1。

3、那么该问题可以使用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]最小顶点y∈Y，并将其移动到X中。2)若y被从Y移动到X中，Y中每个和y相邻的顶点w的λ[w]都要更新(表示经由y到w的一条更短的路径被发现)415139

4、453121∞∞∞1210123456415139453121∞∞4101012345641513945312117134810123456415139453121171348101234564151394531211917481012345619415139453121134810123456Dijkstra算法1.X={1};Y←V-{1};λ[1]←02.fory←2ton3.ify相邻于1thenλ[y]←length[1,y]//Q(n)4.elseλ[y]←∞//O(n)5.endif6.endfor7.forj←1ton-18.令y∈Y,使得

5、λ[y]为最小的//∑(n-i){i=1,…,n-1}=Q(n2)9.X←X∪{y}//Q(n)10.Y←Y-{y}//Q(n)11.for每条边(y,w)//每条边恰好检查一次，Q(m),m=

6、E

7、12.ifw∈Yandλ[y]+length[y,w]<λ[w]then13.λ[w]←λ[y]+length[y,w]//Q(m)1.endif2.endfor3.endfor算法的时间复杂度Q(n)+O(n)+Q(n2)+Q(n)+Q(n)+Q(m)+Q(m)=Q(m+n2)对于任意一个顶点v∈V,假如我们使用δ[v]表示源顶点到顶点v的最短路径的长度，可

8、以证明,上述的贪心法结束后有λ[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→[]→[]→

9、…→[]→[x]→y(A)或π：1→[]→[]→…→[x]→[]…→y(B)对于情形(A)，λ[y]≤λ[x]+length[x,y]//算法要求=δ[x]+length(x,y)//归纳假设=δ[y]//π是最短路径对于情形(B)，我们将x之后的顶点不妨称之为w(w∈Y)，即：1→[]→[]→…→[x]→[w]…→y(B)于是有：λ[y]≤λ[w]//由于y在w之前离开Y≤λ[x]+length(x,w)//算法要求，原因同(A)=δ[x]+length(x,w)//归纳假设=δ[w]//因为π是最短路径≤δ[y]//因为π是最短路径综合(A)(B)情况

10、，总是有λ[y]≤δ[y].我们已经说了，δ[y]是最短路径了，因