动态规划原理罗伯特

动态规划的原理

1． 1．动态规划的基本理论

一．动态规划的术语

在研究现实的系统时，我们必须将系统具体的术语抽象为数学统一的术语。在此先简要介绍动态规划中的常用术语。

级：我们把系统顺序地向前发展划分为若干个阶段，称这些阶段为“级”。在离散动态规划中，“级”顺序的用自然整数编号，即1，2，…，n.

状态（λ）：用来描述、刻画级的特征。状态可以是单变量，也可以时向量。在此，我们假设研究的状态具有“无记忆性”，即当前与未来的收益仅决定于当前的状态，并不依赖于过去的状态和决策的历史。

状态空间（Λ）：由全部系统可能存在的状态变量所组成。

决策：在每一级，当状态给定后，往往可以做出不同的决定，从而确定下一级的状态，这种决定称为决策。描述决策的变量称为决策变量。对每个状态λ∈Λ，有一非空集X(λ)称为λ的决策集。决策变量x(λ)∈X（λ）。

变换：若过程在状态λ，选择决策x(λ)，可确定一个状态集T（λ，x(λ)）,过程将从λ移动到其中某个状态.T(λ,x(λ))称为变换函数，它确定过程从一个状态到另一个状态的演变。T（λ,x(λ)）可分为两种类型，即确定型和不确定型。确定型的T（λ,x(λ)）只含有一个元。不确定型指我们不能确切知道决策的结果，但作

动态规划基本原理

近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOI几乎都至少有一道题目需要用动态规划的方法来解决；而竞赛对选手运用动态规划知识的要求也越来越高，已经不再停留于简单的递推和建模上了。

要了解动态规划的概念，首先要知道什么是多阶段决策问题。 一、多阶段决策问题

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

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

让我们先来看下面的例子：如图所示的是一个带权有向的多段图，要求从A到D的最短

图4-1 带权有向多段图

路径的长度(下面简称最短距离)。

我们可以搜索，枚举图中的每条路径，但当图的规模大起来时，搜索的效率显然不可能尽人意。让我们来试用动态规划的思路分析这道题：从图中可以看到，A点要到达D

第七章 动态规划

习题七

7.1计算如图所示的从A到E的最短路线及其长度（单位：km）：

（1） 用逆推解法； （2） 用标号法。 3 B1 4 D1 2 3 4 C1 3 A 2 B2 1 1 5 D2 1 E 3 3 C2 4 2 5 3 1 B3 5 3 D3

7.2 用动态规划方法求解下列问题

（1） max z ＝x12x2 x33

x1＋x2＋x3 ≤6

xj≥0 （j＝1,2,3）

（2）min z ＝ 3x12＋4x22 ＋x32

x1x2 x3 ≥ 9

xj ≥0 （j＝1,2,3）

7.3 利用动态规划方法证明平均值不等式：

(x1?x2???xn)?(x1x2?xn)n

n设xi ≥0，i＝1，2，?，n。

7.4 考虑一个有m个产地和n个销地的运输问题。设ai（i＝1，2，?，m）为产地i可发运的物资数，bj（j＝1，2

第五章 动态规划（Dynamic Programming）

第一节 离散时间系统的动态规划

一 简单例子 行车问题

穷举法：从S到F共有条路径，每条路径共有3次加法。故共有3?8?24，2n?1.(n?1) 次加法。 动态规划法：

首先计算最后阶段的时间最短的路径：x2(3)?F,可以计算出J(x1(3))=4，J(x2(3))=3 再计算第三阶段的最短路径：x1(2)?x2(3)?F可以计算出J(x1(2))+1+3，

J(x2(2))=2+3。只需要计算x1(2)到J(x1(3))，J(x2(3))及x2(2)到J(x1(3))，J(x2(3))的

最短时间。其中J(xi(.))代表xi(.)到F的最短距离。

然后计算第二阶段的最短路径：x2(1)?x1(2)?x2(3)?F,计算

x1(1?)x2?(2J)2x(和(2))x1(1)?x1(2)?J(x1(2))，取小的

J(x1(1))x2(1)?x1(2)?J(x1(2))和x2(1)?x2(2)?J(x2(2))，取小的J(x2(1))

最后计算第一阶段的最短路径：S?x2(1)?x1(2)?x2(3)?F，计算

S?x1(2)?J(x1(1))和S?x2(1)?J(x2(1)

function [p_opt,fval]=dynprog(x,DecisFun,SubObjFun,TransFun,ObjFun) % x为状态变量，一列代表一个阶段的状态

% M_函数DecisFun（k,x)表示由阶段k的状态值x求出相应的允许决策集合 % M_函数SubObjFun（k,x,u)表示阶段k的指标函数

% M_函数TransFun（k,x,u)是状态转移函数，其中x是阶段k的状态值，u是其决策集合 % M_函数ObjFun（v,f)是第k阶段到最后阶段的指标函数，当ObjFun（v,f)=v+f时，输入ObjFun（v,f)可以省略

% 输出p_opt由4列组成，p_opt=[序号组，最优轨线组，最优策略组，指标函数值组]; % 输出fval是列向量，各元素分别表示p_opt各最优策略组对应始端状态x的最优函数值

k=length(x(1,:)); % k为阶段数 x_isnan=~isnan(x);

f_opt=nan*ones(size(x));

% f_opt为不同阶段、状态下的最优值矩阵，初值为非数

d_opt=f_opt;

动态规划专题分类视图

数轴动规题： ........................................... 1 较复杂的数轴动规 ................................... 4 线性动规 ................................................... 7 区域动规： ............................................. 14 未知的动规： ......................................... 20 数轴动规题：

题1.2001年普及组第4题--装箱问题

【问题描述】有一个箱子容量为V(正整数,0≤V≤20000),同时有n个物品(0

第二行：一个整数，表示物品个数n；接下来n行，分别表示这n个物品的各自体积。 【输出格式】 输出文件box.out只有一行数据，该行只有一个数，表示最小的箱子剩余空间。 【输入样例】 24 6 8 3 12 7 9 7

【输出样例】 0

题2.1996年提高组第4题--砝码秤重 __数据加强版

【问题描述】设有n种砝码,第k种砝码有Ck

7.1多阶段决策过程及实例

在生产和科学实验中，有一类活动的过程，由于它的特殊性，可将过程分为若干个互相联系的阶段，在它的每一个阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线。这种把一个问题可看作是一个前后关联具有链状结构的多阶段过程（如图2-1所示）就称为多阶段决策过程，也称序贯决策过程。这种问题就称为多阶段决策问题。

决策状态1状态决策决策状态状态2n状态图7-1

在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义。因此，把处理它的方法称为动态规划方法。但是，一些与时间没有关系的静态规划（如线性规划、非线性规划等）问题，只要人为地引进“时间”因素，也可以把它视为多阶段决策问题，用动态规划方法去处理。

多阶段决策问题很多，现举例如下： 例1 最短路线问题

设某厂A要把一批货运到E城出售，中间可经过①～⑧城市，各城市间的交通线及距离如图2-2所示，问应选择什么

线性动规

LIS类型DP

【例题1】：最长不下降序列1078

Description:

设有整数序列b1,b2,b3,……,bm, 若存在i1< i2

第一行为一个数n，表示有n个数，第二行为n个整数序列； Output:

第一行为最大长度，第二行为满足长度的序列 Sample Input 14

13 7 9 16 38 24 37 18 4 19 21 22 63 15 Sample Output 8

7 9 16 18 19 21 22 63 【试题分析】

1、阶段和状态：

f[i]：表示以a[i]为最后一个数字的最长不下降序列的最大长度；

阶段i表示前i个数，由于每个阶段只有一个状态，所以用一维数组表示； 2、状态转移方程： 初始化：f[i]=1;

f[i]=max{f[j]+1,j

初始化： i a[i] f[i] 1 13 1 2 7 1 0 3 9 1 0 4 5 6 7 8 9 4 1 0 10 11 12 13 14 19 21 22 63 15 1 0 1 0 1 0 1 0 1 0 16 38 24 37 18 1 0 1 0 1 0 1 0 1 0 pre[i] 0

计算过程： i a[i] f[i]

JSOI2006江苏省青少年信息学奥林匹克集训队夏令营

动态规划初步

江苏省华罗庚中学 杨志军

一、引入

从一个例子说起： 【例题1】

设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示： 13

11 8

12 7 26

6 14 15 8

12 7 13 24 11

从根结点13出发向左、向右的路径长度可以是： 13－11－7－14－7，其和为52 13－11－12－14－13，其和为63 若要求从根结点开始，请找出一条路径，使路径之和最大，若存在多条请输出任意一条。 【问题分析】

① 贪心法往往得不到最优解： 13 本题若采用贪心法则：13－11－12－14－13，其和为63 但存在另一条路：13－8－26－15－24，其和为86

11 8 贪心法问题所在：眼光短浅。

根据贪心法，则13－11－21和45，而实质上13－8－40和

6 21 40 61。

② 若用穷举法：从根结点开始，将所有可能的路径求和，找出最大值，但算法时间复杂性使问题解成为不可能。

当 N＝1 P＝1 N＝2 P＝2

1、生产库存问题

例 某厂在年末估计，下年4个季度市场对该厂某产品的需求量均为dk=3 (k=1,2,3,4)，该厂每季度生产此产品的能力为bk=5 (k=1,2,3,4,)。每季度生产这种产品的固定成本为F=13（不生产时为0），每一产品的单位变动成本为C=2。本季度产品如不能售出，则需发生库存费用g=1/件，仓库能贮存产品的最大数量Ek=4。试问如何安排4个季度的生产，以保证在满足市场需求的前提下，使生产和库存总量用最小?

解：首先分析一下这类问题。设xk—第k季度的计划生产量，sk—第k季度初的库存，?1,xk?0，可以得到数学模型： yk??0,x?0k?4?13yk?2xk?sk?1?min?k?1?s.t.sk?1?sk?xk?3??。 ?xk?(3?4)yk?xk?5??sk?4??xk,sk?0,yk?0or1k?1,2,3,4??显然，这个问题是一个混合整数规划。但由于这类问题可以按时间先后顺序分成四个阶段，故可用动态规划方法求解。

(1) 将每个季度看作一个阶段，就有一个四阶段的决策问题。

(2)Sk--第k季度初的仓库库存量，在问题中，s1=s5=0, 0?sk?E?3,k=2,3,4。 (3) xk--第k季度的生产