动态规划例题

2020-12-08 本文已影响0人 Aniwer

最优二分搜索树

二分搜索树

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

查询操作

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)