![]()
内容推荐 算法是利用电脑解决问题的技巧。本书以轻松的对话方式,采用图解的辅助说明,帮助读者简单且自然地掌握算法的基本概念,并养成主动思考的习惯,达到用算法解决实际问题的目的。全书共分12章,内容包括一切从观察开始、分而治之法、动态规划、贪婪法、修剪与搜索法、树搜索法、问题转换、图算法、计算几何、算法的难题、逼近算法、随机算法等。本书示例丰富,图文并茂,以易于理解的方式阐释算法,帮助程序员在日常项目开发中更好地发挥算法的能量。 目录 推荐序 前 言 1 一切从观察开始 1.1 什么是算法 2 1.2 汉诺塔问题 3 1.3 汉诺塔问题的非递归算法 10 1.4 发现算法的技巧 16 学习效果评测 18 2 分而治之法 2.1 何谓分而治之法 20 2.2 找出优选值 21 2.3 时间复杂度 23 2.4 二维极点问题 25 2.5 快速排序法 30 2.6 快速排序法的时间复杂度 34 2.7 寻找第 k 小值问题 40 2.8 分而治之法的技巧 47 学习效果评测 48 3 动态规划 3.1 何谓动态规划 50 3.2 换零钱 50 3.3 数字金字塔 54 3.4 最长相同子字符串 58 3.5 安排公司聚会 64 3.6 动态规划的技巧 70 学习效果评测 72 4 贪婪法 4.1 何谓贪婪法 75 4.2 最小成本生成树 75 4.3 霍夫曼编码树 83 4.4 贪婪法的陷阱:0—1 背包问题 88 4.5 单位时间工作调度问题 90 4.6 证明贪婪法并介绍Matroid理论 96 4.7 贪婪法的技巧 99 学习效果评测 100 5 修剪与搜索法 5.1 何谓修剪与搜索法 103 5.2 找坏蛋问题 104 5.3 猜数字问题 105 5.4 约瑟夫问题 106 5.5 简化的线性规划问题 113 5.6 修剪与搜索法的技巧 119 学习效果评测 119 6 树搜索法 6.1 何谓树搜索法 122 6.2 树状解空间:n 个皇后问题 123 6.3 回溯法:涂色问题 126 6.4 广度优先搜索法:八数字谜题 128 6.5 加速技巧:旅行商问题 131 6.6 树搜索法的技巧 140 学习效果评测 141 7 问题转换 7.1 何谓问题转换 144 7.2 将相异代表系问题转换成二分图上的匹配问题 145 7.3 将二分图上的匹配问题转换成网络流图问题 147 7.4 将网络流图问题转换成线性规划问题 150 7.5 问题转换的技巧 152 学习效果评测 154 8 图算法 8.1 什么是图 156 8.2 连通分支 157 8.3 Dijkstra zui短路径算法 160 8.4 Bellman—Ford zui短路径算法 168 8.5 双连通分支 175 8.6 图算法的技巧 193 学习效果评测 195 9 计算几何 9.1 何谓计算几何 199 9.2 多边形中的点 200 9.3 天空轮廓 203 9.4 凸包 208 9.5 最近点对 215 9.6 计算几何的技巧 219 学习效果评测 220 10 算法的难题 10.1 什么是 NP—Complete 224 10.2 集合 P 和集合 NP 225 10.3 满足性问题 227 10.4 多项式时间转换 229 10.5 NP 中的难题 230 10.6 NP—Complete 的性质 234 10.7 NP—Complete 的证明技巧 237 学习效果评测 241 11 逼近算法 11.1 什么是逼近算法 244 11.2 最小顶点覆盖问题 244 11.3 装箱问题 247 11.4 平面上的旅行商问题 249 11.5 逼近算法的技巧 252 学习效果评测 252 12 随机算法 12.1 什么是随机算法 256 12.2 随机快速排序法 257 12.3 质数测试 258 12.4 最小割算法 259 12.5 随机算法技巧 265 学习效果评测 265 参考文献 |