《Python Algorithm》8.纠缠的依赖性和记忆

创伤性经历给人们带来了痛苦,而创伤性记忆又纠缠不休,严重地危害着人们的身心健康.本文阐述了记忆纠缠现象及其危害,并探讨如何控制这种记忆纠缠.关键词

《Python Algorithm》8.纠缠的依赖性和记忆

• 引言
  • 动态规划DP
    • 规划
    • 动态
      • 每个选择依赖于前一个
    • 应用
      • 缓存cache
    • 记忆
      • 缓存返回值，再次访问时直接读取cache
  • 例
    • 找到最长递增子序列
      • 蛮力法代码
• DRY
  • 目的
    • 避免你的算法重复自己
  • 经典
    • 斐波那契数列
    • 杨辉三角
  • 代码实现
    • 斐波那契数列
    • 优化
      • 装饰器memo函数
        • 存储子问题结果
    • 求二项式系数
    • 杨辉三角
      • defaultdict
  • 动态规划实现中，memoized实际很少使用
    • 递归降解是算法重要步骤
    • 但被视为数学工具
    • 真正实现的是迭代版本
• 有向无环图DAG的最短路径
  • 方法
    • 从节点v到重点的距离是d(v)
    • 边(u,v)的权重是w(u,v)
    • 在节点u，知道每个邻居v的d(v)
    • 按照使w(u,v)+d(v)最小的邻居v为路径
  • 复杂度
    • Θ(n + m)
  • 代码实现
    • 递归
    • 迭代
  • 类似于找DAG图的最长路径
  • 一般图
    • 最短路径：难一些，Ch9
    • 最长路径：不可解，Ch11
  • sidebar
    • DAG图最短路径的变种
      • 递归
        • 可以从起点开始
      • 迭代
• 最长递增子序列LIS
  • 注意
    • 大部分DP问题不显式包含图，需自己总结DAG图或序贯决策过程
  • 定义子问题
    • 考虑前缀的最长递增子序列
  • 算法
    • 递归分解
      • 已知如何找到前j-1个位置的LIS，找第j个
      • L(j) = max{L(i), i<j && Ai<Aj} + 1, i=1,...,j-1
    • DAG图
      • 描述
        • 每个元素一个节点
        • 每个元素到下一个更大元素有一条隐形的边
      • 问题
        • 找到最优前任
          • 二分
          • 如果不只一组，用哪组都是最优
          • 安全选择是保持最小的那组
  • 代码实现
    • 递归
    • 迭代
    • 二分法
• 序列比较
  • 应用
    • 生物信息学
  • 最长公共子序列LCS
    • 找到编辑距离
      • 操作
        • 插入
        • 删除
        • 替换
      • 两个序列长度m、n，LCS为k，则编辑距离为m+n-2k
    • 类似 LIS
    • 算法
    • 代码实现
      • 递归
      • 迭代
    • 注意和子串区别
      • 子串连续，子序列可不连续
• 背包再度来袭
  • 无界整数背包问题
    • m(r)
      • 对于（剩余的）容量r，能给出的最大值是m(r)
      • 每个r就是子问题
      • 递归分解基于是否用最后单元的容量
        • 不用：m(r)=m(r-1)
        • 用：找到合适的对象
          • m(r) = max{v[i] + m(r-w[i])}, i<=r
    • 代码实现
      • 递归
      • 迭代
    • 时间复杂度
      • Θ(cn)
  • 0-1背包问题
    • m(k,r)
      • 最先k个对象在剩余容量r下的最大值
      • kr=0，则m(i,r)=0
      • 决策
        • 是否放最后一个对象，i=k-1
          • 不放：m(k,r)=m(k-1,r)
          • 放：m(k,r)=v[i]+m(k-1,r-w[i])
    • 代码实现
      • 递归
      • 迭代
      • 提取实际选择物品的集合
• 二进制序列划分
  • 应用
    • 矩阵链相乘
      • 一系列矩阵相乘得到一个矩阵
      • 通过加括号使操作数最小
    • 解析任意上下文无关语言
      • 上下文无关语言的文法可以用乔姆斯基范式重写
      • 产生规则
        • A → BC
          • B、C都不是开始符号
        • A → α
          • 终结符
        • S → ε
          • 空串
      • 加括号解析字符串
        • 每组表示一个非终结符
    • 最优搜索树
      • 哈夫曼问题的严格版本
      • 目的
        • 最小化期望的遍历深度
        • 不能改变叶子顺序
      • 加括号，与树结构一致
        • CLRS 15.5
        • TAOCP v3 6.2.2
  • 问题
    • 为序列按层分段，每段包含两个，找到最优化代价/价值的分区
  • 最优搜索树
    • 每个元素有一个频率，希望最小化期望的遍历深度
    • 输入是有序的，不能改变顺序
    • 找到正确的根节点，和两个子树（拥有更小的间隔）
    • 为简单起见，只考虑代价
    • 结点v的贡献是p(v)*(d(v)+1)
      • p(v)是其相对频率
      • d(v)是其深度
      • 求所有节点的和来取得总代价
        • 1 + sum of p(v)*d(v)
        • 因为p(v)之和是1
    • 给定根r的递归表达式
      • e(i,j) = e(i,r) + e(r+1,j) + sum(p[v] for v in range(i, j))
      • 最终，要尝试每个r in range(i,j)然后选最大值
    • 改进
      • 表达式的求和部分
    • 代码实现
      • 递归
        • Θ(n3)
      • 迭代
        • defaultdict
• 扩展阅读
  • 隐马尔可夫链
    • Viterbi算法
  • 序列比较
    • books by Gusfield and Smyth
    • “Sequence comparison,” by Christian Charras and Thierry Lecroq
    • Python
      • difflib模块
      • sage的knapsack模块
  • DP产生
    • Stuart Dreyfus’s paper “Richard Bellman on the Birth of Dynamic Programming.”
  • DP例子
    • book by Lew and Mauch