算法设计与分析

本书系统地介绍了算法设计策略，包含大量的范例和对应的实现代码，让读者对算法设计策略的基本思想和核心设计步骤有深入的理解与掌握，能够让读者掌握各种算法设计策略的精髓，能够提高读者的算法设计能力，能够让读者具备分析具体问题、选择算法设计策略、给出算法代码的能力。本书适用于计算机科学与技术相关专业的本科和研究生阶段的教材，也可以作为从事实际问题求解的研究工作者的入门教材。

本书共8章，主要从算法的分析与设计两个方面进行介绍。首先，系统地介绍了算法分析
的基本方法，包括对时间复杂性和空间复杂性的分析，并详细介绍了主方法。然后，系统地介绍了各种算法设计策略，包括递归与分治策略、动态规划算法、贪心算法、回溯法、分支限界法、随机算法、线性规划与网络流等。对于每种算法设计策略，从该策略的基本思想、适用问题、算法步骤等多个方面详细讲解，对于复杂的算法设计策略还给出了相关例题。书中包含大量的范例和相应的实现代码，让读者对算法设计策略的基本思想和核心设计步骤有深入的理解与掌握，能够让读者掌握各种算法设计策略的精髓，提高读者的算法设计能力，让读者具备分析具体问题、选择算法设计策略、给出算法代码的能力。
本书适合作为高等院校计算机科学与技术相关专业的本科和研究生阶段的教材，也可以作为从事实际问题求解的研究工作者的参考书。

汪国华，博士，教授，博士生导师，东北林业大学。《算法设计与分析》课程组负责人，主持校教育教学研究项目1项。该课程已经评为了校一流在线课程，并获得了校《优秀研究生教材建设》项目。目前担任东北林业大学信息与计算机工程学院院长，一直致力于人工智能、大数据领域与生命、林学、其他工科领域的多学科交叉的教育模式探索。科研方向是人工智能和生物信息学，主要是利用海量生物高通量数据进行基因组组装与比对算法设计、疾病调控机制、单细胞分类模型研究。作为负责人主持国家863项目1项，863子课题项目1项，国家自然科学基金3项等。2013年入选教育部“新世纪优秀人才支持计划”，2014年入选国家博士后基金会百名博士后国际交流计划派出项目。2011年博士学位论文获得中国计算机学会“2011CCF优秀博士学位论文奖提名”。 李艳娟，女，博士，副教授，硕士生导师，现任衢州学院电气与信息工程学院教师。中国计算机学会（CCF）会员，生物信息学专委会委员。 主要从事生物信息学，机器学习等研究。主持国家自然科学基金1项，主持省级项目2项，主持中央高校基金4项，作为主要成员参与863项目、国家自然科学基金、省级项目6项。以第一作者或通讯作者发表论文20多篇，其中SCI、EI检索18篇。出版教材5部，授权专利12项，计算机软件著作权9项。 先后承担数据机构，算法设计与分析，计算机图形学等课程主讲工作。

第1章 算法概述 1
1.1 引言 3
1.2 算法的概念 4
1.3 算法复杂性分析 8
1.4 本章小结 16
习题 17
第2章 递归与分治策略 19
2.1 递归 22
2.2 分治策略 28
2.3 分治法求解查找问题 30
2.4 分治法求解排序问题 33
2.5 分治法求解复杂计算问题 38
2.6 分治法求解组合问题 51
2.7 本章小结 55
习题 56
第3章 动态规划算法 59
3.1 动态规划的基本概念 62
3.2 备忘录方法 64
3.3 动态规划算法的总体设计思想和基本要素 65
3.4 矩阵连乘问题 67
3.5 最长公共子序列问题 74
3.6   0-1背包问题 80
3.7 优选子段和问题 83
3.8 凸多边形很优三角剖分 88
3.9 本章小结 90
习题 91
第4章 贪心算法 94
4.1 生活中的贪心算法 96
4.2 贪心算法的基本思想 98
4.3 活动安排问题 100
4.4 很优装载问题 104
4.5 哈夫曼编码 108
4.6 贪心算法的正确性验证 116
4.7 本章小结 117
习题 117
第5章 回溯法 120
5.1 回溯法的基本思想 122
5.2 回溯法的算法框架 123
5.3 装载问题 127
5.4 批处理作业调度问题 130
5.5 符号三角形问题 133
5.6   0-1背包问题 135
5.7 优选团问题 138
5.8 旅行商问题 141
5.9 连续邮资问题 145
5.10 回溯法的效率分析 148
5.11 本章小结 149
习题 149
第6章 分支限界法 154
6.1 分支限界法的基本思想 157
6.2 装载问题 161
6.3 布线问题 171
6.4   0-1背包问题 177
6.5 优选团问题 182
6.6 旅行商问题 185
6.7 本章小结 189
习题 190
第7章 随机算法 193
7.1 随机算法的设计思想 196
7.2 随机数发生器 197
7.3 数值随机算法 199
7.4 舍伍德算法 200
7.5 拉斯维加斯算法 203
7.6 蒙特卡罗算法 208
7.7 本章小结 210
习题 210
第8章 线性规划与网络流 212
8.1 线性规划概述 215
8.2 单纯形法的设计思想与步骤 221
8.3 单纯形法的描述与分析 232
8.4 网络优选流问题 235
8.5 最小费用流问题 244
8.6 本章小结 257
习题 257
参考文献 261