




版權(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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 商業(yè)教育中激發(fā)學(xué)生的自主創(chuàng)新精神的教育心理學(xué)方法
- 智慧城市公共設(shè)施的節(jié)水型智能水網(wǎng)建設(shè)
- 醫(yī)療信息培訓(xùn)中的互動游戲化教學(xué)方法研究
- 整合技術(shù)于教學(xué)提升教育質(zhì)量的關(guān)鍵
- 以科技教育為導(dǎo)向的教育政策的反思及未來走向探索
- 教育數(shù)據(jù)挖掘技術(shù)助力教學(xué)質(zhì)量飛躍
- 基于數(shù)據(jù)的教學(xué)行為優(yōu)化及實(shí)踐探索
- 提升學(xué)習(xí)效果教育心理學(xué)的方法論
- 培訓(xùn)機(jī)構(gòu)怎樣做課件
- 抖音商戶IT設(shè)備借用歸還登記管理辦法
- 第三腰椎橫突綜合征學(xué)習(xí)課件
- 四川省成都石室天府2024屆化學(xué)高一下期末考試模擬試題含解析
- 配電柜體項(xiàng)目實(shí)施方案
- 飛機(jī)保險(xiǎn)附加擴(kuò)展保障范圍批單(航空責(zé)任)AVN52E
- 碘海醇外滲的預(yù)防與處理
- 醫(yī)療糾紛-醫(yī)療投訴登記表
- 人民醫(yī)院診斷證明書
- 燃?xì)庥邢薰咎胤N設(shè)備安全管理制度
- 2023年株洲農(nóng)村商業(yè)銀行股份有限公司招聘員工歷年試題(常考點(diǎn)甄選)含答案帶詳解-1
- 嘉峪關(guān)市招聘公辦幼兒園編制外聘用制教師考試真題2022
- 綜合日語說課講課公開課一等獎市優(yōu)質(zhì)課賽課獲獎?wù)n件
評論
0/150
提交評論