算法設計與分析

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

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

第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 ^[2]