5.2动态规划的基本概念和基本方程

动态规划的基本概念与方法动态规划（Dynamic Programming，简称DP）是解决一类最优化问题的一种方法，也是算法设计中的重要思想。

动态规划常用于具有重叠子问题和最优子结构性质的问题。

它将问题分解为子问题，并通过求解子问题的最优解来得到原问题的最优解。

动态规划的基本概念是“最优子结构”。

也就是说，一个问题的最优解可以由其子问题的最优解推导出来。

通过分解问题为若干个子问题，可以形成一个递归的求解过程。

为了避免重复计算，动态规划使用一个表格来保存已经计算过的子问题的解，以便后续直接利用。

这个表格也被称为“记忆化表”或“DP表”。

动态规划的基本方法是“状态转移”。

状态转移指的是，通过已求解的子问题的解推导出更大规模子问题的解。

常用的状态转移方程可以通过问题的递推关系定义。

通过定义好状态转移方程，可以通过迭代的方式一步步求解问题的最优解。

在动态规划中，通常需要三个步骤来解决问题。

第一步，定义子问题。

将原问题划分为若干个子问题。

这些子问题通常与原问题具有相同的结构，只是规模更小。

例如，对于计算斐波那契数列的问题，可以定义子问题为计算第n个斐波那契数。

第二步，确定状态。

状态是求解问题所需要的所有变量的集合。

子问题的解需要用到的变量就是状态。

也就是说，状态是问题（解决方案）所需要的信息。

第三步，确定状态转移方程。

状态转移方程通过已求解的子问题的解推导出更大规模子问题的解。

通常情况下，状态转移方程可以通过问题的递推关系确定。

在实际应用中，动态规划常用于求解最优化问题。

最优化问题可以归纳为两类：一类是最大化问题，另一类是最小化问题。

例如，最长递增子序列问题是一个典型的最大化问题，而背包问题是一个典型的最小化问题。

动态规划的优势在于可以解决许多复杂问题，并且具有可行的计算复杂度。

但是，动态规划也有一些限制。

首先，动态规划要求问题具有重叠子问题和最优子结构性质，不是所有问题都能够满足这两个条件。

其次，动态规划需要存储计算过的子问题的解，对于一些问题来说，存储空间可能会非常大。

动态规划的基本概念基本概念设我们研究某一个过程,这个过程可以分解为若干个互相联系的阶段。

每一阶段都有其初始状态和结束状态,其结束状态即为下一阶段的初始.状态。

第一阶段的初始状态就是整个过程的初始状态,最后一阶段的结束状态就是整个过程的结束状态。

在过程的每一个阶段都需要作出决策,而每一阶段的结束状态依赖于其初始状态和该阶段的决策。

动态规划问题就是要找出某种决策方法, 使过程达到某种最优效果。

这种把问题看作前后关联的多阶段过程称为多阶段决策过程, 可用图9.1表示。

下面介绍动态规划的术语和基本概念。

(l)阶段 把所研究的过程恰当地分为若干个互相联系的相对独立过程。

(2)状态变量 用来描述系统所处状态的变量称为状态变量。

通常用s k 表示第k 阶段的初始状态，则s k +1表示第k 阶段结束时(也就是第k+l 阶段开始时)过程的状态。

通常要求状态变量具有无后效性, 即过程在第k 阶段以后的变化只与该阶段结束时的状态有关, 而与系统如何到达此状态的过程无关。

(3)决策变量的状态转移方程。

系统在第k 阶段中的变化过程, 通常我们并不关心，但我们希望知道该阶段的初始状态与结束状态之间的关系。

我们用以影响该系统的手段，也用一个变量x k 表示，称为决策变量， 则第k 阶段结束时的状态s k +1是决策变量x k 和初始状态s k 的函数, 即s k +1=T (s k ,x k ) (9-1)(9-1)称为状态转移方程。

(4)权函数 反映第k 阶段决策变量x k 的效益函数W k (s k ,x k ) 称为权函数。

(5)指标函数 判断整个过程优劣的数量指标称为指标函数。

当第k 阶段初始状态为s k 时,设我们在此阶段及以后各阶段均采取最优策略时,所获得的效益为f k (s k ), 那么有 ))}(),,(({)(11++∈=k k k k k k D x k k s f x s W F opt s f kk (9-2) 其中opt 表示最优,按具体问题可取为max 或min , D k 是决策变量x k 的定义域;F k 是某一个函数; s k +1=T (s k ,x k ).图9.1例如,描述一质点在已知力场中的运动,若我们选取该质点的坐标(x,y,z)作为状态变量, 则不能满足无后效性要求, 因质点的运动不仅与它当前的坐标有关,还与它如何来到此点的过程有关。

动态规划算法动态规划将复杂的多阶段决策问题分解为一系列简单的、离散的单阶段决策问题,采用顺序求解方法,通过解一系列小问题达到求解整个问题目的；动态规划的各个决策阶段不但要考虑本阶段的决策目标,还要兼顾整个决策过程的整体目标,从而实现整体最优决策。

需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。

必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。

一、动态规划基本思想（一）基本概念描述阶段的变量称为阶段变量k。

阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。

表示每个阶段开始所处的自然状况或客观条件。

通常一个阶段有若干个状态，描述过程状态的变量称为状态变量Sk。

某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态，这种决定称为决策，描述决策的变量成为决策变量Uk。

在实际问题中决策变量取值一般在一个范围，称之为允许决策集合（策略）。

状态转移方程：Sk+1 = Tk（Sk，?Uk）4、指标函数和最优值函数用来衡量所实现过程优劣的一种数量指标，为指标函数。

指标函数常见的形式：（1）各段指标的和的形式（2）各段指标的积的形式其中表示第j阶段的阶段指标（二）基本思想动态规划方法的关键：正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。

要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。

即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。

二、建立动态规划模型的步骤划分阶段：按时间或空间先后顺序，将过程划分为若干相互联系的阶段。

对于静态问题要人为地赋予“时间”概念，以便划分阶段。

正确选择状态变量：选择变量既要能确切描述过程演变又要满足无后效性，而且各阶段状态变量的取值能够确定。

第七章 动态规划主要内容2动态规划的基本概念动态规划的逆推解法运筹学13动态规划的应用4动态规划的基本方程2动态规划的基本方程例1：如图所示线路网络，求A到G的最短路线。

AB 1B 2C 1C 2C 3C 4D 1D 2D 3E 1E 2E 3F 1F 2G538761366835338422123335526643最短路线的性质：如果由起点A经过P点和H点而到达终点G是一条最短路线，则由点P出发经过H点到达点G的这条子路线，必定是从点P 到点G的最短路线。

根据最短路线的性质，寻找最短路线的方法，就是从最后一段开始，由后向前逐步递推，求出各点到G 点的最短路线。

1234562动态规划的基本方程运筹学k=6第六阶段f6(F1)=4f6(F2)=3F1F2G43s6=｛F1,F2｝式12动态规划的基本方程k =5第五阶段f 5(E 1)=min ｛7,8｝=7s 5=｛E 1,E 2,E 3｝E 1E 2E 3F 1F 2G35526643()()()()()73543min ,,min 262151611515=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=F f F E d F f F E d E f ①:d 5(E 1,F 1)+f 6(F 1)=3+4=7②:d 5(E 1,F 2)+f 6(F 2)=5+3=8()115F E u =E 1→F 1→G2动态规划的基本方程k=5第五阶段s k=｛E1,E2,E3｝E1 E2 E3F1F2G 355 26 643()()()()()73543min,,min262151611515=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=FfFEdFfFEdEf()115FEu= ()()()()()53245min,,min262251612525=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=FfFEdFfFEdEf()225FEu= ()()()()()93646min,,min262351613535=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=FfFEdFfFEdEf()235FEu=2动态规划的基本方程k =4第四阶段s 4=｛D 1,D 2,D 3｝()()()()()75272min ,,min 252141511414=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=E f E D d E f E D d D f ()214E D u =D 1D 2D 3E 1E 2E 3F 1F 2G22123335526643()()()()()69251min ,,min 353242522424=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=E f E D d E f E D d D f ()224E D u =()()()()()89353min ,,min 353342523434=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=E f E D d E f E D d D f ()432u D E =2动态规划的基本方程k =3第三阶段s 3=｛C 1,C 2,C 3,C 4｝()()()()()136876min ,,min 242131411313=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=D f D C d D f D C d C f ()113D C u =C 1C 2C 3C 4D 1D 2D 3E 1E 2E 3F 1F 2G6835338422123335526643()()()()()106573min ,,min 242231412323=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=D f D C d D f D C d C f ()123D C u =()()()()()98363min ,,min 343332423333=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=D f D C d D f D C d C f ()233D C u =()()()()()128468min ,,min 343432424343=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=D f D C d D f D C d C f ()343D C u =2动态规划的基本方程k =2第二阶段s 2=｛B 1,B 2｝()()()()()()()1396103131min ,,,min 33312232121311212=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=C f C B d C f C B d C f C B d B f ()212C B u =B 1B 2C 1C 2C 3C 4D 1D 2D 3E 1E 2E 3F 1F 2G8761366835338422123335526643()()()()()()()1612697108min ,,,min 43422333222322222=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=⎪⎭⎪⎬⎫⎪⎩⎪⎨⎧+++=C f C B d C f C B d C f C B d B f ()322C B u =2动态规划的基本方程k =1第一阶段s 1=｛A ｝()()()()()18163135min ,,min 2221121111=⎭⎬⎫⎩⎨⎧++=⎭⎬⎫⎩⎨⎧++=B f B A d B f B A d A f ()11B A u =AB 1B 2C 1C 2C 3C 4D 1D 2D 3E 1E 2E 3F 1F 2G5387613668353384221233355266432动态规划的基本方程()11B A u =()181=A f ()1312=B f ()212C B u =()1622=B f ()322C B u =()1313=C f ()113D C u =()1023=C f ()123D C u =()933=C f ()233D C u =()1243=C f ()343D C u =()714=D f ()214E D u =()624=D f ()224E D u =()834=D f ()234E D u =()715=E f ()115F E u =()525=E f ()225F E u =()935=E f ()235F E u =()416=F f ()G F u =16()326=F f ()G F u =26计算结果汇总A →B 1B 1→C 2C 2→D 1D 1→E 2E 2→F 2F 2→GA →B 1→C 2→D 1→E 2→F 2→G2动态规划的基本方程递推关系()()()()(){} ()⎪⎩⎪⎨⎧==+=+1,2,3,4,5,6,,min771ksfsufsusdsfkkkkkkkukkk边界条件递推关系一般形式()()()()(){}()⎪⎩⎪⎨⎧-==+=+++1,,1,,0,111nnksfsufsusvoptsfnnkkkkkkkukkk()()()()(){}()⎪⎩⎪⎨⎧-==⨯=+++1,,1,,1,,111nnksfsufsusvoptsfnnkkkkkkkukkk加法合成乘法合成2动态规划的基本方程动态规划的最优性原理：作为整个过程的最优策略，无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。

动态规划的基本概念与算法设计动态规划（Dynamic Programming）是一种解决复杂问题的优化方法，常用于计算机科学和数学领域。

它的基本思想是将一个复杂问题分解为若干个相互重叠的子问题，并通过求解子问题的最优解来构建原问题的最优解。

一、动态规划的基本概念动态规划中的概念主要包括以下几个方面：1. 最优子结构（Optimal Substructure）：一个问题的最优解可以由其子问题的最优解来构建。

也就是说，问题的最优解具备递归性质。

2. 无后效性（无后效性）：一个阶段的状态一旦确定，就不受之后决策的影响。

也就是说，在解决某个阶段的问题时，只需要考虑当前阶段的状态和选择，无需关心之后的情况。

3. 重叠子问题（Overlapping Subproblems）：子问题之间可能会出现重叠的情况，即不同的子问题具有相同的子问题。

二、动态规划的算法设计步骤动态规划的算法设计通常包括以下步骤：1. 确定状态：首先要明确问题的求解需要哪些状态量，并将问题抽象化，将问题的每个阶段的状态定义清楚。

2. 确定状态转移方程：根据问题的最优子结构，利用递归的思想，确定问题的状态转移方程。

状态转移方程描述了问题从一个阶段到下一个阶段的状态转移过程。

3. 确定初始条件和边界条件：确定问题的初始状态和边界状态，也就是递归的终止条件。

4. 确定计算顺序：确定问题的计算顺序，通常是从小规模的子问题开始，逐渐扩展到原问题的规模。

5. 填表计算：根据状态转移方程和初始条件，填充计算表格，记录子问题的最优解。

6. 求解原问题：根据计算表格中的最优解，推导出原问题的最优解。

三、动态规划的示例应用为了更好地理解动态规划的基本概念和算法设计步骤，下面以一个经典的示例问题来说明。

问题描述：给定一个数组nums，其中的元素表示一系列可抢劫的房屋的价值。

要求求解出在不触发警报的情况下，可以获得的最大抢劫价值。

解决思路：1. 状态定义：定义一个一维数组dp，其中dp[i]表示前i个房屋能够获得的最大抢劫价值。

动态规划的基本定理和基本方程
动态规划发展的早期阶段，从简单逻辑出发给出了所谓最优性原理，然后在最优策略存在的前提下导出基本方程，再由这个方程求解最优策略。

后来在动态规划的应用过程中发现，最优性原理不是对任何决策过程普遍成立，它与基本方程不是无条件等价，二者之间也不存在任何确定的蕴含关系。

基本方程在动态规划中起着更为本质的作用。

[基本定理]
对于初始状态x1∈X1，策略p1n*={u1*,..u n*}是最优策略的充要条件是对
于任意的k,1<k<=n,有
[推论]
若p1n*∈P1n(x1)是最优策略，则对于任意的k,1<k<n，它的子策略p kn*对于由x1和p1,k-1*确定的以x k*为起点的第k到n后部子过程而言，也是最优策略。

上述推论称为最优化原理，它给出了最优策略的必要条件，通常略述为：不论过去的状态和决策如何，对于前面的决策形成的当前的状态而言，余下的各个决策必定构成最优策略。

根据基本定理的推论可以得到动态规划的基本方程：
其中是决策过程的终端条件，为一个已知函数。

当x n+1只取固定的状态时称固定终端；当x n+1可在终端集合X n+1中变动时称自由终端。

最终要求的最优指标函数满足(10)式：
(9)式是一个递归公式，如果目标状态确定，当然可以直接利用该公式递归求出最优值（这种递归方法将在后文介绍，称作备忘录法），但是一般在实际应用中我们通常将该递归公式改为递推公式求解，这样一般效率会更高一些。