演演算法設計與分析

本書對演演算法設計與分析的基本原理、常用的經典演演算法以及新興發展的智能演演算法進行介紹，重點對各種演演算法的思想、流程結構以及具體的實踐應用過程等方面進行介紹。

本書內容包括緒論、基本數據結構、蠻力演演算法、分治演演算法、貪心演演算法、動態規劃演演算法、回溯演演算法、分支限界演演算法、概率演演算法等經典演演算法的思想和原理，同時還介紹了人工神經網路、模糊邏輯、遺傳演演算法、蟻群演演算法、粒子群優化演演算法、差分進化演演算法，以及分佈估計演演算法等現代計算智能演演算法。本書通俗易懂，圖文並茂，深入淺出，避免其他演演算法書中大量公式、定理、證明等難懂的內容，相反通過大量的圖表示例對各個演演算法進行說明和介紹，不但提供了演演算法的偽代碼，而且通過具體的應用舉例對演演算法的使用方法和使用過程進行說明，以利於讀者快速掌握演演算法分析與設計的原理和精髓。

第1章 緒論1

1.1 演演算法的基本概念2

1.1.1 演演算法的重要性2

1.1.2 演演算法設計與分析的流程3

1.2 演演算法設計與分析的重要問題類型4

1.2.1 排序問題4

1.2.2 查找問題4

1.2.3 圖問題5

1.2.4 組合問題5

1.2.5 數值問題5

1.2.6 幾何問題6

1.3 演演算法複雜性分析基礎6

1.3.1 演演算法複雜性分析的原理6

1.3.2 漸進符號8

1.4 本章小結9

1.5 習題9

第2章 基本數據結構11

2.1 數據結構的概念12

2.2 線性結構15

2.2.1 線性表15

2.2.2 棧18

2.2.3 隊列20

2.2.4 串21

2.3 樹形結構23

2.3.1 樹的定義與性質23

2.3.2 二叉樹24

2.3.3 多叉樹27 演演算法設計與分析目錄 2.4 圖狀結構28

2.4.1 圖的定義28

2.4.2 圖的存儲結構29

2.4.3 圖的遍歷31

2.5 集合與字典33

2.5.1 集合33

2.5.2 字典34

2.6 本章小結35

2.7 習題35

第3章 蠻力演演算法37

3.1 演演算法設計思想38

3.2 排序問題中的蠻力演演算法39

3.2.1 選擇排序39

3.2.2 冒泡排序40

3.3 查找問題中的蠻力演演算法41

3.3.1 順序查找演演算法41

3.3.2 串匹配演演算法42

3.4 組合問題中的蠻力演演算法43

3.4.1 旅行商問題43

3.4.2 背包問題44

3.4.3 任務分配問題45

3.5 幾何問題中的蠻力演演算法46

3.5.1 最近點對問題46

3.5.2 凸包問題46

3.6 本章小結47

3.7 習題48

第4章 分治演演算法51

4.1 演演算法設計思想52

4.2 排序問題中的分治演演算法53

4.2.1 歸併排序53

4.2.2 快速排序55

4.3 查找問題中的分治演演算法56

4.3.1 折半查找56

4.3.2 二叉樹遍歷演演算法57

4.4 組合問題中的分治演演算法58

4.4.1 最大子段和問題58

4.4.2 棋盤覆蓋問題59

4.5 幾何問題中的分治演演算法60

4.5.1 最近點對問題60

4.5.2 凸包問題61

4.6 本章小結62

4.7 習題62

第5章 貪心演演算法65

5.1 演演算法設計思想66

5.1.1 貪心演演算法的設計思想66

5.1.2 貪心演演算法的求解過程66

5.2 圖問題中的貪心演演算法67

5.2.1 單源最短路徑問題： Dijkstra演演算法67

5.2.2 最小生成樹問題： Prim演演算法和Kruskal演演算法70

5.2.3 哈夫曼樹74

5.3 組合問題中的貪心演演算法76

5.3.1 背包問題76

5.3.2 活動安排問題77

5.3.3 多機調度問題78

5.4 本章小結81

5.5 習題81

第6章 動態規劃演演算法85

6.1 演演算法設計思想86

6.1.1 動態規劃演演算法的基本要素86

6.1.2 動態規劃演演算法的基本步驟87

6.2 查找問題中的動態規劃演演算法90

6.2.1 最優二叉查找樹90

6.2.2 近似串匹配問題92

6.3 圖問題中的動態規劃演演算法94

6.3.1 多段圖的最短路徑問題94

6.3.2 多源最短路徑問題： Floyd演演算法95

6.4 組合問題中的動態規劃演演算法97

6.4.1 0/1背包問題97

6.4.2 最長公共子序列問題98

6.5 本章小結100

6.6 習題100

第7章 回溯演演算法103

7.1 演演算法設計思想104

7.1.1 問題的解空間與解空間樹104

7.1.2 解空間樹的動態搜索106

7.1.3 回溯演演算法的求解過程106

7.1.4 回溯演演算法的時間性能107

7.2 圖問題中的回溯演演算法108

7.2.1 深度優先搜索108

7.2.2 TSP問題110

7.3 組合問題中的回溯演演算法113

7.3.1 0/1背包問題113

7.3.2 八皇后問題117

7.3.3 圖著色問題119

7.4 本章小結121

7.5 習題121

第8章 分支限界演演算法123

8.1 演演算法的設計思想124

8.1.1 解空間樹的動態搜索124

8.1.2 分支限界演演算法的設計思想126

8.1.3 分支限界演演算法的時間性能128

8.2 圖問題中的分支限界演演算法128

8.2.1 TSP問題128

8.2.2 單源最短路徑問題130

8.3 組合優化問題中的分支限界演演算法134

8.3.1 0/1背包問題134

8.3.2 任務分配問題136

8.3.3 活動安排問題139

8.4 本章小結142

8.5 習題142

第9章 概率演演算法145

9.1 概率演演算法設計思想與實現基礎146

9.1.1 確定性與隨機性146

9.1.2 各種概率演演算法的設計思想147

9.1.3 隨機數和偽隨機數147

9.2 數值概率演演算法149

9.2.1 投點法計算π值149

9.2.2 拉普拉斯方程狄利克雷問題的求解150

9.3 蒙特卡羅演演算法151

9.3.1 蒙特卡羅演演算法正確率的提升151

9.3.2 串相等性測試問題153

9.3.3 素數性測試154

9.4 拉斯維加斯演演算法156

9.4.1 隨機抽牌問題156

9.4.2 整數因子分解158

9.5 舍伍德演演算法159

9.5.1 舍伍德型的快速排序159

9.5.2 隨機化的選擇演演算法160

9.6 本章小結162

9.7 習題162

第10章 計算智能165

10.1 人工神經網路166

10.1.1 思想來源和發展歷程166

10.1.2 人工神經網路的基本原理167

10.1.3 ANN小結170

10.2 模糊邏輯170

10.2.1 模糊邏輯概述170

10.2.2 模糊邏輯的基本原理171

10.2.3 模糊邏輯技術小結173

10.3 遺傳演演算法174

10.3.1 遺傳演演算法的思想起源174

10.3.2 遺傳演演算法的基本原理175

10.3.3 遺傳演演算法的特點及其發展趨勢176

10.4 蟻群演演算法177

10.4.1 蟻群演演算法的思想來源177

10.4.2 蟻群優化的基本原理178

10.4.3 蟻群優化小結180

10.5 粒子群優化演演算法181

10.5.1 粒子群優化演演算法的思想來源181

10.5.2 粒子群優化演演算法的基本原理181

10.5.3 粒子群優化演演算法的發展趨勢182

10.6 差分進化演演算法183

10.6.1 差分進化概述183

10.6.2 差分進化演演算法的基本原理184

10.6.3 差分進化演演算法小結185

10.7 分佈估計演演算法185

10.7.1 分佈估計演演算法概述185

10.7.2 分佈估計演演算法的基本原理187

10.7.3 分佈估計演演算法的發展趨勢187

10.8 本章小結188

10.9 習題189

附錄A 名詞索引191

索引196

參考文獻199