赞
踩
对于一个固定的问题,他的答案也许是唯一的,但实现正确代码的方式却可以有很多。身为一个典型的平均智商人类,我肯定希望能够省时省力的找到正确答案,而这就取决于算法的使用,这也是算法的魅力。下面我想总结的是动态规划算法。
动态规划(Dynamic programming),基本思想是将问题分解为若干子问题,先对子问题进行求解,再将子问题的解结合得到原问题的解,这点与分治法较为类似。但与分治法不同的是,动态规划能够解决分治法解决不了的子问题互相独立的情况。
其实,不同的子问题的数量大多数只有多项式的量级,分治法求解时子问题被重复的计算了太多次,导致算法效率的降低。如果我们在解决子问题的同时将子问题的答案保存,以便于在后续问题需要时直接获得答案,这样就能避免大量的重复计算。
所以说,动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其他的算法。
一个问题如果可以使用动态规划解决的话,那这个问题具有两个基本要素:最优子结构性质、无后效性和重叠子问题性质。
最优化原理:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)
下面我们通过一个例题来感受一下动态规划思想。
【问题描述】
给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2…,n-1。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
输入数据:第一行为测试数据的组数m;以后每组的第一行表示矩阵个数n,第二行包括n+1个正 整数,表示n个矩阵的行列值。
输出:最少次数及连乘的计算次序。
样例输入:
1
5
5 10 4 6 10 2
样例输出:
348
(A1(A2(A3(A4A5))))
【问题分析】
首先,我们要留意的是,因为矩阵的乘法满足结合律,所以计算次序可能多种多样。例如,给定三个连乘矩阵{A1,A2,A3}的行列值为10,100,5,50,如果计算次序是(A1A2)A3,那么数乘次数为10*100*5+10*5*50=7500,而如果计算次序是A1(A2A3),乘法次数为100*5*50+10*100*50=75000,显然,计算次序不同会导致乘法次数的不同。
【算法分析】
最容易想到的,那肯定是穷举法啦,简单粗暴而且保护脑细胞。仔细分析一下,穷举出所有的计算次序,还要计算需要的数乘次数,从而找出数乘次数最少的方法,这样做的话复杂度是多少呢?不好意思,计算次序呈指数级增长。为了关爱一下自己的计算机,我们还是清楚本场主角动态规划算法吧。
我们设矩阵连乘积AiAi+1…Aj为A[i:j]。那我们的目标就变成了找出A[1:n]的最优计算次序。假设A[i:j]的最优计算次序在矩阵Ak和Ak+1之间将矩阵链断开,那么相应的加括号次序就是:(Ai..... Ak) (Ak+1 …...Aj)。对应的计算量就是,A[i:k]的计算量+A[k+1:j]的计算量+A[i:k]和A[k+1:j]相乘所需的计算量。
经过上述分析,我们如果设计算A[i:j]所需的最少数乘次数为m[i][j],原问题对应解就是m[1][n]。
当i=j时,A[i:j]是单一的矩阵,m[i][j]=0。
当i<j时,根据上述分析,m[i][j]=m[i][k]+m[k+1][j]+pi-1pkpj,所以m[i][j]可以递归定义成
代码如下:
- #include<iostream>
- using namespace std;
- const int N = 100;
- int a[N];//矩阵规模
- int c[N][N];//最优解
- int s[N][N];
- void solution(int n)
- {
- int r,i,j,k;
- for (i=0;i<=n;i++)//初始化对角线
- c[i][i]=0;
- for(r=2;r<=n;r++)//r个矩阵连乘
- {
- for(i=1;i<=n-r+1;i++)//r个矩阵的r-1个空隙中依次测试最优点
- {
- j=i+r-1;
- c[i][j]=c[i][i]+c[i+1][j]+a[i-1]*a[i]*a[j];
- s[i][j]=i;
- for(k=i+1;k<j;k++)//变换分隔位置,逐一测试
- {
- int t=c[i][k]+c[k+1][j]+a[i-1]*a[k]*a[j];
- if(t<c[i][j])//如果变换后的位置更优,则替换原来的分隔方法。
- {
- c[i][j]=t;
- s[i][j]=k;
- }
- }
- }
- }
- }
- void print(int i, int j)
- {
- if(i==j)
- {
- cout<<"A"<<i;
- return;
- }
- cout<<"(";
- print(i,s[i][j]);
- print(s[i][j]+1,j);//递归1到s[1][j]
- cout<<")";
- }
- int main()
- {
- int m;
- cin>>m;
- while(m!=0)
- {
- int n;
- cin>>n;
- for(int i=0;i<=n;i++)
- cin>>a[i];
- solution(n);
- cout<<c[1][n]<<endl;
- print(1,n);
- cout<<endl;
- m--;
- }
- return 0;
- }
总结下来,我们要运用动态规划算法时,可以参考以下几个步骤:
(1)分析最优解的性质,并刻画其结构特征。
(2)递归的定义最优解。
(3)以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值
(4)根据计算最优值时得到的信息,构造问题的最优解
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。