目　　錄





第 1章　貪心算法概述1

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

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

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

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

1.2.1　問題的設(shè)定4

1.2.2　競爭時間4

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

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

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

1.3.1　兩種特殊情況7

1.3.2　貪心算法之間的競爭7

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

1.4　正確性證明11

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

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

1.4.3　成本收益分析14

1.4.4　處理平局的情況15

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

1.5　本章要點(diǎn)18

1.6　章末習(xí)題19

第 2章　哈夫曼編碼21

2.1　編碼21

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

2.1.2　可變長度的編碼22

2.1.3　非前綴編碼23

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

2.1.5　問題定義24

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

2.2　編碼和樹26

2.2.1　3個例子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　一個更復(fù)雜的例子34

2.3.6　運(yùn)行時間37

2.3.7　小測驗(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　小測驗(yàn)3.1的答案50

3.2　Prim算法51

3.2.1　例子51

3.2.2　偽碼53

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

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

3.3.1　探求接近線性的運(yùn)行時間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)行時間分析61

3.3.6　小測驗(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算法的簡單實(shí)現(xiàn)72

*3.6　通過合并查找對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)行時間分析76

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

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

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

3.8　應(yīng)用：單鏈集群85

3.8.1　集群85

3.8.2　自底向上的集群86

3.9　本章要點(diǎn)88

3.10　章末習(xí)題89

第4章　動態(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　小測驗(yàn)4.1～4.2的答案97

4.2　路徑圖的WIS問題的線性時間算法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　小測驗(yàn)4.3～4.4的答案104

4.3　一種重建算法105

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

4.4.1　3個步驟的配方107

4.4.2　子問題的期望屬性108

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

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

4.4.5　為什么叫“動態(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　一種動態(tài)規(guī)劃算法115

4.5.5　例子117

4.5.6　重建117

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

4.6　本章要點(diǎn)119

4.7　章末習(xí)題120

第5章　高級動態(tài)規(guī)劃123

5.1　序列對齊123

5.1.1　驅(qū)動力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　一種動態(tài)規(guī)劃算法130

5.1.7　重新構(gòu)建131

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

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

5.2.1　二叉搜索樹回顧134

5.2.2　平均搜索時間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　一種動態(tài)規(guī)劃算法143

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

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

5.3　本章要點(diǎn)146

5.4　章末習(xí)題147

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

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

6.1.1　單源最短路徑問題150

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

6.1.3　小測驗(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　什么時候應(yīng)該停止159

6.2.5　偽碼160

6.2.6　Bellman-Ford算法的例子161

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

6.2.8　Internet路由165

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

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

6.3.1　問題定義166

6.3.2　簡化為單源最短路徑167

6.3.3　小測驗(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　檢測負(fù)環(huán)174

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

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

6.5　本章要點(diǎn)177

6.6　章末習(xí)題178

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

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