dynamic programming

Posted on:September 4, 2023 at 10:07 AM
预计阅读时长：6 min read 字数：1190

目录

概念

programming:表格法

同分治算法一样，是通过组合子问题的解来解决原问题。

动态规划算法通常用于求解最优化问题。

应用于子问题重叠的情况

步骤

最优解的结构特征

当完成首次切割后，我们将两段钢条看作两个独立的切割问题实。通过组合两个相关子问题的最优解，并在所有可能的两段切割中选取组合收益最大的，构成原问题的最优解。

例子

1.钢条切割

问题描述： 给定1个长度为n的钢条和钢条切割价格条目，求将钢条切割为若干 小段后，得到的最大收益。

长度i12345678910
价格pip_{i}1589101717202430
n=i1+i2+...+ikn = i_{1}+i_{2}+...+i_{k}
rn=pi1+pi2+...+pikr_{n} = p_{i_{1}} + p_{i_{2}} + ... + p_{i_{k}}
r1=1(1=1无切割)r_{1} = 1 \tag{1=1无切割}
r2=5(2=2)r_{2} = 5 \tag{2=2}
r3=8(3=3)r_{3} = 8 \tag{3=3}
r4=10(4=2+2)r_{4} = 10 \tag{4=2+2}
r5=13(5=3+2)r_{5} = 13 \tag{5=3+2}
r6=17(6=6)r_{6} = 17 \tag{6=6}
r7=18(7=6+1/7=2+2+3)r_{7} = 18 \tag{7=6+1/7=2+2+3}
r8=22(8=6+2)r_{8} = 22 \tag{8=6+2}
r9=25(9=6+3)r_{9} = 25 \tag{9=6+3}
r10=30(10=10)r_{10} = 30 \tag{10=10}

更一般的，对于rn≧1r_{n}\geqq{1},我们可以用更短的钢条最优收益来描述

rn=max(pn,ri1+rin−1,...,rin−1+ri1)r_{n} = max(p_n, r_{i_1}+r_{i_{n-1}},...,r_{i_{n-1}}+r_{i_1})

pnp_n指不分割的方案 钢条切割问题满足最优子结构

另一种相似但是更为简单的方案:i部分不分割，剩下的n-i部分进行分割，即问题分解的方式为：将长度为n的钢条分解为左边开始一段不分割以及剩余部分继续分解的结果，公式描述为:

rn=max1≦i≦n(pi+rn−1)r_{n} = max_{\substack{1\leqq{i}\leqq{n}}}(p_{i}+r_{n-1})
CUT-ROD(p,n)
if n=0
    return 0
else
    q = -∞
    for j=1 to n
        q = max{q, p[j]+CUT-ROD(p,n-j)}
    return q
T(n)=1+∑0n−1T(j)↪T(n)=2nT(n) = 1+\sum_0^{n-1}T(j) \hookrightarrow T(n)=2^n

下面展示如何用动态规划解决此问题

仍然按照自然的递归形式编写过程，使用散列表会这数组保存已求解的子问题

MEMOIZED-CUT-ROD(p,n)
    let r[0..n] be a new Array;
    for i=0 to n
        r[i]=-∞;
    //将辅助函数r[n]的值初始化为-∞
    return MEMOIZED-CUT-ROD-AUX(p,n,r)

//上述CUT-ROD的变体，提供备忘机制
MEMOIZED-CUT-ROD-AUX(p,n,r)
    //已知直接返回
    if(r[n]>=0)
        return r[n]
    if(n==0)
        q = 0
    else
        q = -∞
        for j=1 to n
            q = max{q, p[j]+MEMOIZED-CUT-ROD-AUX(p,n-j,r)}
    //将q存入
    r[n] = q
    return q

按照问题的递归结构，自底向上求解,将子问题按照规模排序，再由小到大解决

BOTTOM-UP-CUT-ROD(p,n)
    let r[0..n] be a new Array;
    r[0] = 0
    for j=1 to n
        q = -∞
        for i=1 to j
            q = max{q, p[i]+r[j-i]}
        r[j] = q
    return r[n]

第一行创建一个新数组保存子问题的解,第二行将数组第一个值初始化为0

let r[0..n] be a new Array;
r[0] = 0

3-6行升序求解从1到n的规模为j的子问题

for j=1 to n
        q = -∞
        for i=1 to j

7行解决子问题，不必调用递归，直接访问r[j-i],即以保存的子问题的解

q = max{q, p[i]+r[j-i]}

8行将子问题的解存入数组，9行返回最优解

两种方法具有相同的渐进运行时间，O(n2)O(n^2)

自底向上 嵌套的两层for循环

自顶向下 递归调用, 使用聚合分析,其中

 for j=1 to n
            q = max{q, p[j]+MEMOIZED-CUT-ROD-AUX(p,n-j,r)}

对每个子问题只求解一次，求解规模为∑0ni\sum_0^n{i} = O(n2n^2)

自顶向下递归树的简化版/自顶向下的子问题图

n=4 这是一个有向图,每个顶点唯一地对应一个子问题,标号代表子问题的规模

重构解

上述算法能返回最终的最优收益值，但并没有返回解本身。下面我们拓展动态规划算法，使其返回最优收益值的同时，返回一个最优解。

EXTENDED-BOTTOM-UP-CUT-ROD(p,n)
    let r[0..n] and s[0..n] be a new Array;
    r[0]=0
    for j=1 to n
        q = -∞
        for i=1 to j
            if q < p[i]+r[j-i]
                q = p[i]+r[j-i]
                s[j] = i
        r[j] = q
    return r and s

2.矩阵链乘法

矩阵乘法满足结合律，但乘法顺序不固定，所以需要求解最优乘法顺序，使得乘法次数最少

链接