经典算法——动态规划教程
5星 · 超过95%的资源 需积分: 49 181 浏览量
2010-01-30
08:46:01
上传
评论 5
收藏 763KB DOC 举报 
动态规划是对最优化问题的一种新的算法设计方法。由于各种问题的性质不同，确定
最优解的条件也互不相同，因而动态规划的没计法对不同的问题，有各具特色的表示方式。
不存在一种万能的动态规划算法。但是可以通过对若干有代表性的问题的动态规划算法进
行讨论，学会这一设计方法。
多阶段决策过程最优化问题
动态规划的基本模型
在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系
的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各
个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个
阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种
把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种
问题称为多阶段决策最优化问题。
【例题 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 的最短距离。具体计算过程如下：
：，有：，，
，有：
剩余63页未读，继续阅读
- 1
- 2
- 3
前往页