算法设计与分析.06.动态规划 (2)

动态规划 (2)

  • DP:Dynamic Programming

sequence alignment

  • Edit Distance
    • Gap penalty \(\delta\)(空配)
    • mismatch penalty \(\alpha_{pq}\)(误配)
    • 编辑距离 = 空配 + 误配

  • 给定两个字符串 \(x_1\cdots x_m\)\(y_1\cdots y_n\) ,求最小编辑距离

DP

  • \(OPT(i, j)\) :子问题,\(x_1\cdots x_i\)\(y_1\cdots y_j\) 的最小代价
  • 原始问题:\(OPT(m,n)\)
  • 转移方程
    • 最后面两个字符匹配还是不匹配
    • \(i=0\lor j=0\Rightarrow OPT(i,j)=(i+j)\delta\)

\[ \begin{aligned} OPT(i,j)=\min\{&\\ &OPT(i-1,j-1)+\alpha_{x_iy_j},\\ &OPT(i-1,j)+\delta,\\ &OPT(i,j-1)+\delta,\\ \}&\\ \end{aligned} \]

  • 恢复:traceback,判断进入的是哪一个分支(和谁相等)
  • 时间复杂度:\(O(nm)\)
  • 空间复杂度:\(O(nm)\)

定理

改进

  • 空间复杂度:\(O(m+n)\)
  • 状态转移只依赖于前一行的值,只需要记录前一行和当前行的值
    • \(O(m+n)\)
  • 此时无法恢复最优解
  • 如何在空间复杂度:\(O(m+n)\) 恢复最优解?
    • Hirschberg′s algorithm

Hirschberg′s algorithm

  • 能够恢复最优解
    • 时间复杂度:\(O(nm)\)
    • 空间复杂度:\(O(n+m)\)
  • 分治+动归

Edit distance graph

  • \(f(i,j)\)\((0,0)\)\((i,j)\) 的最短路

  • \(f(i,j)=OPT(i,j)\)
    • 归纳法可证
  • 对于给定的一列,可以 \(O(mn)\) 时间复杂度,\(O(m+n)\) 空间复杂度计算出 \((0,0)\) 到这一列任意点的最短距离 \(f(i,j)\)

  • \(g(i,j)\)\((i,j)\)\((m,n)\) 的最短路
    • 将边反向,此时 \((m,n)\) 等价于上面的 \((0,0)\)
    • 计算 \(g(i,j)\) 此时等价于上面的 \(f(i,j)\)

发现

  • \((0,0)\)\((m,n)\) 的最短路就是 \(f(i,j)+g(i,j)\)
  • 如果 \(q\) 是使得 \(f(q,\dfrac{n}{2})+g(q,\dfrac{n}{2})\) 最小的值,则存在一条\((0,0)\)\((m,n)\) 的最短路经过 \((q,\dfrac{n}{2})\)
  • 分治思想

复杂度

  • 空间复杂度:\(O(m+n)\)
    • 计算 \(f,g\)\(O(m)\)
    • 递归时候记录结果,递归次数小于 \(n\)\(O(n)\)
  • 时间复杂度
    • \(T(m,n)=O(mn\log n)\)
    • \(T\) 对于 \(m,n\) 而言都是非降的

简单分析

\[ T(m,n)\le 2T(m,\dfrac{n}{2})+O(mn) \]

  • 根据递推

\[ T(m,n)=O(mn\log n) \]

  • 分析不紧致,划分的两个子问题实际上更小
    • \(T(q,\dfrac{n}{2}),T(m-q,\dfrac{n}{2})\)

严格分析

  • \(T(m,n)=O(mn)\)
  • \(m+n\) 进行归纳
  • 选择一个常数 \(c\),使其满足

  • \(m+n\) 进行归纳 \(T(m,n)\le 2cmn\)
    • 代入即可

longest common subsequence

  • 最长公共序列

DP1

  • 看最后一个字符是否匹配上

DP2

  • 规约为对齐问题
    • Gap penalty \(\delta=1\)(空配)
    • mismatch penalty \(\alpha_{pq}=\infty\)(误配)
  • 结果:\(\dfrac{m+n-\text{edit distance}}{2}\)

理论下界

  • No \(O(n^{2−\epsilon})\) algorithm unless SETH is false
    • Tight Hardness Results for LCS and other Sequence Similarity Measures

Bellman–Ford–Moore algorithm

  • 最短路问题
    • 有向图 \(G(V,E)\),找到从点 \(s\)\(t\) 的最短路

Dijkstra

  • 单源最短路
    • 不能解决负权边的问题

  • 调整边权让结果可能出错
    • 每条边都加上相同的权重,消除负边

负环

  • 负环:环的权重和为负数
  • 有负环,则不存在最短路
    • 疯狂绕圈圈
  • 如果不存在负环,那么最短路一定是简单路径(无环)
    • 反证法
  • Single-destination shortest-paths problem
    • 没有负环的有向图,给定点 \(t\),计算所有其他点到 \(t\) 的最短路
  • Negative-cycle problem
    • 判定是否存在负环

最短路

  • \(OPT(i, v)\)\(v\to t\) 的最多使用 \(i\) 条边的最短路
  • 原始问题:\(OPT(n-1,v)\)
    • 简单路径最多 \(n-1\) 条边
  • 转移方程

  • 算法
    • 使用当前点的后继节点开更新当前点
    • 记录出边

  • 时间复杂度:\(O(nm)\)
  • 空间复杂度:\(O(n^2)\)
    • 记录矩阵 \(M\)
  • 恢复路径
    • 每次更新 \(M\) 的时候记录前驱
      • \(O(n)\) 空间复杂度
    • traceback,看看进入了哪一个分支
      • \(O(m)\) 时间复杂度

优化

  • \(d[v]\):目前为止找到的 \(v\to t\) 的最短路的长度
  • \(\text{successor}[v]\):目前为止找到的 \(v\to t\) 的最短路的下一个顶点
  • 算法
    • 使用当前点的前驱节点开更新前驱节点
    • 记录入边
    • (这样能够实现第1个优化)

  • 优化细节
    • optm1:如果上一轮迭代中,所有的 \(d[\cdot]\) 都没有更新,则算法结束
    • optm2:如果上一轮迭代中 \(d[w]\) 没有更新,则不需要用它去更新其他点

正确性(长度)

  • \(d[v]\) 一直都代表这某条 \(v\to t\) 的路径的长度
  • 迭代过程中,\(d[v]\) 是非降的
  • \(i\) 轮迭代结束后,\(d[v]\) 比使用 \(j(j\le i)\) 条边的路径要短
    • \(i\) 做归纳法

复杂度

  • 前提是不存在负环
  • 时间复杂度:\(O(nm)\)
  • 空间复杂度:\(O(n)\)

问题

Q1

  • 在中间的某一轮迭代结束后,\(d[w]+e(v,w)\) 可能比 \(d[v]\)
    • \(w=\text{successor}[v]\)
  • \(w\) 更新 \(v\) 之后,可能有其他点更新了 \(w\),此时 \(v\) 并没有跟着更新

Q2

  • 如果存在负环,则后继图可能存在环(互相更新)

正确性(路径)

  • 如果没有负权环,则能够 BF 算法能够找到结果,而且能恢复原始路径

引理

  • 后继图中如果有环,则一定是负权环
  • 对环上所有边,求和如下不等式
    • 当用 \(w\) 更新 \(v\) 时,左右相等
    • 但是之后 \(w\) 可能被其他点更新,此时右边更小

\[ w=\text{successor}[v]\Rightarrow d[v]\ge d[w]+l_{vw} \]

证明

  • 根据上面引理,后继途中没有环,此时必然存在路径 \(v\to t\)
  • 因为算法结束,此时 \(d\) 都没有再更新过了,因此不等式全都取到等号

\[ w=\text{successor}[v]\Rightarrow d[v]= d[w]+l_{vw} \]

  • 此时,对路径上的所边求和,可以得到

  • 左边是最短路径长度,右边是恢复出来的路径
  • 右边和左边相等,因此是最短路

带负权的单源最短路

distance-vector protocols

  • 通信网络
    • 节点:路由器
    • 边:线缆
    • 边的长度:延时
  • BFM 算法的应用

算法

  • Dijkstra’s algorithm:需要网络的全局信息
  • Bellman–Ford–Moore:只需要局部信息
    • 哪条边先更新无所谓,异步更新也能收敛
  • 算法
    • 每个路由器保持它到其他节点的最短路,和每一个最短路的下一跳节点
    • 每个路由器执行多次计算,每次计算得到到一个终点的最短路

问题

  • 边被断开,此时陷入无限循环

算法2

  • Path-vector routing protocols

  • 基于 Dijkstra 算法,保存整个网络拓扑结构

negative cycles

  • 负权环
  • 负权环:货币交换,换了一圈,赚了
  • BFM 算法能够检测负权环
  • 如果满足如下式子,则没有负权环

\[ OPT(n,v)=OPT(n-1,v),\forall v \]

  • 如果对于某些节点 v,\(OPT(n,v)<OPT(n-1,v)\),则路径上存在负权环
    • \(n\) 条边 \(\Rightarrow\) 有环 \(\Rightarrow\) 删除环之后的路径权值变大(因为现在和更新了) \(\Rightarrow\) 环是负权环

算法

  • 时间复杂度:\(O(nm)\)
  • 空间复杂度:\(O(n^2)\)
  • 算法:加一个顶点和 0 权重的边,跑 BFM 算法 \(n\) 次,看是否收敛
    • 检查是否满足 \(OPT(n,v) = OPT(n–1,v)\)

优化

  • 时间复杂度:\(O(nm)\)
  • 空间复杂度:\(O(n)\)
  • BFM 的优化,看第 \(n\) 次迭代有无更新
  • 负环,则沿着后继图一直找,找到环就是负环