当前位置：文档之家 › 第五章 动态规划详解

第五章 动态规划详解

  • 格式：ppt
  • 大小：1.63 MB
  • 文档页数：35

下载文档原格式

  / 35

合集下载

动态规划的基本概念

动态规划的基本概念

且也必然对目标函数给予影响，阶段效应就是执行阶段 决策时给目标函数的影响。
多阶段决策过程关于目标函数的总效应是各阶段的阶段 效应累积形成的。常见的全过程目标函数有以下两种形式： （1）全过程的目标函数等于各阶段目标函数的和，即：

R=r1 (x1, u1) +r2 (x2, u2) +…+rn(xn, un) （2）全过程的目标函数等于各阶段目标函数的积，即： R=r1 (x1, u1) ×r2 (x2, u2) ×…×rn(xn, un)
例2（带回收的资源分配问题）某厂新购某种机床125台。据 估计，这种设备5年后将被其它设备所代替。此机车如在高负荷状 态下工作，年损坏率为1/2，年利润为10万元；如在低负荷状态下 工作，年损坏率为1/5，年利润为6万元。问应如何安排这些机床 的生产负荷，才能使5年内获得的利润最大？ 本问题具有时间上的次序性，在五年计划的每一年都要作出 关于这些机床生产负荷的决策，并且一旦作出决策，不仅影响到 本年利润的多少，而且影响到下一年初完好机床数，从而影响以 后各年的利润。所以在每年初作决策时，必须将当年的利润和以 后各年利润结合起来，统筹考虑。 与上面例1、例2类似的多阶段决策问题还有资源分配、生产 存贮、可靠性、背包、设备更新问题等等。
在基本方程中， rk(xk, uk)， xk+1=T(xk, uk)都是已知函数，
最优子策略fk（xk）与fk+1（xk+1）之间是递推关系， 要求出fk（xk）及uk(xk)，需要先求出fk+1（xk+1），这 就决定了应用动态规划基本方程求最优策略总是逆着 阶段的顺序进行的。
另一方面，由于k+1阶段的状态xk+1=T(xk, uk)是由前面的状态 和决策所形成的，在计算fk+1（xk+1）时还不能具体确定xk+1的，这 就要求必须就k+1阶段的各个可能状态计算fk+1（xk+1），因此动态 规划不但能求出整个问题的最优策略和最优目标值，而且还能求 出决策过程中所有可能状态的最优策略及最优目标值。

管理运筹学第5章动态规划

管理运筹学第5章动态规划
递推关系的建立
根据阶段划分、状态转移方程和最优解的性质，建立递推关系。
递推关系的求解
通过递推关系求解各阶段的最优解，最终得到整个问题的最优解。
03
动态规划的求解方法
逆推法
总结词
逆推法是从目标状态出发，逆向推算出达到目标状态的最优决策，逐步推算出初始状态的最优决策。
详细描述
逆推法的基本思想是将问题分解为若干个相互联系的阶段，从最后阶段开始，依次向前推算出每个阶 段的最优决策，直到达到初始状态。这种方法适用于具有重叠子问题和最优子结构的问题，可以避免 重复计算，提高求解效率。
详细描述
资源分配问题通常需要考虑资源的约束条件、 各部门或个体的需求和优先级，以及如何平 衡各方利益。动态规划通过将问题分解为一 系列子问题，逐一求解最优解，最终得到整 体最优解。
生产与存储问题
总结词
生产与存储问题主要研究在生产过程 中如何平衡生产与库存的关系，以最 小化生产成本和库存成本。
详细描述
特点
动态规划适用于具有重叠子问题和最优子结构特性的问题，通过将原问题分解 为子问题，逐个求解并存储子问题的解，避免了重复计算，提高了求解效率。
动态规划的重要性
解决复杂问题
动态规划能够解决一些复杂的问题，如资源分配、生产计 划、物流调度等，这些问题通常难以通过传统方法求解。
提高计算效率
通过避免重复计算，动态规划能够显著提高计算效率，尤 其在处理大规模问题时，能够大大减少计算时间和资源消 耗。
05
动态规划的优化策略
多阶段决策优化
01
02
03
阶段划分
将问题划分为若干个相互 关联的阶段，每个阶段都 有自己的决策变量和状态 转移方程。
状态转移

管理运筹学 第5章 动态规划

管理运筹学 第5章 动态规划

第一阶段：
* * * * 最优解： x = 0 x = 1 x = 0 x = 1 1 2 3 4
练习.
1.石油输送管道铺设最优方案的选择问题.下图中A为出 发点,E为目的地,B,C,D分别为三个必须建立油泵加压 站的地区,图中的线段表示管道可铺设的位置,线段旁 的数字为铺设管道线所需的费用.问如何铺设管道才使 总费用最小.
－
－ －
0
0 0
0
0 0
－
－
0
0
0
0 1 1 1 1
20 20 20 20
20 20 20 1
第三阶段：
s3
0 1 2 3 4
x3
r ( s , x ) f ( s 4 x ) 3 3 3 4 3 3
0 1 2 － － － － －
f 3 ( s3 )
0 0 0 0 11
x *3
0 0 0 0 1
咨询项目类型 待处理客户数 处理每个客户所 处理每个客 需工作日数 户所获利润
1 3 4 7 2 8 11 20
1 2 3 4
4 3 2 2
解：用动态规划来求解此题。 我们把此问题分成四个阶段，第一阶段我们决策将 处理多少个第一种咨询项目类型中的客户，第二阶段决 策将处理多少个第二种咨询项目类型中的客户，第三阶 段、第四阶段我们也将作出类似的决策。我们设 s k ＝分配给第k种咨询项目到第四种咨询项目的所 有客户的总工作日（第k阶段的状态变量）。 x k =在第k种咨询项目中处理客户的数量（第k阶段 的决策变量）。 已知 s 1 ＝10 并有 s T ( s , x ) s 3 x , T ( s , x ) s x ,s 3 2 2 2 2 2
件重量为wi公斤，每件价值ci元。现有一只可装载重量W 公斤的背包，求各种物品应各取多少件放入背包，使背 包中物品的价值最高。 这个问题可以用整数规划模型来描述。设xi为第i种 物品装入背包的件数（i =1, 2, …, n），背包中物品的总 价值为z，则 Max z = c1x1+c2x2+ … +cnxn s.t. w1x1+w2x2+…+wnxn≤W x1, x2, …, xn0 且为整数。

动态规划

动态规划

第五章 动态规划1、用动态规划方法求下面交通图由A 到B 的最短时间。

图1注：各点之间的连线旁边数字，表示时间。

2、设有三种机器，使用也分三个时期。

第一个时期使用三种机器的耗费分别为6，8，9；第二个时期使用三种机器的耗费分别为10，12，8；第三个时期使用三种机器的耗费分别为2，5，6。

但是机器的使用不是任意的，只能按图的顺序使用。

问题是如何安排机器使总耗费最小？（化为网络最短路问题求解）图23、某工厂进行甲、乙、…………………………………………………………………表1丙三种新产品的试制，估计这些新产品试制成功的概率分别为0.6，0.4和0.3。

由于工厂急于推出新产品，故厂方领导决定再拨2万元的研制费，以期提高新产品研制的概率。

据有关专家估计，把增加的研制费用于各种新产品试制时，试制成功概率如表1所示。

试把这批研制费分配给各新产品试制项目（不分配，分配给1万元或分配给2万元），以使这三种新产品均研制成功的概率最大。

新产品成功的概率P N时期1时期2时期3机器1机器2 机器34、用动态规划方法求 表2 12max ()910f x x x =+ 约束条件：1121232515,0x x x x x ≤+≤≥5、某厂生产一种产品，该产品在未来四个月的销售量估计如表2所示。

该项产品的生产准备费用为每批5百元，每件的生产费用1元，每件的存储费用每月为1元。

假定1月初的存货为1百件。

5月初的存货为0。

试求该厂在四个月内的最优生产计划。

6、现有一批资金，总额为5万元拟投资于改造三个工厂。

先对三个工厂拟订了几个不同的技术改造方案，其所需资金和投产后新增收益如表3所示。

问总投资额5万元应如何分配使用，才能使三个工厂改造后的新增收益最大？7、用动态规划方法求2123max ()492f x xx x=++约束条件：12312310,,0,x x x x x x ++=≥且为整数8、写出下列问题的动态规划的基本方程。

运筹学——动态规划

运筹学——动态规划

优子策略。该原理的具体解释是，若某一全过程
最优策略为：
p1
(s1 )
{u1
(s1 ),
u 2
(s2
),
,
u
k
(sk
),
u
n
(sn
)}
则对上述策略中所隐含的任一状态而言，
第k子过程上对应于该状态的最优策略必然包
含在上述全过程最优策略p1*中，即为
pk
(sk
)
{u
k
(sk
),
u
k 1
(sk
1
),
2．正确地定义状态变量sk，使它既能正确地描述过 程的状态，又能满足无后效性．动态规划中的状 态与一般控制系统中和通常所说的状态的概念是 有所不同的，动态规划中的状态变量必须具备以 下三个特征：
20
2021/7/26
(1)要能够正确地描述受控过程的变化特征。 (2)要满足无后效性。即如果在某个阶段状态已经给定，那么在
sk 1 Tk (sk ,uk (sk ))
上式称为多阶段决策过程的状态转移方程。有些问题的 状态转移方程不一定存在数学表达式，但是它们的状态 转移，还是有一定规律可循的。
12
2021/7/26
(六) 指标函数 用来衡量策略或子策略或决策的效果的某种数量
指标，就称为指标函数。它是定义在全过程或各 子过程或各阶段上的确定数量函数。对不同问题 ，指标函数可以是诸如费用、成本、产值、利润 、产量、耗量、距离、时间、效用，等等。
7
2021/7/26
（二）状态、状态变量和可能状态集 1.状态与状态变量。用以描述事物(或系统)在某特 定的时间与空间域中所处位置及运动特征的量，称 为状态。反映状态变化的量叫做状态变量。状态变 量必须包含在给定的阶段上确定全部允许决策所需 要的信息。按照过程进行的先后，每个阶段的状态 可分为初始状态和终止状态，或称输入状态和输出 状态，阶段k的初始状态记作sk，终止状态记为sk+1 。但为了清楚起见，通常定义阶段的状态即指其初 始状态。

05-动态规划解析

05-动态规划解析

6sk
f
* K 1
(0.96sk
0.21xk )},k
4,3,2,1
最少费用运输问题
出
2
发 城
Q4
市3
城市A A1 7 4 6
3 A2 2
4
41 A3 5 3个转运点
城市B B1 1 4
6 B2 3
3 B3 3 3个转运点
城市C 3 C1 3
4 4
C2
海 T港
2个转运点 动态规划求解表
最少费用运输问题
动态规划
>>
最少费用运输问题
将货物从城市Q运到海港T，途中经过城市A、B、C，
三个城市各有3、3、2个转运点，各点运费如图，
求从Q到T的最优路线，使总运费最少。
城市A
城市B
城市C
出2
发 城
Q
4
市3
A1 7 64
3 A2 2
4
41 A3 5
3个转运点
B1 4
1
B2
6 3
3 B3 3
3个转运点
C1 3
C2 4
2个转运点
海
T港
动态规划
动态规划是解决多阶段决策过程最优化问题的 一种方法。由美国数学家贝尔曼（Ballman） 等人在20世纪50年代提出。他们针对多阶段决 策问题的特点，提出了解决这类问题的“最优 化原理”，并成功地解决了生产管理 、 工程 技术等方面的许多实际问题。
动态规划
动态规划是现代企业管理中的一种重要决策 方法，可用于最优路径问题、资源分配问题、 生产计划和库存问题、投资问题、装载问题、 排序问题及生产过程的最优控制等。
动态规划的基本概念
阶段 状态 决策和策略 状态转移 指标函数

运筹学 第05章 动态规划

运筹学 第05章 动态规划
通过贝尔曼方程逆序求出条件最优目标函 数值集合和条件最优决策集合
k=n时，
f n xn optrn xn , un f n1 xn1
un
不存在n+1阶段
f n1 xn1 0
f n xn optrn xn , un
f n xn rn xn , u'n ( xn )
产品Q1
（件）
产品Q2
（件）
产品Q3
（件）
2 2 5
0 4 5 4
1500 800 2000
产品的利润 （千元/ 件）
示例(5.1-2)
设uk ,2,3表示第k天生产三种产品的哪一种 1
设xk xk1，xk 2，xk 3 表示第k天开始生产前三种原料的数量 2 3 0 0 2 4，b 1500, 800, 200T ，C 3, 5, 4 令A 3 2 5
必须就阶段n的所有可能状态 xn X n计算 u 'n ( xn ) 和 f n xn
un
动态规划问题求解步骤(2)
k=n-1时，
f n1 xn1 optrn xn1 , un1 f n xn
所有可能的f n xn 都已求出
根据 xn Tn1 xn1 , un1 ，就阶段n-1的所有可能状 态 xn 1 X n 1 计算 u 'n 1 ( xn 1 ) 和 f n 1 xn 1 余者类推，直到阶段1
u1
x1
u2
x2
u7
x3 … x7 周六 x8 r7
周日
r1
周一
r2
动态规划概念(5)
uk（k=1,2,3,4,5,6,7）表示第k天生产三种产 品中的哪一种以及生产多少 x1=技术环境A、市场环境C和原料b xk+1=技术环境A、市场环境C和原料b +第k 天剩余的原料 （k=1,2,3,4,5,6,7） rk=第k天生产产品获得的利润 总利润=r1+ r2+ r3+ r4+ r5+ r6+ r7

运筹学-第3版-课件-第5章 动态规划

运筹学-第3版-课件-第5章 动态规划

C1
2
1 2 2 3
D1 D2
3
2
A
B2
5
C2
6
E
4
2
B3
C3
3
D3
同样的理由，可以递推得其余阶段的铺设路线，如阶 段3在C1点的决策是D1，阶段4在D1点的决策只有E点； 由于到E点是整个铺设管道的终点，至此，决策过程完成， 铺设一条A点到E点的管道是由四个阶段的管道组成的， 如A---B3---C1---D1---E，它也称为一个策略。
B
阶段2
C
阶段3
D
阶段4
E
5
B1
4 4
6
3 6
C1
2
1 2
2
D1 D2 D3
3 4
2
A
B2
5
C2
6
E
2
3
B3
C3
3
在阶段2，从B3点出发，只有C1、C3两种可 选择的点， 如选C1,则C1就是阶段2在B3点的决策结果； C1点既是阶段2铺设管道的终点，又是阶段3 铺设管道的起点；
5
B1
4 4
6 3 6
使S= f ( xi ) 16 u j =
i 1 6 t
f ( x ) 16(5x
为最小，其中
i 1 i
6
j 1
1
4 x2 3x3 2 x4 x5 185)
100xi ,0 xi 15 f ( xi ) 120xi 300,15 < xi 30
第5章 动态规划
运 筹 帷 幄 之 中 Dynamic Programming
决 胜 千 里 之 外

运筹学第五章动态规划

运筹学第五章动态规划

和 dk 2 (sk ))；
(4) 允许决策集： D k ( s k ) ( x k , y k ) 0 ≤ y k ≤ s k ; 0 ≤ x k ≤ 1 0 0 0 ( s k y k )
状态转移方程： s k 1 s k x k y k ,s 1 5 0 0k4,3,2,1
其中s 5 表示第四阶段末的状态； (5) 阶段指标： v k ( s k ,x k ,y k ) q k y k p k x k ，k4,3,2,1；
5.1 动态规划的基本概念和模型
5.1.1 动态规划的基本概念
下面结合实例来介绍动态规划的基本概念：
【例5.1】 如图5.1所示，在处有一水库，现需从点铺设一条 管道到点，弧上的数字表示与其相连的两个地点之间所需修建 的渠道长度，请找出一条由到的修建线路，使得所需修建的渠 道长度最短。
2
A4
3
B
7
(1) 按月份分段： k4,3,2,1；
(2) 状态变量： s k 表示第 k 个月月初的库存量；
(3) 决策变量： dk1(sk表) 示第 k 个月已有库存 s的k 情况下，要定
购的商品量， dk2表(sk示) 第 个月k 已有库存 的商品量(为方便，后面将分别依次用 ，
的 来x sk 情 代k y况 替k 下，要d销k1(售sk )
(6) 动态规划基本方程：
fk(s k) (x k,y m k) a D x k(s k)v k(s k,x k,y k) fk 1 (s k 1 )
f5 (s 5 ) 0 k 4 ,3 ,2 ,1
求解（要求板书） 辅图1
辅图2
辅图3
5.2.3 动态规划的顺序解法
【 例 5.3】 图 5.3 所 示 为 一 水 利 网 络 ， A 为 水 库 ， 分B 1 ,别B 2 为,B 3 不;C 同1 ,C 的2 ,供C 3 水;D 目1 ,D 的2地，试找出给各供水目的地供水的 最短路线。

大学运筹学经典课件第五章动态规划

大学运筹学经典课件第五章动态规划

生产计划问题的动态规划解法
根据生产阶段和生产量的不同组合，构建动 态规划模型进行求解。
经典案例
多阶段生产问题、批量生产计划问题等。
图像处理与计算机视觉中的应用
图像处理中的动态规划应用
通过动态规划算法对图像进行分割、边缘检测、特征提取等 操作。
计算机视觉中的动态规划应用
在目标跟踪、立体视觉、光流计算等领域，利用动态规划求 解最优路径或策略。
决策的无后效性
在动态规划中，每个阶段的决策只与 当前状态有关，而与过去的状态和决 策无关。
边界条件与状态转移方程
边界条件
动态规划问题的边界条件通常指的是问题的初始状态和终止 状态。
状态转移方程
描述问题状态之间转移关系的方程，通常根据问题的具体性 质建立。通过状态转移方程，可以逐步推导出问题的最优解 。
应用领域
03
适用于具有时序性和阶段性特点的问题，如资源分配、任务调
度、路径规划等。
动态规划与人工智能的融合应用
强化学习
结合动态规划和强化学习算法， 通过智能体与环境交互学习最 优决策策略，实现自适应的动
态规划求解。
深度学习
利用深度学习模型强大的特征 提取和表达能力，对动态规划 中的状态转移和决策规则进行
经典案例
图像分割中的最短路径算法、立体匹配中的动态规划算法等 。
06
动态规划的扩展与前沿研究
随机动态规划
随机动态规划模型
描述随机环境下多阶段决策 问题的数学模型，涉及期望 总收益最大化或期望总成本
最小化。
求解方法
通过引入状态转移概率和决 策规则，将随机动态规划问 题转化为确定性动态规划问 题求解，常用方法有值迭代
自顶向下的求解方法（记忆化搜索）

运筹学课件 第五章动态规划

运筹学课件 第五章动态规划
2013-11-30 11

(1)在第四阶段 此时只要再走一步即到终点⑩ (B地)。 目前状态 s4可以是⑧或⑨，可选择的下一状 态X4 是⑩ 所以f4 (8) =d4 (8, 10) =3, f4 (9)=d4 (9, 10)=4 (2)在第三阶段 在第三阶段，还需两步才能到达终点，此时 f3 ( s3)=min{d3 ( s3，X3)+f4 (s4)} 目前状态s3可 以是⑤、⑥、⑦，可选择的下一状态X3有两个 点⑧或⑨
通过计算，可知从 A地到 B地总路程最小 值为 11。
2013-11-30 16
三、动态规划的基本概念

1、阶段： 把所给问题的过程恰当地分为 若干个相互联系的阶段，以便能按一定的次序 去求解。描述阶段的变量称为阶段变量，常用 k 表示。 阶段的划分，一般是根据时间和空间的自然 特征来划分，但要便于把问题的过程能转化为 多阶段的决策过程，如例 1中可分为4个阶段来 求解，k=1, 2, 3, 4。
uk
2013-11-30 27
* pk ,n 表示sk sn的最优策略, 则最优值函数
基本方程 f k ( sk ) opt vk ( sk , u k ) f k 1 ( sk 1 ) u k Dk sk 1 Tk ( sk , u k ) k 1,2, , n f (s ) 0 n 1 n 1 这是一个逆推方程.
2013-11-30 20
4.策略 策略：决策按顺序构成的序列，用p表示。
p k ,n ( sk ) : 第k阶段起至第n阶段止的策略 pk ,n ( sk ) {uk ( sk ), uk 1 ( sk 1 )... , un ( sn )} 当k 1时. p1,n ( s1 )为全过程策略. p1,n ( s1 ) P ,n ( s1 ) 1

第5章动态规划.ppt

第5章动态规划.ppt


企业在使用设备时都要考虑设备的更
新问题，因为设备越陈旧所需的维修费用
越多，但购买新设备则要一次性支出较大
的费用；现某企业要决定一台设备未来8
年的更新计划，已预测了第j年购买设备
的价格为Kj，设Gj为设备经过j年后的残
值，Cj为设备连续使用j-1年后在第j年
的维修费(j＝1，2，…，8)，问应在哪些
5.3动态规划模型的建立与求解 5.3.1动态规划模型的建立
资源分配问题 例5 某公司有资金10万元，若投资于项目j(j＝ 1，2，3)的投资额为xi时，其收益分别为g1(x1) ＝4x1，g2(x2)＝9x2，g3(x3)＝2x32，问应如何 分配投资数额才能使总收益最大?
fk (sk )

min{d uk
k
(
sk
,
uk
)

f k 1 ( sk 1 )}
f6(s6) 0
k 5,4,3,2,1
图7-2
5.1.2.动态规划的基本原理
动态规划方法的基本思想：
(1) 将多阶段决策过程划分阶段，恰当地选取状态变 量、决策变量及定义最优指标函数，从而把问题化 成一族同类型的子问题，然后逐个求解。
Vk,n = Vk,n（sk,sk+1,…,sn）
指标函数Vk,n的最优值，称为相应的最优指标
函数，记为fk(sk)。
5.2动态规划的基本概念和基本原理
5.1.2.动态规划的基本原理
• Bellman最优化原理
•作为整个过程的最优策略具有这 样的性质：即无论过去的状态和 决策如何，对前面的决策所形成 的状态而言，余下的诸决策必须 构成最优策略。
例1 生产与存贮问题

动态规划的最优性原理

动态规划的最优性原理
f3（C1）=min｛d（C1D1）+f4（D1）,d（C1D2）+f4（D2）｝ =min｛4+7,2+8｝=10, u3(C1)= D2 f3（C2）=min｛d（C2D2）+f4（D2）,d（C2D3）+f4（D3）｝ =min｛5+8,7+6｝=13, u3(C2)= D2或D3 f3（C3）=min｛d（C3D2）+f4（D2）,d（C3D3）+f4（D3）｝ =min｛10+8,9+6｝=15, u3(C3)= D3
一般情况下，多阶段决策问题存在下面的递推关系： fk（xk）= opt｛ rk(xk, uk(xk))﹡fk+1（T(xk, uk)）｝ uk∈ Dk(uk) fn+1（xn+1）=C k=n,n-1,…,1 这里rk(xk, uk(xk))是第阶段采用uk(xk)决策产生的阶段效应；fn+1（xn+1）=C是边界条件；“﹡”号大多数情况下是 “+”号，也可能是“×”号。称上述递推关系为动态规划的基本方程，这个方程是最优化原理的具体表达形式。
K=4时，出发点有D1，D2，D3，记 f4（Di）（i=1,2,3）为Di到E的最短距离；u4(Di)表示从状态Di出发采取的决策Байду номын сангаас显然： f4（D1）=7，u4(D1)=E f4（D2）=8，u4(D2)=E f4（D3）=6，u4(D3)=E K=3时，出发点有C1，C2，C3
运 筹 学
第五章 动态规划
演讲人姓名
CLICK HERE TO ADD A TITLE
2 动态规划的最优性原理
如例1，A—B2—C1—D2—E是由A到E的最短路线，我们在该路线上任取一点C1 ，按照最优性原理C1—D2—E应该是C1到E的最短路。很容易用反证法证明这一结论的正确性，从而说明最优性原理的正确性。 按最优性原理，可以将例1分成A—B—C—D—E 4个阶段，由后向前逐步求出各点到E的最短线路，直至求出A至E的最短线路。

55动态规划.

55动态规划.

9
7
4
17
11
5
3
13
5
这种方式使用起来更简单明了，最佳路线的确定方法也 20很19/8容/8 易[f(sk)－d(sk,sk+1)=f(sk+1)]，是一种值得推荐的方法。 15
在上述的求解过程中,各段的计算都利用了第 k 段和第 k+1 段的如下 关系：
fk （ sk ）＝min{ d k （ sk ， U k ）＋ fk+1 (sk+1 ) (k=4,3,2,1) (1)
在动态规划中，状态必须具有如下性质：即当某阶段状
态给定以后，在这阶段以后过程的发展不受这段以前各状态
的影响 , 这称作无后效性。如果所选定的变量不具备无后效性，
就不能作为状态变量来构造动态规划模型。如在例5.1中，当
某阶段的状态变量确定以后，假定s3=C2,因而在确定第3 阶段
的货运路线时，就只与C2 这个城市有关，而与货物由哪个城
所以, 所谓动态规划, 就是解决多阶段决策和过程最优化问题的一 种数学规划方法。显然, 由于它所解决问题的多阶段性, 因此它必然与 时间有着密切的关系, 随着时间的推移或过程的发展而决定各阶段的决 策, 从而, 产生了一个决策序列, 这就是动态的意思。然而它也可处理与 2时01间9/8无/8 关的静态问题, 只要在问题中人为地引入“时间”因素, 将问题 2 看成一个多阶段的决策过程即可。
阶段有6条路线,第4 阶段有2 条路线。
2019/8/8
5
二、状态(state)
各阶段开始时的客观条件或出发点称作状态，描述各阶
段状态的变最称作状态变量, 用s表示。状态变量的取值集合 称为状态集合, 用S表示。在例5.1中，第一阶段的状态为A， 第二阶段的状态为城市B1，B2和B3。所以状态变量s1的集合 S1={A},s2 的 集 合 是 S2={B1,B2,B3}, 依 次 有 S3={C1,C2,C3}, S4={D1,D2}。所以,在这里,状态变量的取值实际上是给定集合 的一个元素。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

7 2
8 3
16 4
f(1, 4) = 15 + 28 + 44 = 87 最优 = f(1, 3) + g(1, 4) w不变
n=4 时：前3堆的第2种情况。 4级 3级 2级 1级 13 序号 1
44 28 15 7
2
= f(2, 3) + g(1, 3) + g(1, 4)
若f(1,3)越小，则f(1,4)就越小。
F(2)
F(1)
F(1)
F(0)
F(1)
F(0)
树中可以看出，计算F(5)时要重复计算F(2)、F(3) 显然降低时间效率。此即交叠子问题，F(5) 分为 两个子问题 F(4) 和 F(3)，F(4)包含了F(3) 。
★ 单起点最短路径问题 （区别于完全最短路径问题）
概念：给定一个连通图（有向或者无向），求给定起始顶点到结束顶点 的最短路径，此即单起点（单源）最短路径问题。完全最短路径 问题要求找到从每个顶点到其他所有顶点之间的最短路径。 分段：顶点集分为k个不相交子集Vd ,1≤d≤k , k≥2 , 级内顶点不相邻。 任一条边 (u,v)，u∈Vd，v∈Vd+m，m≥1。令 |V1| = |Vk| = 1。 分级 k = 1 V1 从源点到收 点依次编号 16 源 1 点 k=2 V2 19 2 k=3 V3 12 10 5 k=4 V4 k=5 V5 计算方向
★ 数塔
问题：设有一三角形数塔如图。求一条自塔顶到塔底的路径，该路径上 节点值之和最大。 5级 91 13 46 7
78 4级
67 3级 11
73
8 65 26
18
2级 1级
40
27 14
39 15
32 8
6 12
7
13
24
11
分段：每一级台阶自然划分为一个阶段，成为多阶段决策的优化问题。 无法分段的问题，不能用动态规划法求解。 求解：动态规划法求解。自底向上计算，各实例计算满足最优性原则，
求解算法
动态的含义：求解算法施加的状态是变化的。 当前状态只与其直接前趋状态有关，对其直接 前趋状态施加求解算法，成为当前状态。 最优性原则 (Principle of Optimality)： 一个最优问题任何实例的最优解，是由该实例
......
求解算法
阶段 2
求解算法
的子实例的最优解组成的。对特定问题该原则
因3堆有2种归并法，所以一共5小类归并法。前1堆第1种情况：
4级 3级 2级 1级 13 序号 1

44 31 15 7
2
f(1, 4) = 15 + 31 + 44 = 90 = f(2, 4) + g(1, 4) w不变 = f(2, 3) + g(2, 4) + g(1, 4)
若f(2,4)越小，则f(1,4)就越小。 8
第5章 动态规划
★ 动态规划概述 ★ 数塔 ★ 最小代价子母树 ★ 非优化问题实例 ★ 单起点最短路径问题 ★最优二叉查找树 ★ 01背包问题
★ 动态规划概述
动态规划（Dynamic Programming），在20 世纪50年代由美国数学家 Richard Bellman（理查德 .贝尔曼）发明，作为多阶段决策过程最优化
如实例18的子实例为12和7，max(12+6, 7+6)=18。
数塔：动态规划法与穷举法的时间效率比较
输入规模：为便于分析，选择数塔层数k (k>0)； 基本操作：节点值求和运算；增长函数：加法次数与 k 的关系； 效率类别：没有最佳、最差情况；（都要从塔顶计算到塔底） 增长率（次数）： 各层节点数升序：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... 节点总数 n 升序：1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... 层数k（顶为1）：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ... 路径总数 t 升序： 2, 4, 8, 16, 32, ..., t = 2k-1, k>1 1. 穷举法：T(k) = (k-1) 2k-1，k>1 （指数级） 本例k=5，每条路径上5个节点做4次加法，共64次加法。 2. 动态规划法：（层节点数 = 层数） 自底向上计算，k层加法总数为k-1层节点数×2，有效率计算式： T(k) = 2×(k-1+...+3+2+1) = k(k-1), k>1 （平方级） 本例加法总数 2×(4+3+2+1) = 20次，比64次少很多。
★ 非最优化问题实例
求中国象棋马的路径
6 5 4 3 2 1 6
可用回溯法和递归法求解， 但递归法效率 很低，栈空间占用很大。
5 4 3 2 1 6 5 4 3 2 1
问题：在m×n棋盘上，求马从P点跳到Q点的所有路径。
Q
P P
Q
P
Q
Q
P P
Q
P
Q
★ 最小代价子母树
问题：n (n>1) 堆沙子，重量向量 W = (w1,...wn)。要将它们归并为1堆， 归并规则：每次只能将相邻2堆归并为1堆，经过 n-1 次归并后， 最终归并为一堆。总代价为归并过程中新产生的沙堆质量之和， 这个代价最小的归并树称为最小代价子母树。 分析：属于最优化问题，目标为总代价最小。 分段：显然需要 n-1 次归并才能将 n 堆归并为 1 堆。自然地可以将每次 归并划分为一个阶段，成为多阶段决策问题，尝试动态规划法。 求解：（此处采用自底向上的分析，找规律较简洁） 当 n=2 时：仅一种归并法即2合1。 13 7 8 16 21 4 18 当 n=3 时：有2种归并方法，第一种归并方法如图，前1堆后2堆。 3级
不一定满足（罕见），有必要检查其适用性。 子实例组成父实例，父实例分解为子实例。
阶段 1
对于某些多阶段决策问题，问题本身没有最优化要求，比如后面要讲到的
求中国象棋马从棋盘上一点移动到另一点的全部路径问题，又如计算裴波
那契序列的动态规划算法，它们属于非最优化问题的动态规划法。 动态规划法的特点： 1. 分阶段（级）决策。对最优化问题，用最优性原则设计。 2. 一般采用自顶向下分析（规模减小），自底向上计算（规模增加）。 计算过程是一级一级（一阶段一阶段）地向前推进，直到最终状态。
w[k ]
k i
j
f[i,j] ← 0(1 ≤ i ≤ n,1 ≤ j ≤ n); for i ←2 to n do //i表示层次,也是归并沙子的堆数,在上图中,表示行号 for j ←1 to n-i+1 do //表示列号 begin min ←f[i-1,j]; for k ←i-1 step -1 untill 1 do if min>f[k,j]+f[i-k,j+k] then //min{ f(1,n-1),f(1,2)+f(3,n),f(1,3)+f(4,n)… min ← f[k,j]+f[i-k,j+k] ; f[i,j] ←g[j,i+j-1]+min; end; return(f[n,1]); endp;
★设D(i,j)是从顶点集Vi中的点j到t的一条最小耗费路线,cost(i,j) 是这条路线的耗费.由后向前推算,得:
cost(i,j)=min{C(j,l)+cost(i+1,l)} C(j,l):表示顶点集Vi中的顶点j到顶点集Vi+1中的点l的耗费 cost(i+1,l):表示顶点集Vi+1中的点l到目标点t的耗费
递推求解中的交叠子问题 （非最优化问题）
实例：计算裴波那契数的递归版本。 动态规划法：自底向上计算 递推式： 依次计算F(0), F(1), F(2), ..., F(n) n > 1 ，F(n) = F(n-1) + F(n-2) 一次，各次计算结果存入数组， 最后一个元素就是F(n)。用一个 F(0) = 0, F(1) = 1 例如，F(5) 计算过程用 递归树 表示： 单循环即可简单实现。 F(5) F(4) F(3) F(2) F(1) F(3) F(2) F(1) F(0)
复杂度很高、计算量很大的问题（如求最佳子集的组合问题），要找出
一切可能解，所耗费的计算时间可能是不可以接受的。因此，人们为了 降低求解问题的难度，把求解过程分为一系列阶段，各个阶段依次按照 最优性原则计算，最后阶段计算得到最优解。包括 分段、求解 两大步。 注：不能段化的问题不能用动态规划法求解。
阶段 n
的一种通用方法，对最优化问题提出最优性原则，从而创建最优化问题
的一种新算法设计技术——动态规划，它是一种重要的应用数学工具。 至少在计算机科学圈子里，人们不仅用它解决特定类型的最优化问题， 而最终把它作为一种通用的算法设计技术，即包括某些非最优化问题。 多阶段决策过程最优化： 现实世界里有许多问题属于这种情况：它有很多解，应用要求最优解。 穷举法通过找出全部解，再从中选出最优解。这种方法对于那些计算
3
16
4
n=4 时：前1堆的第2种情况。
4级 44 31 24 7 2 8 3 f(1, 4) = 24 + 31 + 44 = 99 = f(2, 4) + g(1, 4) w不变 = f(3, 4) + g(2, 4) + g(1, 4) 若f(2,4)越小，则f(1,4)就越小。 16 4 f(1, 4) = 20 + 24 + 44 = 88
28 15
7 2 8 3
f(i, j) —— 从第 i 堆到第 j 堆的代价和。 g(i, j) —— 从第 i 堆到第 j 堆的重量和。 f(1, 3) = 15 + 28 = 43 （最优结果） = f(2, 3) + g(1, 3)