内容简介
本书分为回溯法、图、动态规划、网格等部分。回溯法部分介绍单向搜索和双向搜索，给出高级搜索的技巧；图部分分为图遍历和图算法章节，先介绍图遍历的方法，再以最小生成树问题、单源最短路径问题、多源最短路径问题、网络流问题中的经典算法为例，介绍了十余种算法的原理和相关应用；动态规划部分逐一介绍了集合型、区间型、图论型、概率型、非典型动态规划，并介绍了空间、时间上的优化技巧，以及相应的备忘、松弛技巧；网格部分作为独立的专题汇集了与网格相关的各种习题。
展开全文
- 版权信息
- 版 权
- 内容提要
- 序
- 前 言
- 资源与支持
- 第1章 回溯法
- 1.1 八皇后问题
- 1.2 搜索
- 1.2.1 单向搜索
- 1.2.2 双向搜索
- 1.3 剪枝
- 1.3.1 正方形剖分
- 1.3.2 关灯问题
- 1.4 15数码问题
- 1.5 小结
- 第2章 图和图遍历
- 2.1 基本概念
- 2.1.1 图的属性
- 2.1.2 欧拉公式
- 2.1.3 路与连通
- 2.2 图的表示
- 2.2.1 邻接矩阵
- 2.2.2 边列表和前向星
- 2.2.3 邻接表
- 2.2.4 链式前向星
- 2.3 图遍历
- 2.3.1 广度优先遍历
- 2.3.2 深度优先遍历
- 2.4 图遍历的应用
- 2.4.1 图的连通性
- 2.4.2 最短路径
- 2.4.3 最长简单路径
- 2.4.4 图的着色
- 2.4.5 最近公共祖先
- 2.4.6 割顶
- 2.4.7 割边
- 2.4.8 强连通分支
- 2.4.9 半连通分支
- 2.4.10 2-SAT
- 2.4.11 图的直径
- 2.4.12 树的重心
- 2.5 拓扑排序
- 2.6 小结
- 第3章 图算法
- 3.1 基本概念
- 顶点度
- 3.2 图的回路
- 3.2.1 欧拉回
- 3.2.2 中国投递员问题
- 3.2.3 哈密顿回
- 3.2.4 旅行商问题
- 3.3 最小生成树
- 3.3.1 Prim算法
- 3.3.2 Kruskal算法
- 3.3.3 最小生成树的扩展问题
- 3.3.4 度限制最小生成树
- 3.3.5 次最优最小生成树
- 3.4 最短路径问题
- 3.4.1 Moore-Dijkstra算法
- 3.4.2 Bellman-Ford算法
- 3.4.3 Floyd-Warshall算法
- 3.4.4 传递闭包
- 3.4.5 最小化的最大距离
- 3.4.6 差分约束系统
- 3.4.7 第K短路径问题
- 3.5 网络流问题
- 3.5.1 基本概念
- 3.5.2 Ford-Fulkerson方法
- 3.5.3 Edmonds-Karp算法
- 3.5.4 Dinic算法
- 3.5.5 ISAP算法
- 3.5.6 最小截问题
- 3.5.7 最小费用最大流问题
- 3.6 边独立集与二部图匹配
- 3.6.1 网络流解法
- 3.6.2 Hungarian算法
- 3.6.3 Hopcroft-Karp算法
- 3.6.4 Gale-Shapley算法
- 3.6.5 Edmonds算法
- 3.7 二部图加权完备匹配
- 3.7.1 网络流解法
- 3.7.2 Kuhn-Munkres算法
- 3.8 点支配集、点覆盖集、点独立集
- 3.8.1 点支配集
- 3.8.2 点覆盖集
- 3.8.3 点独立集与最大团
- 3.9 路径覆盖和边覆盖
- 3.9.1 最小路径覆盖
- 3.9.2 最小边覆盖
- 3.10 树的相关问题求解
- 3.10.1 最小点支配
- 3.10.2 最小点覆盖
- 3.10.3 最大点独立
- 3.11 小结
- 第4章 动态规划
- 4.1 背包问题
- 4.1.1 01背包问题
- 4.1.2 完全背包问题
- 4.1.3 多重背包问题
- 4.1.4 背包问题扩展
- 4.2 备忘
- 4.2.1 3n + 1问题
- 4.2.2 正交范围查询
- 4.2.3 最大正方形（长方形）
- 4.2.4 整数划分
- 4.2.5 博弈树
- 4.2.6 备忘与递推
- 4.3 松弛
- 4.3.1 Moore-Dijkstra算法
- 4.3.2 Bellman-Ford算法
- 4.3.3 Floyd-Warshall算法
- 4.4 集合型动态规划
- 4.5 区间型动态规划
- 4.5.1 矩阵链乘法
- 4.5.2 石子合并问题
- 4.6 图论型动态规划
- 4.6.1 路径计数
- 4.6.2 树形动态规划
- 4.6.3 旅行商问题
- 4.6.4 双调欧几里得旅行商问题
- 4.7 概率型动态规划
- 4.8 非典型动态规划
- 4.9 动态规划的优化
- 4.9.1 空间优化
- 4.9.2 状态优化
- 4.9.3 二进制优化
- 4.9.4 单调队列优化
- 4.9.5 斜率优化
- 4.9.6 四边形不等式优化
- 4.10 子序列和子串问题
- 4.10.1 最短编辑距离
- 4.10.2 最长公共子序列
- 4.10.3 最长公共子串
- 4.10.4 最长递增子序列
- 4.10.5 最长不重复子串
- 4.10.6 最长回文子串
- 4.10.7 最大连续子序列和（积）
- 4.11 贪心算法
- 4.11.1 部分背包问题
- 4.11.2 纸币找零问题
- 4.11.3 硬币兑换问题
- 4.11.4 霍夫曼编码
- 4.11.5 最优策略选择
- 4.12 小结
- 第5章 网格
- 5.1 矩形网格
- 5.1.1 网格行走
- 5.1.2 Flood-Fill算法
- 5.1.3 国际象棋棋盘
- 5.1.4 骑士周游问题
- 5.2 三角形网格
- 5.3 六边形网格
- 5.4 经度与纬度
- 5.5 小结
- 附录A 如何使用UVa OJ
- A.1 注册
- A.2 提交
- 附录B ASCII表
- 附录C C++运算符优先级
- 参考资料
展开全部
版权信息
出版社：人民邮电出版社
出版时间：2022
作者：邱秋 编著
温馨提示：
1.本电子书已获得正版授权，由出版社通过知传链发行。
2.该电子书为虚拟物品，付费之后概不接收任何理由退款。电子书内容仅支持在线阅读，不支持下载。
3.您在本站购买的阅读使用权仅限于您本人阅读使用，您不得/不能给任何第三方使用，由此造成的一切相关后果本平台保留向您追偿索赔的权利！版权所有，后果自负！
得书感谢您对《程序设计竞赛训练营：算法与实践》关注和支持，如本书内容有不良信息或侵权等情形的，请联系本网站。
出版时间：2022
作者：邱秋 编著
温馨提示：
1.本电子书已获得正版授权，由出版社通过知传链发行。
2.该电子书为虚拟物品，付费之后概不接收任何理由退款。电子书内容仅支持在线阅读，不支持下载。
3.您在本站购买的阅读使用权仅限于您本人阅读使用，您不得/不能给任何第三方使用，由此造成的一切相关后果本平台保留向您追偿索赔的权利！版权所有，后果自负！
得书感谢您对《程序设计竞赛训练营：算法与实践》关注和支持，如本书内容有不良信息或侵权等情形的，请联系本网站。
程序设计竞赛训练营：算法与实践
免费读 (VIP)