第一节 动态规划简介

基本概念

  动态规划(DP)是运筹学的一个分支,是求解决策过程最优化的数学方法。它将多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。在现实生活中,我们经常会使用到动态规划。例如求最短路径、库存管理、排序、装载等问题,用动态规划方法比用其他方法更加简便。

  动态规划主要用于求解以时间划分阶段的动态过程问题。但是在一些与时间无关的问题中,我们可以人为地引入时间因素,把它视为多阶段决策过程,也可以使用动态规划来求解。

基本思想

  动态规划算法经常用于求解具有某种最优性的问题中。在这类问题里,可能会有很多的可行解。每个解都对应一个值,我们希望得到具有最优解的值。动态规划算法的思路与分治法类似,其具体的思想也是将问题分割成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。

  在使用分治法的过程中,有些子问题可能计算了多次。如果我们能够保存已经解决的子问题的答案,在需要的时候直接拿出来,这样就会节省很多时间。我们可以使用一个表来存放我们计算的子问题的结果,无论这个问题在以后是否会用到,只要它被计算过,我们就将它存入表格中。这就是动态规划的基本思想。

相关术语与性质

  首先,我们来介绍动态规划的三要素——阶段、状态和决策。

  阶段:把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,阶段数就可能不同.描述阶段的变量称为阶段变量。在多数情况下,阶段变量是离散的,用k表示。此外,也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策,且在任意两个不同的时刻之间允许有无穷多个决策时,阶段变量就是连续的。

  状态:状态表示每个阶段开始面临的自然状况或客观条件,它不以人们的主观意志为转移,也称为不可控因素。过程的状态通常可以用一个或一组数来描述,称为状态变量。一般,状态是离散的,但有时为了方便也将状态取成连续的。

  决策:一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择(行动)称为决策。在最优控制中,也称为控制。在许多问题中,决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量,因状态满足无后效性,故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。

  在介绍决策时,我们提到了一个很重要的性质——无后效性。这是动态规划算法的的基本准则:

  我们要求状态具有下面的性质:如果给定某一阶段的状态,则在这一阶段以后过程中的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了;换句话说,过程的每一次实现可以用一个状态序列表示,在前面的例子中每阶段的状态是该线路的始点,确定了这些点的序列,整个线路也就完全确定。从某一阶段以后的线路开始,当这段的始点给定时,不受以前线路(所通过的点)的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性。

  状态转移方程:给定k阶段状态变量x(k)的值后,如果这一阶段的决策变量一经确定,第k+1阶段的状态变量x(k+1)也就完全确定,即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化,那么可以把这一关系看成(x(k),u(k))与x(k+1)确定的对应关系,我们来用x(k+1)=Tk(x(k),u(k))表示。它展示了从k阶段到k+1阶段的状态转移规律,我们称之为状态转移方程。

  由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程,可供选取的策略有一定的范围限制,这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。

  最优化原理:作为整个过程的最优策略,它满足:相对前面决策所形成的状态而言,余下的子策略必然构成“最优子策略”。一个问题满足最优化原理也称其拥有最优子结构性质。最优性原理实际上是要求问题的最优策略的子策略也是最优。

理解

  综合前面的概念,如果我们把动态规划求解问题的过程比作工厂的生产线,那么阶段就是生产某个商品的不同环节,状态就是工件当前的状态,决策就是对工件进行的操作。之前对工件进行的操作只是在当时起效,我们可以在后面的过程中对它进行进一步的加工。不同阶段是对前面产品的一个小小的总结,由一个个过程,最终构成了最终的生产线。

  一个状态经过一个决策变成了另外的一个状态,这个过程就是状态转移。而用来描述状态转移的方程就是状态转移方程。

适用范围

  虽然动态规划很强大,但是它并不是万能的,只能够解决多阶段决策最优化问题。一般在题目中,出现让你求最优解的就要考虑使用动态规划了。但是需要满足一下两个条件。

  1. 最优子结构(最优化原理)
  2. 无后效性

  一个最优解,它的子问题的解也是最优解,我们就称这个问题具有最优子结构。那无后效性呢?就是在状态i求解时需要用到状态j,而求解j的时候需要k…当求解状态N的时候,需要用到i。那么这个时候就形成了一个环,无法求解了。

解题方法

  在判断题目可以使用动态规划解决之后,我们可以使用以下几种方法进行解题:

  1. 模型匹配法我们首先要考虑的就是这个方法了。分析题目,如果这个题目是我们之后讲到的模型,就可以直接套用;
  2. 三要素法确定题目中的三要素,从比较明显的入手,尝试解题;
  3. 规律法多计算出几组数据,试寻找他们之间的联系,建立方程;
  4. 边界条件法找到问题的边界条件,分析边界条件和与之邻接状态之间的联系。
  5. 放宽约束和增加约束对问题修改,增加或删除一些条件,以便于解题。