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

作者: [美] 蒂姆·拉夫加登（Tim Roughgarden）

出版社: 人民邮电出版社

出版时间: 2023-07

版次: 1

ISBN: 9787115563347

定价: 69.80

装帧: 平装

开本: 其他

纸张: 胶版纸

页数: 188页

字数: 190千字

分类: 计算机与互联网

3 张插图图片

8人买过

“算法详解”系列图书共有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
内容简介:
“算法详解”系列图书共有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