【免费】动态规划基础########资源-CSDN文库

需积分: 0 8 浏览量 2022-12-11 11:42:24 上传评论收藏 344KB PPTX 举报

资源推荐

资源详情

资源评论

动态规划程序设计是对解最优化问题的一种途径、一种方法，

而不是一种特殊算法。不像前面所述的那些搜索或数值计算那样，

具有一个标准的数学表达式和明确清晰的解题方法。动态规划程序

设计往往是针对一种最优化问题，由于各种问题的性质不同，确定

最优解的条件也互不相同，因而动态规划的设计方法对不同的问题

，有各具特色的解题方法，而不存在一种万能的动态规划算法，可

以解决各类最优化问题。因此读者在学习时，除了要对基本概念和

方法正确理解外，必须具体问题具体分析处理，以丰富的想象力去

建立模型，用创造性的技巧去求解。我们也可以通过对若干有代表

性的问题的动态规划算法进行分析、讨论，逐渐学会并掌握这一设

计方法。

具体计算过程如下：

S1：K=4有

F4（D1）=3，F4（D2）=4，F4（D3）=3；

S2：K=3有

F3（C1）=MIN{D3（C1，D1）+F4（D1），D3（C1，D2）+F4（D2）}

=MIN{5+3，6+4}=8

F3（C2）=D3（C2，D1）+F4（D1）=5+3=8

F3（C3）=D3（C3，D3）+F4（D3）=8+3=11

F3（C4）=D3（C4，D3）+F4（D3）=3+3=6

S3：K=2有

F2（B1）=MIN{D2（B1，C1）+F3（C1），D2（B1，C2）+F3（C2），

D2（B1，C3）+F3(C3)}=MIN{1+8,6+8,3+11}=9

F2（B2）=MIN{D2（B2，C2）+F3（C2），D2（B2，C4）+F3（C4）}

=MIN{8+8，4+6}=10

S4：K=1有

F1（A）=MIN{D1（A，B1）+F2（B1），D1（A，B2）+F2（B2）}

=MIN{5+9，3+10}=13

因此由A点到E点的全过程最短路径为A→B2→C4→D3→E；最短路程长度为13。

从以上过程可以看出，每个阶段中，都求出本阶段的各个初始状态到终点E的最短距

离，当逆序倒推到过程起点A时，便得到了全过程的最短路径和最短距离。

在上例的多阶段决策问题中，各个阶段采取的决策，一般来说是与阶段有关的，决

策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出

来的，故有“动态”的含义，我们称这种解决多阶段决策最优化的过程为动态规划程序设计

方法。

 动态规划的基本概念和基本模型构成

现在我们来介绍动态规划的基本概念。

1.阶段和阶段变量：

用动态规划求解一个问题时，需要将问题的全过程恰当地分成若干个相互联系的阶

段，以便按一定的次序去求解。描述阶段的变量称为阶段变量，通常用K表示，阶段的

划分一般是根据时间和空间的自然特征来划分，同时阶段的划分要便于把问题转化成多

阶段决策过程，如例题1中，可将其划分成4个阶段，即K=1，2，3，4。

2.状态和状态变量：

某一阶段的出发位置称为状态，通常一个阶段包含若干状态。一般地，状态可由变

量来描述，用来描述状态的变量称为状态变量。如例题1中，C3是一个状态变量。

3.决策、决策变量和决策允许集合：

在对问题的处理中作出的每种选择性的行动就是决策。即从该阶段的每一个状态出

发，通过一次选择性的行动转移至下一阶段的相应状态。一个实际问题可能要有多次决

策和多个决策点，在每一个阶段的每一个状态中都需要有一次决策，决策也可以用变量

来描述，称这种变量为决策变量。在实际问题中，决策变量的取值往往限制在某一个范

围之内，此范围称为允许决策集合。如例题1中，F3（C3）就是一个决策变量。

4.策略和最优策略：

所有阶段依次排列构成问题的全过程。全过程中各阶段决策变量所组成的有序总体

称为策略。在实际问题中，从决策允许集合中找出最优效果的策略成为最优策略。

5.状态转移方程

前一阶段的终点就是后一阶段的起点，对前一阶段的状态作出某种决策，产生后一

阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。

剩余46页未读，继续阅读

内容反馈

Nocturnal_wolf

粉丝: 39
资源: 6

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip