目　　錄





第 1章　貪心算法概述1

1.1　貪心算法設(shè)計(jì)范例1

1.1.1　算法設(shè)計(jì)范例1

1.1.2　貪心算法設(shè)計(jì)范例的特性2

1.2　一個(gè)調(diào)度問題4

1.2.1　問題的設(shè)定4

1.2.2　競(jìng)爭(zhēng)時(shí)間4

1.2.3　目標(biāo)函數(shù)5

1.2.4　小測(cè)驗(yàn)1.1的答案6

1.3　開發(fā)一種貪心算法6

1.3.1　兩種特殊情況7

1.3.2　貪心算法之間的競(jìng)爭(zhēng)7

1.3.3　小測(cè)驗(yàn)1.2～1.3的答案10

1.4　正確性證明11

1.4.1　沒有平局時(shí)的情況：高層計(jì)劃12

1.4.2　在相鄰逆序?qū)χ薪粨Q作業(yè)13

1.4.3　成本收益分析14

1.4.4　處理平局的情況15

1.4.5　小測(cè)驗(yàn)1.4～1.5的答案17

1.5　本章要點(diǎn)18

1.6　章末習(xí)題19

第 2章　哈夫曼編碼21

2.1　編碼21

2.1.1　固定長(zhǎng)度的二進(jìn)制編碼21

2.1.2　可變長(zhǎng)度的編碼22

2.1.3　非前綴編碼23

2.1.4　非前綴編碼的優(yōu)點(diǎn)23

2.1.5　問題定義24

2.1.6　小測(cè)驗(yàn)2.1～2.2的答案25

2.2　編碼和樹26

2.2.1　3個(gè)例子26

2.2.2　什么樣的樹表示非前綴編碼28

2.2.3　問題定義（精練版）28

2.3　哈夫曼的貪心算法29

2.3.1　通過連續(xù)的歸并創(chuàng)建樹29

2.3.2　哈夫曼的貪心準(zhǔn)則32

2.3.3　偽碼32

2.3.4　例子34

2.3.5　一個(gè)更復(fù)雜的例子34

2.3.6　運(yùn)行時(shí)間37

2.3.7　小測(cè)驗(yàn)2.3的答案37

*2.4　正確性證明38

2.4.1　高層計(jì)劃38

2.4.2　細(xì)節(jié)39

2.5　本章要點(diǎn)44

2.6　章末習(xí)題45

第3章　最小生成樹47

3.1　問題定義47

3.1.1　圖47

3.1.2　生成樹48

3.1.3　小測(cè)驗(yàn)3.1的答案50

3.2　Prim算法51

3.2.1　例子51

3.2.2　偽碼53

3.2.3　簡(jiǎn)單的實(shí)現(xiàn)55

*3.3　通過堆提升Prim算法的速度56

3.3.1　探求接近線性的運(yùn)行時(shí)間56

3.3.2　堆數(shù)據(jù)結(jié)構(gòu)56

3.3.3　如何在Prim算法中使用堆57

3.3.4　基于堆的實(shí)現(xiàn)的偽碼59

3.3.5　運(yùn)行時(shí)間分析61

3.3.6　小測(cè)驗(yàn)3.3的答案61

*3.4　Prim算法：正確性證明62

3.4.1　最小瓶頸屬性62

3.4.2　生成樹的一些有趣結(jié)論65

3.4.3　定理3.4（MBP意味著MST）的證明67

3.4.4　綜合運(yùn)用69

3.5　Kruskal算法69

3.5.1　例子69

3.5.2　Kruskal算法的偽碼71

3.5.3　Kruskal算法的簡(jiǎn)單實(shí)現(xiàn)72

*3.6　通過合并查找對(duì)Kruskal算法進(jìn)行加速73

3.6.1　合并查找數(shù)據(jù)結(jié)構(gòu)73

3.6.2　基于合并查找的實(shí)現(xiàn)的偽碼75

3.6.3　基于合并查找的實(shí)現(xiàn)的運(yùn)行時(shí)間分析76

3.6.4　合并查找的快速有余而嚴(yán)謹(jǐn)不足的實(shí)現(xiàn)：父圖77

3.6.5　小測(cè)驗(yàn)3.5～3.7的答案82

*3.7　Kruskal算法的正確性證明83

3.8　應(yīng)用：?jiǎn)捂溂��?5

3.8.1　集群85

3.8.2　自底向上的集群86

3.9　本章要點(diǎn)88

3.10　章末習(xí)題89

第4章　動(dòng)態(tài)規(guī)劃概述93

4.1　加權(quán)獨(dú)立集合問題94

4.1.1　問題定義94

4.1.2　自然的貪心算法失敗了95

4.1.3　分治算法可行嗎96

4.1.4　小測(cè)驗(yàn)4.1～4.2的答案97

4.2　路徑圖的WIS問題的線性時(shí)間算法98

4.2.1　最優(yōu)子結(jié)構(gòu)和推導(dǎo)公式98

4.2.2　一種不成熟的遞歸方法100

4.2.3　使用緩存的遞歸算法101

4.2.4　一種迭代式的自底向上的實(shí)現(xiàn)103

4.2.5　小測(cè)驗(yàn)4.3～4.4的答案104

4.3　一種重建算法105

4.4　動(dòng)態(tài)規(guī)劃的原則107

4.4.1　3個(gè)步驟的配方107

4.4.2　子問題的期望屬性108

4.4.3　一個(gè)可重復(fù)的思維過程109

4.4.4　動(dòng)態(tài)規(guī)劃和分治算法的區(qū)別109

4.4.5　為什么叫“動(dòng)態(tài)規(guī)劃”110

4.5　背包問題111

4.5.1　問題定義111

4.5.2　最優(yōu)子結(jié)構(gòu)和推導(dǎo)公式113

4.5.3　子問題115

4.5.4　一種動(dòng)態(tài)規(guī)劃算法115

4.5.5　例子117

4.5.6　重建117

4.5.7　小測(cè)驗(yàn)4.5～4.6的答案118

4.6　本章要點(diǎn)119

4.7　章末習(xí)題120

第5章　高級(jí)動(dòng)態(tài)規(guī)劃123

5.1　序列對(duì)齊123

5.1.1　驅(qū)動(dòng)力123

5.1.2　問題定義124

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

5.1.4　推導(dǎo)公式129

5.1.5　子問題129

5.1.6　一種動(dòng)態(tài)規(guī)劃算法130

5.1.7　重新構(gòu)建131

5.1.8　小測(cè)驗(yàn)5.1～5.3的答案132

*5.2　最優(yōu)二叉搜索樹133

5.2.1　二叉搜索樹回顧134

5.2.2　平均搜索時(shí)間135

5.2.3　問題定義136

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

5.2.5　推導(dǎo)公式141

5.2.6　子問題142

5.2.7　一種動(dòng)態(tài)規(guī)劃算法143

5.2.8　改善運(yùn)行時(shí)間145

5.2.9　小測(cè)驗(yàn)5.4～5.5的答案145

5.3　本章要點(diǎn)146

5.4　章末習(xí)題147

第6章　再論最短路徑算法150

6.1　邊長(zhǎng)可能為負(fù)的最短路徑150

6.1.1　單源最短路徑問題150

6.1.2　負(fù)環(huán)152

6.1.3　小測(cè)驗(yàn)6.1的答案154

6.2　Bellman-Ford算法154

6.2.1　子問題155

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

6.2.3　推導(dǎo)公式158

6.2.4　什么時(shí)候應(yīng)該停止159

6.2.5　偽碼160

6.2.6　Bellman-Ford算法的例子161

6.2.7　Bellman-Ford算法的運(yùn)行時(shí)間164

6.2.8　Internet路由165

6.2.9　小測(cè)驗(yàn)6.2～6.3的答案165

6.3　所有頂點(diǎn)對(duì)的最短路徑問題166

6.3.1　問題定義166

6.3.2　簡(jiǎn)化為單源最短路徑167

6.3.3　小測(cè)驗(yàn)6.4的答案168

6.4　Floyd-Warshall算法168

6.4.1　子問題168

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

6.4.3　偽碼172

6.4.4　檢測(cè)負(fù)環(huán)174

6.4.5　Floyd-Warshall算法的總結(jié)和開放性問題175

6.4.6　小測(cè)驗(yàn)6.5～6.6的答案176

6.5　本章要點(diǎn)177

6.6　章末習(xí)題178

附錄　章末習(xí)題答案節(jié)選180

后記　算法設(shè)計(jì)工作指南187