《算法设计》学习笔记-动态规划

当某些问题不能用贪心算法来解决的时候，我们可以考虑动态规划。动态规划的思想类似于分治，探索所有可能的解，然后把问题分解成一系列子问题，然后为越来越大的子问题构筑正确的解。

加权的区间调度问题

我们有n个请求，标记为1,2,…,n。每个请求i指定了开始时间s_i和结束时间f_i。每个区间i也有一个值，即权重v_i。如果两个区间不重叠，那么它们是相容的。求一个彼此相容的子集，是所选区间的值的总和最大。

定义p(j)，表示区间j中最大的序标i<j，使得区间i和j不相交。就是i是在j开始前结束的，左边最近的区间。
定义OPT(n)是最优解，则：
OPT(j) = max(vj+OPT(p(j)),OPT(j-1))

一个记录了中间计算结果的算法：
M-Compare-Opt(j)
  If j=0 then
    Return 0
  Else if M[j]不为空 then
    Return M[j]
  Else
    定义M[j]=max(vj+M-Compare-Opt(p(j)), M-Compare-Opt(j-1))
    Return M[j]
  Endif

分段最小二乘

用尽可能少的线段来拟合二维平面上的点。给定一组点P={(x₁,y₁), (x₂,y₂),…,(x_n,y_n)}。我们用p_i来表示点(x_i,y_i)。首先把P分成若干段，每个段是P的子集，表示一组连续的坐标。对于P中划分的每个分段S，计算出相对于S中的点的误差最小的线。定义划分的penalty为以下项之和：
(i)P划分的段数乘以固定的给定乘数C>0;
(ii)对于每个段，穿过该段的最优线的误差值

如果最优划分的最后一段是pi,...,pn，那么最优解的值就是OPT(n)=ei,n+C+OPT(i-1)
对于点p1,...pj上的子问题OPT(j)=min1≤i≤j(ei,j+C+OPT(i-1))

Segmengted-Least-Squares(n)
  数组M[0...n]
  置M[0]=0
  For 所有的对 i≤j
    为分段pi,...pj计算最小方差ei,j
  Endfor
  For j=1,2,...,n
    使用递归OPT(j)公式来计算M[j]
  Endfor
  Return M[n]

Find-Segmnets(j)
  If j=0 then
    不输出
  Else
    找到一个i使得ei,j+C+M[i-1]最小
    输出分段{pi,...pj}和Find-Segments(i-1)的结果
  Endif

子集和问题

在考虑调度问题中，有一台可以处理作业的机器，以及一组请求{1，2，…,n}。对于某个数W，我们只能在时刻0和时刻W期间内使用该资源。每个请求对应于一个作业，处理它需要时间w_i。我们希望选择一个子集S，使得S中作业的总时间≤W，并且尽可能大。

如果w<wi，那么OPT(i,w)=OPT(i-1,w)；否则
    OPT(i,w)=max(OPT(i-1,w), wi+OPT(i-1,w-wi))

Subset=Sum(n,W)
  数组M[0...n, 0...W]
  对每个w=0,1,...,W，初始化M[0,w]=0
  For i=1,2,...,n
    For w=0,...,W
      利用递归OPT(i,w)公式来计算M[i,w]
    Endfor
  Endfor
  Return M[n,W]

算法的时间复杂度为O(nW)

背包问题也可以用类似的方法来递归解决

RNA二级结构（略）

序列对比

如何定义两个字符串之间的相似性？假设给定两个字符串X和Y，其中X是由符号序列x₁x₂…x_m组成，Y是由符号序列y₁y₂…y_n组成。匹配(matching)是一组有序对，其性质是每个项最多出现一对。如果不存在交叉对，那么这两个集合中的匹配M是一个比对(alignment)。我们对相似性的定义将基于找到X和Y之间的最优比对。假设M是X和Y之间的给定比对。
(i)存在一个参数δ>0，它定义了空隙罚分(gap cost)。对于在m中不匹配的X或Y的每个位置（空隙），产生δ的开销
(ii)对于字母表中没对字母p和q，存在用q对齐p的不匹配开销(mismatch cost)，记为α_pq。通常假设每个字母p的α_pp=0
(iii)M的开销是其空隙开销和不匹配开销的总和，我们寻求最低开销的对齐

设M是X和Y的任意比对，如果(m,n)!∈M，则X的第m个位置或Y的第n个位置在M中没有匹配

在最优比对M中，至少以下之一为真
(i)（m,n)∈M
(ii)X的第m个位置不匹配
(iii)Y的第n个位置不匹配

对于i≥1和j≥1，最小比对开销满足以下递归：
OPT(i,j)=min[αxiyi+OPT(i-1,j-1), δ+OPT(i-1,j),δ+OPT(i,j-1))]

Alignment(X,Y)
  数组A[0...m,0...n]
  对每个i，初始化A[i,0]=iδ
  对每个j，初始化A[0,j]=jδ
  For j=1,...,n
    For i=1,...m
      利用递归计算OPT(i,j)公式计算A[i,j]
    Endfor
  Endfor
  Return A[m,n]

图中的最短路径

前面讨论过通过Dijkstra算法解决所有边的开销都是正数的情况，对于更一般的情况，需要用到动态规划的算法。
设G=(V,E)是有向图，假设每条边(i,j)∈E具有权重c_ij。在没有负环的情况下，考虑最小开销路径。如果G没有负环，那么存在一条从s到t的简单最短路径（没有重复节点），因此最多有n-1条边。我们用OPT(i,v)表示使用最多i条边的路径的最小开销，我们最初的问题是计算OPT(n-1,s)

如果i>0，那么
OPT(i,v)=min(OPT(i-1,v),minw∈V(OPT(i-1,w)+cvw))

Shortest-Path(G,s,t)
  n=G中点的个数
  数组M[0...n-1,V]
  对于所有其他v∈V，定义M[0,t]=0且M[0,v]=∞
  For i=1,...,n-1
    For v∈V以任何顺序
      利用递归OPT(i,v)计算M[i,v]
    Endfor
  Endfor
  Return M[n-1,s]