算法详解 卷3 贪心算法和动态规划

“算法详解”系列图书共有4卷，本书是第3卷—贪心算法和动态规划。其中贪心算法主要包括调度、最小生成树、聚类、哈夫曼编码等，动态规划主要包括背包、序列对齐、最短路径、最佳搜索树等。本书的每一章均有小测验和章末习题，这将为读者的自我检查以及进一步学习提供方便。 本书作者提供丰富而实用的资源，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生、想要培养和训练算法思维、计算思维的IT专业人士，以及面试官和正在准备面试的应聘者阅读、参考。

蒂姆·拉夫加登（Tim Roughgarden）是哥伦比亚大学计算机科学系的教授，之前曾任教于斯坦福大学计算机科学系，他从2004年开始教授和研究算法。本书是他的《算法详解》四部曲的第三卷，基于他从2012年开始定期举行的在线算法课程编写。

目　　录 第 1章　贪心算法概述 1 1.1　贪心算法设计范例 1 1.1.1　算法设计范例 1 1.1.2　贪心算法设计范例的特性 2 1.2　一个调度问题 4 1.2.1　问题的设定 4 1.2.2　竞争时间 4 1.2.3　目标函数 5 1.2.4　小测验1.1的答案 6 1.3　开发一种贪心算法 6 1.3.1　两种特殊情况 7 1.3.2　贪心算法之间的竞争 7 1.3.3　小测验1.2～1.3的答案 10 1.4　正确性证明 11 1.4.1　没有平局时的情况：高层计划 12 1.4.2　在相邻逆序对中交换作业 13 1.4.3　成本收益分析 14 1.4.4　处理平局的情况 15 1.4.5　小测验1.4～1.5的答案 17 1.5　本章要点 18 1.6　章末习题 19 第 2章　哈夫曼编码 21 2.1　编码 21 2.1.1　固定长度的二进制编码 21 2.1.2　可变长度的编码 22 2.1.3　非前缀编码 23 2.1.4　非前缀编码的优点 23 2.1.5　问题定义 24 2.1.6　小测验2.1～2.2的答案 25 2.2　编码和树 26 2.2.1　3个例子 26 2.2.2　什么样的树表示非前缀编码 28 2.2.3　问题定义（精练版） 28 2.3　哈夫曼的贪心算法 29 2.3.1　通过连续的归并创建树 29 2.3.2　哈夫曼的贪心准则 32 2.3.3　伪码 32 2.3.4　例子 34 2.3.5　一个更复杂的例子 34 2.3.6　运行时间 37 2.3.7　小测验2.3的答案 37 *2.4　正确性证明 38 2.4.1　高层计划 38 2.4.2　细节 39 2.5　本章要点 44 2.6　章末习题 45 第3章　最小生成树 47 3.1　问题定义 47 3.1.1　图 47 3.1.2　生成树 48 3.1.3　小测验3.1的答案 50 3.2　Prim算法 51 3.2.1　例子 51 3.2.2　伪码 53 3.2.3　简单的实现 55 *3.3　通过堆提升Prim算法的速度 56 3.3.1　探求接近线性的运行时间 56 3.3.2　堆数据结构 56 3.3.3　如何在Prim算法中使用堆 57 3.3.4　基于堆的实现的伪码 59 3.3.5　运行时间分析 61 3.3.6　小测验3.3的答案 61 *3.4　Prim算法：正确性证明 62 3.4.1　最小瓶颈属性 62 3.4.2　生成树的一些有趣结论 65 3.4.3　定理3.4（MBP意味着MST）的证明 67 3.4.4　综合运用 69 3.5　Kruskal算法 69 3.5.1　例子 69 3.5.2　Kruskal算法的伪码 71 3.5.3　Kruskal算法的简单实现 72 *3.6　通过合并查找对Kruskal算法进行加速 73 3.6.1　合并查找数据结构 73 3.6.2　基于合并查找的实现的伪码 75 3.6.3　基于合并查找的实现的运行时间分析 76 3.6.4　合并查找的快速有余而严谨不足的实现：父图 77 3.6.5　小测验3.5～3.7的答案 82 *3.7　Kruskal算法的正确性证明 83 3.8　应用：单链集群 85 3.8.1　集群 85 3.8.2　自底向上的集群 86 3.9　本章要点 88 3.10　章末习题 89 第4章　动态规划概述 93 4.1　加权独立集合问题 94 4.1.1　问题定义 94 4.1.2　自然的贪心算法失败了 95 4.1.3　分治算法可行吗 96 4.1.4　小测验4.1～4.2的答案 97 4.2　路径图的WIS问题的线性时间算法 98 4.2.1　最优子结构和推导公式 98 4.2.2　一种不成熟的递归方法 100 4.2.3　使用缓存的递归算法 101 4.2.4　一种迭代式的自底向上的实现 103 4.2.5　小测验4.3～4.4的答案 104 4.3　一种重建算法 105 4.4　动态规划的原则 107 4.4.1　3个步骤的配方 107 4.4.2　子问题的期望属性 108 4.4.3　一个可重复的思维过程 109 4.4.4　动态规划和分治算法的区别 109 4.4.5　为什么叫“动态规划” 110 4.5　背包问题 111 4.5.1　问题定义 111 4.5.2　最优子结构和推导公式 113 4.5.3　子问题 115 4.5.4　一种动态规划算法 115 4.5.5　例子 117 4.5.6　重建 117 4.5.7　小测验4.5～4.6的答案 118 4.6　本章要点 119 4.7　章末习题 120 第5章　高级动态规划 123 5.1　序列对齐 123 5.1.1　驱动力 123 5.1.2　问题定义 124 5.1.3　最优子结构 126 5.1.4　推导公式 129 5.1.5　子问题 129 5.1.6　一种动态规划算法 130 5.1.7　重新构建 131 5.1.8　小测验5.1～5.3的答案 132 *5.2　最优二叉搜索树 133 5.2.1　二叉搜索树回顾 134 5.2.2　平均搜索时间 135 5.2.3　问题定义 136 5.2.4　最优子结构 137 5.2.5　推导公式 141 5.2.6　子问题 142 5.2.7　一种动态规划算法 143 5.2.8　改善运行时间 145 5.2.9　小测验5.4～5.5的答案 145 5.3　本章要点 146 5.4　章末习题 147 第6章　再论最短路径算法 150 6.1　边长可能为负的最短路径 150 6.1.1　单源最短路径问题 150 6.1.2　负环 152 6.1.3　小测验6.1的答案 154 6.2　Bellman-Ford算法 154 6.2.1　子问题 155 6.2.2　最优子结构 156 6.2.3　推导公式 158 6.2.4　什么时候应该停止 159 6.2.5　伪码 160 6.2.6　Bellman-Ford算法的例子 161 6.2.7　Bellman-Ford算法的运行时间 164 6.2.8　Internet路由 165 6.2.9　小测验6.2～6.3的答案 165 6.3　所有顶点对的最短路径问题 166 6.3.1　问题定义 166 6.3.2　简化为单源最短路径 167 6.3.3　小测验6.4的答案 168 6.4　Floyd-Warshall算法 168 6.4.1　子问题 168 6.4.2　最优子结构 170 6.4.3　伪码 172 6.4.4　检测负环 174 6.4.5　Floyd-Warshall算法的总结和开放性问题 175 6.4.6　小测验6.5～6.6的答案 176 6.5　本章要点 177 6.6　章末习题 178 附录　章末习题答案节选 180 后记　算法设计工作指南 187