动态规划算法（具体问题具体分析）

动态规划（dunamic programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼等人在研究多阶段决策过程的优化问题时，提出著名的最优化原理，从此创立了动态规划。动态规划应用及其广泛，包括工程技术、经济、工业产业、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

1.原理

动态规划在经济管理、生产调度、工程技术和最有控制等方面得到了广泛应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其他方法求解更方便。

2.概念引入

在现实生活中，有一类活动的过程，由于他的特殊性，可将过程分成若干个互相联系的阶段，在他的每个阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，他依赖与当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有‘’动态‘’的含义，称这种解决多阶段决策最优化的过程为动态规划方法。

3.基本思想

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解为若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解决的子问题的答案。不管该子问题以后是否被用到，只要他被计算过，就将其结果填入表中，这就是动态规划的基本思路。具体的动态规划算法多种多样，到那时他们具有相同的填表格式。

4.适用条件

多阶段决策问题中，各个阶段采用的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有动态的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。

任何思想方法都有一定的局限性，超出了特定条件，他就失去了作用。同样动态规划也并不是万能的。使用动态规划的问题必须满足最优化原理和无后效性。

a.最优化原理（最优子结构性质）

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

b.无后效性

将各阶段按照一定的次序列排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，无后效性。

c.子问题的重叠性

动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，他在实现的过程中，不得不存储产生过程中的各种状态，所以他的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受，而搜索算法在时间上无法承受，所以我们舍空间而取时间。

5.分类

动态规划的数学模型。根据决策过程的演变是确定性的还是随机性的。可分为确定性决策过程和随机性决策 过程。另外，也可按照时间参量是离散的或是连续的变量。可分为离散决策过程和连续决策过程。组合起来就有离散确定性、离散随机性、连续确定性、连续随机性四种决策过程模型。

对于确定性的决策过程。问题中的下一段的状态已由当前段的状态及决策完全确定。对于随机性决策过程，他与确定性决策过程的区别在于下一段的状态并不能由当前段的状态及决策完全确定，而是按某种概率分布来决定下一段的状态。这种概率分布是由当前段的状态和策略完全确定。

6.局限性

动态规划对于解决多阶段决策问题的效果是明显的，但是动态规划也有一定的局限性。首先，他没有统一的处理方式，必须根据问题的各种性质并结合一定的技巧来处理；另外当变量的维度增大时，总的计算量及存储量急剧增大。因而，受计算机的存储量及计算速度的限制，当今的计算机仍不能用动规划来解决较大规模的问题，这就是‘’维数障碍‘’

7.基本概念

多阶段决策问题

如果一类活动过程可以分为若干个互相联系的阶段，在每一个阶段都需做出决策（采取措施），一个阶段的决策确定以后，常常影响到下一个阶段的决策，从而就完全确定了一个过程的活动路线，则称他为多阶段决策问题

各个阶段的决策构成一个决策序列，称为一个策略。每一个阶段都有若干个决策可供选择，因而有许多策略供我们选取，对应于一个策略可以确定活动的效果，这个效果可以用数量来确定，策略不同，效果也不同，多阶段策略问题就是要在可以选择那些策略中间选取一个最优策略，使在预定的标准下达到最好的效果。

动态规划问题中的术语

阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便求解，过程不同，阶段数就可能不同，描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用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阶段的状态转移规律，称为状态转移方程。

最优化原理：作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子决策必然构成“最优子策略”。

最优性原理实际上要求问题的最优策略的子策略也是最优。