动态规划
找到用较小子问题的最优解来表达更大规模问题的最优解的一个递推的等式。带权的区间调度
对区间j定义p(j)为使得区间i与j不相交的最大的标记i < j, i是最右边的与j不冲突的区间。
$$
OPT(j)=\begin{cases}
0,\quad if\ j=0 \\
max{v_j+OPT(p(j)),OPT(j-1)},\quad otherwise
\end{cases}
$$
递归的备忘录形式 自顶向下
用一个数组M[0…n]保存中间计算结果
1 | Input: n, s1,...,sn, f1,...,fn, v1,...,vn |
输出最优解 O(n)
j属于一个区间集合{1,…,j} 的最优解当且仅当：$v_j+OPT(p(j)) > OPT(j-1)$
1 | Find-Solution(j){ |
迭代算法计算M[] 自底向上
Input: n, s1,…,sn, f1,…,fn , v1,…,vn
Sort jobs by finish times so that f1≤f2≤… ≤fn.
Computep(1), p(2), …, p(n)
Iterative-Compute-Opt { //O(n)
M[0] = 0 forj = 1 to n
M[j] = max(vj+ M[p(j)], M[j-1])
}
区别动态规划与分治策略：子问题是否独立
分段的最小二乘
罚分度量函数: E + c L 在所有直线上的平方误差之和E，直线的数目L
OPT(j) =对于点pi, pi+1, . . . , pj的最优解
e(i, j) = 关系到pi, pi+1, . . . , pj的任何直线的最小误差
$$
OPT(j)=\begin{cases}
0,\quad if\ j=0 \\
min_{1≤i≤j}{e(i,j)+c+OPT(i-1)},\quad otherwise
\end{cases}
$$
自底向上
INPUT: n, p1,…,pN,c
Segmented-Least-Squares() {
M[0] = 0
for j = 1 to n
for i = 1 to j
compute the least square error eij for the segment pi,…, pj //O(n)
for j = 1 to n
M[j] =$min_{1≤i≤j}{e(i,j)+c+OPT(i-1)}$ //O(n^2)
return M[n]
}
总的算法代价是O(n^3)；如果预先计算了统计信息e(i, j) ，那么代价就是 O(n^2)
通过数组M 向回寻找计算最优的划分
Find-Segments(j)
If j=0 then
不用输出
Else
找一个使得e(i,j)+c+M[i-1]最小的i
输出这一段{pi,…,pj}作为直线段，以及输出递归函数Find-Segments(i-1)的结果
End if
背包问题
增加一个变量
$$
OPT(i,w)=\begin{cases}
0,\quad if\ i=0 \\
OPT(i-1,w),\quad if\ wi>w \\
max{OPT(i-1,w),vi+OPT(i-1,w-wi)},\quad otherwise
\end{cases}
$$
自底向上算法，填满一个n*W的二维数组
Input: n, w1,…,wN, v1,…,vN
for w = 0 to W
M[0, w] = 0
for i = 1 to n
for w = 1 to W
if(wi> w)
M[i, w] = M[i-1, w]
else
M[i, w] = $max{OPT(i-1,w),vi+OPT(i-1,w-wi)}$
return M[n, W]
Θ(nW)，伪多项式。在O(n)时间内找到最优集合。
RNA二级结构
没有尖的转弯：S中每个对的两端被至少四个插入的碱基所分割. 即如果(bi, bj) ∈S, 那么i < j -4.
$$
OPT(i,j)=\begin{cases}
0,\quad if\ i≥j-4 \\
max{OPT(i,j-1),1+max_t{OPT(i,t-1)+OPT(t+1,j)}},\quad otherwise
\end{cases}
$$
$max_t$遍取所有的t,使得bt与bj是一对被允许的碱基.
存在O(n^2)个子问题;每次求值用O(n)时间,总运行时间是O(n^3)
序列比对
空隙罚分δ; 不匹配罚分$α_{pq}$
一个比对M是一些有序配对xi-yj 的集合，每一项至多出现在一个配对中， 而且没有配对交叉.
$$
OPT(i,j)=\begin{cases}
jδ,\quad if\ i=0 \\
min\begin{cases}
α_{x_iy_j}+OPT(i-1,j-1)\quad\\
δ+OPT(i-1,j)\quad \\
δ+OPT(i,j-1)\quad
\end{cases}\quad otherwise\\
iδ,\quad if\ j=0
\end{cases}
$$
算法
Sequence-Alignment(m, n, x1x2…xm, y1y2…yn, δ, α) {
for i = 0 to m M[0, i] = iδ
for j = 0 to n M[j, 0] = jδ
for i = 1 to m
for j = 1 to n
M[i, j] = min(α[xi, yj] + M[i-1, j-1], δ+ M[i-1, j], δ+ M[i, j-1])
returnM[m, n]
}
时间和空间复杂度：Θ(mn)
线性空间的序列比对
Space-Efficient-Alignment(X,Y)
数组B[0…m,0…1]
初始化对每个i令B[i,0]=iδ
For j=1,…,n
B[0,1] =jδ
For i=1,…,m
B[i,1]= min(α[xi, yj] + B[i-1, 0], δ+ B[i-1, 1], δ+ B[i,0])
Endfor
将B的第一列移到第0列来为下一次迭代留出空间
对每个i修改B[i,0]=B[i,1]
Endfor
O(mn)的时间与O(m)的空间.
最优序列比对算法可以在O(m + n) 空间，O(mn)时间复杂度内完成。把动态规划算法和分治算法结合起来Divide-and-Conquer-Alignment(X,Y)
令m是X中的符号个数
令n是Y中的符合个数
If m<=1或N<=2, then
使用Alignment(X,Y)计算最优比对
调用Space-Efficient-Alignment(X,Y[1:n/2])
调用Backward-Space-Efficient-Alignment(X,Y[n/2+1:n])
令q是使得f(q,n/2)+g(q,n/2)达到最小的指标
把(q,n/2)加到全局表P中
Divide-and-Conquer-Alignment(X[1:q],Y[1:n/2])
Divide-and-Conquer-Alignment(X[q:m],Y[n/2:n])
返回P
采用待定系数法式的归纳法可以证明算法Divide-and-Conquer在长度为m与n的串上运行时间是O(mn).
图中的最短路径
OPT(i, v) 表示至多使用i条边的v-t最短路径的最小费用。
$$
OPT(i,v)=\begin{cases}
0,\quad if\ i=0 \\
min{OPT(i-1,v),min_{(v,w)∈E}{OPT(i-1,w)+c_{vw}}},\quad otherwise
\end{cases}
$$
算法
Shortest-Path(G, t) {
foreach node v ∈V
M[0, v] ←∞
M[0, t] ←0
for i = 1 to n-1
foreach node v ∈V
M[i, v] ←M[i-1, v]
foreach edge (v, w) ∈E
M[i, v] ←min { M[i, v], M[i-1, w] + cvw}
}
表M有n^2项，每项O(n)时间计算，时间复杂度：O(n^3)，空间复杂度：O(n^2)
改进
对每个结点v更新一个值M[v]，即我们至今已经找到的从v到t的最短路径的长度。为了帮助复原这条最短路径，记录每个结点通向终点t的路径上它后面的第一个结点；只要距离M[v]更新，我们就更新 这个值(first[v]).
O(mn)时间
$M[v]=min(M[v],min_{w∈V}(M[w]+c_{vw}))$
1 | PUsh-Based-Shortest-Path(G,s,t){ |
图中的负圈
增加一个终点t。如果G有n个结点且 OPT(n,v)!=OPT(n-1,v),那么一条从v到t 的费用OPT(n,v)的路径P包含一个圈C,并 且C有负费用。