《Python Algorithm》11.疑难问题

《Python Algorithm》11.疑难问题本期主题“刑事案件量刑中的疑难问题”,以问答形式解读11个刑事案件量刑疑难问 题。

《Python Algorithm》11.疑难问题和（有限的）马虎

• 引言
  • 本章结构
    • 解释世界上最大的悬而未决的基本问题
    • 根据这些思想展示一些困难的问题
    • 跟随Voltaire的智慧，松弛你的需求，使靠近目标成为可能
• 归约重提
  • 例
    • 如果想要证明X难，找到某个难问题Y，归约到X
  • hard消歧义
    • 问题很难，任何算法解决它都是指数级
      • 对计算机难
    • 问题是否难以解决不知道，但还没有找到多项式级的算法
      • 对人难
  • sidebar
    • 子问题归约
      • 如果问题包括一个难的子问题，问题整体也难
• Not in Kansas Anymore?
  • 出处
    • 《绿野仙踪》（1939）
  • P=NP?
    • 回答是/否的决策问题可以很快验证，其答案是否可以很快计算
  • P
    • 可以在多项式时间（最坏）解决的问题
  • NP
    • 描述
      • 可以被用被称为非确定图灵机（NTM）这个魔法计算法以多项式时间解决的
      • 考虑解决问题和检查解决方案的区别
    • NTM
      • 任何时间要选择时，总能猜对
• 同时，回到Kansas
  • NPC
    • NP完全问题
    • NP问题中最难的
    • 我们不知道他们是否难处理，如果解决了一个，就是解决了所有
    • c是NPC
      • c本身是NP
      • 每个NP问题可以以多项式时间归约到c
    • 完全性
    • NP-hard问题
      • NPC包括NP中所有NP-hard问题
      • NP-hard问题
        • 最短路：旅行商问题
    • 注意
      • 一些上下文中，人们把NP-hard问题称为NP完全问题
  • sidebar
    • 不对称，CO-NP和算法奇迹
      • NP类被定义的不对称
        • 包括NTM能以多项式时间解决的所有“是”的答案
          • 找选择到答案的计算
        • 没有提及“否”的答案
          • 需要确定有没有这样的计算存在？
      • co-NP
        • 互补NP问题
        • 对于每个“是”，需要“否”，反之亦然
        • 如果找到单个NP完全问题在NP和co-NP交集
          • NP=co-NP
            • 不对称消失
• 从哪里来？到哪里去？
  • 第一个NP完全问题
    • 布尔可满足性问题（SAT）
    • Cook-Levin定理
      • 证明
        • 使用逻辑公式，询问有什么方法使之为真
        • 合取范式CNF
  • k-CNF-SAT问题
    • k>2
    • 简化：k-SAT
  • Circuit SAT
  • 哈密顿图
    • 简单的NP完全问题
    • Ch5
    • 创建SAT解决机制
  • sidebar
    • 2-SAT是NP完全问题么？谁知道……
    • 一个永不停歇的故事
      • Complexity Zoo
      • 停机问题
• 动物园里的怪物
  • 概述
    • 本节介绍一些知名的NP完全问题
    • 目的
      • 给出一些难题的概览以便你更容易认识编程中遇到问题的难度
      • 给一些例子说明如何证明难度
  • 回到背包问题
    • 问题
      • 选择子集
    • 背包问题和他的小伙伴们
      • 划分问题
        • 一组数（比如整数），划分成两个和相等的列表
      • 装箱问题
        • 有一组货物，大小0-k间
        • 我们希望将其装入大小k的集装箱中
      • 子集和问题
        • 一组数，找到一个子集使其和为给定的常数k
      • 背包问题（整数）
    • 整数规划
      • 线性规划第一个分支
  • 分团与着色
    • 着色问题
      • 两色
        • 二部图
      • 三色
        • 方法
      • k色
        • k>2
        • NP完全问题
    • 分团覆盖问题
      • 分团：一个完整的图形
      • 相关
        • 独立集问题
      • 找到k分团覆盖问题等同k着色
      • 顶点覆盖问题
      • 集合覆盖问题
  • 路径和回路
    • 方向
      • 有向和无向哈密顿图是等价的
    • 最长路径问题
      • 检查是否是哈密顿图
    • 最短路径问题
      • 通常情况下，等同于最长路径
      • 然而，最短路径不允许负值，即不允许最长路径正值
        • 归约失败，不能说明是NP-hard
        • 实际上不是
    • 旅行商问题（TSP）
      • 多数是NP-hard的
      • 带权无向图，找到路径通过所有节点，加权和尽可能小
        • 最小费用哈密顿图
      • 通用版本
        • 图是完整的
          • 一般也是哈密顿图
        • 归约不管用
      • 度量旅行商问题
        • 度量是距离函数d(a,b)
          • 测量a，b两点距离
          • 不是直线或欧式距离
        • d(a,c) <= d(a,b) + d(b,c)
        • 有多项式近似的算法
• 前路漫漫，大智若愚
  • 小调整可以极大改善难题
    • 本节：在你寻找最优解时允许一定程度的“马虎”
    • 下节：算法设计的“祈祷”学校
  • 澄清近似的想法
    • 允许算法找到一个不是最优但在一定比例范围最好的解
    • 比例
      • factor
      • 近似比
  • 背包问题
    • 无界整数背包问题可用一个因子2通过贪心法近似
    • 正确性验证
    • 定上界
    • 定下界
  • 近似算法
    • 关键点
      • 不知道通往最优的确切比率
      • 只能给出一个保证最坏如何
      • 如果能评估能得到的最优有多好，可以使用它替代实际最优
    • 参考文献
      • Approximation Algorithms, by Vijay V. Vazirany
  • 度量TSP问题
    • 找到一些无效的，乐观的方案
    • 调整，直到得到合法的方案
    • 最小生成树
    • 最重要的事
      • 忽略回溯，取得捷径
    • 代码实现
      • Twice around the tree
    • Christofides算法
      • 取代便利树的边两次
      • 在生成树的奇度点创建一个最小费用匹配
• 拼命寻找解决方案
  • 方法
    • 可以创建一个简单粗暴的方法，但是进行一些猜测避免过多的计算
  • 保证运行时间
    • 像快排，最坏时间很差，但平均时间很好
  • 可用算法
    • A*
    • 人工进化
    • 模拟退火
    • 分支定界
      • 特殊版本
        • alpha-beta剪枝
      • 解决NP-hard问题的重要工具
      • 考虑0-1背包问题
• 故事的寓意是
  • 建议
    • 遵从Ch4的两条建议
      • 是否真的理解问题了？
      • 是否到处去找归约在哪？
    • 如果被难住，再看看归约，但从NP-hard问题而不是已知如何解决的问题考虑
      • 如果发现，说明问题很难
    • 考虑Ch4最后一点建议
      • 能探索额外的假设使问题变小么？
    • 可以松弛么？
      • 如果不是要求百分百最优，也许有近似算法可用
  • 代码
    • 使用分支定界法解决背包问题
• 扩展阅读
  • 元启发式方法
  • 遗传编程