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

目　　录





第 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