6、7-动态规划1
需积分: 0 171 浏览量
2022-08-08
19:47:41
上传
评论
收藏 1.73MB DOCX 举报
动态规划主要用于求解能够用不同的划分阶段表
示的动态过程的优化问题。
一般的动态规划问题可以简单地表示为一个多阶
段决策问题，其表示如下：
比方说，我们要求解如下的最短路问题：
用动态规划求解的多阶段模型必须具有无后效性，
也被称为马尔可夫（Markov）性。也就是说对于下面的
问题：
给定 s
k
，系统以后的状态就完全由 k 及其以后各阶
段的决策所决定，和系统经由什么路径到达 s
k
无关，
即和 s
1
,s
2
,...,s
k-1
,的取值无关。
对于无后效的最短路问题，我们可以通过图解法解
决：从最后阶段开始逆过程行进方向依次导出到终点的
最短距离（最优过程指标函数）及相应路径（最优决策）
其合理性来源于任何满足马尔可夫性的序贯决
策问题所具有的最优性原理：对于先前决策所形成的状
态而言，其以后的所有决策应能构成最优策略。
另一方面，通过顺推的方法求出上面最短路问题也
是可行的。
评论0