动态规划例题

作者: Aniwer | 来源:发表于2020-12-08 15:29 被阅读0次

最优二分搜索树

二分搜索树

是一棵空树
具有下列性质的二叉树
- 若左子树不空，则左子树上所有结点的值均小于它的根结点的值
- 若右子树不空，则右子树上所有结点的值均大于它的根结点的值
- 左、右子树分别为二叉搜索树

查询操作

MEMBER(x,S)：若x在S中则返回”yes”，否则返回”no”
设有n个实数 $a_1$ < $a_2$ <…< $a_n$ 构成集合S
指令MEMBER(x,S)中的x可能是某个 $a_i$ ，也可能不在S中。把不在S中的数按区间分为n+1类，以 $b_0$ ， $b_1$ ，…， $b_n$ 作为每一类数的代表（虚节点）

定义

$p_i$ 为MEMBER ( $a_i$ ,S)出现的频率（i=1,2,…,n）
$q_j$ 为MEMBER ( $b_j$ ,S)出现的频率（j=0,1,2,…,n）
$\sum_{i=1}^np_i$ + $\sum_{j=0}^nq_j$ =1
定义一棵二分搜索树的总耗费： $\sum_{i=1}^np_i(depth(a_i)+1)$ + $\sum_{j=0}^nq_j(depth(b_j))$
最优二分搜索树即耗费最小的二分搜索树

分析

若 $T_0$ 是最优二分搜索树，它的根是 $a_k$ （第k小的数）
则ak的左子树中必然包含了{ $a_1$ … $a_{k-1}$ }，ak的右子树中必然包含了{ $a_{k+1}$ … $a_n$ }。
考察一棵树接到另一个结点之下构成一棵新树时耗费的增加
设有一棵由结点 $b_i$ ， $a_{i+1}$ ， $b_{i+1}$ ，…， $a_j$ ， $b_j$ 构成的树
按定义该树的耗费为 $\sum_{l=i+1}^jp_l(depth(a_l)+1)$ + $\sum_{l=i}^jq_l(depth(b_l))$
把这棵树接到到另一个结点之下构成一棵新树时，这棵子树中的每个结点的深度在新树中均
增加了1，则该子树在新树中的耗费增加了 $\sum_{l=i+1}^jp_l$ + $\sum_{l=i}^jq_l$ = $q_i$ +( $p_{i+1}$ + $q_{i+1}$ )+...+( $p_j$ + $q_j$ )= $w_{ij}$
任何一颗子树中结点的编号都是连续的，而且，最优树中的任何一棵子树，也必然
是关于子树中结点的最优树，因此最优二分搜索树具有最优子结构性质
若规模为m≤n-1的最优子树均已知，就可以通过逐一计算以 $a_1$ ， $a_2$ ，…， $a_n$ 为根的树的耗费来确定（使耗费达到最小的）根 $a_k$ 并找出最优二分搜索树,在上述计算中，规模较小（ m≤n-1 ）的最优子树在计算中要多次被用到，因此，该问题具有高度重复性
$T_{ij}$ :有一棵由结点 $b_i$ ， $a_{i+1}$ ， $b_{i+1}$ ，…， $a_j$ ， $b_j$ 构成的耗费最小的树
树以 $a_k$ 作为根(i+1≤k≤j)
$b_i$ ， $a_{i+1}$ ， $b_{i+1}$ ，…， $a_{k-1}$ ， $b_{k-1}$ 在左子树
$b_k$ ， $a_{k+1}$ ， $b_{k+1}$ ，…， $a_j$ ， $b_j$ 在右子树
这样的树中耗费最小的必然是以 $T_{i,k-1}$ 为其左子树，以 $T_{kj}$ 为其右子树
记 $c_{ij}$ 是最优子树 $T_{ij}$ 的耗费
树 $T_{ij}$ 的总耗费由三个部分组成
左子树的耗费: $c_{i,k-1}$ + $w_{i,k-1}$
右子树的耗费: $c_{kj}$ + $w_{kj}$
根的耗费: $p_k$
总耗费= $c_{i,k-1}$ + $w_{i,k-1}$ + $c_{k,j}$ + $w_{k,j}$$c_{k,j}$ + $w_{k,j}$ = $c_{i,k-1}$ + $c_{kj}$ + $w_{ij}$
已知 ${p_i}$ （i=1,2,…,n）， ${q_i}$ （j=0,1,2,…,n）
若已知 $w_{i,j-1}$ ，则根据 $w_{ij}$ = $w_{i,j-1}$ + ${p_j}$ + ${q_j}$ 的定义计算出 $w_{ij}$
所以，当 $c_{i,k-1}$ 和 $c_{kj}$ 已知，以 $a_k$ 为根的树的最小总耗费能在O(1)时间内计算出来
综上，分别计算以 $a_{i+1}$ , $a_{i+2}$ ,..., $a_j$ 为根，含有结点 $b_i$ ， $a_{i+1}$ ， $b_{i+1}$ ，…， $a_j$ ， $b_j$ 的树的总耗费，从中选出耗费最小的树，即为最优子树
$c_{ij}$ = $\min_{i<k≤j}$ { $c_{i,k-1}$ + $c_{kj}$ + $w_{ij}$ }
三层循环，Θ( $n^3$ )

优化

可以证明：若最小耗费树 $T_{i,j-1}$ 和 $T_{i+1,j}$ 的根分别为 $a_p$ 和 $a_q$ ，则必有⑴p≤q；⑵最小耗费树 $T_{ij}$ 的根 $a_k$ 满足p≤k≤q
因此，求 $\min_{i<k≤j}$ { $c_{i,k-1}$ + $c_{kj}$ + $w_{ij}$ }时，无需在 $a_{i+1}$ ~ $a_j$ 间一一尝试，只需要从 $a_p$ 和～ $a_q$ 找一个根即可

流水作业调度

问题

n个作业，m项任务，m台机器
设有n个任务，每一个作业i均被分解为m项任务： $T_{i1}$ , $T_{i2}$ , $T_{im}$ (1≤i≤n，故共有n×m个任务)，要把这些任务安排到m台机器上进行加工
需要满足条件：

每个作业i的第j项任务 $T_{ij}$ (1≤i≤n, 1≤j≤m) 只能安排在机器 $P_j$ 上进行加工
作业i的第j项任务 $T_{ij}$ (1≤i≤n, 2≤j≤m)的开始加工时间均安排在第j-1项任务 $T_{i,j-1}$ 加工完毕之后
任何一台机器在任何一个时刻最多只能承担一项任务
设任务 $T_{ij}$ 在机器 $P_j$ 上进行加工需要的时间 $t_{ij}$ ，如果所有 $t_{ij}$ (1≤i≤n, 1≤j≤m)均已给出，要找出一种安排任务的方法，使得完成这n个作业的加工时间为最少，这个安排称之为最优流水作业调度
流水作业调度一般均指的是非优先调度，即任何任务一旦开始加工，就不允许被中断，直到该任务被完成

分析

当机器数m≥3时，流水作业调度问题是一个NP-hard问题。当m=2时，该问题可有多项式时间的算法。
记 $t_{i1}$ 为 $a_i$ （作业i在 $P_1$ 上加工所需时间）, $t_{i2}$ 为 $b_i$ （作业i在 $P_2$ 上加工所需时间）
当机器 $P_1$ 空闲时，则任何一个作业的第一个任务都可以立即在 $P_1$ 上执行
必有一个最优调度使得在 $P_1$ 上的加工是无间断的
必有一个最优调度使得在 $P_2$ 上的加工空闲时间（从0时刻起算）为最小，同时还满足在 $P_1$ 上的加工是无间断的
若在 $P_2$ 上的加工次序与在 $P_1$ 上的加工次序不同，则只可能增加加工时间。所以仅需要考虑在 $P_1$ 和 $P_2$ 上加工次序完全相同的调度
最优调度具有如下性质：
在所确定的最优调度的排列中去掉第一个执行作业后，剩下的作业排列仍然还是一个最优调度，即该问题具有最优子结构的性质
在计算规模为n的作业集合的最优调度时，该作业集合的子集合的最优调度会被多次用到，即该问题亦具有高度重复性

求解

N={1，2，┅，n}是全部作业的集合，作业集S是N的子集合即有S⊆N
对机器 $P_2$ 需等待t个时间单位以后才可以用于S中的作业加工（t也可以为0即无须等
待）
记g(S,t)为在此情况下完成S中全部作业的最短时间
g(S,t)= $min_{i∈S}$ { $a_i$ + g(S-{i}, $b_i$ +max{t- $a_i$ ,0})}
当S=N即全部作业开始加工时，t=0
g(N,0)= $min_{1≤i≤n}$ { $a_i$ + g(N-{i}, $b_i$ )}
该算法的时间复杂度为指数量级，因为算法中对N的每一个非空子集都要进行一次计算，而N的非空子集共有 $2^n$ -1个，因此不能直接使用动态规划方法来求解该问题

进一步求解

Johnson不等式：min{ $a_j$ , $b_i$ } ≥ min{ $a_i$ , $b_j$ }
当min{ $a_i$ , $a_j$ , $b_i$ , $b_j$ }为 $a_i$ 或者 $b_j$ 时，Johnson不等式成立，此时把i排在前j排在后的调度用时较少；反之，若min{ $a_i$ , $a_j$ , $b_i$ , $b_j$ }为 $a_j$ 或者 $b_i$ 时，则j排在前i排在后的调度用时较少
推广：当min{ $a_1$ , $a_2$ ,┅, $a_n$ , $b_1$ , $b_2$ ,┅, $b_n$ }= $a_k$ 时，则对任何i≠k，都有min{ $a_i$ , $b_k$ } ≥ min{ $a_k$ , $b_i$ }成立，故此时应将作业k安排在最前面，作为最优调度的第一个执行的作业;当min{ $a_1$ , $a_2$ ,┅, $a_n$ , $b_1$ , $b_2$ ,┅, $b_n$ }= $b_k$ 时，则对任何i≠k，都有min{ $a_k$ , $b_i$ } ≥ min{ $a_i$ , $b_k$ }成立，故此时应将作业k安排在最后面，作为最优调度的最后一个执行的作业
n个作业中首先开工（或最后开工）的作业确定之后，对剩下的n-1个作业采用相同方法可再确定其中的一个作业,应作为n-1个作业中最先或最后执行的作业；反复使用这个方法直到最后只剩一个作业为止，即可确定最优调度
为O(nlgn)

总结

满足1）高度重复性 2）最优子结构性质时，一般采用动态规划法，但偶尔也可能得不到高效的算法
若问题本身不是NP-hard问题，进一步分析后就有可能获得效率较高的算法
若问题本身就是NP-hard问题，与其它的精确算法相比，动态规划法性能一般不算太坏，但有时需要对动态规划法作进一步的加工

备忘录LCS

备忘录方法

当某个问题可以用动态规划法求解,但二维数组中有相当一部分元素在整个计算中都不会被用到
因此，不需要以递推方式逐个计算二维数组中元素，而采用备忘录方法：数组中的元素只是在需要计算时才去计算，计算采用递归方式，值计算出来之后将其保存起来以备它用
若有大量的子问题无需求解时，用备忘录方法较省时

求解

当 $x_i$ = $y_j$ 时，求C[i,j]只需知道C[i-1,j-1]，而无需用到C[i,0]～C[i,j-1]及C[i-1,j]～C[i-1,n]，所以只需求出一个LCS时，可能有一些C[p,q]在整个求解过程中都不会用到
将C[i,0]与C[0,j] 初始化为0，其余m×n个C[i,j]全部初始化为-1
若x[i]=y[j]，则去检查C[i-1,j-1]：若C[i-1,j-1]> -1（已经计算出来），就直接把C[i-1,j-1]+1赋给C[i,j]，返回；若C[i-1,j-1]=-1（尚未计算出来），就递归调用LCS(X,Y,i-1,j-1,C) 计算出C[i-1,j-1]，然后再把C[i-1,j-1]+1赋给C[i,j]，返回
若x[i]不等于y[j]，则检查C[i-1,j]和C[i,j-1]：若两者均 > -1（已经计算出来），则把max{ C[i-1,j], C[i,j-1]} 赋给C[i,j]，返回；若C[i-1,j], C[i,j-1] 两者中有一个等于-1（尚未计算出来），或两者均等于-1，就递归调用LCS将其计算出来，然后再把max{ C[i-1,j], C[i,j-1]} 赋给C[i,j]

最长递增子序列问题（LIS）

问题

假设A =< $a_1$ , $𝑎_2$ , … , $𝑎_𝑛$ >为由n个不同的实数组成的序列
递增子序列𝐿 =< $a_{𝑘_1}$ , $a_{𝑘_2}$ , … , $a_{𝑘_m}$ >
其中 $𝑘_1$ < $𝑘_2$ <…< $𝑘_𝑚$ 并且 $a_{𝑘_1}$ < $a_{𝑘_2}$ < … < $a_{𝑘_m}$
求最大的𝑚值

最大子段和问题

问题

n个整数序列 $a_1$ … $a_n$ ，求该序列形如 $\sum_{k=i}^ja_k$ 的子段和的最大值
当所有整数均为负整数时定义其最大子段和为0

分治解法

如果将所给的序列a[1..n]分为长度相等的两段a[1:n/2]和a[n/2+1:n],分别求出这两段最大子段和，则a[1..n]的最大子段和有三种情形：

a[1:n]的最大子段和与a[1:n/2]的最大子段和相同；
a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同；
a[1:n]的最大子段和为 $\sum_{k=i}^ja_k$ ，1≤ i ≤ n/2，n/2+1 ≤ j ≤ n
对于1、2可以递归求解
对于3:
a[n/2]、a[n/2+1]在最优子序列中
可以在a[1:n/2]中计算出 $s_1$ = $max_{1≤ i ≤ n/2}\sum_{k=i}^ja_k$
可以在a[n/2+1:n]中计算出 $s_2$ = $max_{n/2+1 ≤ i ≤ n}\sum_{k=n/2+1}^ia_k$
$s_1$ + $s_2$ 即为最优

代码

void MaxSubSum(int *a，int left，int right)
{
    int sum=0;
    if (left==right) sum=a[left]>0?a[left]:0;
    else{ 
        int center=(left+right)/2;
        int leftsum=MaxSubSum(a,left,center);
        int rightsum=MaxSubSum(a,center+1,right);
        int s1=0; int lefts=0;
        for(int i=center;i>=left;i--){ 
            lefts+=a[i]; 
            if (lefts>s1) s1=lefts;
        }
        int s2=0; int rights=0;
        for (int i=center+1; i<=right; i++){
            rights+=a[i]; 
            if (rights>s2) s2=rights;
        }
        sum=s1+s2;
        if (sum<leftsum) sum=leftsum;
        if (sum<rightsum) sum=rightsum;
    }
    return sum;
}

分析

算法所需的计算时间T(n)满足典型的分治算法递归式：

$T(n)=\left\{ \begin{aligned} O(1) && n≤c \\ 2T(n/2)+O(n) && n>c \\ \end{aligned} \right.$

基于主方法和主定理，T(n)=O(nlogn)

动态规划解法

记b[j]= $max_{1≤i<j}\sum_{k=i}^ja_k$ ，1≤j≤n，则
$max_{1≤i≤j≤n}\sum_{k=i}^ja[k]$ = $max_{1≤j≤n}max_{1≤i≤j}\sum_{k=i}^ja[k]$ = $max_{1≤j≤n}b[j]$
因此，当b[j-1]>0,b[j]=b[j-1]+a[j]；否则，b[j]=a[j]。得出
b[j]= $max_{1≤j≤n}{b[j-1]+a[j],a[j]}$

代码

int MaxSum(int n，int *a)
{
    int sum=0, b=0;//初始化最大子段和为0，b[0]=0
    for (int i = 1; i <= n; i++){
        if (b>0) b+=a[i];
        else b=a[i];
        if (b>sum) sum=b;//更新当前找到的最大子段和
    }
    return sum;
}

分析

O(n)

动态规划例题

最优二分搜索树

二分搜索树

查询操作

定义

分析

优化

流水作业调度

问题

分析

求解

进一步求解

总结

备忘录LCS

备忘录方法

求解

最长递增子序列问题（LIS）

问题

最大子段和问题

问题

分治解法

代码

分析

动态规划解法

代码

分析

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

如果我是算法大师就好了