算法-动态规划入门(C++实现)

2022-02-01 11:52
83
0
添加收藏

 对于一个固定的问题,他的答案也许是唯一的,但实现正确代码的方式却可以有很多。身为一个典型的平均智商人类,我肯定希望能够省时省力的找到正确答案,而这就取决于算法的使用,这也是算法的魅力。下面我想总结的是动态规划算法。

    动态规划(Dynamic programming),基本思想是将问题分解为若干子问题,先对子问题进行求解,再将子问题的解结合得到原问题的解,这点与分治法较为类似。但与分治法不同的是,动态规划能够解决分治法解决不了的子问题互相独立的情况。

      其实,不同的子问题的数量大多数只有多项式的量级,分治法求解时子问题被重复的计算了太多次,导致算法效率的降低。如果我们在解决子问题的同时将子问题的答案保存,以便于在后续问题需要时直接获得答案,这样就能避免大量的重复计算。

      所以说,动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其他的算法。

     一个问题如果可以使用动态规划解决的话,那这个问题具有两个基本要素:最优子结构性质、无后效性和重叠子问题性质。

      最优化原理:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

      无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。

      重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)

   

     下面我们通过一个例题来感受一下动态规划思想。
 

1.矩阵连乘问题
【问题描述】

     给定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)根据计算最优值时得到的信息,构造问题的最优解
————————————————
版权声明:本文为CSDN博主「不可能我吊哥天下无敌」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/aller_665720/article/details/120990102

 

 

全部评论