算法詳解 卷3 貪心算法和動(dòng)態(tài)規(guī)劃

目　　錄


第 1章　貪心算法概述 1
1.1　貪心算法設(shè)計(jì)范例 1
1.1.1　算法設(shè)計(jì)范例 1
1.1.2　貪心算法設(shè)計(jì)范例的特性 2
1.2　一個(gè)調(diào)度問(wèn)題 4
1.2.1　問(wèn)題的設(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　開(kāi)發(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　沒(méi)有平局時(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　問(wèn)題定義 24
2.1.6　小測(cè)驗(yàn)2.1～2.2的答案 25
2.2　編碼和樹(shù) 26
2.2.1　3個(gè)例子 26
2.2.2　什么樣的樹(shù)表示非前綴編碼 28
2.2.3　問(wèn)題定義（精練版） 28
2.3　哈夫曼的貪心算法 29
2.3.1　通過(guò)連續(xù)的歸并創(chuàng)建樹(shù) 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章　最小生成樹(shù) 47
3.1　問(wèn)題定義 47
3.1.1　圖 47
3.1.2　生成樹(shù) 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　通過(guò)堆提升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　生成樹(shù)的一些有趣結(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　通過(guò)合并查找對(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)捂溂?85
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ú)立集合問(wèn)題 94
4.1.1　問(wèn)題定義 94
4.1.2　自然的貪心算法失敗了 95
4.1.3　分治算法可行嗎 96
4.1.4　小測(cè)驗(yàn)4.1～4.2的答案 97
4.2　路徑圖的WIS問(wèn)題的線性時(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　子問(wèn)題的期望屬性 108
4.4.3　一個(gè)可重復(fù)的思維過(guò)程 109
4.4.4　動(dòng)態(tài)規(guī)劃和分治算法的區(qū)別 109
4.4.5　為什么叫“動(dòng)態(tài)規(guī)劃” 110
4.5　背包問(wèn)題 111
4.5.1　問(wèn)題定義 111
4.5.2　最優(yōu)子結(jié)構(gòu)和推導(dǎo)公式 113
4.5.3　子問(wèn)題 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　問(wèn)題定義 124
5.1.3　最優(yōu)子結(jié)構(gòu) 126
5.1.4　推導(dǎo)公式 129
5.1.5　子問(wèn)題 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)二叉搜索樹(shù) 133
5.2.1　二叉搜索樹(shù)回顧 134
5.2.2　平均搜索時(shí)間 135
5.2.3　問(wèn)題定義 136
5.2.4　最優(yōu)子結(jié)構(gòu) 137
5.2.5　推導(dǎo)公式 141
5.2.6　子問(wèn)題 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　單源最短路徑問(wèn)題 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　子問(wèn)題 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ì)的最短路徑問(wèn)題 166
6.3.1　問(wèn)題定義 166
6.3.2　簡(jiǎn)化為單源最短路徑 167
6.3.3　小測(cè)驗(yàn)6.4的答案 168
6.4　Floyd-Warshall算法 168
6.4.1　子問(wèn)題 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é)和開(kāi)放性問(wèn)題 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