文档介绍：算法设计与分析
王多强
******@hust.
六、动态规划
2017/10/15
3
动态规划的一般方法
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。
1. 多阶段决策过程
阶段:事件的发展过程分为若干个相互联系的阶段。事件的发展总是从初始状态开始,依次经过第一阶段、第二阶段、第三阶段、…,直至最后一个阶段结束。
阶段变量:描述阶段的变量称为阶段变量。在多数情况下,阶段变量是离散的,用k表示。
阶段变量也有连续的情形,如过程可以在任何时刻作出决策,且在任意两个不同的时刻之间允许有无穷多个决策时,阶段变量就是连续的,对此这里不做过多讨论。
2017/10/15
4
状态:状态表示每个阶段开始面临的自然状况或客观条件。它不以人们的主观意志为转移,也称为不可控因素。它既是当前阶段某途径的起点,也是前面阶段某途径的终点。
状态变量:过程的状态通常可以用一个或一组数来描述,称为状态变量。一般,状态是离散的,但有时为了方便也将状态取成连续的。当然,在现实生活中,由于变量形式的限制,所有的状态都是离散的,但从分析的观点,有时将状态作为连续的处理将会有很大的好处。
状态变量可以是多维的,用向量表示;实际中在每个阶段的状态维数甚至可以不同。
状态集合:当过程按所有可能不同的方式发展时,过程各段的状态变量将在某一确定的范围内取值,状态变量取值的集合称为状态集合。
2017/10/15
5
假设事件在初始状态后需要经过n个这样的阶段。一般情况下,从i阶段发展到i+1阶段(0≤i<n)可能有多种不同的途径,而事件必须从中选择一条途径往前进展。使过程从一个状态演变到下一状态。
决策:在一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择称为决策。也就是在两个阶段间选择发展途径的行为。
决策变量:描述决策的变量称决策变量,用一个数或一组数表示。不同的决策对应着不同的数值。
决策序列:事件的发展过程之中需要经历n个阶段,需要做n次“决策”,这些“决策”就构成了事件整个发展过程的一个决策序列。
多阶段决策过程:具备上述特征的过程称为多阶段决策过程(multistep decision process) ,求解多阶段决策过程问题就是求取事件发展的决策序列。
2017/10/15
6
无后效性:对任意的阶段i,阶段i以后的行为仅依赖于i阶段的状态,而与i阶段之前,过程如何达到这种状态的方式无关,这种性质称为无后效性。
状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,而不能直接作用于未来的发展。
如果某一阶段的状态已确定,则在这一阶段以后,过程的发展就不再受这阶段以前各段状态的直接影响,所有各阶段都确定时,整个过程也就确定了。
因状态满足无后效性,故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。
状态转移方程:阶段之间状态变量值的变化存在一定的关系,如果给定i阶段的状态变量x(i)的值后,第i+1阶段的状态变量x(i+1)就可以完全确定,即x(i+1)的值随x(i)和第i阶段的决策u(i)的值变化而变化,可以把这一关系看成(x(i),u(i))与x(i+1)确定的对应关系,用
x(i+1)=Ti(x(i),u(i))
表示。
这种从i阶段到i+1阶段的状态转移规律称为状态转移方程。
2017/10/15
7
2017/10/15
8
最优化问题:
每一决策都附有一定的“成本”,决策序列的成本是序列中所有决策的成本之和。
设从阶段i到阶段i+1有pi种不同的选择,则从阶段1至阶段n共有p1p2……pn种不同的途径,每个途径对应一个决策序列。
问:这些途径里面,哪一个的成本最小?
——如何求取最优决策序列?
2017/10/15
9
可行解:从问题开始阶段到最后阶段每一个合理的决策序列都是问题的一个可行解。
目标函数:用来衡量可行解优劣的标准,通常以函数形式给出。
最优解:能够使目标函数取极值的可行解。
多阶段决策过程的最优化问题就是:求能够获得问题最优解的决策序列——最优决策序列。
2017/10/15
10
2. 多阶段决策过程的求解策略
问题的决策序列表示为:(x1,x2,…,xn)
其中xi表示第i阶段的决策:
x1 x2 x3 … xn
S0 → S1 → S2 →……→ Sn
1)枚举法
穷举可能的决策序列,从中选取可以获得最优解的决策序列:
若问题的决策序列由n次决策构成,每一阶段分别有p1、p2、…、pn种选择,则可能的决策序列将有p1p2…pn个。