第 1章 回溯法 1

1.1　八皇后問題　1

1.2　搜索　10

1.2.1　單向搜索　10

1.2.2　雙向搜索　16

1.3　剪枝　17

1.3.1　正方形剖分　26

1.3.2　關(guān)燈問題　27

1.4　15數(shù)碼問題　29

1.5　小結(jié)　38

第　2章 圖遍歷　39

2.1　基本概念　39

2.1.1　圖的屬性　39

2.1.2　歐拉公式　40

2.1.3　路與連通　40

2.2　圖的表示　41

2.2.1　鄰接矩陣　41

2.2.2　邊列表和前向星　41

2.2.3　鄰接表　42

2.2.4　鏈?zhǔn)角跋蛐恰?3

2.3　圖遍歷　44

2.3.1　廣度優(yōu)先遍歷　44

2.3.2　深度優(yōu)先遍歷　50

2.4　圖遍歷的應(yīng)用　53

2.4.1　圖的連通性　53

2.4.2　短路徑　54

2.4.3　長簡單路徑　56

2.4.4　圖的著色　57

2.4.5　近公共祖先　57

2.4.6　割頂　65

2.4.7　割邊　68

2.4.8　強(qiáng)連通分支　70

2.4.9　半連通分支　77

2.4.10　2-SAT　78

2.4.11　圖的直徑　83

2.4.12　樹的重心　84

2.5　拓?fù)渑判颉?5

2.6　小結(jié)　87

第3章　圖算法　89

3.1　基本概念　89

3.2　圖的回路　90

3.2.1　歐拉回　90

3.2.2　中國投遞員問題　104

3.2.3　哈密頓回　105

3.2.4　旅行商問題　107

3.3　小生成樹　107

3.3.1　Prim算法　107

3.3.2　Kruskal算法　109

3.3.3　小生成樹的擴(kuò)展問題　111

3.3.4　度限制小生成樹　111

3.3.5　次小生成樹　114

3.4　短路徑問題　118

3.4.1　Moore-Dijkstra算法　118

3.4.2　Bellman-Ford算法　126

3.4.3　Floyd-Warshall算法　130

3.4.4　傳遞閉包　132

3.4.5　小化的距離　134

3.4.6　差分約束系統(tǒng)　134

3.4.7　第K短路徑問題　138

3.5　網(wǎng)絡(luò)流問題　140

3.5.1　基本概念　141

3.5.2　Ford-Fulkerson方法　142

3.5.3　Edmonds-Karp算法　144

3.5.4　Dinic算法　149

3.5.5　ISAP算法　153

3.5.6　小截問題　158

3.5.7　小費(fèi)用流問題　159

3.6　邊獨(dú)立集與二部圖匹配　161

3.6.1　網(wǎng)絡(luò)流解法　162

3.6.2　Hungarian算法　164

3.6.3　Hopcroft-Karp算法　169

3.6.4　Gale-Shapley算法　171

3.6.5　Edmonds算法　172

3.7　二部圖加權(quán)完備匹配　176

3.7.1　網(wǎng)絡(luò)流解法　176

3.7.2　Kuhn-Munkres算法　177

3.8　點(diǎn)支配集、點(diǎn)覆蓋集、點(diǎn)獨(dú)立集　185

3.8.1　點(diǎn)支配集　185

3.8.2　點(diǎn)覆蓋集　185

3.8.3　點(diǎn)獨(dú)立集與團(tuán)　188

3.9　路徑覆蓋和邊覆蓋　188

3.9.1　小路徑覆蓋　188

3.9.2　小邊覆蓋　189

3.10　樹的相關(guān)問題求解　189

3.10.1　小點(diǎn)支配　189

3.10.2　小點(diǎn)覆蓋　190

3.10.3　點(diǎn)獨(dú)立　191

3.11　小結(jié)　191

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

4.1　背包問題　193

4.1.1　01背包問題　193

4.1.2　完全背包問題　197

4.1.3　多重背包問題　197

4.1.4　背包問題擴(kuò)展　198

4.2　備忘　200

4.2.1　3n 1問題　201

4.2.2　正交范圍查詢　203

4.2.3　正方形（長方形）　203

4.2.4　整數(shù)劃分　206

4.2.5　博弈樹　206

4.2.6　備忘與遞推　210

4.3　松弛　217

4.3.1　Moore-Dijkstra算法　218

4.3.2　Bellman-Ford算法　220

4.3.3　Floyd-Warshall算法　220

4.4　集合型動(dòng)態(tài)規(guī)劃　222

4.5　區(qū)間型動(dòng)態(tài)規(guī)劃　229

4.5.1　矩陣鏈乘法　229

4.5.2　石子合并問題　231

4.6　圖論型動(dòng)態(tài)規(guī)劃　238

4.6.1　路徑計(jì)數(shù)　241

4.6.2　樹形動(dòng)態(tài)規(guī)劃　243

4.6.3　旅行商問題　246

4.6.4　雙調(diào)歐幾里得旅行商問題　247

4.7　概率型動(dòng)態(tài)規(guī)劃　250

4.8　非典型動(dòng)態(tài)規(guī)劃　255

4.9　動(dòng)態(tài)規(guī)劃的優(yōu)化　257

4.9.1　空間優(yōu)化　257

4.9.2　狀態(tài)優(yōu)化　258

4.9.3　二進(jìn)制優(yōu)化　262

4.9.4　單調(diào)隊(duì)列優(yōu)化　262

4.9.5　斜率優(yōu)化　265

4.9.6　四邊形不等式優(yōu)化　268

4.10　子序列和子串問題　271

4.10.1　短編輯距離　271

4.10.2　長公共子序列　274

4.10.3　長公共子串　276

4.10.4　長遞增子序列　277

4.10.5　長不重復(fù)子串　280

4.10.6　長回文子串　281

4.10.7　連續(xù)子序列和（積）　285

4.11　貪心算法　287

4.11.1　部分背包問題　288

4.11.2　紙幣找零問題　289

4.11.3　硬幣兌換問題　292

4.11.4　霍夫曼編碼　293

4.11.5　策略選擇　295

4.12　小結(jié)　296

第5章　網(wǎng)格　297

5.1　矩形網(wǎng)格　297

5.1.1　網(wǎng)格行走　297

5.1.2　Flood-Fill算法　299

5.1.3　國際象棋棋盤　302

5.1.4　騎士周游問題　304

5.2　三角形網(wǎng)格　309

5.3　六邊形網(wǎng)格　312

5.4　經(jīng)度與緯度　312

5.5　小結(jié)　313

附錄A　如何使用UVa OJ　314

附錄B　ASCII表　317

附錄C　C 運(yùn)算符優(yōu)先級　318

附錄D　習(xí)題索引　319

參考資料　320