算法设计与分析 （2011年张军创作的图书）

内容简介

本书对算法设计与分析的基本原理、常用的经典算法以及新兴发展的智能算法进行介绍，重点对各种算法的思想、流程结构以及具体的实践应用过程等方面进行介绍。

本书内容包括绪论、基本数据结构、蛮力算法、分治算法、贪心算法、动态规划算法、回溯算法、分支限界算法、概率算法等经典算法的思想和原理，同时还介绍了人工神经网络、模糊逻辑、遗传算法、蚁群算法、粒子群优化算法、差分进化算法，以及分布估计算法等现代计算智能算法。本书通俗易懂，图文并茂，深入浅出，避免其他算法书中大量公式、定理、证明等难懂的内容，相反通过大量的图表示例对各个算法进行说明和介绍，不但提供了算法的伪代码，而且通过具体的应用举例对算法的使用方法和使用过程进行说明，以利于读者快速掌握算法分析与设计的原理和精髓。

图书目录

第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