1多阶段决过程的优化 动态规圳方法导引 例5.1:为了说明动态规划的基本思想方法 和特点,下面以图5-1所示为例讨论的求最短路 问题的方法。 第一种方法称做全枚举法或穷举法。它的 基本思想是列举出所有可能发生的方案和结果 再对它们一—进行比较,求出最优方案。这里从 v到的路程可以分为4个阶段。第一段的走法 有三种,第二三两段的走法各有两种,第四段的 走法仅一种,因此共有3×2×2×1=12条可能的 路线。分别算岀各条路线的距离,最后冼行比较 可知最优路线是ⅵ- V V1a,最短 距高是18
17 1.多阶段决策过程的最优化 四、动态规划方法导引 例5.1：为了说明动态规划的基本思想方法 和特点，下面以图5-1所示为例讨论的求最短路 问题的方法。 第一种方法称做全枚举法或穷举法。它的 基本思想是列举出所有可能发生的方案和结果， 再对它们一一进行比较，求出最优方案。这里从 v1到v10的路程可以分为4个阶段。第一段的走法 有三种，第二三两段的走法各有两种，第四段的 走法仅一种，因此共有3×2×2×1＝12条可能的 路线，分别算出各条路线的距离，最后进行比较， 可知最优路线是v1 →v3 → v7 → v9 →v10 ,最短 距离是18．
录阶段夹菜过程的提花化 显然,当组成交通网络的节点很多 时,用穷举法求最优路线的讣算工作量 将会十分庞大,而且其中包含着许多重 复计算 第二种方法即所谓“局部最优路径” 法,是说某人从k出发。他并不顾及全线 是否最短,只是选择当前最短途径 “逢近便走” 错误地以为局部最优会 致整体最优。在这种想法指导下,所取 决策必是V→>V V5 10 程长度是20:显然,这种方法的结果常 是错误的 18
18 1.多阶段决策过程的最优化 显然，当组成交通网络的节点很多 时，用穷举法求最优路线的计算工作量 将会十分庞大，而且其中包含着许多重 复计算． 第二种方法即所谓“局部最优路径” 法，是说某人从k出发，他并不顾及全线 是否最短，只是选择当前最短途径， “逢近便走” ，错误地以为局部最优会 致整体最优，在这种想法指导下，所取 决策必是v1 →v3 →v5 → v8 → v10 ，全 程长度是20；显然，这种方法的结果常 是错误的．
1多阶段决过程的优化 第三种方法是动态规划方法。动态 规划方法寻求该最短路问题的基本思想 是,首先将问题划分为4个阶段。每次的 选择总是综合后继过程的一并最优进行 考慮,在各段所有可能状态的最优后继 过程都已求得的情况下,全程的最优路 线便也随之得到。 为了找出所有可能状态的最优后继 程 边态规划方法总是从过程的最后 阶段开始考慮。然后逆着实际过程发展 的顺序,逐段向前递推计算直至始点
19 1.多阶段决策过程的最优化 第三种方法是动态规划方法。动态 规划方法寻求该最短路问题的基本思想 是，首先将问题划分为4个阶段，每次的 选择总是综合后继过程的一并最优进行 考虑，在各段所有可能状态的最优后继 过程都已求得的情况下，全程的最优路 线便也随之得到。 为了找出所有可能状态的最优后继 过程，动态规划方法总是从过程的最后 阶段开始考虑，然后逆着实际过程发展 的顺序，逐段向前递推计算直至始点
1多阶段决过程的最优化 具体说,此问题先从开始,因为是 终点。再无后继过程,故可以接着考虑第4阶 上所有可能状态,的最优后续过程.因 为从啊,v到v0的路线是唯一的,所以, 的最优决策和最优后继过程就是到v10,它价 的最短距离分别是5和3。 接着考虑阶段3上可能的状态 到V的最优决策和最优后继过程,在状态V 上,虽然到v是8,到v是9,但是综合考虑后 继过程整体最优,取最优决策是到,最优后 继过程是V→v→0,最短距离是12.同 理,状态v的最优决策是至;v的最优决 策是到v
20 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
录阶段夹菜过程的提花化 同样,当阶段3上所有可能状态的最 优后继过程都已求得后,便可以开始考慮 阶段2上所有可能状态的最优决策和最优 后继过程,如V的最优决策是刭κ,最优路 线是V→0,最短距离是15依此 类推,最后可以得到从初始状态V的最优 决策是到w最优路线是→吟听 全程的最短距离是18。图51中粗实线表 示各点到的最优路线,每点上方括号内的 数字表示该点到终点的最短路距离
21 1.多阶段决策过程的最优化 同样，当阶段3上所有可能状态的最 优后继过程都已求得后，便可以开始考虑 阶段2上所有可能状态的最优决策和最优 后继过程，如v2的最优决策是到v5,最优路 线是v2→v5→v9→v10 ，最短距离是15…依此 类推，最后可以得到从初始状态v1的最优 决策是到v3最优路线是v1→v3→v7→v9→v10 ， 全程的最短距离是18。图5—1中粗实线表 示各点到的最优路线，每点上方括号内的 数字表示该点到终点的最短路距离