《算法之道》精华 难解问题部分

• 本书作者邹恒明，作者另有一本书《数据结构之弦》，以及《操作系统之哲学原理》都是很好的书
• 这本书可以算得上是深入浅出，文笔很好，作者添加了很多自己的思考
• 本文包括难解问题部分

第十三章 易解与难解

• 易解指的是多项式问题，难解指的是指数级问题
• 决策问题
  • 需要输出答案是/否
  • 若回答为是，通常需要一个证人来证明。对一个潜在证人，证明之后即为真证人
  • 优化问题和决策问题之间可以相互转化
• P类问题
  • 确定性多项式时间可解
  • 对于一个决策问题，输入的大小为n，能在n的多项式时间内解决，正确输出是/否
• NP类问题
  • 非确定性多项式时间可解
  • 对于一个决策问题，大小为n的潜在证人，能在n的多项式时间内解决，正确输出此证人是否为真
  • P类问题指的是能否多项式时间给出答案，NP类问题指的是能否在多项式时间内判断一个潜在答案是否正确
• （确定性）图灵机
  • 图灵机为一个状态机，根据当前状态、下一个输入字符确定输出、磁头移动方向、下一个状态
  • 任一个问题、算法都能表述为一个字符串，因此图灵机可以解决很多问题
• 非确定性图灵机
  • 与确定性图灵机相比，给定状态与输入可以有多种选择
  • 能够同时进入所有状态路径，且能做出最好的选择以达到接受状态
  • 非确定性算法：在非确定性图灵机上运行的算法
  • NP问题的另一个定义：使用非确定性算法，在多项式时间内解决
• P与NP的关系
  • 所有P类问题都是NP的
  • 所有NP不一定是P，直觉如此，但无法证明
  • 部分NP为P，目前已经找到多项式解法，目前没有找到多项式解法的NP问题称为NP-hard

第十四章 NP完全问题

• 如果NP里每一个问题都可以多项式时间规约到S，则S称为NP难（严谨的定义）。S不比NP里面任一问题容易
• 如果问题S既是NP难，又是NP里的问题，则称为NP完全问题
• NP完全的属性
  • 非确定性算法多项式时间可解
  • 完全：解决一个就解决了所有NP完全问题
• 若找到一个NP完全问题的确定性解法，就证明了NP=P
• 若找到一个NP难优化问题的多项式时间解，就证明了NP=P
• NP完全的意义：若能证明一个问题为NP完全问题，则无需再寻找精确解，找到启发性的近似解即可
• 常见NP完全问题
  • 3-SAT
  • 整数分割
  • 顶点覆盖
  • 汉密尔顿回路 可规约至旅行商问题
  • 完全子图
  • 图的着色
  • 旅行商
  • 整数规划属于NP难问题，但不是NP问题，因此不是NP完全问题

第十五章 无解与近似

• NP完全只是NP里最难的问题，目前没有找到多项式解法
• 难解问题不存在多项式解法
• 不可决定问题：是无解的，即使是指数级也无济于事。但又潜在证人
• 对于NP完全和难解问题，可以尝试找出次优解
  • 智能穷举
    • 能找的最优解
    • 两种剪枝策略：回溯法、分支限界
    • 如八皇后问题
  • 近似算法
    • 能找到近似的解
    • 如聚类问题、启发式搜索、模拟退火、遗传算法
  • 本地搜索
    • 一种贪婪策略
    • 不断向更优的可行解移动，可能仅能找到局部最优解