可以朗读 语音朗读
136千字 字数
2023-09-01 发行日期
展开全部

主编推荐语

本书为“算法详解”系列之一。

内容简介

全书共有6章，主要介绍了快速识别NP-Hard问题的方法和处理NP的算法工具。本书的每一章均有小测验、章末习题，这为读者的自我检查以及进一步学习提供了方便。

本书提供了丰富而实用的资料，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生，想要培养和训练算法思维与计算思维的IT专业人士，以及正在准备面试的应聘者和面试官阅读参考。

目录

  • 版权信息
  • 内容提要
  • 前言
  • 致谢
  • 资源与支持
  • 第1章 什么是NP问题
  • 1.1 MST和TSP：算法的难解之谜
  • 1.1.1 最小生成树问题
  • 1.1.2 旅行商问题
  • 1.1.3 解决TSP的尝试和失败
  • 1.1.4 小测验1.1和小测验1.2的答案
  • 1.2 读者的不同专业层次
  • 1.3 容易的问题和困难的问题
  • 1.3.1 多项式时间的算法
  • 1.3.2 多项式时间与指数级时间
  • 1.3.3 容易的问题
  • 1.3.4 相对难以处理
  • 1.3.5 困难的问题
  • 1.3.6 P≠NP猜想
  • 1.3.7 NP问题的临时定义
  • 1.3.8 随机化和量子算法
  • 1.3.9 微妙性
  • 1.4 NP问题的算法策略
  • 1.4.1 通用、正确、快速（选择其二）
  • 1.4.2 通用性的妥协
  • 1.4.3 正确性的妥协
  • 1.4.4 最坏情况运行时间的妥协
  • 1.4.5 关键思路
  • 1.5 证明NP问题：一个简单的方案
  • 1.5.1 转化
  • 1.5.2 使用转化来设计快速算法
  • 1.5.3 使用转化对NP问题进行扩展
  • 1.5.4 无环最短路径是NP问题
  • 1.5.5 小测验1.3的答案
  • 1.6 新手错误和可接受的不准确说法
  • 1.7 本章要点
  • 1.8 章末习题
  • 1.8.1 挑战题
  • 1.8.2 编程题
  • 第2章 正确性的妥协：高效的不准确算法
  • 2.1 完成工时最小化
  • 2.1.1 问题定义
  • 2.1.2 贪心算法
  • 2.1.3 Graham算法
  • 2.1.4 运行时间
  • 2.1.5 近似的正确性
  • 2.1.6 定理2.1的证明
  • 2.1.7 最长处理时间优先（LPT）
  • 2.1.8 定理2.2的证明
  • 2.1.9 小测验2.1～2.3的答案
  • 2.2 最大覆盖
  • 2.2.1 问题定义
  • 2.2.2 更多的应用
  • 2.2.3 一种贪心算法
  • 2.2.4 GreedyCoverage算法的糟糕例子
  • 2.2.5 近似正确性
  • 2.2.6 一个关键的辅助结论
  • 2.2.7 定理2.3的证明
  • 2.2.8 小测验2.4和小测试2.5的答案
  • *2.3 影响最大化
  • 2.3.1 社交网络的瀑布模型
  • 2.3.2 例子
  • 2.3.3 影响最大化问题
  • 2.3.4 一种贪心算法
  • 2.3.5 近似正确性
  • 2.3.6 影响是覆盖函数的一个加权和
  • 2.3.7 定理2.4的证明
  • 2.3.8 小测验2.6的答案
  • 2.4 TSP的2-OPT启发式算法
  • 2.4.1 处理TSP
  • 2.4.2 通过2-变换改进路线
  • 2.4.3 2-OPT算法
  • 2.4.4 运行时间
  • 2.4.5 解决方案质量
  • 2.4.6 小测验2.7和小测验2.8的答案
  • 2.5 局部搜索的原则
  • 2.5.1 可行解决方案的元图（Meta-Graph）
  • 2.5.2 局部搜索算法设计范例
  • 2.5.3 三个建模决策
  • 2.5.4 两个算法设计决策
  • 2.5.5 运行时间和解决方案质量
  • 2.5.6 避免低质量的局部最优解
  • 2.5.7 什么时候应该使用局部搜索？
  • 2.5.8 小测验2.9和小测验2.10的答案
  • 2.6 本章要点
  • 2.7 章末习题
  • 2.7.1 挑战题
  • 2.7.2 编程题
  • 第3章 速度的妥协：准确的非高效算法
  • 3.1 TSP的Bellman-Held-Karp算法
  • 3.1.1 底线：穷举搜索
  • 3.1.2 动态规划
  • 3.1.3 最优子结构
  • 3.1.4 推导公式
  • 3.1.5 子问题
  • 3.1.6 Bellman-Held-Karp算法
  • 3.1.7 小测验3.1的答案
  • *3.2 通过颜色编码寻找最长路径
  • 3.2.1 动机
  • 3.2.2 问题定义
  • 3.2.3 子问题的初次试探
  • 3.2.4 颜色编码
  • 3.2.5 计算最低成本全色路径
  • 3.2.6 正确性和运行时间
  • 3.2.7 随机化挽救危局
  • 3.2.8 最终的算法
  • 3.2.9 运行时间和正确性
  • 3.2.10 再论PPI网络
  • 3.2.11 小测验3.2～3.4的答案
  • 3.3 问题特定的算法与万能魔盒
  • 3.3.1 转化和万能魔盒
  • 3.3.2 MIP和SAT解决程序
  • 3.3.3 将要学习的和不会学习的
  • 3.3.4 再论新手易犯的错误
  • 3.4 混合整数规划解决程序
  • 3.4.1 例子：背包问题
  • 3.4.2 更基本意义上的MIP
  • 3.4.3 MIP解决程序的一些起点
  • 3.5 可满足性解决程序
  • 3.5.1 示例：图形着色
  • 3.5.2 可满足性
  • 3.5.3 把图形着色问题表达为SAT
  • 3.5.4 SAT解决程序：一些起点
  • 3.6 本章要点
  • 3.7 章末习题
  • 3.7.1 挑战题
  • 3.7.2 编程题
  • 第4章 证明NP问题
  • 4.1 再论转化
  • 4.2 3-SAT问题和Cook-Levin定理
  • 4.3 整体思路
  • 4.3.1 再论新手易犯的错误
  • 4.3.2 18个转化
  • 4.3.3 为什么要啃艰涩的NP问题证明？
  • 4.3.4 小测验4.1的答案
  • 4.4 一个转化模板
  • 4.5 独立子集问题是NP问题
  • 4.5.1 主要思路
  • 4.5.2 定理4.2的证明
  • *4.6 有向汉密尔顿路径问题是NP问题
  • 4.6.1 变量的编码和真值指派
  • 4.6.2 约束条件的编码
  • 4.6.3 定理4.3的证明
  • 4.7 TSP是NP问题
  • 4.7.1 无向汉密尔顿路径问题
  • 4.7.2 定理4.4的证明
  • 4.8 子集求和问题是NP问题
  • 4.8.1 基本方法
  • 4.8.2 例子：4顶点环路
  • 4.8.3 例子：5顶点环路
  • 4.8.4 定理4.5的证明
  • 4.9 本章要点
  • 4.10 章末习题
  • 挑战题
  • 第5章 P、NP及相关概念
  • *5.1 难处理性的累积证据
  • 5.1.1 通过转化创建一个案例
  • 5.1.2 为TSP选择集合C
  • *5.2 决策、搜索和优化
  • *5.3 NP：具有容易识别的解决方案的问题
  • 5.3.1 复杂类NP的定义
  • 5.3.2 NP中的问题实例
  • 5.3.3 NP问题是可以通过穷举搜索解决的
  • 5.3.4 NP问题
  • 5.3.5 再论Cook-Levin定理
  • 5.3.6 小测验5.1的答案
  • *5.4 P≠NP猜想
  • 5.4.1 多项式时间可解决的NP问题
  • 5.4.2 P≠NP猜想的正式定义
  • 5.4.3 P≠NP猜想的状态
  • *5.5 指数级时间假设
  • 5.5.1 NP问题需要指数级的时间吗？
  • 5.5.2 强指数级时间假设（SETH）
  • 5.5.3 容易问题的运行时间下界
  • *5.6 NP完全问题
  • 5.6.1 Levin转化
  • 5.6.2 NP中最难的问题
  • 5.6.3 NP完全问题的存在
  • 5.7 本章要点
  • 5.8 章末习题
  • 挑战题
  • 第6章 案例研究：FCC激励拍卖
  • 6.1 无线频谱再利用
  • 6.1.1 从电视到移动电话
  • 6.1.2 无线频谱的一次最近重分配
  • 6.2 回购执照的启发式贪心算法
  • 6.2.1 4个临时的简化假设
  • 6.2.2 遭遇加权独立子集问题
  • 6.2.3 启发式贪心算法
  • 6.2.4 多频道情况
  • 6.2.5 遭遇图形着色问题
  • 6.2.6 小测验6.1的答案
  • 6.3 可行性检查
  • 6.3.1 改编为可满足性问题
  • 6.3.2 加入边际约束条件
  • 6.3.3 重新安置问题
  • 6.3.4 技巧#1：预解决程序（寻求一种容易的解决之道）
  • 6.3.5 技巧#2：预处理和简化
  • 6.3.6 技巧#3：SAT解决程序的组合
  • 6.3.7 容忍失败
  • 6.3.8 小测验6.2的答案
  • 6.4 降序时钟拍卖的实现
  • 6.4.1 拍卖和算法
  • 6.4.2 例子
  • 6.4.3 重新实现FCCGreedy算法
  • 6.4.4 是时候提供补偿了
  • 6.5 最终结果
  • 6.6 本章要点
  • 6.7 章末习题
  • 6.7.1 挑战题
  • 6.7.2 编程题
  • 后记 算法设计实战指南
  • 附录 问题提示和答案
展开全部

评分及书评

尚无评分
目前还没人评分

出版方

人民邮电出版社

人民邮电出版社是工业和信息化部主管的大型专业出版社，成立于1953年10月1日。人民邮电出版社坚持“立足信息产业、面向现代社会、传播科学知识、服务科教兴国”，致力于通信、计算机、电子技术、教材、少儿、经管、摄影、集邮、旅游、心理学等领域的专业图书出版。