采用步步逼近的方式構(gòu)造問題的解，其下一步的選擇總是在當(dāng)前看來收效最快和效果最明顯的那個。
使用前提： 驗(yàn)證貪心模式的有效性
最小生成樹（minimum spanning tree）
輸入：無向圖G=(V, E); 邊權(quán)重w(e)
輸出：樹T=(V, E')旬渠，
其中迫吐， 使得權(quán)重 = \sum_{e \in E'} w_e)
樹的性質(zhì)
- 具有n個節(jié)點(diǎn)的樹的邊數(shù)為n-1
- 一個無向圖是樹讯检，當(dāng)且僅當(dāng)任意兩個節(jié)點(diǎn)間僅存在唯一路徑
Kruskal算法
不斷地重復(fù)地選擇未被選中的邊中權(quán)重最輕而且不會形成環(huán)的一條。
procudure kruskal
for all u in V:
makeset(u)
sort the edges E by weight
for all edges {u, v} in E, in increasing order of weight:
if find(u) != find(v)
add edge {u,v} to X
union(u, v)
- makeset(x): 創(chuàng)建一個僅包含x的獨(dú)立集合
- find(x): x屬于哪個集合挽拂？
- union(x, y): 合并包含x和y的集合
共需要|V|次makeset + 2|E|次find + |V|-1次union操作
find操作不一定成功觸發(fā)union操作惭每，因此最壞情況下會需要2|E|次
數(shù)據(jù)結(jié)構(gòu)：有向樹
集合中的頂點(diǎn)對應(yīng)樹的節(jié)點(diǎn)，每個節(jié)點(diǎn)包含一個父指針亏栈，一級級指向樹根台腥。樹根的父指針指向該元素自身。
node
- p //父節(jié)點(diǎn)指針
- rank //該節(jié)點(diǎn)下懸掛的子樹高度
- 方案一
合并時讓較低的樹的根指向較高的樹的根（基于等級的合并）
procedure makeset(x)
p(x) = x
rank(x) = 0
procedure find(x)
while(x != p(x))
x = p(x)
return x
procedure union(x, y)
rx = find(x), ry = find(y)
if rx == ry return
if rank(rx) > rank(ry)
p(ry) = rx
else if rank(rx) == rank(ry)
p(rx) = ry
rank(ry) += 1
else
p(rx) = ry
- 方案二
路徑壓縮: 循著一系列的父指針最終找到樹根后仑扑，改變所有這些父指針的目標(biāo)览爵，使其直接指向樹根
procedure find(x)
while(x != p(x))
p(x) = find(p(x))
return x
find中rank未進(jìn)行更新，此時rank的含義無法解釋為子樹的高度镇饮。
此時有向樹的高度不會超過2蜓竹。
- 方案三
我們可以發(fā)現(xiàn)find和union操作均只關(guān)心樹的頂層，是否可以直接使用樹高為2的有向樹呢储藐？并在union()操作中俱济，對于兩個樹高為2的有向樹，進(jìn)行其中一棵的壓縮钙勃。
但仔細(xì)分析可以得出蛛碌，此方案與方案二本質(zhì)相同，僅將find()操作總共所做的工作轉(zhuǎn)移到union()操作中辖源。
| 方案序號 | makeset | find | union | 該部分效率 |
|---|---|---|---|---|
| 1 | O(1) | O(logn) | O(logn) | (V+E)logn |
| 2 | O(1) | > O(1) | > O(1) | V+E |
方案2如何平攤分析蔚携？TODO
總時間復(fù)雜度為T(sort)和T(find/union)中較大的那個
see java implement: greedy.mst.KruskalMST
Prim算法
算法中間階段的邊集X構(gòu)成一個子樹，該子樹頂點(diǎn)的集合表示為S克饶。我們選擇S中頂點(diǎn)與S外頂點(diǎn)之間的最輕邊加入X酝蜒，即以最小代價將所有原本不屬于S的頂點(diǎn)包含進(jìn)來。
與Dijkstra的關(guān)系
偽代碼基本一致矾湃，區(qū)別體現(xiàn)在優(yōu)先隊(duì)列排序使用的鍵值
- Prim: 鍵值為節(jié)點(diǎn)與集合S中頂點(diǎn)間的最輕邊的權(quán)重亡脑；
- Dijkstra：鍵值為節(jié)點(diǎn)到起始點(diǎn)的完整路徑長度；
pseudocode如下：
procedure prim
for all u in V
dist(u) = \infty
pre(u) = nil
dist(s) = 0
PQ = makequeue(V) (using dist-values as keys)
while PQ is not empty
u = deletemin(PQ)
for all edges (u, v) in E
if dist(v) > l(u, v)
dist(v) = l(u, v)
pre(v) = u
decreasekey(PQ, v)
可以看到僅是dist(u)+l(u, v)變?yōu)?strong>l(u, v)
see java implement: greedy.mst.PrimMST
哈夫曼編碼
- 編碼壓縮
壓縮比越高邀跃，隨機(jī)性越低霉咨，可預(yù)測性越好
- 無前綴特性，任一個碼字都不應(yīng)該是其他碼字的前綴
無前綴編碼中每個字符對應(yīng)于樹中的一個葉節(jié)點(diǎn)
procedure Huffman(f)
Input: An array f[1...n] of frequencies
Output: An encoding tree with n leaves
let H be a priority queue of integers, ordered by f
for i = 1 to n: insert(H, i)
for k = n + 1 to 2n -1
i = deletemin(H), j = deletemin(H)
create a node numbered k with children i,j
f[k] = f[i] + f[j]
insert(H, k)
編碼輸出
call print(root, 1)
print(node, num) {
if node is null return
print node's code based on num
:num to binary and then remove the head '1'
print(node.left, 2*num)
print(node.right, 2*num + 1)
}
see implement: greedy.Huffman
其他
Horn公式
問題描述
Horn公式中最基本的對象是取值為true或false的布爾變量拍屑，變量的知識通過蘊(yùn)涵式途戒、純否定兩類子句來表達(dá)。給定某個由以上兩類子句構(gòu)成的集合僵驰，我們需要判斷是否存在一個一致的解釋棺滞，即一組使得所有子句都滿足的變量(true/false)賦值裁蚁，該解釋成為該Horn公式的一個可滿足賦值。
求解策略
從所有變量為false開始继准，依次將“只需且不得不”這樣做以使得某個蘊(yùn)涵式滿足的變量置為true；一旦所有的蘊(yùn)涵式都得到滿足矮男，再回頭檢查是否所有否定子句仍然滿足移必。
集合覆蓋
問題描述
圖中的點(diǎn)表示一組城鎮(zhèn)，需要建設(shè)一些新的學(xué)校毡鉴。
具體要求：
- 所有的學(xué)校都必須建在城鎮(zhèn)上
- 從任意一個城鎮(zhèn)觸發(fā)崔泵，都應(yīng)該可以在30英里的范圍到達(dá)其中的某一所學(xué)校
那么，最少需要建多少所學(xué)校呢猪瞬？
較優(yōu)解求解策略（貪心）
對每個城鎮(zhèn)x憎瘸，令S(x)為在其30英里范圍內(nèi)的城鎮(zhèn)集合。
選取包含未被覆蓋元素的最大集合Si陈瘦，不斷重復(fù)幌甘，直到所有元素都被覆蓋。
貪心算法的逼近因子
貪心算法的解與實(shí)際的最優(yōu)解的規(guī)模之比可能因問題輸入的不同而不同痊项，但是總小于ln(n)锅风。我們稱這一最大比值為貪心算法的逼近因子。
寫在最后
- 立個Flag鞍泉，
TODOwill be done some day皱埠。 - 渣代碼，且輕噴:worried:咖驮。
