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

图书信息

作者	蒂姆·拉夫加登(Tim Roughgarden) 著
出版社	人民邮电出版社有限公司
ISBN	9787115563347
出版时间	2023-07-01
字数	12.3万
分类	科技,计算机,网络,程序设计

读书简介

“算法详解”系列图书共有4卷，本书是第3卷—贪心算法和动态规划。其中贪心算法主要包括调度、最小生成树、聚类、哈夫曼编码等，动态规划主要包括背包、序列对齐、最短路径、最佳搜索树等。本书的每一章均有小测验和章末习题，这将为读者的自我检查以及一步学习提供方便。 本书作者提供丰富而实用的资源，能够帮助读者提升算法思维能力。

目录

内容提要

前 言

服务与支持

提交勘误信息

与我们联系

关于异步社区和异步图书

第1章 贪心算法概述

1.1 贪心算法设计范例

1.2 一个调度问题

1.3 开发一种贪心算法

1.4 正确性证明

1.5 本章要点

1.6 章末习题

第2章 哈夫曼编码

2.1 编码

2.2 编码和树

2.3 哈夫曼的贪心算法

*2.4 正确性证明

2.5 本章要点

2.6 章末习题

第3章 最小生成树

3.1 问题定义

3.2 Prim算法

*3.3 通过堆提升Prim算法的速度

*3.4 Prim算法：正确性证明

3.5 Kruskal算法

*3.6 通过合并查找对Kruskal算法进行加速

*3.7 Kruskal算法的正确性证明

3.8 应用：单链集群

3.9 本章要点

3.10 章末习题

第4章 动态规划概述

4.1 加权独立集合问题

4.2 路径图的WIS问题的线性时间算法

4.3 一种重建算法

4.4 动态规划的原则

4.5 背包问题

4.6 本章要点

4.7 章末习题

第5章 高级动态规划

5.1 序列对齐

*5.2 最优二叉搜索树

5.3 本章要点

5.4 章末习题

第6章 再论最短路径算法

6.1 边长可能为负的最短路径

6.2 Bellman-Ford算法

6.3 所有顶点对的最短路径问题

6.4 Floyd-Warshall算法

6.5 本章要点

6.6 章末习题

附录 章末习题答案节选

后记 算法设计工作指南