算法之美:动态规划

标签: 算法 动态规划 | 发表时间:2011-08-23 22:15 | 作者:Bourbon kongshanzhanglao
出处:http://www.cnblogs.com/

前言

和分治法一样,动态规划(dynamic programing)是通过组合子问题的解而解决整个问题的。注意这里的programing翻译成立规划而不是编程。维基百科上写道

This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger subproblems by using the solutions to small subproblems.

这说明动规的关键是table,是子问题。而且动规的子问题是相互关联的。而分治算法是将问题划分成相对独立的子问题,递归的解决所有子问题,

然后合并子问题成为最终的结果。在这个过程中,分治法会做很多不必要的工作,即重复地求解公共子问题。

动规对每个子问题之求解一遍,并且将其结果保存在表中,从而避免了子问题被重复计算。

适用范围

1.动态规划通常情况下应用于最优化问题,这类问题一般有很多个可行的解,每个解有一个值,而我们希望从中找到最优的答案。

2.该问题必须符合无后效性。当前状态是历史的完全总结,过程的演变不再受此前各种状态及决策的影响。

简单动态规划问题



最大子数组和问题

题目

一个有N个整数元素的一位数组(A[0], A[1],...,A[n-1], A[n]),这个数组当然有很多子数组,那么数组之和的最大值是什么呢?

这是一道很简单的题目,但是要想写出时间复杂度为O(n)的最优解法还是需要仔细推敲下的。

例如有数组 int A[5] = {-1, 2, 3, -4, 2};

符合条件的子数组为  2,3  即答案为 5;

再明确一下题意

    1.子数组必须是连续的。

            2.不需要返回子数组的具体位置。

    3.数组中包含:正整数,零,负整数。

例如

数组: {1, -2, 3, 5, -3, 2}   返回值为 8

数组: {0, -2, 3, 5, -1, 2}   返回值为 9

数组: {-9, -2, -3, -5, -6}   返回值为 -2  注意子数组不能为空

首先我们看看最直接的穷举法

int MaxSubString(int* A, int n)
{
  int max = min;  //初始值为负无穷大
  int sum;
  for(int i = 0; i < n; i++)
  {
    sum = 0;
    for(int j = i; j < n; j++)
    {
      sum += A[j];
      if(sum > max)
        max = sum;
    }
  }
  return max;
}

这种方法最直接,当也是最耗时的,他的时间复杂度为O(n^2);

问题分析

可以优化吗?答案是肯定的,可以考虑数组的第一个元素,以及最大的一段数组(A[i], ..., A[j]),和A[0]的关系,有一下几种情况:

    1. 当0 = i = j 时,元素A[0]本身构成和最大的一段;

    2. 当0 = i < j 时,和最大的一段以A[0]开始;

    3. 当0 < i 时, 元素A[0]和最大的一段没有关系。

从上面3中情况可以看出。可以将一个大问题(N个元素数组)转化为一个较小的问题(N-1个元素的数组)。假设已经知道(A[1], ...,A[n-1])中和最大的一段数组之和为All[1],并且已经知道

(A[1],...,A[n-1])中包含A[1]的和最大的一段数组为Start[1]。那么不难看出 (A[0], ..., A[n])中问题的解All[0] = max{ A[0], A[0] + start[1], All[1] }。通过这样的分析,可以看出这个问题

无有效性,可以用动态规划来解决。

解决方案

int MaxSubString(int* A, int n)
{
        int Start = A[n - 1];
        int All = A[n - 1];
        for(int i = n - 2; i >= 0; i--)    //从后向前遍历,反之亦可。
        {
                Start = max( A[i], A[i] + Start);
                All = max(Start, All);
        }
        return All[0];                       //All[0] 中存放结果
}

我们通过动规算法解决该问题不仅效率很高(时间复杂度为O(n)),而且极其简便。




01背包问题

题目

这题非常有名,只要是计算机专业的应该都有听说过。有N件物品和一个容量为V的背包。第i件物品的体积是c[i],价值是v[i]。求解将哪些物品装入背包可使价值总和最大。

我们把题目具体下, 有5个商品,背包的体积为10,他们的体积为 c[5] = {3,5,2,7,4};  价值为 v[5] = {2,4,1,6,5};


问题分析

这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。可以将背包问题的求解看作是进行一系列的决策过程,即决定哪些物品应该放入背包,哪些不放入背包。

如果一个问题的最优解包含了物品n,即Xn = 1,那么其余X1, X2, .....,Xn-1 一定构成子问题1,2,.....,n-1在容量C - cn时的最优解。如果这个最优解不包含物品n,即Xn = 0;

那么其余 X1, X2.....Xn-1一定构成了子问题 1,2,....n-1在容量C时的最优解。  //请各位仔细品味这几句话

根据以上分析最优解的结构递归定义问题的最优解    f[i][v] = max{ f[i-1][v] , f[i-1][v - c[i]] + v[i]}

解决方案

#include<iostream>

#define max(a,b) ((a) > (b) ? a : b)
int c[5] = {3,5,2,7,4};
int v[5] = {2,4,1,6,5};
int f[6][10] = {0};
//f[i][v] = max{ f[i-1][v] , f[i-1][v - c[i]] + w[i]}

int main()
{
	for(int i = 1; i < 6; i++)
		for(int j = 1; j < 10 ;j++)
		{
			if(c[i] > j)//如果背包的容量,放不下c[i],则不选c[i]
				f[i][j] = f[i-1][j];        
			else
			{
				f[i][j] = max(f[i-1][j], f[i-1][j - c[i]] + v[i]);//转移方程式
			}
		}
		std::cout<<f[5][9];
	return 0;
}

01背包问题是最基本的动态规划问题,也是最经典,最易懂的。所以请读者仔细推敲这段代码。它包含了背包问题中设计状态、方程的最基本思想。



矩阵连乘问题

题目

给定n个矩阵{A1,A2,...,An},其中Ai与Ai+1是可乘的,i = 1,2, ...n-1。考虑这n个矩阵的乘积。由于竞争乘法满足结合律,故计算矩阵的连乘有许多不同的计算次序。

这种计算次序可以用加括号的方式确定。若一个矩阵连乘的计算次序完全确定,这是就说该连乘已完全加括号。

例如,矩阵连乘A1 *A2 *A3 *A4 可以有5种完全加括号的方式:(A1 *(A2 *(A3 *A4 ))), (A1 *((A2 *A3) *A4)),((A1 *A2 )*(A3 *A4)),

(((A1 *A2 )*A3 )*A4)。每种加括号的方式确定了一个计算的次序。不同的计算次序与矩阵连乘的计算量有密切的关系。关于矩阵如何相乘这里我就不赘述了请看about matrix 

考虑3个矩阵{A1,A2,A3}连乘的例子,假设这3个矩阵的维数分别为 10×100, 100×5, 5×50。若按照((A1*A2)*A3)计算,则计算次数为10×100×5 + 10×5×50 = 7500

若按(A1*(A2*A3))计算,则计算次数为   100×5×50 + 10×100×50 = 75000。第1种方法的计算次数是后者的10倍!由此可以看出,不同的加括号方式确定不同的计算次序对

矩阵乘法的运算量影响是巨大的。

矩阵连乘为题定义如下:给定n个矩阵{A1,A2,...,An},矩阵A1的维数为pi-1×pi, i = 1,2, ..., n,如何给矩阵连乘A1*A2*....*An完全加上括号使用矩阵乘法中计算次数最少。

问题分析

若用穷举法,能够证明需要指数时间来求解。但是时间代价高昂。现在考虑用动态规划来求解连乘问题。

为方便起见用Ai...j表示矩阵乘法Ai*Ai+1*....Aj的结果。其中i<j。那么Ai*Ai+1*.....Aj一定在Ak与Ak+1之间被分裂。i <= k < j。问题Ai*Ai+1 ... Aj完全加括号的开销等于计算矩阵

Ai...k 与计算 Ak+1...j的开销,再加上他们的结果相乘的开销。问题的最优子结构可以描述如下:假定问题Ai*Ai+1*...Aj被完全加括号的最优方式是在Ak与Ak+1之间被分裂,那么分裂

之后,最优解Ai*Ai+1*....Aj中的子链Ai*Ai+1....Ak一定是问题Ai*Ai+1*...*Ak的最优加括号方式。同样,最优解Ak+1*Ak+2*...Aj的子链一定是问题Ak+1*Ak+2*...Aj最优加括号方式。

根据上面分析,设m[i,j]表示计算Ai...j所需的最小计算次数    m[i,j] = min{m[i,k]+m[k+1,j]+pi-1pKpj }

解决方案

#include<iostream>
void main()
{
        int m[8][8], min;
        int r[8] = {10, 20, 50, 1, 100, 4, 20, 2};     /* 矩阵维数 */
 
        /* 初始化 */
       memset(m,0,sizeof(m));
        /* 每此增量加一 */
        for (int l = 1; l < 7; l++) 
       {
              /* 对于差值为 l 的两个元素 */
              for (int i = 1; i <= 7 - l; i++) 
             {
                  j = i + l;
                  /* 求其最小组合方式 */
                  min = m[i][i] + m[i+1][j] + r[i-1] * r[i] * r[j];
                  middle[i][j] = i;
                  for (int k = i + 1; k < j; k++)
                 {
                       if (min > m[i][k] + m[k+1][j] + r[i-1] * r[k] * r[j]) 
        {
                               min = m[i][k] + m[k+1][j] + r[i-1] *r[k]* r[j];
                                        middle[i][j] = k;
                        }
                  }
                        m[i][j] = min;
             }
        }
        std::cout<<m[1][N];
}

由以上代码可以很容易看出算法的时间复杂度为O(n^3)。即便如此也比穷举法的指数级时间复杂度快。

尾声

动态规划绝对不是一两篇文章可以讲清楚的。当然也不是通过一两道题目可以完全学会。学习的关键是用动规的思想去想问题,去设计状态转移方程式。

动态规划还有很多变形,如状态压缩,树形等等。这些题目虽然很难,但是工作学习之余,一边听歌,一边推敲。也是人生一大快事

作者: Bourbon 发表于 2011-08-23 22:15 原文链接

评论: 2 查看评论 发表评论


最新新闻:
· Y Combinator 举办 Demo Day,63 家创业公司亮相(2011-08-24 12:16)
· iPhone 5将支持CDMA/GSM双模(2011-08-24 12:09)
· Google+最新更新将出现在Gmail联系人栏目中(2011-08-24 12:06)
· 软件正在通吃所有工作(2011-08-24 12:05)
· 苹果两大成功动力:乔布斯文化与软硬件结合(2011-08-24 11:59)

编辑推荐:Hack, Everything!

网站导航:博客园首页  我的园子  新闻  闪存  小组  博问  知识库

相关 [算法 动态规划] 推荐:

算法之美:动态规划

- kongshanzhanglao - 博客园-首页原创精华区
和分治法一样,动态规划(dynamic programing)是通过组合子问题的解而解决整个问题的. 注意这里的programing翻译成立规划而不是编程. This is also usually done in a tabular form by iteratively generating solutions to bigger and bigger subproblems by using the solutions to small subproblems..

常用算法之动态规划法

- - 标点符
动态规划是一种将原问题拆解为若干子问题的求解方法,常常用于重叠子问题的和最有结构性能的问题. 通过动态规划的方法,计算量则圆圆小于一般的解法. 原因在于,对于重叠子问题,一般情况下会被重复计算,而动态规划则是将重复的计算简化为计算一次就放入结果表中,在下一次计算时则从结果表中查询,从而直接获得结果,因此使性能得到提升.

五大常用算法:分治、动态规划、贪心、回溯和分支界定

- - CSDN博客综合推荐文章
   在计算机科学中,分治法是一种很重要的算法. 字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并. 这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)…….

KMP、AC自动机在字符串匹配类动态规划问题中的应用

- Sosi - C++博客-Mato is No.1
有一类动态规划(其中也包含递推)问题,要求满足一些限制条件的字符串,这些限制条件是“需要含有某个子串”或“不能含有某个子串”,那么KMP、AC自动机等就有大用了. 题意:字符集中有一些字符,给出每个字符的出现概率(它们的和保证为1),再给出一个子串B,求:任给一个长度为N的字符串A(只能包含字符集中的字符),使得S是A的子串的概率.

缓存算法

- lostsnow - 小彰
没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法,我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候,用了哪个缓存对象.

BFPRT算法

- zii - 小彰
BFPRT算法的作者是5位真正的大牛(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan),该算法入选了在StackExchange上进行的当今世界十大经典算法,而算法的简单和巧妙颇有我们需要借鉴学习之处. BFPRT解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度.

贪心算法

- Shan - 博客园-首页原创精华区
顾名思义,贪心算法总是作出在当前看来最好的选择. 也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择. 当然,希望贪心算法得到的最终结果也是整体最优的. 虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解. 如单源最短路经问题,最小生成树问题等.

缓存算法

- 成 - FeedzShare
来自: 小彰 - FeedzShare  . 发布时间:2011年09月25日,  已有 2 人推荐. 没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率.

K-Means 算法

- - 酷壳 - CoolShell.cn
最近在学习一些数据挖掘的算法,看到了这个算法,也许这个算法对你来说很简单,但对我来说,我是一个初学者,我在网上翻看了很多资料,发现中文社区没有把这个问题讲得很全面很清楚的文章,所以,把我的学习笔记记录下来,分享给大家. k-Means 算法是一种  cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法.

查找算法:

- - CSDN博客推荐文章
从数组的第一个元素开始查找,并将其与查找值比较,如果相等则停止,否则继续下一个元素查找,直到找到匹配值. 注意:要求被查找的数组中的元素是无序的、随机的. 比如,对一个整型数组的线性查找代码:. // 遍历整个数组,并分别将每个遍历元素与查找值对比. 要查找的值在数组的第一个位置. 也就是说只需比较一次就可达到目的,因此最佳情况的大O表达式为:O(1).