版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
第8章貪心算法8.1簡介例子例子:有4種硬幣,面值分別為2角5分、一角、五分和一分?,F(xiàn)在要求以最少的硬幣個數(shù)找給顧客6角三分。通常是:先拿兩個2角5分的+1個一角+3個一分這種找法所拿出的硬幣個數(shù)最少。這種算法其實就是貪心算法。顧名思義:該算法總是作出在當前看來最好的選擇,并且不從整體上考慮最優(yōu)問題,所作出的選擇只是在某種意義上的局部最優(yōu)解。上面的解法得到的恰好也是最優(yōu)解。因此,貪心方法的效率往往是很高的。假如,面值有一角一分、五分和一分,要找給顧客一角五分。如果還是使用上述貪心算法,得到的解是:一個一角一分+4個一分。而最優(yōu)解是3個5分。又例如:154135437121154135437121424261615353求節(jié)點1到節(jié)點6的最短路徑。用貪心法得19,而實際為17。顯然貪心算法不能對所有問題都能得到最優(yōu)解,但是對很多問題(包括很多著名的問題)都能產(chǎn)生整體最優(yōu)解。例如,我們今天要講的圖的單元最短路徑問題、最小生成樹問題。在有些情況下,算法不能得到整體最優(yōu)解,但是結果確是最優(yōu)解的很好近似。貪心選擇性質所謂貪心選擇性質是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇來達到,即貪心選擇來達到。這是貪心算法可行的第一個基本要素.也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別:動態(tài)規(guī)劃算法:每步所做出的選樣往往依賴于相關子問題的解,因而只有在解出相關子問題后.才能做出選擇。貪心算法:僅在當前狀態(tài)下做出最好選樣,即局部最優(yōu)選則。然后再去解做出這個選擇后產(chǎn)生的相應的子問題。貪心算法所做出的貪心選則可以依賴于以往做過的選則,但決不依賴于將來所做的選樣,也不依賴于子問題的解。動態(tài)規(guī)劃:是自底向上的方法解各子問題;貪心算法:是自頂向下的方法。每做出一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題.使用貪心法的難點在于:證明所設計的算法確實能夠正確解決所求解的問題。即對于一個具體的問題,必須證明每一步所做出的貪心選擇最終導致問題的整體最優(yōu)解。首先,考察問題的一個整體最優(yōu)解,并證明可修改這個最優(yōu)解,使其以貪心選擇開始。做出貪心選擇后.原問題簡化為規(guī)模更小的類似子問題。然后,用數(shù)學歸納法證明、通過每一步做貪心選擇.最終可得到問題的整體最優(yōu)解。其中,證明貪心選擇后的問題簡化為規(guī)模最小的類似子問題的關鍵在于利用該問題的最優(yōu)子結構性質。最優(yōu)子結構性質:當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時,稱此問題具有最優(yōu)子結構性質。貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結構性質,這是兩類算法的一個共同點。但是都具有最優(yōu)子結構的問題該選則貪心法還是動態(tài)規(guī)劃算法求解?是否能用動態(tài)規(guī)劃法的也能用貪心算法解?背包問題:給定n種物品和一個背包,物品i的體積為,價值為。已經(jīng)知道背包的承重量為C。假設是物體i被裝入背包的部分,;要求裝滿背包且背包內物體價值最大。max選擇方法:目標函數(shù)的值增加最快,而包載容量的消耗較慢的物體裝入包中。故優(yōu)先選擇價值體積比最大的物體裝入背包。背包與0-1背包的區(qū)別:結論0-1背包問題能用動態(tài)規(guī)劃法解,但不能用貪心法解。8.3單源最短路徑問題(狄斯奎諾Dijkstra’s算法)一、問題描述是一個有向圖,每條邊上有一個非負整數(shù)表示長度值,其中有一個頂點稱為源節(jié)點。所謂的單源最短路徑問題就是:求解該源節(jié)點到所有其它節(jié)點的最短路徑值。不失去一般性,我們假設并且=1。那么該問題可以使用Dijkstra’s算法來求解,該算法是一種貪心算法,并且能求得最優(yōu)解。二、算法思想開始時,我們將所有的頂點劃分為兩個集合。所有已經(jīng)計算好的頂點存放在中,中表示還沒有計算好的。中的每個頂點有一個對應的量,該值是從源頂點到(并且只經(jīng)由中的頂點)的最短路徑值。下面就是選擇一個最小頂點,并將其移動到中。一旦被從移動到中,中每個和相鄰的頂點的都要更新:表示經(jīng)由到的一條更短的路徑被發(fā)現(xiàn)了。對于任意一個頂點,假如我們使用表示源頂點到頂點的最短路徑,最后,我們可以證明上述的貪心法結束后有。三、算法DIJKSTRA輸入:含權有向圖G=(V,E),V={1,2,…n}輸出:G中頂點1到其他頂點的距離1.;;2.Fory←2tonIfy相鄰于1thenElse;Endif6.endfor7.forj←1ton-18.令,找到最小9.X←X∪{y}/*將從移動到中10Y←Y-{y}For每條邊{y,w}Ifw∈Yand+length[y,w]<then/*更新中和相鄰頂點的值endfor15.endfor四、舉例說明:(手工解該題目)算法的詳細實現(xiàn):有向圖用鄰接表來表示如圖假設每條邊是非負的X和Y集合用兩個向量來表示X[1..n],Y[1..n]。初始時X[1]=1,Y[1]=0.并且對于2<=i<=n,X[i]=0,Y[i]=1.因此,執(zhí)行的操作,就是X[y]=1,的操作就是,Y[y]=0。五、證明下面來證明,使用該DIJKSTRA方法得到的是最優(yōu)解,也就是。其中,表示源頂點到頂點的最短路徑;是從源頂點到(并且只經(jīng)由中的頂點)的最短路徑值。證明:歸納法顯然假設,當前將移動到中,并且在之前移動到中的任何一個頂點,都有。由于是有限的,也就是說必定存在一條從1到路徑,長度為(我們需要來證明)。那么這條路徑總可以寫作::1→[]→[]→。。?!鶾]→[]→[]→y在上述序列中,我們總是可以找到一個頂點,不妨稱之為(),使得之后的頂點均屬于,并且x是在y前最遲離開Y的頂點。所以有以下兩種情形:1→[]→[]→。。。→[]→[x]→y(A)或是1→[]→[]→。。。→[x]→[]…→y(B)√對于情形(A),算法要求歸納假設(A)是最短路徑√對于情形(B),我們將之后的頂點不妨稱之為,即:1→[]→[]→。。?!鶾x]→[w]…→y(B)于是有:由于在之前離開算法要求歸納假設因為是最短路徑因為是最短路徑我們已經(jīng)說了,是最短路徑了,因此。六、算法分析O(n2)或O(mn)稠圖的線性時間算法把算法的復雜度從O(n2)降到O(mlogn).基本思想是用最小堆數(shù)據(jù)結構來保持集合Y中的頂點,使Y組中離V-Y最近的頂點y可以在O(logn)時間內被選出.算法8.2SHORTESTPATH輸入:含權有向圖G=(V,E),V={1,2,…n}輸出:G中頂點1到其他頂點的距離.假設已有一個空堆H1.;;2.Fory←2tonIfy相鄰于1thenINSERT(H,y)Else;Endif6.endfor7.forj←1ton-18.Y←DELETEMIN(H)10Y←Y-{y}For對每個鄰接于y的頂點w∈YIf+length[y,w]<then/*更新中和相鄰頂點的值endifIfthenINSERT(H,w)ELSESIFTUP(H,H-1(w))endifendfor15.endfor其中,H-1(w)返回w再H中的位置,可以用一個數(shù)組實現(xiàn)。8.3最小生成樹設G=(V,E)是無向連通帶權圖,(V,T)是是G的一個子圖,并且T是一顆樹,那么稱(V,T)是G的生成樹。如果T的權之和是所有生成樹中最小的,那么則稱之為最小生成樹。我們假定G是連通的,如果G是非連通的,那么,可以對G的每個子圖應用求解最小生成樹的算法。網(wǎng)絡的最小生成樹在實際中有廣泛應用。例如,在設計通信網(wǎng)絡時,用圖的頂點表示城市,用邊(v,w)的權c[v][w]表示建立城市v和城市w之間的通信線路所需的費用,則最小生成樹就給出了建立通信網(wǎng)絡的最經(jīng)濟的方案。最小生成樹性質用貪心算法設計策略可以設計出構造最小生成樹的有效算法。本節(jié)介紹的構造最小生成樹的Prim算法和Kruskal算法都可以看作是應用貪心算法設計策略的例子。盡管這2個算法做貪心選擇的方式不同,它們都利用了下面的最小生成樹性質:設G=(V,E)是連通帶權圖,U是V的真子集。如果(u,v)E,且uU,vV-U,且在所有這樣的邊中,(u,v)的權c[u][v]最小,那么一定存在G的一棵最小生成樹,它以(u,v)為其中一條邊。這個性質有時也稱為MST性質。8.33Kruskal算法(克魯斯卡爾)一、基本思想Kruskal算法構造G的最小生成樹的基本思想是,首先將G的n個頂點看成n個孤立的連通分支。將所有的邊按權從小到大排序。然后從第一條邊開始,依邊權遞增的順序查看每一條邊,并按下述方法連接2個不同的連通分支:當查看到第k條邊(v,w)時,如果端點v和w分別是當前2個不同的連通分支T1和T2中的頂點時,就用邊(v,w)將T1和T2連接成一個連通分支,然后繼續(xù)查看第k+1條邊;如果端點v和w在當前的同一個連通分支中,就直接再查看第k+1條邊。這個過程一直進行到只剩下一個連通分支時為止。例如,對前面的連通帶權圖,按Kruskal算法順序得到的最小生成樹上的邊如下圖所示。二、KRUSKAL算法輸入:具有n個頂點的帶權連通無向圖輸出:的最小生成樹以非降序的方式對中各條邊的權進行排序foreachMAKESET();endforwhilelet為中的下一條邊ifthentoendifendwhile關于集合的一些基本運算可用于實現(xiàn)Kruskal算法。按權的遞增順序查看等價于對優(yōu)先隊列執(zhí)行removeMin運算。可以用堆實現(xiàn)這個優(yōu)先隊列。對一個由連通分支組成的集合不斷進行修改,需要用到抽象數(shù)據(jù)類型并查集UnionFind所支持的基本運算。三、Kruskal算法的正確性證明:我們只要證明,使用Kruskal算法過程中,每次循環(huán)所得到的(從空集增至最小生成樹)總是圖G的最小生成樹的子集即可。使用歸納法+反證法。G總是具有一個最小生成樹,不妨記為。當前要加入的邊為。包含的那顆子樹的所有頂點用表示。假設在加入之前得到的均滿足,其中。令,下面我們要證明也是圖G的最小生成樹的子集。依據(jù)歸納假設,有。如果:顯然有如果:那么必將構成一個環(huán),也就是不再是樹。我們知道中必定包含這樣一條邊,且,且cost()cost()。否則,將被選擇加入。下面我們來證明就是。定義,那么也是圖的一個生成樹,并且cost()<cost()。也就是說,是最小生成樹,那么不是最小生成樹。矛盾。所以必定是屬于的。也就必定有。證明完畢。四、時間復雜度:當圖的邊數(shù)為e時,Kruskal算法所需的計算時間是。8.4Prim算法(普里姆)一、基本思想設G=(V,E)是連通帶權圖,V={1,2,…,n},。構造G的最小生成樹.Prim算法的基本思想:首先置S={1},然后,只要S是V的真子集,就作如下的貪心選擇:選取滿足條件iS,jV-S,且c[i][j]最小的邊,將頂點j添加到S中。這個過程一直進行到S=V時為止。在這個過程中選取到的所有邊恰好構成G的一棵最小生成樹。利用最小生成樹性質和數(shù)學歸納法容易證明,上述算法中的邊集合T始終包含G的某棵最小生成樹中的邊。因此,在算法結束時,T中的所有邊構成G的一棵最小生成樹。例如,對于右圖中的帶權圖,按Prim算法選取邊的過程如下頁圖所示二、算法算法8.4PRIM輸入:含權有向圖G=(V,E),V={1,2,…n}輸出:由G生成的最小耗費生成樹T組成的邊的集合1.T←{};X←{1};Y←V-{1}2.Fory←2tonIfy相鄰于1thenN[y]←1C[y]←c[1,y]Else;Endif8.endfor9.forj←1ton-1{尋找n-1條邊}10.令,找到最小11.T←T∪{(y,N[y]}{將邊y,N[y]加入T}12.X←X∪{y}/*將從移動到中13Y←Y∪{y}For每個相鄰于y的頂點w∈YIfc[y,w]<C[w]thenN[w]←yC[w]←c[y,w]endif19.endfor20.endfor在上述Prim算法中,還應當考慮如何有效地找出滿足條件iS,jV-S,且權c[i][j]最小的邊(i,j)。三、算法分析用這個辦法實現(xiàn)的Prim算法所需的計算時間為當圖的邊數(shù)為e時,Kruskal算法所需的計算時間是。當時,Kruskal算法比Prim算法差,但當時,Kruskal算法卻比Prim算法好得多。8.6哈夫曼編碼哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%~90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0,1串表示各字符的最優(yōu)表示方式。哈夫曼編碼思想:給出現(xiàn)頻率高的字符較短的編碼,出現(xiàn)頻率較低的字符以較長的編碼,可以大大縮短總碼長。前綴碼對每一個字符規(guī)定一個0,1串作為其代碼,并要求任一字符的代碼都不是其他字符代碼的前綴。這種編碼稱為前綴碼。例:a:10,b:101存在二義性編碼的前綴性質可以使譯碼方法非常簡單。表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹,即樹中任一結點都有2個兒子結點。平均碼長定義為:使平均碼長達到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。構造哈夫曼編碼哈夫曼提出構造最優(yōu)前綴碼的貪心算法,由此產(chǎn)生的編碼方案稱為哈夫曼編碼。哈夫曼算法以自底向上的方式構造表示最優(yōu)前綴碼的二
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 測繪管理與法律法規(guī)-注冊測繪師《測繪管理與法律法規(guī)》模擬試卷4
- 科技輔助醫(yī)療家屬如何利用科技幫助血液病患者
- 課題申報參考:老齡化與人口均衡發(fā)展研究
- 課題申報參考:空間耦合視角下城市藍綠景觀對居民情感的協(xié)同提升機制與調控對策
- 科技農(nóng)業(yè)裝備升級與教育同步發(fā)展
- 小腸健康管理在醫(yī)療科技發(fā)展中的應用
- 教育行業(yè)多元化發(fā)展下的少兒英語培訓招生活動挑戰(zhàn)與機遇
- 2024年H-系列卷材涂料項目資金申請報告
- 小學科學項目式學習的教學策略研究
- 科技在改善孕婦生活質量中的應用研究
- 廣東省佛山市2025屆高三高中教學質量檢測 (一)化學試題(含答案)
- 人教版【初中數(shù)學】知識點總結-全面+九年級上冊數(shù)學全冊教案
- 2024-2025學年人教版七年級英語上冊各單元重點句子
- 2025新人教版英語七年級下單詞表
- 公司結算資金管理制度
- 2024年小學語文教師基本功測試卷(有答案)
- 未成年入職免責協(xié)議書
- 項目可行性研究報告評估咨詢管理服務方案1
- 5歲幼兒數(shù)學練習題
- 2024年全國體育單招英語考卷和答案
- 食品安全管理制度可打印【7】
評論
0/150
提交評論