《Python Algorithm》4.归纳、递归、归约

《Python Algorithm》4.归纳、递归、归约 python归纳算法_【Python算法】归纳、递归、归简 归简法(reduction) 指的是将某一问题转化成另一个问题,将一个未知问题归简成一个已解决的问题。

《Python Algorithm》4.归纳、递归、归约

• 术语
  • reduction（归约）
    • 转换一个未知问题A为已知问题B来解决
    • 可能涉及输入和/或输出
  • induction（归纳/数归）
    • 首先说明一个基础情况为真，然后证明n为真时n+1为真
  • recursion（递归）
    • 一个函数调用自己
• 噢，那很简单！
  • 示例
    • 目的
      • 找出一组数中最接近的两个
    • 方法
      • 两层循环逐一对比
      • 排序后比较前后值
  • 说明如何将问题A转换成问题B求解，即归约
• 1，2，许多
  • 示例
    • 奇数和
    • 树
    • 用L型块覆盖一个缺一角的n阶（n=2**k）棋盘
  • 说明归纳法和分治算法
• 镜像，镜像
  • 递归是归纳的镜像
  • 代码实现
    • L型覆盖棋盘问题
    • 排序（递归/迭代）
      • 插入排序
        • 假设前面n-1个已排序，插入第n个
      • 选择排序
        • 找出最大的元素放到第n位
  • 递归深度限制
    • Python：1000次
    • 尾递归优化
  • 任何递归都可以写成迭代，反之亦然
  • sidebar
    • Where is the reduction?
• 使用归纳和递归设计
  • 找到一个最佳排列
    • 问题
      • 8个人买了8张电影票，找到合适的位置使最满意
      • 这是一个匹配问题
        • 更多见Ch10
    • 偶图（Bipartite graph）
      • 顶点可分成两个不相交的集使同一集合顶点不相邻的图
    • 代码实现
      • 方法
        • 递归
        • 迭代（使用引用计数）
      • 优化
        • 引用计数
    • sidebar/tips
      • collections模块
        • Counter类
        • defaultdict
      • 排序和FAM计数
        • 基数排序
        • 桶排序
  • 名人问题
    • 问题
      • 在人群中找到某个名人
        • 名人谁都不认识
        • 所有人都认识名人
      • 检查一组依赖关系找出起始点
        • 一个多线程应用中的多个线程
        • 寻找不等待其他线程的一个线程
    • 核心
      • 寻找一个节点拥有从所有其他节点来的入边，但没有出边
    • 代码实现
      • 笨法：两层循环嵌套
      • 迭代依次消除不符合条件的人
  • 拓扑排序
    • 有向无环图DAG
    • 代码实现
      • 递归
    • 思想
      • 没有入边的排在第一位
      • 使用计数，可将线性复杂度转为常数
    • sidebar/tip
      • unix系统的tsort
      • 拓扑排序与Python的MRO
• 更强的假设
  • 问题
    • 有些时候不能执行或有效的执行归纳的步骤
    • 选择子问题的顺序是重要的，但有时需要有一个更强的假设将额外信息带入归纳
  • 平衡因子
    • 平衡树
      • Ch6
      • 空树或其左右子树的高度差绝对值不超过1，且左右子树都是平衡树
    • 计算平衡因子
      • 依据高度确定
      • 加强假设
        • 假设可以找到任意k<n结点树的平衡因子和高度
        • 可以使用高度在归纳的步骤中
  • 更多例子
    • 最近点问题（Ch6）
    • interval containment问题（Ex4-21）
  • sidebar/tip
    • 深度优先
      • Ch5
    • 反向归纳法
• 不变式和正确性
  • 循环不变（loop invariants）
    • 对于给定的条件，每次循环迭代后均为真
    • 如果不变总是被保持，并且有终止条件，则认为是正确的
  • 例
    • 插入排序
  • 步骤
    • 使用归纳法显示每次迭代后均为真
    • 如果算法终止，确保答案正确
    • 确保算法可以终止
• 张驰法和逐渐改善
  • 张驰法
    • 来源于数学
    • 描述一些逐渐近似解决问题的优化方法
    • 运用在算法中
      • 描述关键步骤
      • 特别是基于动态规划的最短路径
        • Ch8、9
      • 寻找最大流
        • Ch10
  • 例
    • 你在一个机场
      • 可以搭飞机到其他机场
        • 时间A：list/dict
      • 从某机场坐火车到城市
        • 时间B：list of lists/dict of dicts
    • 问题
      • 估算到每个城市的时间
    • 代码与解释
  • tip
    • Ch8
      • DAGs
    • Ch9
      • Bellman-Ford
      • Dijkstra
• 归约+对照=难度证明
  • 本节是Ch11的铺垫
  • 归约的使用
    • 归约在课本里一般只用于讨论问题复杂度
    • 以说明不能解决某一给定问题
  • 难度证明
    • 我们只允许简单的归约
    • 归约问题A到B
      • 如果B简单，A必须也简单
  • 举例
    • A：找到DAG图两个节点的最长路径
    • B：找到DAG图两个节点的最短路径
    • 归约A到B，将所有边看为负值
  • 快速的归约+快速的B解决方案=快速的A解决方案
  • 对照
    • 如果A难，B也难
  • 遇到一个新问题X
    • 已知
      • Y难
    • 问题
      • 使用归约表明X难
    • 答案
      • 归约Y到X
  • 结论
    • 如果可以归约A到B，则B至少和A一样难
    • 如果想表明X难，已知Y难，归约Y到X
• 解决问题的建议
  • 建议
    • 确保真正理解问题
      • 确定
        • 输入
        • 输出
        • 关系
      • 尝试找到熟悉的结构
        • 序列
        • 图
      • 一个直接粗暴的解决方案可能帮助我们理清问题
    • 寻找归约
      • 转换输入到另一个能解决的问题
      • 转换输出使你能使用
      • 归约规模为n的实例到k<n，扩展递归方法回到n
    • 是否有额外的假设可以利用
      • 固定值域的整数排序比任意值更高效
      • 使用DAG寻找最短路比任意图更简单
      • 边使用非负权重比任意权重更简单
• 扩展阅读
  • 本章灵感
    • Udi Manber’s: Using induction to design algorithms
  • 理解递归
    • 函数式语言
      • Haskell
      • Clojure
    • 书
      • Rabhi and Lapalme
      • Okasaki
  • 递归的不动点理论
    • 书
      • Zohar Manna
      • Michael Soltys
  • 解决问题的建议
    • Pólya’s How to Solve It
    • The Algorithm Design Manual by Steven Skiena