采用步步逼近的方式構(gòu)造問題的解，其下一步的選擇總是在當(dāng)前看來收效最快和效果最明顯的那個。

使用前提： 驗證貪心模式的有效性

最小生成樹（minimum spanning tree）

輸入：無向圖G=(V, E); 邊權(quán)重w(e)
輸出：樹T=(V, E')，

其中， 使得權(quán)重 = \sum_{e \in E'} w_e)

樹的性質(zhì)

1. 具有n個節(jié)點的樹的邊數(shù)為n-1
2. 一個無向圖是樹，當(dāng)且僅當(dāng)任意兩個節(jié)點間僅存在唯一路徑

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的獨立集合
• 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)：有向樹
集合中的頂點對應(yīng)樹的節(jié)點，每個節(jié)點包含一個父指針，一級級指向樹根。樹根的父指針指向該元素自身。

有向樹

1. p //父節(jié)點指針
2. rank //該節(jié)點下懸掛的子樹高度

• 方案一
  合并時讓較低的樹的根指向較高的樹的根（基于等級的合并）

  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未進行更新，此時rank的含義無法解釋為子樹的高度。
此時有向樹的高度不會超過2。

• 方案三
  我們可以發(fā)現(xiàn)find和union操作均只關(guān)心樹的頂層，是否可以直接使用樹高為2的有向樹呢？并在union()操作中，對于兩個樹高為2的有向樹，進行其中一棵的壓縮。

但仔細分析可以得出，此方案與方案二本質(zhì)相同，僅將find()操作總共所做的工作轉(zhuǎn)移到union()操作中。

方案2如何平攤分析？TODO
總時間復(fù)雜度為T(sort)和T(find/union)中較大的那個

see java implement: greedy.mst.KruskalMST

Prim算法

算法中間階段的邊集X構(gòu)成一個子樹，該子樹頂點的集合表示為S。我們選擇S中頂點與S外頂點之間的最輕邊加入X，即以最小代價將所有原本不屬于S的頂點包含進來。

與Dijkstra的關(guān)系
偽代碼基本一致，區(qū)別體現(xiàn)在優(yōu)先隊列排序使用的鍵值

• Prim: 鍵值為節(jié)點與集合S中頂點間的最輕邊的權(quán)重；
• Dijkstra：鍵值為節(jié)點到起始點的完整路徑長度；

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

哈夫曼編碼

• 編碼壓縮

壓縮比越高，隨機性越低，可預(yù)測性越好

• 無前綴特性，任一個碼字都不應(yīng)該是其他碼字的前綴

無前綴編碼中每個字符對應(yīng)于樹中的一個葉節(jié)點

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的布爾變量，變量的知識通過蘊涵式、純否定兩類子句來表達。給定某個由以上兩類子句構(gòu)成的集合，我們需要判斷是否存在一個一致的解釋，即一組使得所有子句都滿足的變量(true/false)賦值，該解釋成為該Horn公式的一個可滿足賦值。

求解策略
從所有變量為false開始，依次將“只需且不得不”這樣做以使得某個蘊涵式滿足的變量置為true；一旦所有的蘊涵式都得到滿足，再回頭檢查是否所有否定子句仍然滿足。

集合覆蓋

問題描述

具體要求：

1. 所有的學(xué)校都必須建在城鎮(zhèn)上
2. 從任意一個城鎮(zhèn)觸發(fā)，都應(yīng)該可以在30英里的范圍到達其中的某一所學(xué)校
   那么，最少需要建多少所學(xué)校呢？

較優(yōu)解求解策略（貪心）
對每個城鎮(zhèn)x，令S(x)為在其30英里范圍內(nèi)的城鎮(zhèn)集合。
選取包含未被覆蓋元素的最大集合Si，不斷重復(fù)，直到所有元素都被覆蓋。

貪心算法的逼近因子
貪心算法的解與實際的最優(yōu)解的規(guī)模之比可能因問題輸入的不同而不同，但是總小于ln(n)。我們稱這一最大比值為貪心算法的逼近因子。

寫在最后

• 立個Flag，TODO will be done some day。
• 渣代碼，且輕噴:worried:。