第四講貪心算法.ppt_第1頁
第四講貪心算法.ppt_第2頁
第四講貪心算法.ppt_第3頁
第四講貪心算法.ppt_第4頁
第四講貪心算法.ppt_第5頁
已閱讀5頁,還剩10頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、第四講 貪心算法,組網(wǎng)問題,打算把一組計(jì)算機(jī)通過連接所選的計(jì)算機(jī)對組建成一個(gè)網(wǎng)絡(luò)。每條鏈與一個(gè)維護(hù)成本相聯(lián)系。,圖的形成: 節(jié)點(diǎn) 計(jì)算機(jī) 邊 鏈 邊權(quán) 維護(hù)成本,最便宜的網(wǎng)絡(luò)是什么?,解決方案: (i) 必須連接所有節(jié)點(diǎn) (ii) 不能包含圈,因?yàn)檫@種情況下可能有更便宜的網(wǎng)絡(luò)。,斷言刪除一個(gè)圈不會斷開一個(gè)圖。,因此答案是樹(連通且無圈),樹,一個(gè)連通且無圈的無向圖稱作樹,一棵樹有多少邊?,一棵有n個(gè)節(jié)點(diǎn)的樹有n-1條邊,樹的性質(zhì)-1,斷言: 一棵有n個(gè)節(jié)點(diǎn)的數(shù)有 n-1 條邊,為了理解這點(diǎn),一個(gè)時(shí)刻建樹的一條邊.,開始時(shí)刻: n 節(jié)點(diǎn), 無邊 n 連通分量,當(dāng)添加一條邊 e 時(shí): (i) e的

2、端點(diǎn)必須在不同的分量中 (否則產(chǎn) 生一個(gè)圈) (ii) 添加 e合并二個(gè)連通分量 (iii)連通分量數(shù)減1,在結(jié)束時(shí)刻: 一個(gè)連通分量,因此: 按照這種方法,n-1 肯定被添加。,樹的性質(zhì)-2,每個(gè)有|V|-1條邊的圖是樹嗎?,斷言: 任何連通無向圖,如果|E| = |V| - 1 則必然是樹。,證明:假設(shè) G 是連通且無向的圖, |E| = |V|-1.,在G上運(yùn)行下列過程: while it has a cycle: remove a cycle edge,結(jié)果: G = (V, E) where EE。G 連通且無圈: 因此是棵樹。,由于 G 是棵樹,因此 |E| = |V|-1.,這樣

3、 E = E, 因此沒有邊被移去,從而 G 開始就是棵樹。,可以通過數(shù)一棵連通圖有多少條邊來判斷圖是否是樹。,組 網(wǎng),打算把一組計(jì)算機(jī)通過連接所選的計(jì)算機(jī)對組建成一個(gè)網(wǎng)絡(luò)。每條鏈與一個(gè)維護(hù)成本相聯(lián)系。,最便宜的網(wǎng)絡(luò)是什么?,最小生成樹 (MST),輸入: 圖 G = (V,E); 邊的權(quán) we,輸出: 樹 T = (V, E), E E,目標(biāo): 最小化,最小生成樹的數(shù)量是指數(shù)級: 因此不能采用每棵樹都去試的方法。,而是采用貪心算法: 一個(gè)時(shí)刻添一條樹邊.,假設(shè)已經(jīng)選取了一些邊 X E, 目前是OK (即. X 是某個(gè)MST的一部分). 下一步添加哪條邊?,割的性質(zhì),斷言: 設(shè) XE 是圖G =

4、 (V,E)的某個(gè)最小生成樹T 的一部分。,選取一個(gè)節(jié)點(diǎn)子集 SV 使得 X 在S 和 V-S之間無邊。設(shè) e是S 和 V-S之間最輕的邊。,那么 Xe 是某個(gè)MST T的一部分,證明: 如果 e 在 T中, 結(jié)論自然成立。因此假設(shè)不在。,添加 e 到 T; 這產(chǎn)生唯一的圈 C。這個(gè)圈有另外一條邊跨 S和V-S; 稱它為e.,T = T + e e 是連通的。它有|V|-1條邊,因此,它是棵樹。,cost(T) = cost(T) + w(e) w(e) cost(T) 因此 T 也是一棵 MST, 且包含 X e.,一般MST算法,X = / edges picked so far repe

5、at until |X| = |V|-1: pick a set S V such that X has no edges between S and V-S let e be the lightest edge between S and V-S X = Xe,Kruskal算法,X = for all edges e in order of increasing weight: if adding e to X does not create a cycle: X = X e,為什么這是正確的?,Kruskal算法,procedure kruskal(G,w) input: graph G

6、 = (V,E); edge weights we output: X contains the edges of an MST X = for all nodes u: makeset(u) for edges (u,v) in order of increasing weight: if find(u) find(v): X = X (u,v) union(u,v),X = for all e in order of increasing we: if e does not create a cycle in X: add e to X,起初每個(gè)節(jié)點(diǎn)自身是個(gè)連通分量。 當(dāng)添加一條邊(u,v

7、)時(shí), u,v的連通分量合并,需要一種數(shù)據(jù)結(jié)構(gòu)來維護(hù)不相交集合。,操作: makeset(x) 形成一個(gè)僅僅含x的集合。 find(x) x屬于哪個(gè)集合? union(x,y) 合并包含x和y的集合。,時(shí)間: O(E log E) + (V-1) x union + 2E x find,Union-find數(shù)據(jù)結(jié)構(gòu),procedure makeset(x) px = x rankx = 0 procedure find(x) while x px: x = px return x,操作: makeset(x) 形成一個(gè)僅僅含x的集合。 find(x) X屬于哪個(gè)集合? union(x,y) 合

8、并包含x和y的集合。,每個(gè)集合存儲為一個(gè)有向樹。 如,二個(gè)集合 b,e 和 a,c,d,f,g,h:,父母指針: p(b) = e, p(g) = d, 等. 每個(gè)集合的根是它的代表(或名稱)。,每個(gè)節(jié)點(diǎn)有個(gè)數(shù)值 rank.,Union很容易:只須將根指針指向另一樹的根!,通過rank合并,對并操作的二種選擇:,選擇 1: root = e,選擇 2: root = h,每個(gè)節(jié)點(diǎn)有個(gè)數(shù)值 rank. 根節(jié)點(diǎn)的rank 和樹的高度相關(guān)。 讓rank較小的根指向rank較大的根。,例子,procedure makeset(x) px = x rankx = 0 procedure find(x)

9、while x px: x = px return x procedure union(x,y) rootx = find(x) rooty = find(y) if rootx = rooty: return if rankrootx rankrooty: prooty = rootx else: prootx = rooty if rankrootx = rankrooty: rankrooty+,makeset(a), makeset(b), ., makeset(g) union(c,h), union(g,d), union(a,f), union(b,e), union(g,c),

10、 union(c,a),注意: rankx = 根為 x 的子樹高度 根為 x 的子樹有 2rankx 個(gè)節(jié)點(diǎn)。,數(shù)據(jù)結(jié)構(gòu)性質(zhì),procedure makeset(x) px = x rankx = 0 procedure find(x) while x px: x = px return x procedure union(x,y) rootx = find(x) rooty = find(y) if rootx = rooty: return if rankrootx rankrooty: prooty = rootx else: prootx = rooty if rankrootx = rankrooty: rankrooty+,我們已經(jīng)知道: rankx = 根為 x 的子樹高度 根為 x 的子樹有2rankx 個(gè)節(jié)點(diǎn)。,因此,如果一共有n個(gè)元素,則每棵樹的高度最多是 log n. find, union 操作時(shí)間是 O(log n).,Krusk

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論