算法设计与应用

本书主要讨论和分析基础算法，包括排序、递归、分治、动态规划、贪心、图算法、回溯和分支限界，以及匹配与指派。为了让读者不仅掌握算法，也能够理解算法的设计思想，本书对算法的解读通常通过作者称为“思路”的方式展开，并通过设置问题和解答问题的方式，让读者不仅对算法知其然，也知其所以然。尽管这些算法是基础算法，但它们在实际中有着广泛的应用。本书的另一大特点是对算法应用的讨论，这些讨论一方面体现算法的应用价值，另一方面激发读者对算法进一步学习的兴趣。 本书可作为高等院校计算机类专业本科生的算法课程的教材，也可作为各行业从事算法设计和开发的人员的技术参考书。

林海，现任武汉大学-国家网络安全学院副教授，先后毕业于法国巴黎第六大学(硕士)和法国国立高等通信学校(博士)，并取得了计算机网络博士学位，是武汉大学作为人才引进的优秀青年学术骨干。在加入武汉大学之前，曾经先后在法国电信 Orange 研究院从事博士后研究和在中兴通讯欧洲研究所(巴黎)从事系统工程师工作。本书作者一直从事算法方面的教学和研究，有着多年本科生《算法设计与分析》和研究生《高级算法》教学经验。

前言 第1章算法概念和基础 11基本概念 111搜索 112排序 12算法复杂度 121时间复杂度 122算法的时间复杂度 123空间复杂度 13数据结构 131堆 132不相交集 14本章小结 15习题 第2章排序 21比较排序 211冒泡排序 212堆排序 213插入排序 214归并排序 22线性排序 221桶排序 222计数排序 223基数排序 23本章小结 24习题 第3章递归 31基本概念 32递归例子 321生成排列 322整数划分 33复杂度的递归方法求解 331展开法 332代入法 333递归树方法 334主方法 335几种递归形式的复杂度分析 34本章小结 35习题 第4章分治 41基本概念 42快速排序 43最大子数组问题 44最近点对问题 45棋盘覆盖问题 46寻找第k小元素 47分治在傅里叶变换中的应用* 48本章小结 49习题 第5章动态规划 51基本概念和步骤 52最大子数组问题 530-1背包问题 54旅行商问题 55最长公共子序列 56斯坦纳最小树* 57状态压缩动态规划 571集合状态压缩 572空间状态压缩 58动态规划和贝尔曼方程* 59本章小结 510习题 第6章贪心 61基本概念 62小数背包和0-1背包 621小数背包贪心算法的正确性证明 6220-1背包贪心算法 63最小生成树 631Kruskal算法 632Prim算法 64霍夫曼编码 65贪心算法在稳定匹配中的应用* 66本章小结 67习题 第7章图算法 71深度优先搜索 711无向图的深度优先搜索 712有向图的深度优先搜索 713应用：寻找图的关节点 72广度优先搜索 721无向图的广度优先搜索 722有向图的广度优先搜索 723应用：最短路径（跳数） 73单源最短路径 731Dijkstra算法 732Bellman-Ford算法 733SPFA算法 734差分约束系统 74多源最短路径 741Floyd算法（弗洛伊德算法） 742Johnson算法 75最短路径在网络路由中的应用* 76本章小结 77习题 第8章回溯和分支限界 81回溯的基本方法 811回溯法的基本步骤 812回溯法的通用框架 82骑士巡游问题 830-1背包问题 84最大团问题 841最大团的回溯算法 842Bron-Kerbosch算法 85分支限界法 851基本方法 852旅行商问题 853任务指派问题 86分支限界在流水线作业调度中的应用* 87本章小结 88习题 第9章匹配与指派 91基本概念 92基于图的匈牙利算法 921匹配问题 922指派问题 93基于矩阵的匈牙利算法 931算法流程 932最大化指派 94匹配算法在多目标跟踪中的应用* 95本章小结 96习题 参考文献