没有合适的资源?快使用搜索试试~ 我知道了~
经典动态规划,其中好几个关于动态规划的例题,帮助理解这个重要的内容。
资源推荐
资源详情
资源评论
动态规划是对最优化问题的一种新的算法设计方法。由于各种问题的性质不同,确定
最优解的条件也互不相同,因而动态规划的没计法对不同的问题,有各具特色的表示方式。
不存在一种万能的动态规划算法。但是可以通过对若干有代表性的问题的动态规划算法进
行讨论,学会这一设计方法。
多阶段决策过程最优化问题
动态规划的基本模型
在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系
的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此各
个阶段决策的选取不能任意确定,它依赖于当前面临的状态,又影响以后的发展。当各个
阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线。这种
把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种
问题称为多阶段决策最优化问题。
【例题 1】最短路径问题。图中给出了一个地图,地图中每个顶点代表一个城市,两个
城市间的连线代表道路,连线上的数值代表道路的长度。现在,想从城市 A 到达城市 E,
怎样走路程最短,最短路程的长度是多少?
【分析】把从 A 到 E 的全过程分成四个阶段,用 k 表示阶段变量,第 1 阶段有一个初
始状态 A,两条可供选择的支路 ABl、AB2;第 2 阶段有两个初始状态 B1、 B2,B1 有三
条可供选择的支路,B2 有两条可供选择的支路……。用 dk(x
k
,x
k+1
)表示在第 k 阶段由初始
状态 x
k
到下阶段的初始状态 x
k+1
的路径距离,Fk(x
k
)表示从第 k 阶段的 x
k
到终点 E 的最短距
离,利用倒推方法求解 A 到 E 的最短距离。具体计算过程如下:
:,有:,,
,有:
,有:
: ,有:
!!!
""""因此由 ! 点到 # 点的全过程的最短路径为 !$ 一$$$#。最短路程长度
为 。
""""从以上过程可以看出,每个阶段中,都求出本阶段的各个初始状态到过程终点 # 的最短
路径和最短距离,当逆序倒推到过程起点 ! 时,便得到了全过程的最短路径及最短距离,
同时附带得到了一组最优结果即各阶段的各状态到终点 # 的最优结果。
在上例的多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策
依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,
故有“动态”的含义,称这种解决多阶段决策最优化问题的方法为动态规划方法。
根据上例分析和动态规划的基本概念,可以得到动态规划的基本模型如下:
(1)确定问题的决策对象。
(2)对决策过程划分阶段。
(3)对各阶段确定状态变量。
(4)根据状态变量确定费用函数和目标函数。
(5)建立各阶段状态变量的转移过程,确定状态转移方程。
动态规划的基本知识
动态规划是研究一类最优化问题的方法,在经济、工程技术、企业管理、工农业生产
及军事等领域中都有广泛的应用。近年来,在 ACM/ICPC 中,使用动态规划(或部分应用
动态规划思维)求解的题不仅常见,而且形式也多种多样。而在与此相近的各类信息学竞赛
中,应用动态规划解题已经成为一种趋势,这和动态规划的优势不无关系。
1、动态规划的常用名词
在学习动态规划之前,先得对下面的名词有所了解。本书将标准名词作了一些简化,便
于大家更好的理解。
(1)状态(smte)
对于一个问题,所有可能到达的情况(包括初始情况和目标情况)都称为这个问题的一个
状态。
(2)状态变量(s
k
)
对每个状态 k 关联一个状态变量 s
k
,它的值表示状态 k 所对应的问题的当前解值。
(3)决策(decision)
决策是一种选择,对于每一个状态而言,你都可以选择某一种路线或方法,从而到达下
一个状态。
(4)决策变量(d
k
)
在状态 k 下的决策变量 d
k
的值表示对状态 k 当前所做出的决策。
(5)策略
策略是一个决策的集合,在我们解决问题的时候,我们将一系列决策记录下来,就是一
个策略,其中满足某些最优条件的策略称之为最优策略。
(6)状态转移函数(t)
从一个状态到另一个状态,可以依据一定的规则来前进。我们用一个函数 t 来描述这样
的规则,它将状态 i 和决策变量 d
i
映射到另一个状态 j,记为 t(i,d
i
)=j
(7)状态转移方程(f)
状态转移方程 f 描述了状态变量之间的数学关系。一般来说,与最优化问题相应,状态
转移方程表示 s
i
的值最优化的条件,或者说是状态 i 所对应问题的最优解值的计算公式,
用代数式表示就是:
s
i
=f({(s
j
,d
j
)|i=t(j,d
j
),对决策变量 d
j
所有可行的取值})
2、最优化原理
1951 年美国数学家 R.Bellman 等人,根据一类多阶段问题的特点,把多阶段决策问题
变换为一系列互相联系的单阶段问题,然后逐个加以解决。一些静态模型,只要人为地引
进“时间”因素,分成时段,就可以转化成多阶段的动态模型,用动态规划方法去处理。与
此同时,他提出了解决这类问题的“最优化原理”(Principleofoptimality):
“一个过程的最优决策具有这样的性质:即无论其初始状态和初始决策如何,其今后诸策
略对以第一个决策所形成的状态作为初始状态的过程而言,必须构成最优策略”。简言之,
一个最优策略的子策略,对于它的初态和终态而言也必是最优的。
这个“最优化原理”如果用数学化一点的语言来描述的话,就是:假设为了解决某一优化
问题,需要依次作出 n 个决策 D
1
,D
2
,…,D
n
,如若这个决策序列是最优的,对于任何一
个整数 k,1 < k < n,不论前面 k 个决策是怎样的,以后的最优决策只取决于由前面决策所
确定的当前状态,即以后的决策 D
k+1
,D
k+2
,…,D
n
也是最优的。
最优化原理是动态规划的基础。任何一个问题,如果失去了这个最优化原理的支持,就
不可能用动态规划方法计算。
3、什么是动态规划
动态规划是运筹学的一个分支。与其说动态规划是一种算法,不如说是一种思维方法来
得更贴切。因为动态规划没有固定的框架,即便是应用到同一道题上,也可以建立多种形
式的求解算法。许多隐式图上的算法,例如求单源最短路径的 Dijkstra 算法、广度优先搜
索算法,都渗透着动态规划的思想。还有许多数学问题,表面上看起来与动态规划风马牛
不相及,但是其求解思想与动态规划是完全一致的。
因此,动态规划不像深度或广度优先那样可以提供一套模式,需要的时候,取来就可以
使用;它必须对具体问题进行具体分析处理,需要丰富的想象力去建立模型,需要创造性
的思想去求解。
4、动态规划适于解决什么样的问题
准确地说,动态规划不是万能的,它只适于解决一定条件的最优策略问题。
或许,大家听到这个结论会很失望:其实,这个结论并没有削减动态规划的光辉,因为
属于上面范围内的问题极多,还有许多看似不是这个范围中的问题都可以转化成这类问题。
上面所说的“满足一定条件”主要指下面两点:
(1)状态必须满足最优化原理;
(2)状态必须满足无后效性。
所谓的无后效性是指:“过去的决策只能通过当前状态影响未来的发展,当前的状态是对
以往决策的总结”。
这条特征说明什么呢?它说明动态规划适于解决当前决策和过去状态无关的问题。状态,
出现在策略的任何一个位置,它的地位都是相同的,都可以实施同样的决策。这就是无后
效性的内涵。
5、用动态规划解题的好处
说了这么多的动态规划,它到底给我们解题能带来什么好处呢?
其实动态规划的最大优势在于它具有极高的效率,而且动态规划还有其他的优势,例如:
动态规划可以得出一系列解,算法清晰简便,程序易编、易调,等等。
最优化原理与无后效性
上面已经介绍了动态规划模型的基本组成,现在需要解决的问题是:什么样的“多阶段
决策问题”才可以采用动态规划的方法求解?
一般来说,能够采用动态规划方法求解的问题必须满足. 最优化原理 和. 无后效性原则 。
(1)动态规划的最优化原理。作为整个过程的最优策略具有如下性质:无论过去的状态
和决策如何,对前面的决策所形成的当前状态而言,余下的诸决策必须构成最优策略。
可以通俗地理解为子问题的局部最优将导致整个问题的全局最优,即问题具有最优子结
构的性质,也就是说一个问题的最优解只取决于其子问题的最优解,非最优解对问题的求
解没有影响。在例题 1 最短路径问题中,A 到 E 的最优路径上的任一点到终点 E 的路径也
必然是该点到终点 E 的一条最优路径,满足最优化原理。下面来讨论另外一个问题。
【例题 2】余数最少的路径。
""""如图所示,有 个点,分别是
!、、、,相邻两点用两条连线
,
%
& &表示两条通行的道路。连
线上的数字表示道路的长度。定义从 ! 到
的所有路径中,长度除以 所得余数最小的
路径为最优路径。
""""求一条最优路径。
【分析】在这个问题中,如果还按照例题 1 中的方法去求解就会发生错误。按照例题
1 的思想,A 的最优取值可以由 B 的最优取值来确定,而 B 的最优取值为(1+3) mod 4 =
0,所以 A 的最优值应为 2,而实际上,路径 C1-C3-C5 可得最优值为(2+1+1) mod 4 =
0,所以,B 的最优路径并不是 A 的最优路径的子路径,也就是说,A 的最优取值不是由 B
的最优取值决定的,即其不满足最优化原理,问题不具有最优子结构的性质。
由此可见,并不是所有的“决策问题”都可以用“动态规划”来解决,运用“动态规划”来处理
问题必须满足最优化原理。
(2)动态规划的无后效性原则。所谓无后效性原则,指的是这样一种性质:某阶段的状
态一旦确定,则此后过程的演变不再受此前各状态及决策的影响。也就是说,“未来与过去
无关”,当前的状态是此前历史的一个完整总结,此前的历史只能通过当前的状态去影响过
程未来的演变。具体地说,如果一个问题被划分各个阶段之后,阶段 I 中的状态只能由阶
段 I+1 中的状态通过状态转移方程得来,与其他状态没有关系,特别是与未发生的状态没
有关系,这就是无后效性。从图论的角度去考虑,如果把这个问题中的状态定义成图中的
顶点,两个状态之间的转移定义为边,转移过程中的权值增量定义为边的权值,则构成一
个有向无环加权图,因此,这个图可以进行“拓扑排序”,至少可以按他们拓扑排序的顺序
去划分阶段。
看一看下面的两个具体例子。
【例题 3】货郎担问题。对于平面给定的 n 个点,编程确定一条连结各点的、闭合的游
历路线问题。图中给出了 7 个点的情况问题的解。
【例题 4】旅行路线问题。在货郎担问题的基础上,若规定这种游历路线先从最左边开
始,严格地由左至右到最右边的点,然后再严格地由右至左到出发点,求整个路程最短的
路径长度。图中给出了 7 个点问题的解。
例 图 货郎担问题 例 图 旅行路线图
【分析】这两个问题看起来很非常相似,但本质上是完全不同的。为了方便讨论,可
以将每个顶点标记号码。由于必然经过最右边的顶点 7,所以一条路(P1-P2)可以看做两条
路(P1-7)与(P2-7)的结合。因此,这个题目的状态可以用两条道路结合的形式表示。可以
把这些状态中,两条路中起始顶点相同的状态归于一个阶段,设为阶段[P1,P2]。
那么,对于旅行路线问题来说,阶段[P1,P2]如果可以由阶段[Q1,Q2]推出,则必须满
足的条件就是:Pl < Q1 或 P2 < Q2。例如,阶段[3,4]中的道路可以由阶段[3,5]中的道路
加一条边 4—5 得出,而阶段[3,5]的状态却无法由阶段[3,4]中的状态得出,因为在旅行
路线问题的要求中必须严格地由左到右来旅行。所以如果已经知道了阶段[3,4]中的状态,
则阶段[3,5]中的状态必然已知,因此,问题满足无后效性原则,可以考虑用动态规划方
法求解。
""""而对于货郎担问题,阶段与阶段之间没有什么必然的“顺序”。
如道路','属于阶段(,),可由属于阶
段(,)的道路','推出;而道路
','属于阶段(,),可由属于阶段(,)的道路
','推出。如果以顶点表示阶段,推出关系表示
边,那么,阶段(,)与阶段(,)对应的关系就如图右所示。
可以很清晰地看出,这两个阶段的关系是“有后效性”的。因为这个
图中存在“环路”。对于这个问题是不能像上一个问题那样来解决
的。
阶段关系图
剩余63页未读,继续阅读
资源评论
A1965104943
- 粉丝: 0
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功