目　　錄





第 1章　貪心算法概述1

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

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

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

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

1.2.1　問題的設(shè)定4

1.2.2　競爭時間4

1.2.3　目標函數(shù)5

1.2.4　小測驗1.1的答案6

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

1.3.1　兩種特殊情況7

1.3.2　貪心算法之間的競爭7

1.3.3　小測驗1.2～1.3的答案10

1.4　正確性證明11

1.4.1　沒有平局時的情況：高層計劃12

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

1.4.3　成本收益分析14

1.4.4　處理平局的情況15

1.4.5　小測驗1.4～1.5的答案17

1.5　本章要點18

1.6　章末習題19

第 2章　哈夫曼編碼21

2.1　編碼21

2.1.1　固定長度的二進制編碼21

2.1.2　可變長度的編碼22

2.1.3　非前綴編碼23

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

2.1.5　問題定義24

2.1.6　小測驗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　哈夫曼的貪心準則32

2.3.3　偽碼32

2.3.4　例子34

2.3.5　一個更復雜的例子34

2.3.6　運行時間37

2.3.7　小測驗2.3的答案37

*2.4　正確性證明38

2.4.1　高層計劃38

2.4.2　細節(jié)39

2.5　本章要點44

2.6　章末習題45

第3章　最小生成樹47

3.1　問題定義47

3.1.1　圖47

3.1.2　生成樹48

3.1.3　小測驗3.1的答案50

3.2　Prim算法51

3.2.1　例子51

3.2.2　偽碼53

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

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

3.3.1　探求接近線性的運行時間56

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

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

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

3.3.5　運行時間分析61

3.3.6　小測驗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　綜合運用69

3.5　Kruskal算法69

3.5.1　例子69

3.5.2　Kruskal算法的偽碼71

3.5.3　Kruskal算法的簡單實現(xiàn)72

*3.6　通過合并查找對Kruskal算法進行加速73

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

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

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

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

3.6.5　小測驗3.5～3.7的答案82

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

3.8　應用：單鏈集群85

3.8.1　集群85

3.8.2　自底向上的集群86

3.9　本章要點88

3.10　章末習題89

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

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

4.1.1　問題定義94

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

4.1.3　分治算法可行嗎96

4.1.4　小測驗4.1～4.2的答案97

4.2　路徑圖的WIS問題的線性時間算法98

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

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

4.2.3　使用緩存的遞歸算法101

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

4.2.5　小測驗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　一個可重復的思維過程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)和推導公式113

4.5.3　子問題115

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

4.5.5　例子117

4.5.6　重建117

4.5.7　小測驗4.5～4.6的答案118

4.6　本章要點119

4.7　章末習題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　推導公式129

5.1.5　子問題129

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

5.1.7　重新構(gòu)建131

5.1.8　小測驗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　推導公式141

5.2.6　子問題142

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

5.2.8　改善運行時間145

5.2.9　小測驗5.4～5.5的答案145

5.3　本章要點146

5.4　章末習題147

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

6.1　邊長可能為負的最短路徑150

6.1.1　單源最短路徑問題150

6.1.2　負環(huán)152

6.1.3　小測驗6.1的答案154

6.2　Bellman-Ford算法154

6.2.1　子問題155

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

6.2.3　推導公式158

6.2.4　什么時候應該停止159

6.2.5　偽碼160

6.2.6　Bellman-Ford算法的例子161

6.2.7　Bellman-Ford算法的運行時間164

6.2.8　Internet路由165

6.2.9　小測驗6.2～6.3的答案165

6.3　所有頂點對的最短路徑問題166

6.3.1　問題定義166

6.3.2　簡化為單源最短路徑167

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

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

6.4.6　小測驗6.5～6.6的答案176

6.5　本章要點177

6.6　章末習題178

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

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