Chapter13-貪婪算法.pptVIP

數(shù)據(jù)結(jié)構(gòu)與算法,2010年秋季,授課教師：方 芳 授課班級：115091-3、114091班,Chapter13 貪婪算法,內(nèi)容提要,13.1 示例問題提出 13.2 貪婪算法的思想 13.3 貪婪算法的應(yīng)用 貨箱裝船 拓?fù)渑判?單源最短路徑 最小耗費(fèi)生成樹,2、單源點(diǎn)最短路徑,1、源點(diǎn)：路徑上的第一個頂點(diǎn)；,2、終點(diǎn)：路徑上的最后一個頂點(diǎn)；,3、最短路徑：從源點(diǎn)到終點(diǎn)所經(jīng)過的邊上的權(quán)值之和為最小的路徑。,邊上權(quán)值非負(fù)情形的單源最短路徑問題,【問題描述】給定一個帶權(quán)有向圖D和源點(diǎn)v，求從v到D中其余各頂點(diǎn)的最短路徑單源點(diǎn)的最短路徑。,問題針對有向圖 G，每條邊都有一個非負(fù)的長度（耗費(fèi)）aij，路徑的長度即為此路徑所經(jīng)過的邊的長度之和。,例 給定如下帶權(quán)有向圖D，則從頂點(diǎn)1到其余頂點(diǎn)之間的最短路徑如下表所示：,單源最短路徑示例：源點(diǎn)1,1,1,1,1,1,3,3,4,2,3,4,5,0,2,3,4,6,迪杰斯特拉算法求得的每一條最短路徑必定只有兩種情況： 1）由源點(diǎn)直接到達(dá)終點(diǎn)， 2）是只經(jīng)過已經(jīng)求得最短路徑的頂點(diǎn)到達(dá)終點(diǎn),（1）窮舉法,求出從源點(diǎn)到各個終點(diǎn)的所有路徑，找出其中到各個終點(diǎn)的最短路徑。,（2）Dijkstar（迪杰斯特拉）算法,Dijkstar提出按各條最短路徑長度遞增的順序逐步產(chǎn)生最短路徑。,首先求出從源點(diǎn)v0到其余各頂點(diǎn)中長度最短的一條， 然后參照它求出長度次短的一條最短路徑， 依此類推，直到從源點(diǎn)v0到其余各頂點(diǎn)的最短路徑全部求出為止。,如何求從某一源點(diǎn)到各個終點(diǎn)的路徑 ?,分步法求最短路徑，每一步產(chǎn)生一個到達(dá)新的目的頂點(diǎn)的最短路徑；,Dijkstar算法的貪婪準(zhǔn)則,【貪婪準(zhǔn)則】 還未產(chǎn)生最短路徑的頂點(diǎn)中，選擇路徑長度最短的目的頂點(diǎn)按路徑長度順序產(chǎn)生最短路徑。,利用數(shù)組 p，前驅(qū)頂點(diǎn) pi給出從s到達(dá)i的路徑中頂點(diǎn)i前面的那個頂點(diǎn)。 從s到頂點(diǎn)i的路徑可反向創(chuàng)建：從i出發(fā)按照pi, ppi, pppi, 的順序，直到到達(dá)頂點(diǎn)s或0。,算法實(shí)現(xiàn)：最短路徑的存儲,p1:5 = 0,1,1,3,4。 i=5開始，則頂點(diǎn)序列為pi=4，p4=3，p3=1=s， 因此從1到5的路徑：為1-3-4-5。,輔助數(shù)組di：頂點(diǎn)當(dāng)前最短路徑長度,每個數(shù)組元素di中存放：從源點(diǎn)s到終點(diǎn)i的當(dāng)前最短路徑長度。,初始時，di=asi，即disti的值為鄰接矩陣a中第s行上各元素的值。,a=,輔助數(shù)組di的變化,對所有未找到最短路徑的頂點(diǎn)j，進(jìn)行判斷,修改dj ，使得 dj = di + aij,if（djdi + aij）經(jīng)過已經(jīng)求得最短路徑的頂點(diǎn)到達(dá)終點(diǎn),即dj = min dj, di + aij ,else 不修改 源點(diǎn)直接到達(dá)終點(diǎn),dj與di + aij的大小,L表,源點(diǎn)未到達(dá)頂點(diǎn)表 采用數(shù)據(jù)結(jié)構(gòu)： 無序鏈表 VS. 最小堆 初始值： 與源點(diǎn)鄰接的頂點(diǎn)鏈表 更新情況： 某個頂點(diǎn)j的dj發(fā)生變化，且不在L中，則加入到鏈表中,Dijkstar算法偽代碼,（1）初始化di=asi（1in) 對于鄰接于s的所有頂點(diǎn)i，置pi=s，對于其余的頂點(diǎn)pi=0; 對于pi 0的所有頂點(diǎn)建立L表； （2）若L為空，終止，否則轉(zhuǎn)至（3） （3）從L中刪除d值最小的頂點(diǎn)，標(biāo)識為i； （4）對于與i鄰接的所有還未到達(dá)的頂點(diǎn)j，更新dj值為mindj,di+aij；若dj發(fā)生了變化且j還未在L中，則置pj=i，并將j加入L，轉(zhuǎn)至（2）。,例,a=,Dijkstar算法（程序13-5）,template void AdjacencyWDigraph:ShortestPaths(int s,T d, int p) if (s n) throw OutOfBounds( ); Chain L; /未到達(dá)頂點(diǎn)鏈表 ChainIterator I; /鏈表遍歷器 / initialize d, p, and L for (int i = 1; i = n; i+) di = asi; if (di = NoEdge) pi = 0; else pi = s; L.Insert(0,i); ,a=,初始化d，p,初始化L,i=3,/ L表為空，表示所有頂點(diǎn)均找到路徑 while (!L.IsEmpty( ) / 在未到達(dá)頂點(diǎn)L表中，查找d值最小的頂點(diǎn) int *v = I.Initialize(L); int *w = I.Next( ); while (w) if (d*w d*v) v = w; w = I.Next( ); ,Dijkstar算法（程序13-5）,/ 頂點(diǎn)*v作為下一個源點(diǎn)，搜索與之關(guān)聯(lián)的頂點(diǎn)j / 若頂點(diǎn)j的d值不是最優(yōu)，則更新dj和pj int i = *v; L.Delete(*v); for (int j = 1; j di + aij) dj = di + aij; 更新dj為最優(yōu)值 if (!pj) L.Insert(0,j); pj = i; 更新其前驅(qū)頂點(diǎn) / End of while (!L.IsEmpty( ) ,L鏈表的變化 d的變化 L的變化 p的變化 初始值：5-3-2 0 1 1 0 1 Step1： i=3, 5-2， d4=3 4-5-2 p4=3 Step2： i=4, 5-2, d5=6 p5=4 Step3： i=2, 5 Step4： i=5, 空 0 1 1 3 4,反向輸出P,對于具有n個頂點(diǎn)和e條邊的帶權(quán)有向圖， 無論采用鄰接矩陣，還是鄰接鏈表，時間復(fù)雜度均為O(n2) 原因：必須至少對每一條邊檢查一次！ 鄰接矩陣僅能優(yōu)化最后一個循環(huán) O(e),Dijkstar算法復(fù)雜度分析,【問題描述】已知一個各邊權(quán)值均大于0的帶權(quán)有向圖，對每一對頂點(diǎn) vi vj，要求求出vi 與vj之間的最短路徑和最短路徑長度。,【解決方法一】：輪流以每一個頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次，即可求得每一對頂點(diǎn)之間的最短路徑，總的時間復(fù)雜度為O(n3)。,【思考】如何求所有頂點(diǎn)之間的最短路徑,【解決方法二】：Floyd（弗洛伊德）算法,【生成樹定義】已知G(V,E)是一個無向連通圖，E(G)為圖G的邊集，則從圖中任一頂點(diǎn)出發(fā)遍歷圖時，必定將E(G)分成兩個集合T(G)和B(G):,T(G)：遍歷圖G時所經(jīng)過的邊的集合；,B(G)：遍歷圖G時未經(jīng)過的邊的集合；,則G=(V,T)稱為G的一棵生成樹。,3、最小生成樹,（1）G是圖G的極小連通子圖，即G中有n個頂點(diǎn)，n-1條邊；,（2）無向連通圖的生成樹不是唯一的，對連通圖不同的遍歷，就得到不同的生成樹。,例,深度優(yōu)先生成樹,廣度優(yōu)先生成樹,生成樹的特點(diǎn),（1）深度優(yōu)先生成樹：由深度優(yōu)先搜索得到的；,（2）廣度優(yōu)先生成樹：由廣度優(yōu)先搜索得到的。,對于一個帶權(quán)的連通圖，如何找出一棵生成樹，使得各邊上的權(quán)值總和達(dá)到最小，是一個有實(shí)際意義的問題。,生成樹的類型,【構(gòu)造原則】,（2）盡可能選取權(quán)值小的邊，但不能構(gòu)成回路（環(huán)）；,（3）必須使用且僅使用n-1條邊，使n個頂點(diǎn)連通起來。,（1）必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造；,給定一個無向連通網(wǎng)G，在G的所有生成樹中，某一棵生成樹其n-1條邊上權(quán)值之和為最小，則這棵生成樹為最小生成樹。,WG(Tmin)=minWG(T)|TST,最小耗費(fèi)（代價）生成樹及構(gòu)造原則,最小耗費(fèi)生成樹構(gòu)造方法,三種方法： Kruskal方法：克魯斯卡爾 Prim方法：普里姆 Sollin方法,選擇n-1條邊； 【貪婪準(zhǔn)則】 從剩下的邊中選擇一條不會產(chǎn)生環(huán)路的具有最小耗費(fèi)的邊加入已選擇的邊的集合中。,（1）Kruskal算法,【注意】加入邊不能產(chǎn)生環(huán)路，否則得不到生成樹 。,是一種按照網(wǎng)中邊的權(quán)值遞增的順序構(gòu)造最小生成樹的方法。,按權(quán)值遞增的次序選擇n-1條邊，每選一條邊，要判斷是否構(gòu)成回路。,（1）設(shè)無向圖連通網(wǎng)為G(V,E)，T為G的最小生成樹，初始時T=V,（此時T中有n個連通分量）；,（2）按照邊的權(quán)值遞增的順序，考察E(G)中的每條邊e，判斷加入e后，T中的邊是否構(gòu)成回路；,（3）依次判斷E(G)中的每條邊，直到T的連通分量為1時（或T的邊數(shù)為n-1時），此連通分量T即為G的一棵最小生成樹。,Kruskal算法思想,G,T,V(G)=1,2,3,4,5,6,E(G)= (1,2),(1,5),(1,6),(2,3), (2,4),(2,6),(3,4),(4,5),(4,6),(5,6),V(T)=1,2,3,4,5,6,E(T)= (2,3),(3,4),(1,5), (2,6),(1,2) ,Kruskal算法示例,（1）V(T) V(G)，置E(T)的初態(tài)為空集；,（2）while（E(T)中的邊數(shù)n） 從E(G)中選取權(quán)值最小的邊e，并從E(G)中刪去它； if（邊e加入E(T)中不構(gòu)成回路） 將邊e加入E(T)中； 邊數(shù)加1； ,Kruskal算法偽碼描述,初始用最小堆存放E中所有的邊，構(gòu)造過程中存放剩余的邊； 用并查集的運(yùn)算，檢查依附于一條邊的兩個頂點(diǎn)是否同在一個連通分量上（即是否同在并查集的一個子集合上） 是，則舍去這條邊； 否，將此邊加入最小生成樹T中，并將這兩個頂點(diǎn)放在同一個連通分量上； 直到形成一個連通分量為止。,利用最小堆和并查集實(shí)現(xiàn)Kruskal算法,補(bǔ)充：集合的樹形表示方法,假設(shè)集合S由若干個元素組成，可以按照某一規(guī)則把集合S分成若干個互不相交的子集合，稱之為等價分類。,例如，集合S=1,2,3,4,5,6,7,8,9,10，可以分成如下三個不相交的子集合：,S1=1,2,4,7 S2=3,5,8 S3=6,9,10,同樣，也可以將兩個集合合并成一個新的集合： S1S2=1，2，3，4，5，7，8,P268 8.10.2 在線等價類,用一棵樹表示一個集合，樹中的一個結(jié)點(diǎn)表示集合中的一個元素，樹結(jié)構(gòu)采用雙親表示法。,S1=1,2,4,7,S2=3,5,8,S3=6,9,10,求集合的并集：把一個集合的樹根結(jié)點(diǎn)作為另一個集合的樹根結(jié)點(diǎn)的孩子結(jié)點(diǎn)。,查找某個元素所在的集合，可以沿著該元素的雙親域向上查，當(dāng)查到某個元素的雙親域值為0時，該元素就是所查元素所屬的樹根結(jié)點(diǎn)。,并查集支持以下三種操作： Union (Root1, Root2) /并操作，把子集合Root2并入Root1 Find (x) /搜索單元素x所在的集合，并返回該集合的名字 UnionFind (s) /構(gòu)造函數(shù)，將并查集中s個元素初始化為只有一個單元素的子集合。,對于并查集來說，每個集合用一棵樹表示。集合元素的編號從1到 n。其中 n 是最大元素個數(shù)。,并查集 (Union-Find Sets),class UnionFind public: UnionFind(int Size = 10); UnionFind() delete parent; delete root; void Union(int, int); int Find(int); private: int *parent; 保存該樹中節(jié)點(diǎn)的個數(shù) bool *root; 根節(jié)點(diǎn)標(biāo)志 ;,并查集類的定義,UnionFind:UnionFind(int n) /初始化，一個元素作為一類或一棵樹 root = new booln+1; parent = new intn+1; for (int e = 1; e = n; e+) parente = 1; 節(jié)點(diǎn)個數(shù)為1 roote = true; 為根節(jié)點(diǎn) ,并查集類的初始化,void UnionFind:Union(int i, int j) if (parenti parentj) 將i作為j的子樹 parentj += parenti; rooti = false; parenti = j; else 將j作為i的子樹 parenti += parentj; rootj = false; parentj = i; ,并查集類：合并算法,重量規(guī)則P271,int UnionFind:Find(int e) int j = e; while (!rootj) j = parentj; 找到包含e的樹的根 int f = e; while (f != j) int pf = parentf; parentf = j; f = pf; return j; ,并查集類：查找算法,路徑壓縮P273,一旦查找成功，修改從查找節(jié)點(diǎn)到根的 路徑上所有節(jié)點(diǎn)的指針，直接指向根節(jié)點(diǎn),邊節(jié)點(diǎn)定義,template class EdgeNode friend ostream ,遍歷器定義13-7: 注意派生體系,virtual,定義遍歷器,實(shí)現(xiàn)遍歷器,Kruskal實(shí)現(xiàn),使用入口,Kruskal算法（程序13-6）,template t0n-2中返回最小生成樹 bool UNetwork:Kruskal(EdgeNode t ) int n = Vertices( ); int e = Edges( ); / 建立網(wǎng)絡(luò)邊節(jié)點(diǎn)數(shù)組 InitializePos( ); EdgeNode *E = new EdgeNode e+1; int k = 0; / cursor for E,for (int i = 1; i H(1); H.Initialize(E, e, e);,按照頂點(diǎn)編號，依次找到與該頂點(diǎn)鄰接的邊，并記錄到邊節(jié)點(diǎn)數(shù)組中，形如(i, j, c),UnionFind U(n); k = 0; while (e ,時間復(fù)雜度 O(n+eloge),每次選擇多條邊來創(chuàng)建最小生成樹， 選擇下一條邊的【貪婪準(zhǔn)則】： 從剩下的邊中選擇一條耗費(fèi)最小的邊，并且它的加入應(yīng)使所有入選的邊仍是一棵樹。 【注意】可從任一頂點(diǎn)開始，往 T中加入一條代價最小的邊(u,v)，使T與(u,v)的并仍是一棵樹。,（2）Prim算法,已知連通網(wǎng)G=(V,E)，設(shè)其最小生成樹G=(U,T),（1）初始時，令集合U=u0（假設(shè)構(gòu)造最小生成樹時，從頂點(diǎn)u0出發(fā)）；集合T=；,（2）從所有uU，vV-U的邊中，選取具有最小權(quán)值的邊（u,v），將頂點(diǎn)v加入集合U中，將邊(u,v)加入集合T中；,（3）重復(fù)（2），直到U=V時，最小生成樹構(gòu)造完畢，集合T中包含了最小生成樹的所有邊。,Prim算法思想,6,1,3,2,4,5,Prim算法構(gòu)造最小生成樹示例,U 1 ，V-U2, 3, 4, 5, 6,U 1,5 ，V-U2, 3, 4, 6,U 1,5,2，V-U3, 4, 6,U 1,5,2,3，V-U4, 6,U 1,5,2,3,4，V-U6,U 1,5,2,3,4,6，V-U空,時間復(fù)雜度O(n2),Prim算法偽代碼,/假設(shè)網(wǎng)絡(luò)中至少具有一個頂點(diǎn) 設(shè)T為所選擇的邊的集合，初始化T= 設(shè)TV為已在樹中的頂點(diǎn)的集合，置TV=1 令E為網(wǎng)絡(luò)中邊的集合 while（E!= )&(|T|!=n-1) 令(u,v)為最小代價邊，其中uTV，v V-TV if（沒有這種邊）break E=E-(u-v) /從E中刪除此邊 在T中加入邊（u,v） if(|T|=n-1)T是一棵最小生成樹 else 網(wǎng)絡(luò)是不連通的，沒有最小生成樹,Kruskal VS. Prim,Kruskal算法的時間復(fù)雜度：O(n+eloge) Prim算法的時間復(fù)雜度：O(n2) 結(jié)論： Kruskal算法與網(wǎng)中邊數(shù)相關(guān)，適合求邊稀疏的網(wǎng)的最小生成樹 Prim算法只與網(wǎng)中節(jié)點(diǎn)數(shù)相關(guān)，適合求邊稠密的網(wǎng)的最小生成樹,（3）Solin算法：了解,算法每步選擇若干條邊，在每步開始時，所選擇的邊及圖中的 n個頂點(diǎn)形成一個生成樹的森林， 選擇邊的【貪婪準(zhǔn)則】： 在每一步中為森林中的每棵樹選擇一條邊，這條邊剛好有一個頂點(diǎn)在樹中且邊的代價最小。 【注意】一個森林中的兩棵樹可以選擇同一條邊，因此必須多次復(fù)制同一條邊。,貪婪算法總結(jié),用于求解最優(yōu)化問題； 選擇可行性檢查解答檢查； 選擇過程總是選擇局部的最佳者； 由空集合開始，循序加入新解來得到最后的答案； 不保證一定會得到最佳解，需要證明。,貪婪算法的思想 貪婪算法的應(yīng)用 拓?fù)渑判?單源點(diǎn)最短路徑 最小生成樹,本章小結(jié),課后練習(xí),Page432：練習(xí)27 提高篇：搜集資料，實(shí)現(xiàn)Prim算法,實(shí)習(xí)六 貪婪算法應(yīng)用,【問題描述】 設(shè)計(jì)一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。,【基本要求】 （1）設(shè)計(jì)學(xué)校的校園平面圖，所含景點(diǎn)不少于10個。圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。 （2）為來訪客人提供圖中任意景點(diǎn)相關(guān)信息查詢； （3）為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€景點(diǎn)之間的一條最短的簡單路徑。,【測試數(shù)據(jù)】 根據(jù)實(shí)際情況指定。,【實(shí)現(xiàn)提示】 一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個無向網(wǎng)（帶權(quán)無向圖）。頂點(diǎn)和邊均含有相關(guān)信息。,弗洛伊德算法仍然使用前面定義的圖的鄰接矩陣Edgenn來存儲帶權(quán)有向圖。,設(shè)置一個nn的矩陣A(k)，其中除對角線的元素都等于0外，其它元素a(k)ij表示頂點(diǎn)vi到頂點(diǎn)vj的路徑長度，k表示運(yùn)算步驟。,算法的基本思想,開始時，以任意兩個頂點(diǎn)之間的有向邊的權(quán)值作為路徑長度，沒有有向邊時，路徑長度為；,多源點(diǎn)最短路徑算法: Floyd（弗洛伊德）,以后逐步嘗試在原路徑中加入其它頂點(diǎn)作為中間頂點(diǎn)，如果增加中間頂點(diǎn)后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑，修改矩陣元素。具體做法為：,第一步，讓所有邊上加入中間頂點(diǎn)v0，取Aij與Ai0+A0j中較小的值作Aij的值，完成后得到A(1)，,第二步，讓所有邊上加入中間頂點(diǎn)v1，取Aij與Ai1+A1j中較小的值，完成后得到A(2)，如此進(jìn)行下去，當(dāng)?shù)趎步完成后，得到A(n)，A(n)即為我們所求結(jié)果