• 热门专题

动态规划总结

作者:  发布日期:2016-12-22 20:36:28
Tag标签:动态  
  • 动态规划(Dynamic Programming, DP)思想启发于分治算法的思想,也是将复杂问题化解若干子问题,先求解小问题,再根据小问题的解得到原问题的解。但是DP与分治算法不同的是,DP分解的若干子问题,往往是互相不独立的,这时如果用分治算法求解,那么会对重叠子问题重复进行求解,从而使得浪费大量的时间。那么如果我们保存已经计算过的子问题的解,这样当再次计算该子问题时,可以直接使用,这样可以节约大量的时间。

    DP正是利用一个表记录所有已经求解过的子问题的答案,只要一个子问题被求解过,就将其答案保存起来,无论以后的计算是否会用到,这就是DP的基本思想。

    设计动态规划的四个步骤:

    1、刻画一个最优解的结构特征。

    2、递归地定义最优解的值。

    3、计算最优解的值,通常采用自底向上的方法。

    4、利用计算出的信息构造一个最优解。

    动态规划的应具备两个要素:

    1、最优子结构性质。当问题的最优解包含了其子问题的最优解时,称该问题具有最有子结构性质;

    2、重叠子问题性质。

    首先看一个算法导论中第一个例子,钢条切割问题

    问题:给定一根长度为n英寸的钢条和一个价格表,求钢条的最佳切割方案,使得销售收益最大。

    对于长度为n的钢条总共有种不同的切割方案。设距离钢条左端i(i = 1,2,....n-1)英寸处为可切割点,那么我们对每个切割点都可以选择切或者不切,则总共有种方法。因此暴力枚举每一种可能是不行的。

    设长度为n的钢条的最大收益为(n>=1)。

    1、最优子结构

    对于长度为n的钢条,假设第一刀在i(i= 1,.....n-1)处切割,使得收益最大。得到的两个小段钢条长度为i,n-i,那么对于其收益也是最大的。假设不是,即在长度为i和长度为n-i的钢条分别有更好的切割方案,使得对应的收益更大,那么将这两个更优切割方案的收益相加,会得到一个比在i处切割所得收益更大的方案,那么说明开始第一刀就不是最优的,与假设相矛盾!因此本问题具有最有子结构的性质。

    2、递归地定义最优解的值

    有一个更加简单明了的切割方法,假设我们最优的第一刀直接切出一个距离左端为i(i = 1, ....n-1)的钢条,这一段整体收益最大,即不再对这一段继续切割。我们只对剩余长度为n-i的钢条,继续切割,求其收益最大的切割方案,这样问题只化为一个更小的子问题。

    由此,我们可以知道长度为n的递推公式为:

    若i取n时表示整体不切割,收益最大,此时剩余部分n-i的收益为为0。

    3、计算最优解的值

    我们先根据2的递推公式,用递归的方式先求解,如下:

     

    int CutRod(int p[], int n)
    {
        if(n == 0)
            return 0;
        int q = INT_MIN;
        for(int i = 1; i <= n; ++i)
            if(q < p[i]+CutRod(p, n-i))
                q = p[i]+CutRod(p, n-i);
        return q;
    }
    开始的时候,我们说过,对于切割点i(i = 1, ...., n-1),我们可以选择切或者不切,总共有种情况,由此我们可以知道该算法的时间复杂度为,(其实它枚举了每一种情况),这是一个指数级的算法,肯定是不行的。那么时间浪费在哪里了?

     

    我们用当n=4时,做个例子,其递归过程如下:

    每个节点表示子问题的规模,从父节点s到子节点t的边,表示从钢条的左端切下一段长度为s-t的小钢条,然后递归地求解剩余规模为t的子问题。

    由上图可以知道,有很多相同的子问题,被大量的重复计算,从而浪费了大量的时间,那么如何解决这问题?我们可以用空间来换取时间,申请一张表,来储存每次新子问题的答案,这样下次再遇到相同的子问题,直接查表取得,而无需计算,从而可以节约大量的时间。

     

    int CutRod(int p[], int r[], int n)
    {
        if(r[n] >= 0)
            return r[n];
        if(n == 0)
            return 0;
        int q = INT_MIN;
        for(int i = 1; i <= n; ++i)
            if(q < p[i]+CutRod(p, r, n-i))
                q = p[i]+CutRod(p, r, n-i);
        r[n] = q;
        return q;
    }
    
    int MemoizedCutRod(int p[], int n)
    {
        int r[n+1];
        for(int i = 0; i <= n; ++i)
            r[i] = INT_MIN;
        return 
    }
    这是一个的算法,由此可以看出,算法的效率得到了大大的提高。

     

    我们知道,每次递归调用函数,这也是需要时间花销的,我们上面的算法实现全部都是用自上而下的思想来求解最优值的,由1,我们知道子问题的最优解决定着原问题的最优解,那么可以从最小规模开始计算,这样当计算规模较大的问题时,所需的子问题已经全部计算出来,并且被记录下来,这样就可以直接拿来使用,这就自底向上的思想来求解最优值,该问题的自底向上方法的实现如下:

     

    #include <iostream>
    #include <cstdlib>
    #include <cstring>
    
    using namespace std;
    
    int main()
    {
        int n;
        cin>>n;
        int price[11] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
        int r[n+1];
    
        for(int i = 0; i<= n; ++i)
            r[i] = 0;
    
        for(int i = 1; i <= n; ++i)//规模长度为i
        {
            int q = INT_MIN;
            for(int j = 1; j <= i; ++j)//计算规模为i的最大收益
            {
                if(q < price[j] + r[i-j])//因为i>i-j,所以当计算r[i]时,r[i-j]已经解决,可以直接用
                    q = price[j] + r[i-j];
            }
            r[i] = q;
        }
        cout<<r[n];
    }
    4、利用计算出的信息构造一个最优解

     

    如果只需求解最大收益,这么此步可以被省略,但是如果需要打印出来最佳的切割方案,那么原算法仍需稍微改动。我们另外申请一个数组label[],专门来存储最佳切割点的。其实现如下:

     

    #include <iostream>
    #include <cstdlib>
    #include <cstring>
    
    using namespace std;
    
    int main()
    {
        int n;
        cin>>n;
        int price[11] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
        int r[n+1];
        int label[n+1];
        memset(label, 0, sizeof(label));
        for(int i = 0; i<= n; ++i)
            r[i] = 0;
    
        for(int i = 1; i <= n; ++i)//规模长度为i
        {
            int q = INT_MIN;
            for(int j = 1; j <= i; ++j)//计算规模为i的最大收益
            {
                if(q < price[j] + r[i-j])//因为i>i-j,所以当计算r[i]时,r[i-j]已经解决,可以直接用
                {
                    q = price[j] + r[i-j];
                    label[i] = j;
                }
            }
            r[i] = q;
        }
        cout<<r[n]<<endl;
        //打印最佳切割方案
        while(n > 0)
        {
            cout<<label[n]<<" ";
            n = n - label[n];
        }
        cout<<endl;
    }
    那么到此,我们利用DP的设计步骤全部实现钢条的切割问题,下面我们再看一个矩阵相乘的例子,这是把原问题分解为两个子问题,来求解矩阵相乘所需的最小次数的。请参考本人笔记:

     

    http://blog.csdn.net/hearthougan/article/details/25834141
     

    由这两个问题我们可以更加深刻地理解DP的两个要素。何时需要动态规划,主要也是考察问题是否具备这两个要素,现在分析一下这两个要素:

    I、最优子结构

    这是动态规划求解最优解的第一步。最优子结构性质是:一个问题的最优解包含其子问题的最优解。发掘最优子结构性质的过程,遵循如下模式:

    1、证明问题最优解的第一个组成部分是做出一个选择。如,选择钢条第一次切割的位置,第一次选择矩阵链的划分位置等。做出这次选择会产生一个或者多个待解的子问题。

    2、对于一个给定问题,在其可能的第一步选择中,你假,定已经知道哪种选择才会得到最优解。现在无需关心这种选择是如何得到的,只是假定已经知道了这种选择。

    3、给定可获得最优解选择后,确定这次选择会产生哪些子问题,以及如何更好地刻画子空间一个刻画子问题空间的经验是:保持子问题空间尽可能简单,只在必要时才扩展它。

    4、利用Cut-and-paste方法证明:作为原问题最优解的组成部分,每个子问题的解就是它本身的最优解。证明这一点,就是利用反证法:假定子问题的解不是其自身的最优解,那么我们可以从原问题中“剪切”掉这些非最优解,将最优解“粘贴”进去,从而得到一个原问题更优的解,这与最初的解释原问题的最优解的前提假设相矛盾。

    对于不同的问题,最优子结构体现在两个方面:

    1、原问题的最优解涉及多少个子问题

    2、在确定最优解使用哪些子问题时,我们需要考察多少种选择。

    II、重叠子问题

    适合动态规划方法求解最优解的问题应该具备:子问题的空间必须足够“小”,即问题的递归算法会反复地求解相同的子问题,而不是一直生成新的子问题重叠子问题性质:递归算法反复求解相同的子问题。

    与之对应的分治算法,其求解问题时,通常在递归的每一步都生成全新的子问题。而动态规划则是,把子问题的解存放在一张表里,在需要的时候直接取出,此步操作的时间复杂仅是常量时间,故而降低了时间复杂度!

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规