第四講貪心算法.ppt

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