如何从动态规划的角度去看问题
算法导论(MIT 6.006 第19讲)
动态规划的核心处理流程是什么?
1: 定义子问题
计算子问题的数量
2:猜测(尝试所有可能的方式,获取最好的)
计算选择的数量
3: 关联所有的子问题
计算单个子问题所需要处理的时间
4: 重用子问题结果并记下新的结果,或者使用DP的bottom-up方式(需要注意没有环)
计算总耗时
5: 解决原有的问题
对结果进行组合等等会划掉部分额外的时间总的来说就是:尝试所有可能的子问题的结果,将最好的可能子结果存储下来,然后重复利用已经解决的子问题,递归去解决所有的问题(猜测+记忆+递归)
它消耗的时间为: 子问题的数量 * 每个子问题处理所需要时间
例1:斐波那契数列
使用递归的方式求斐波那契数列
fib(n): if n<=2:f=1; else: f= fib(n-1)+fib(n-2); return f;
这种方式的运行时间为 $\theta$($2^{n/2}$),空间为O(1)
T(n)=T(n-1)+T(n-2)+O(1) $\geq$ 2T(n-2)= $\theta$($2^{n/2}$)
Memoized DP 算法求斐波那契数列
fib(n): memo={} if n in memo:return memo[n]; if n<=2:f=1; else f=fib(n-1)+fib(n-2); memo[n]=f; return f;
这种方式的运行时间为$\theta(n)$,空间为O(n)
memo的存在使得实际产生调用的只有 fib(1) .... fib(n),共n次,区域的直接从memo中获取,使用常量的时间
Bottom-up DP算法求斐波那契数列
fib(n): fib={} for i in range(1,n+1): if i<=2: f=1 else: f=fib[i-1]+fib[i-2] fib[i]=f return fib[n]
这种方式的运行时间为$\theta(n)$,空间可以只用O(1)
它可以看做是一种拓扑排序(针对DAG),对于使用空间其实只需要记住前两个即可
例2:最短路径
要求s到t的最短路径,那么必定会经过与t相邻的一条边,如图示的u,那么最短路径$\delta(s,t)$=$min_{(u,t)\in E}(\delta(s,u)+w(u,t))$
$\delta(s,u)$就是需要递归调用处理的部分
对于DAG:$\delta(s,t)$每个子问题的处理时间为 indegree(t)+O(1)
indegree(t):入度数也就是类似(u,t)边的数量,需要去遍历所有t的入边O(1):判断是不是有入边
总共的执行时间为
$$\sum_{v\in V}(indegree(v)+O(1))=O(E+V)$$
当图中有环的时候求最短路径产生的问题
要求s到v的最短路径 $\delta(s,v)$,首选需要去求 $\delta(s,a)$,然后是$\delta(s,b)$,到b节点有两条路径:$\delta(s,s)$和$\delta(s,v)$,此时去memo中查$\delta(s,v)$是不存在的,又会这回查询,导致了一个死循环
解决图中有环的时候求最短路径的问题
方式是去环,将原来的图一层一层的展开。
假设从s到v需要的路径为k步,那么可以得到 $\delta_k(s,v)$=$min_{(b,v)\in E}(\delta_{k-1}(s,b)+w(b,v))$,当k递减到0的时候,其实也就是从s到s本身
所需要的展开层数为:|V|-1
对于求最短路径来讲,最长不能超过|V|-1,否则就是成环,会造成循环的情况(从0开始的计数),这就是为什么Bellman-Ford的外层循环是 |V|-1
每层的节点数为所有的节点。那么总共的节点数为|V'|=|V|(|V|-1)+1=O($V^2$),边数是|E'|=|E|(|V|-2)+1=O(VE)。转换后的图是DAG图,那么实际上的时间为O(V'+E')=O(VE)。这也就是从动态规划的角度去看Bellman-Ford算法
节点的数目是1个源点,边的数目是每多一层实际上就多了加了一遍所有的边。
斐波那契数列与最短路径使用动态规划处理步骤的对比
例子 | 斐波那契数列 | 最短路径 |
---|---|---|
1:定义子问题 | $F_k$ 其中$1\leq k \leq n$ | $\delta_k(s,v)$ 其中 $v\in V, 0\leq k < V $ |
子问题数量 | n | $V^2$ |
2:猜测 | 什么都没做,完全是定义 | 节点v的入边(如果存在的话) |
选择的数量 | 1 | v的入边数+1 |
3:关联所有的子问题 | $F_k=F_{k-1}+F_{k-2}$ | $\delta_k(s,v) =min_{(u,v)\in E}(\delta_{k-1}(s,u)+w(u,v))$ |
子问题的时间 | $\theta(1)$ | $\theta(1+入度(v))$ |
4:重用子问题结果并记下新的结果 | for k=1,..,n | for k=0,1,..,V-1 |
总共耗时 | $\theta(n)$ | $\theta(VE)+\theta(V^2)$ (如果存在入度,就有后项) |
5:解决原有的问题 | $F_n$ | $\delta_{v-1}(s,v) ,v \in V$ |
额外耗时 | $\theta(1)$ | $\theta(V)$(Bellman-Ford最后的遍历) |