动态规划(一):线形动态规划基础

Source
版权声明:转载请注明出处(作者转载的文章除外) https://blog.csdn.net/guoyangfan_/article/details/81151515

  嗯,要想学好动态规划,一是要有足够的IQ(怀疑自己没有),一是要有足够的时间精力,二是要有学下去的信心。现在,让我们这些刚刚入门动态规划的初学这上路吧。。。。

一:动态规划历史

动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,提出了著名的最优化原理(principle of optimality),把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解,创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》,这是该领域的第一本著作。---百度百科。

  相信你看完之后,对动态规划有一个非常浅的印象了,那就是:把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。记住这个定理,我们要用好久。(到后来会理解的)

 

二:动态规划类型

  动态规划种类繁多:线形动态规划,背包动态规划,区间动态规划,树形动态规划,数位动态规划,状态压缩类动态规划等等。

  动态规划最可怕的就是:没有固定的解法.

  但只要记住一点:把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解

  好了,让我们来逐个击破吧。

 

   前言:它是多阶段决策过程的最优化问题

  (一).线形动态规划:

    顾名思义,线形动态规划的模型类似线段。在这种模型的题目中,我们要先推断出各阶段之间的关系,列出关于各阶段之间的关系的方程。现在让我们来看一道例题(因为动态规划没有固定的解法,只能靠自己理解了)          

  首先我们来看最长上升子序列问题

  这个问题基于这样一个背景,对于含有n个元素的集合S = {a1、a2、a3……an},对于S的一个子序列S‘ = {ai,aj,ak},若满足ai<aj<ak,则称S'是S的一个上升子序列,那么现在的问题是,在S众多的上升子序列中,含有元素最多的那个子序列的元素个数是多少呢?或者说这样上升的子序列最大长度是多少呢?

    对于这种问题,我们先给出一段小代码,再进行详细的解释:

s[0]=-inf;
f[0]=0;
for(int i=1;i<=n;++i)
{
  for(int j=0;j<i;++j)
  {
    if(s[i]>s[j])
     f[i]=max(f[i],f[j]+1)
  }
}

  好了,现在进行详细解释。我们看到:这个动态规划的方程是f[i]=max(f[i],f[j]+1);

(备注:下文阶段、答案其实是同一个意思,决策类似与选择,请自己根据语境切换为自己舒适的词)

  为什么是这个方程呢?

  我们设 i 表示目前要操作的那个阶段,则,f[i]表示1~i中最长上升子序列;j 表示在这个阶段之前的调用已经操作过的阶段下标。那么,我们根据先前讲的多阶段决策过程中的最优解,每一个解都是根据先前的做出的决策进行目前阶段的决策的。那么好,开始分析方程本身:

1.  为什么 j从0开始循环到i-1 且 f[0]=0 ,s[0] 赋值为极小值(-inf)?

目前阶段 i 代表的S[i] 本身也可以算作一个上升子序列,且目前f[i]这个答案并没有做过决策,初值还是0。所以我们让j从0开始,给第一个阶段 f[0] 赋值为0,因为在阶段为0时的最大上升子序列为0。至于j从0到i-1表示调用之前决策过的阶段,逐步逼近最优解。还有,s[0]赋值为极小值意义是 i 代表的S[i] 本身也可以算作一个上升子序列,s[0]必须要比S[i]小;(因为s[i]>s[j])时才会进行决策;

 

2.  为什么方程f[i]=max(f[i],f[j]+1);是对的?

  因为(s[i]>s[j])且(s[j]> s[k](s[j]做决策时比较大小是的s[k])),所以,s[i] 必定大于 s[k],属于上升子序列。所以,在当前阶段下,有两种选择:

 1.  选择当前的较优解。 2. 选择前一阶段的最优解再加上1(现在的数值算一个)

 于是,这些比较的活就交给我们的max选择最优解了(其实手动判断也是可以的),判处来后,我们逐渐逼近最优解。

 

3.    输出:

枚举一边,找个最大值,输出一下。

 

小结

其实动态规划要难可以难,要简单可以简单(像这题)。我们无法列举出所有的题目,但我们只要记住这句话:每一个解都是根据先前的做出的决策进行目前阶段的决策的。

相信我,这句话很有用。

 

下一期:背包动态规划