本书旨在讲解数据结构和算法的核心知识。本书主要内容包括线性表、栈、队列、串、数组、广义表、树、图、查找算法、排序算法、递推算法、递归算法、枚举算法、贪心算法、回溯算法、数值算法和实用算法等。本书适合计算机专业的学生、软件开发专业人员等阅读。
电子书
内容简介
算法详解系列图书共有4卷，本书是第4卷——NP-Hard问题算法。全书共有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 编程题
- 后记 算法设计实战指南
- 附录 问题提示和答案
展开全部
算法详解（卷4）——NP-Hard问题算法是2023年由人民邮电出版社出版,作者蒂姆·拉夫加登（Tim。
温馨提示：
1.本电子书已获得正版授权，由出版社通过知传链发行。
2.该电子书为虚拟物品，付费之后概不接收任何理由退款。电子书内容仅支持在线阅读，不支持下载。
3.您在本站购买的阅读使用权仅限于您本人阅读使用，您不得/不能给任何第三方使用，由此造成的一切相关后果本平台保留向您追偿索赔的权利！版权所有，后果自负！
得书感谢您对《算法详解（卷4）——NP-Hard问题算法》关注和支持，如本书内容有不良信息或侵权等情形的，请联系本网站。
电子书
电子书
增强了剥削的算法，难道不懂歧视吗？看似中立的人工智能技术，是如何一步步蚕食劳动者的生存空间的？被平台剥夺了话语权的劳动者，如何摆脱“算法领导”？人工智能是一种看似中立的技术，但它越来越多地被用于管理劳动力，做出聘用和解聘员工的决定。它在工作场所的普及让人以为，管理体系变得更加公平有效了。毕竟，算法是“不懂”歧视的。本书探讨了人工智能对工人生活的现实影响。本书认为，人工智能与资本主义下的大多数技术一
电子书
本书从算法设计策略和算法实际应用两方面入手，介绍了6类常用的算法：蛮力法、分治法、贪心法、动态规划法、回溯法和分支限界法。本书以“算法设计基础知识+算法经典应用案例”为主线，讲解了各章内容，分析了各类算法的特点，帮助读者理解算法的基本概念、掌握算法的关键设计步骤和了解算法所适用的问题。
电子书
本书以作者在算法设计领域的研究成果为基础，给出了求解批调度问题的一系列组合算法，以及求解网络优化问题的若干组合算法。主要研究了极小化加权完工时间和、**大延迟和**大完工时间3种调度目标函数，以及网络中的呼叫接纳、利润极大化和t区间的k染色问题等。本书可作为从事调度理论、组合**优化、算法设计与应用科技人员的参考书。
电子书
本书共分9章，内容包括：算法设计基础、算法效率分析基础、迭代法、蛮力法、分治法、回溯法与分支界限法、贪心算法、动态规划、随机算法。
电子书
本书旨在为读者建立完整的深度学习知识体系。全书内容包含3个部分，第一部分为与深度学习相关的数学基础；第二部分为深度学习的算法基础以及相关实现；第三部分为深度学习的实际应用。
电子书
本书内容包括：算法初步、排序算法、查找、双指针问题、哈希算法、深度优先搜索算法、广度优先搜索算法、回溯算法、动态规划、贪心算法、分治算法、并查集、最短路径算法和数论算法等常见算法。
电子书
本书凝聚了作者多年的Python教学经验，内容通俗易懂，旨在剖析递归及其本质。本书不仅结合Python程序和JavaScript程序讲述编程的基础知识，还讲述如何利用递归算法计算阶乘，计算斐波那契数列，遍历树，求解迷宫问题，实现二分搜索，完成快速排序和归并排序，计算大整数乘法，计算排列和组合，解决八皇后问题等。本书不仅适合开发人员阅读，还可供计算机相关专业的师生参考。
