l多阶段决策过程的最优化 动态规划求解的多阶段决策问题的特点 通常多阶段决策过程的发展是通过状态的 系列变换来实现的。一般情况下,系统在某个阶 段的状态转移除与本阶段的状态和决策有关外 还可能与系统过去经历的状态和决策有关。因此, 问题的求解就比较困难复杂。而适合于用动态规 划方法求解的只是一类特殊的多阶段决策问题, 即具有“无后效性”的多阶段决策过程。所谓无 后效性,又称马尔柯夫性,是指系统从某个阶段 往后的发展,仅由本阶段所处的状态及其往后的 决策所决定,与系统以前经历的状态和决策(历史) 无关
12 1.多阶段决策过程的最优化 三、动态规划求解的多阶段决策问题的特点 通常多阶段决策过程的发展是通过状态的一 系列变换来实现的。一般情况下，系统在某个阶 段的状态转移除与本阶段的状态和决策有关外， 还可能与系统过去经历的状态和决策有关。因此， 问题的求解就比较困难复杂。而适合于用动态规 划方法求解的只是一类特殊的多阶段决策问题， 即具有“无后效性”的多阶段决策过程。所谓无 后效性，又称马尔柯夫性，是指系统从某个阶段 往后的发展，仅由本阶段所处的状态及其往后的 决策所决定，与系统以前经历的状态和决策(历史) 无关
1多阶段决策过程的最优化 四、动态规划方法导引 例5.1:为了说明动态规划的基本思想方法 和特点,下面以图5-1所示为例讨论的求最短路 问题的方法。 第一种方法称做全枚举法或穷举法。它的 基本思想是列举出所有可能发生的方案和结果 再对它 进行比较,求出最优方案。这里从 v到v的路程可以分为4个阶段。第一段的走法 有三种,第二三两段的走法各有两种,第四段的 走法仅一种,因此共有3×2×2×1=12条可能的 路线,分别算出各条路线的距离,最后进行比较 可知最优路线是吃→吆亠 吃10,最短 距离是18
13 1.多阶段决策过程的最优化 四、动态规划方法导引 例5.1：为了说明动态规划的基本思想方法 和特点，下面以图5-1所示为例讨论的求最短路 问题的方法。 第一种方法称做全枚举法或穷举法。它的 基本思想是列举出所有可能发生的方案和结果， 再对它们一一进行比较，求出最优方案。这里从 v1到v10的路程可以分为4个阶段。第一段的走法 有三种，第二三两段的走法各有两种，第四段的 走法仅一种，因此共有3×2×2×1＝12条可能的 路线，分别算出各条路线的距离，最后进行比较， 可知最优路线是v1 →v3 → v7 → v9 →v10 ,最短 距离是18．
l多阶段决策过程的最优化 显然,当组成交通网络的节点很多时,用 穷举法求最优路线的计算工作量将会十分庞大, 而且其中包含着许多重复计算 第二种方法即所谓“局部最优路径”法, 是说某人从k出发,他并不顾及全线是否最短, 只是选择当前最短途径,“逢近便走”,错误 地以为局部最优会致整体最优,在这种想法指 导下,所取决策必是ⅵ→3→亐→哟→0 全程长度是20;显然,这种方法的结果常是错 误的
14 1.多阶段决策过程的最优化 显然，当组成交通网络的节点很多时，用 穷举法求最优路线的计算工作量将会十分庞大， 而且其中包含着许多重复计算． 第二种方法即所谓“局部最优路径”法， 是说某人从k出发，他并不顾及全线是否最短， 只是选择当前最短途径， “逢近便走” ，错误 地以为局部最优会致整体最优，在这种想法指 导下，所取决策必是v1 →v3 →v5 → v8 → v10 ， 全程长度是20；显然，这种方法的结果常是错 误的．
1多阶段决策过程的最优化 第三种方法是动态规划方法。动态 规划方法寻求该最短路问题的基本思想 是,首先将问题划分为4个阶段,每次的 选择总是综合后继过程的一并最优进 考虑,在各段所有可能状态的最优后继 过程都已求得的情况下,全程的最优路 线便也随之得到。 为了找出所有可能状态的最优后继 过程,动态规划方法总是从过程的最后 阶段开始考虑,然后逆着实际过程发展 的顺序,逐段向前递推计算直至始点 15
15 1.多阶段决策过程的最优化 第三种方法是动态规划方法。动态 规划方法寻求该最短路问题的基本思想 是，首先将问题划分为4个阶段，每次的 选择总是综合后继过程的一并最优进行 考虑，在各段所有可能状态的最优后继 过程都已求得的情况下，全程的最优路 线便也随之得到。 为了找出所有可能状态的最优后继 过程，动态规划方法总是从过程的最后 阶段开始考虑，然后逆着实际过程发展 的顺序，逐段向前递推计算直至始点
多阶段决策过程的最优化 具体说,此问题先从吃开始,因为vo是终点。 再无后继过程,故可以接着考虑第4阶段上所有可 状态K,的最优后续过程.因为从,到vo的 路线是唯一的,所以,v的最优决策和最优后继 过程就是到v0,它们的最短距离分别是5和3 接着考虑阶段3上可能的状态听 到 10的最优决策和最优后继过程.在状态v5上,虽然 到v是8,到是9,但是综合考虑后继过程整体最 优,取最优决策是到v,最优后继过程是→9 1o,最短距离是12.同理,状态的最优决策 v;v的最优决策是到v
16 1.多阶段决策过程的最优化 具体说，此问题先从v10开始，因为v10是终点。 再无后继过程，故可以接着考虑第4阶段上所有可能 状态v8 ,v9的最优后续过程．因为从v8 ,v9 到v10的 路线是唯一的，所以v8 ,v9 的最优决策和最优后继 过程就是到v10 ，它们的最短距离分别是5和3。 接着考虑阶段3上可能的状态v5 ,v6 , v7 , 到 v10的最优决策和最优后继过程．在状态V5上，虽然 到v8是8，到v9是9，但是综合考虑后继过程整体最 优，取最优决策是到v9,最优后继过程是v5→v9 → v10 ，最短距离是12．同理，状态v6的最优决策是至 v8 ；v7的最优决策是到v9