資源描述：
《Ch-5貪心策略》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第5章貪心策略5.1概述問題導(dǎo)入：找零錢問題有4種硬幣，面值分別為2角5分、1角、5分和1分?，F(xiàn)在要求以最少的硬幣個(gè)數(shù)找給顧客6角3分。通常做法是：先拿2個(gè)2角5分的＋1個(gè)1角＋3個(gè)一分這種找法所拿出的硬幣個(gè)數(shù)最少。這種算法其實(shí)就是貪心算法。（考慮動(dòng)態(tài)規(guī)劃法如何求解？）顧名思義，該算法總是做出在當(dāng)前看來最好的選擇，并且不從整體上考慮最優(yōu)問題，所做出的每一步選擇只是在某種意義上的局部最優(yōu)選擇，逐步擴(kuò)大解的規(guī)模。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的（上面的解法得到的恰好是最優(yōu)解）。但未必總是得到最優(yōu)解。假如，面值有1角1分、5分和1分，要找給顧客1角
2、5分。如果還是使用上述貪心算法，得到的解是：1個(gè)1角1分＋4個(gè)1分。而實(shí)際上最優(yōu)解是3個(gè)5分。雖然貪心算法不能對(duì)所有問題都得到整體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解，例如：?jiǎn)卧醋疃搪窂絾栴}、最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。貪心法的難點(diǎn)在于它的正確性證明。5.1單源最短路徑問題G=(V,E)是一個(gè)有向圖，每條邊上有一個(gè)非負(fù)整數(shù)表示長(zhǎng)度值，其中有一個(gè)頂點(diǎn)稱為源節(jié)點(diǎn)。所謂的單源最短路徑問題就是：求解該源節(jié)點(diǎn)到所有任一節(jié)點(diǎn)的最短路徑的長(zhǎng)度。不失一般性，假設(shè)V={1,2,3,...,n}并且s=1。
3、那么該問題可以使用Dijkstra算法來求解，該算法是一種貪心算法，并且能求得最優(yōu)解。開始時(shí)，我們將所有的頂點(diǎn)劃分為兩個(gè)集合X={1},Y={2,3,4,..,n}。所有已經(jīng)計(jì)算好的頂點(diǎn)存放在X中，Y中表示還沒有計(jì)算好的。Y中的每個(gè)頂點(diǎn)y有一個(gè)對(duì)應(yīng)的量λ[y]，該值是從源頂點(diǎn)到y(tǒng)(并且只經(jīng)由X中的頂點(diǎn))的最短路徑的長(zhǎng)度。Dijkstra算法假設(shè)V={1,2,3,...,n}并且s=1。1)選擇一個(gè)λ[y]最小頂點(diǎn)y∈Y，并將其移動(dòng)到X中。2)若y被從Y移動(dòng)到X中，Y中每個(gè)和y相鄰的頂點(diǎn)w的λ[w]都要更新(表示經(jīng)由y到w的一條更短的路徑被發(fā)現(xiàn))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算法的時(shí)間復(fù)雜度Q(n)+O(n)+Q(n2)+Q(n)+Q(n)+Q(m)+Q(m)=Q(m+n2)對(duì)于任意一個(gè)頂點(diǎn)v∈V,假如我們使用δ[v]表示源頂點(diǎn)到頂點(diǎn)v的最短路徑的長(zhǎng)度，可
8、以證明,上述的貪心法結(jié)束后有λ[v]=δ[v]下面來證明使用該方法得到的是最優(yōu)解，也就是λ[y]=δ[y]。證明:歸納法1)顯然λ[1]=δ[1]=02)假設(shè)當(dāng)前將y移動(dòng)到X中，并且在y之前移動(dòng)到X中的任何一個(gè)頂點(diǎn)c，都有λ[c]=δ[c]。（第二數(shù)學(xué)歸納法）由于λ[y]是有限的，也就是說必定存在一條從1到y(tǒng)路徑，長(zhǎng)度為λ[y]（我們需要來證明λ[y]=δ[y]）。那么這條路徑總可以寫作：1→[]→[]→…→[]→[]→[]→y在上述序列中，我們總是可以找到一個(gè)頂點(diǎn)，不妨稱之為x(x∈X),使得x之后的頂點(diǎn)均屬于Y。所以有以下兩種情形：π：1→[]→[]→
9、…→[]→[x]→y(A)或π：1→[]→[]→…→[x]→[]…→y(B)對(duì)于情形(A)，λ[y]≤λ[x]+length[x,y]//算法要求=δ[x]+length(x,y)//歸納假設(shè)=δ[y]//π是最短路徑對(duì)于情形(B)，我們將x之后的頂點(diǎn)不妨稱之為w(w∈Y)，即：1→[]→[]→…→[x]→[w]…→y(B)于是有：λ[y]≤λ[w]//由于y在w之前離開Y≤λ[x]+length(x,w)//算法要求，原因同(A)=δ[x]+length(x,w)//歸納假設(shè)=δ[w]//因?yàn)棣惺亲疃搪窂健堞腫y]//因?yàn)棣惺亲疃搪窂骄C合(A)(B)情況
10、，總是有λ[y]≤δ[y].我們已經(jīng)說了，δ[y]是最短路徑了，因
