目錄

• 1.貪心算法步驟
• 2.兩個(gè)關(guān)鍵要素
• 3.兩種背包問(wèn)題
  3.1 0-1背包問(wèn)題（適用于動(dòng)態(tài)規(guī)劃，不滿足貪心選擇性質(zhì)）
  3.2 分?jǐn)?shù)背包問(wèn)題（適用于貪心算法）
• 4.實(shí)例
  4.1 活動(dòng)選擇問(wèn)題
  4.2 霍夫曼編碼
  4.3 最小生成樹(shù)算法
  參見(jiàn)最小生成樹(shù)
  4.4 最短路徑Dijkstra算法
  參見(jiàn)最短路徑專題
  4.5 最小生成樹(shù)與最短路徑問(wèn)題的比較

1.貪心算法步驟

step1.將最優(yōu)化問(wèn)題轉(zhuǎn)換為這樣的形式：對(duì)其最初一次選擇后渺氧，只剩下一個(gè)子問(wèn)題需要求解
step2.證明做出貪心選擇后，原問(wèn)題總是存在最優(yōu)解腾窝，即貪心選擇總是安全的
step3.證明做出貪心選擇后涌乳，剩余的子問(wèn)題滿足性質(zhì)：其最優(yōu)解與貪心選擇組合即可得到原問(wèn)題的最優(yōu)解鹤耍，這樣就得到了最優(yōu)子結(jié)構(gòu)哮缺。

2.兩個(gè)關(guān)鍵要素

1）貪心選擇性質(zhì)
可以通過(guò)做出局部最優(yōu)（貪心）選擇來(lái)構(gòu)造全局最優(yōu)解。

動(dòng)態(tài)規(guī)劃方法中妓忍，每個(gè)步驟都要進(jìn)行一次選擇虏两，但選擇通常依賴于子問(wèn)題的解。一般以一種自底向上的方式求解動(dòng)態(tài)規(guī)劃問(wèn)題世剖。

貪心算法中定罢，在進(jìn)行第一次選擇之前不求解任何子問(wèn)題，只是做出當(dāng)時(shí)看來(lái)最佳的選擇旁瘫。貪心算法通常是自頂向下的祖凫，進(jìn)行一次又一次選擇，將給定問(wèn)題實(shí)例變得更小酬凳。

證明每個(gè)步驟做出貪心選擇能生成全局最優(yōu)解惠况。這種證明通常首先考察某個(gè)子問(wèn)題的最優(yōu)解，然后用貪心選擇來(lái)修改此解宁仔，從而得到一個(gè)相似的最優(yōu)解稠屠。

2）最優(yōu)子結(jié)構(gòu)
一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解。
全部證明：將子問(wèn)題的最優(yōu)解與貪心選擇組合在一起就能生成原問(wèn)題的最優(yōu)解翎苫。（數(shù)學(xué)歸納法）

一個(gè)問(wèn)題：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)的區(qū)別?

貪心算法問(wèn)題的最優(yōu)解包括兩部分：貪心選擇 + 子問(wèn)題的最優(yōu)解
a.貪心選擇性質(zhì)針對(duì)的是貪心選擇部分
b.最優(yōu)子結(jié)構(gòu)針對(duì)的是子問(wèn)題的最優(yōu)解
這兩個(gè)合起來(lái)权埠，就構(gòu)成了貪心問(wèn)題的最優(yōu)解，缺一不可

3.兩種背包問(wèn)題

3.1 0-1背包問(wèn)題（適用于動(dòng)態(tài)規(guī)劃煎谍，不滿足貪心選擇性質(zhì)）

3.2 分?jǐn)?shù)背包問(wèn)題（適用于貪心算法）

4.實(shí)例

4.1 活動(dòng)選擇問(wèn)題

1）最優(yōu)子結(jié)構(gòu)
Sij表示在ai結(jié)束后開(kāi)始弊知，在aj開(kāi)始前結(jié)束的那些活動(dòng)的集合；
Aij是Sij的一個(gè)最大相互兼容的活動(dòng)子集
ak屬于Aij

求解Aij分解為兩個(gè)子問(wèn)題：尋找Sik中的兼容活動(dòng)粱快，以及尋找Skj中的兼容活動(dòng)：

證明：

使用c[i,j]表示集合Sij的最優(yōu)解大小，可得：

2）貪心選擇性質(zhì)（如下定理是基于fi排列順序而言的）
貪心選擇：選擇最先結(jié)束的活動(dòng)（或者選擇最晚開(kāi)始的活動(dòng)）

特別注意：這里構(gòu)造出來(lái)的也是一個(gè)最大兼容活動(dòng)子集，并非是唯一一個(gè)事哭！

3）貪心算法

4.2 霍夫曼編碼

編碼問(wèn)題：根據(jù)字符出現(xiàn)的頻率漫雷，構(gòu)造出字符的最優(yōu)二進(jìn)制表示，使得壓縮率最優(yōu)鳍咱。

變長(zhǎng)編碼：賦予高頻字符短字碼降盹，賦予低頻字符長(zhǎng)字碼

前綴碼：既沒(méi)有任何字碼是其他字碼的前綴。前綴碼可以簡(jiǎn)化解碼過(guò)程谤辜。

文件的最優(yōu)編碼方案總是對(duì)應(yīng)一顆滿二叉樹(shù)蓄坏。若C為字母表且所有字符的出現(xiàn)頻率均為正數(shù)，則最優(yōu)前綴碼對(duì)應(yīng)樹(shù)恰有|C|個(gè)葉節(jié)點(diǎn)丑念，每個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)字母表中一個(gè)字符涡戳，且恰有|C| - 1個(gè)內(nèi)部節(jié)點(diǎn)。

證明：

對(duì)于一顆滿二叉樹(shù)而言：
1）最簡(jiǎn)單情況：一個(gè)根節(jié)點(diǎn)+兩個(gè)葉子脯倚，滿足情況
2）一顆滿二叉樹(shù)可以由最簡(jiǎn)單情況重復(fù)衍生而來(lái)：將一個(gè)葉子替換為一個(gè)子樹(shù)（一個(gè)根渔彰，兩個(gè)葉子）
    此時(shí)葉子增加1（增加兩個(gè)，減少一個(gè)）推正，內(nèi)部節(jié)點(diǎn)增加1（葉子節(jié)點(diǎn)轉(zhuǎn)變而來(lái)的）

因此恍涂，有|C|-1個(gè)內(nèi)部節(jié)點(diǎn)，|C|個(gè)葉子節(jié)點(diǎn)

1）算法代碼

2）貪心選擇性質(zhì)（圖是象征性的植榕，不是一定的）
關(guān)鍵在于：用貪心選擇去修改最優(yōu)編碼樹(shù)再沧，得到的還是一顆最優(yōu)編碼樹(shù)

3）最優(yōu)子結(jié)構(gòu)（反證法，一般用cut-paste方法）

4.3 最小生成樹(shù)算法

參見(jiàn)最小生成樹(shù)

4.3.1 最小生成樹(shù)問(wèn)題

4.3.2 貪心選擇性質(zhì)

貪心策略：

該算法的理解：
a.集合A總保持無(wú)環(huán)狀態(tài)尊残，因?yàn)槭且豢脴?shù)炒瘸；因此對(duì)于集合A為安全的邊(u, v)所連接的是GA中不同的連通分量；因此夜郁，每執(zhí)行一次循環(huán)什燕，減少一棵樹(shù)
b.算法執(zhí)行的任意時(shí)刻，圖GA = (V, A)是一個(gè)森林竞端，GA中的每個(gè)連通分量是一棵樹(shù)
算法開(kāi)始時(shí)屎即，集合A為空，森林中包含|V|棵樹(shù)事富，每棵樹(shù)只有一個(gè)節(jié)點(diǎn)技俐；
c.由a, b可知，while循環(huán)總共執(zhí)行|V| - 1次统台，當(dāng)整個(gè)森林僅包含一棵樹(shù)時(shí)雕擂，終止

循環(huán)不變式：
在每次循環(huán)之前，A是某棵最小生成樹(shù)的一個(gè)子集贱勃。

安全邊：滿足如下條件的邊稱之為安全邊井赌。
將邊(u, v)加入到集合A中谤逼，使得A不違反循環(huán)不變式，即AU{(u, v)}也是某棵最小生成樹(shù)的子集仇穗。

切割：無(wú)向圖G=(V, E)的一個(gè)切割(S, V-S)是集合V的一個(gè)劃分
橫跨：邊(u, v)橫跨切割(S, V-S)表示一個(gè)端點(diǎn)在集合S流部，一個(gè)在V-S
尊重：如果集合A中不存在橫跨該切割的邊，則稱該切割尊重集合A
輕量級(jí)邊：在橫跨一個(gè)切割的所有邊中纹坐，權(quán)重最小的邊稱為輕量級(jí)邊

貪心策略中辨認(rèn)安全邊的規(guī)則：

一個(gè)推論：

一個(gè)問(wèn)題：為什么該切割尊重集合A

根據(jù)定義：因?yàn)榧螦中不存在橫跨該切割的邊
該切割區(qū)分了C枝冀，將集合A分為兩部分，C和A-C耘子，但是C和A-C并不連通果漾。
所以不存在橫跨該切割的一條輕量級(jí)邊。

4.3.3 最優(yōu)子結(jié)構(gòu)

如果一個(gè)問(wèn)題的最優(yōu)解中包含了子問(wèn)題的最優(yōu)解谷誓，則該問(wèn)題具有最優(yōu)子結(jié)構(gòu)绒障。
最小生成樹(shù)是滿足最優(yōu)子結(jié)構(gòu)的，下面會(huì)給出證明：
最優(yōu)子結(jié)構(gòu)描述：假設(shè)我們已經(jīng)得到了一個(gè)圖的最小生成樹(shù)(MST) T片林，(u, v)是這棵樹(shù)中的任意一條邊端盆。如圖所示：

現(xiàn)在我們把這條邊移除，就得到了兩棵子樹(shù)T₁和T_{2费封，
如圖：}

T₁是圖G₁=(V₁, E₁)的最小生成樹(shù)焕妙，G₁是由T₁的頂點(diǎn)導(dǎo)出的圖G的子圖，E₁={(x, y)∈E, x, y ∈V₁}
同理可得T₂是圖G₂=(V₂, E₂)的最小生成樹(shù)弓摘，G₂是由T₂的頂點(diǎn)導(dǎo)出的圖G的子圖焚鹊，E₂={(x, y)∈E, x, y ∈V₂}
現(xiàn)在我們來(lái)證明上述結(jié)論：使用剪貼法。w(T)表示T樹(shù)的權(quán)值和韧献。
首先權(quán)值關(guān)系滿足：w(T) = w(u, v)+w(T₁)+w(T₂)
假設(shè)存在一棵樹(shù)T₁'比T₁更適合圖G1末患，那么就存在T'={(u,v)}UT₁'UT₂'，那么T'就會(huì)比T更適合圖G锤窑，這與T是最優(yōu)解相矛盾璧针。得證。

• 特別注意渊啰，上圖中(u, v)這條邊是連接兩棵樹(shù)的最小邊（安全邊）

4.3.4 Kruskal算法

4.3.5 Prim算法

該算法的一個(gè)簡(jiǎn)要分析：

初始化：r.key = 0探橱，其余節(jié)點(diǎn)u.key = 無(wú)窮大
第一次循環(huán)：將r從Q中剔除，并更新r的所有鄰節(jié)點(diǎn)的key
以此類推

4.4 最短路徑Dijkstra算法

參見(jiàn)最短路徑專題

4.4.1 最短路徑問(wèn)題

4.4.2 最優(yōu)子結(jié)構(gòu)

4.4.3 Dijkstra算法的適用條件以及貪心選擇性質(zhì)

前提條件：Dijkstra算法解決的是帶權(quán)重的有向圖上單源最短路徑問(wèn)題绘证，該算法要求所有邊的權(quán)重都為非負(fù)值隧膏。

算法說(shuō)明1.松弛操作

1）最短路徑的表示（v.Π）
對(duì)每個(gè)結(jié)點(diǎn)，維持一個(gè)前驅(qū)結(jié)點(diǎn)v.Π嚷那。該前驅(qū)結(jié)點(diǎn)可能是另一個(gè)結(jié)點(diǎn)或者NIL胞枕。
設(shè)G=(V, E)是一個(gè)帶權(quán)重的有向圖，其權(quán)重函數(shù)為w魏宽，假定G不包含從s可以到達(dá)的權(quán)重為負(fù)值的環(huán)路腐泻，因此决乎，所有的最短路徑都有定義。一棵根節(jié)點(diǎn)為s的最短路徑樹(shù)是一個(gè)有向子圖G' = (V', E')

2）松弛操作（v.d）
對(duì)于每個(gè)結(jié)點(diǎn)v贫悄，維持一個(gè)屬性v.d瑞驱，用來(lái)記錄從源節(jié)點(diǎn)s到結(jié)點(diǎn)v的最短路徑權(quán)重的上界。

松弛操作是唯一導(dǎo)致最短路徑估計(jì)和前驅(qū)結(jié)點(diǎn)發(fā)生變化的操作窄坦。
Dijkstra算法對(duì)每條邊僅松弛一次。

3）最短路徑和松弛操作的一些性質(zhì)

1.三角不等式
證明：最短路徑性質(zhì)凳寺，最短路徑是最短的鸭津，那必須成立

2.上界性質(zhì)
證明：歸納法
基礎(chǔ)步：顯然成立
歸納步：根據(jù)歸納假設(shè)，松弛前肠缨，成立逆趋；松弛后，唯一可能發(fā)生改變只有v.d
  v.d = u.d + w(u, v) >= δ(s, u) + w(u, v) >= δ(s, v)
因?yàn)槭窍陆缟罐龋匀〉较陆缈隙ú粫?huì)變化

3.收斂性質(zhì)
1）根據(jù)上界性質(zhì)闻书，松弛前有u.d = δ(s, u)，松弛后仍成立
2）對(duì)(u, v)松弛后
   v.d <= u.d + w(u, v)  
        = δ(s, u) + w(u, v)
        = δ(s, v)  (根據(jù)最優(yōu)子結(jié)構(gòu)脑慧，前提是s->u->v是一條最短路徑)
   根據(jù)上界性質(zhì)魄眉，v.d >= δ(s, v)，因此有v.d = δ(s, v)

其中為什么進(jìn)行松弛后v.d <= u.d + w(u, v)?
因?yàn)椋?a. 如果v.d <= u.d + w(u, v)闷袒，松弛操作不會(huì)改變u.d和v.d的值
b. 如果v.d > u.d + w(u, v)坑律，松弛操作后，v.d = u.d + w(u, v)

4.路徑松弛性質(zhì)
使用歸納法囊骤，根據(jù)收斂性質(zhì)可以證明

5.前驅(qū)子圖性質(zhì)晃择，需要證明三條性質(zhì)都滿足
1）VΠ是從源節(jié)點(diǎn)s可以到達(dá)的結(jié)點(diǎn)的集合
    因?yàn)閂Π中的點(diǎn)δ(s, v)都是有限值，因此都可以到達(dá)
2）GΠ形成一棵根節(jié)點(diǎn)為s的樹(shù)
a. 首先證明GΠ是無(wú)環(huán)路的
b. 證明對(duì)于屬于VΠ的每個(gè)結(jié)點(diǎn)v也物，在圖GΠ中存在一條從源點(diǎn)s到結(jié)點(diǎn)v的唯一簡(jiǎn)單路徑
3）對(duì)于所有屬于VΠ的結(jié)點(diǎn)v宫屠，圖GΠ中從結(jié)點(diǎn)s到結(jié)點(diǎn)v的唯一簡(jiǎn)單路徑是圖G中從結(jié)點(diǎn)s到結(jié)點(diǎn)v的一條最短路徑。

5-2 GΠ形成一棵根節(jié)點(diǎn)為s的樹(shù)

5-3 對(duì)于所有屬于VΠ的結(jié)點(diǎn)v滑蚯，圖GΠ中從結(jié)點(diǎn)s到結(jié)點(diǎn)v的唯一簡(jiǎn)單路徑是圖G中從結(jié)點(diǎn)s到結(jié)點(diǎn)v的一條最短路徑浪蹂。
首先搞清楚前驅(qū)子圖的定義：

證明如下：

算法導(dǎo)論證明是不是有誤？
1）對(duì)于最優(yōu)子結(jié)構(gòu)膘魄，可以用cut-paste來(lái)證明：如果不是G中的最短路徑乌逐，那么還有一條更短的路徑，與v.d = δ(s, d)矛盾
2）對(duì)算法道路中的證明稍微修改创葡，將>=號(hào)改為=浙踢，是否可行？
因?yàn)槊看嗡沙诤笥笑?s, v) = δ(s, u) + w(u, v)灿渴；
這里有一個(gè)特別說(shuō)明：對(duì)于一條簡(jiǎn)單路徑上的結(jié)點(diǎn)洛波，因?yàn)橹挥兴沙诓僮鞑趴梢愿淖兦膀?qū)結(jié)點(diǎn)和v.d胰舆，所以在GΠ中的邊，都有>=蹬挤；否則不會(huì)有松弛操作缚窿，因此這里的>=是滿足的。

算法說(shuō)明2.算法的操作
Dijkstra算法在運(yùn)行過(guò)程中維持的關(guān)鍵信息是一組結(jié)點(diǎn)集合S焰扳。從源節(jié)點(diǎn)s到該集合中每個(gè)結(jié)點(diǎn)之間的最短路徑已經(jīng)被找到倦零。算法重復(fù)從結(jié)點(diǎn)集V-S中選擇最短路徑估計(jì)最小的結(jié)點(diǎn)u，將u加入到集合S吨悍，然后對(duì)所有從u出發(fā)的邊進(jìn)行松弛扫茅。
使用一個(gè)最小優(yōu)先隊(duì)列Q來(lái)保存結(jié)點(diǎn)集合，每個(gè)結(jié)點(diǎn)的關(guān)鍵值是其d值育瓜。

算法說(shuō)明3.貪心選擇性質(zhì)的證明

特別說(shuō)明：

第一次看的時(shí)候有一個(gè)地方不懂：在將u加入到集合S時(shí)葫隙，y.d = δ(s, y)
這個(gè)是根據(jù)收斂性質(zhì)來(lái)的

• Dijkstra算法的貪心選擇性質(zhì)：
  1）加入集合S的，都有u.d = δ(s, u)躏仇；此時(shí)與S中點(diǎn)相鄰的點(diǎn)v都已經(jīng)被松弛過(guò)了恋脚。并且s到最小的v必然存在一條最短路徑，并且已經(jīng)被松弛過(guò)了焰手，因此v.d=δ(s, v)肯定成立糟描。
  2）為什么s到最小的v存在一條最短路徑，而且必然是s~u-v册倒，因?yàn)樗械穆窂绞欠秦?fù)的蚓挤，并且v還未加入到S中，所以任何經(jīng)過(guò)其他路徑再到v的路徑都要比這條路徑長(zhǎng)驻子。

  
  

4.5 最小生成樹(shù)與最短路徑問(wèn)題的比較

4.5.1 問(wèn)題定義的區(qū)別

1）最小生成樹(shù)（帶權(quán)重?zé)o向圖）

2）最短路徑（帶權(quán)重有向圖灿意；Dijkstra解決的是單源最短路徑問(wèn)題）

4.5.2 Prim和Dijkstra算法

目的不一樣：
Prim求的是整個(gè)生成樹(shù)的連接最小，所以一直找最小的邊加入
Dijkstra求的是從源點(diǎn)到其他所有點(diǎn)的最短距離崇呵，所以要不斷relax更新（減戌途纭）源點(diǎn)到各個(gè)點(diǎn)的距離

1）最小生成樹(shù)的Prim算法

2）單源最短路徑的Dijkstra算法