如何从动态规划的角度去看问题

WindChaser 2019-06-27

算法导论(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的入边(如果存在的话)
选择的数量1v的入边数+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,..,nfor 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最后的遍历)

相关推荐