1多阶殷决过程的录龙化 具体说,此问题先从0开始,因为v0是 终点。再无后继过程,故可以接着考虑第4阶 毅上所有可能状态,v的最优后续过程.因 为从v,巧到v的路线是唯一的,所以,v 最优决策和最优后继过程就是到vρ,它们 的最短距离分别是5和3。 接着考虚阶段3上可能的状态,而6,v 到v0的最优决策和最优后继过程.在状态V5 上,虽然到κ是8,到是9,但是综合考虑后 继过程整体最优,取最优决策是到ⅳ,最优后 继过程是V 最短距离是12.同 埋,状态v的最优决策是至;V的最优决 策是到vgo
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
项多阶段决歌过程的圾优化 同样,当阶段3上所有可能状恋的最 优后继过程都已求得后,便可以开始考慮 阶段2上所有可能状态的最优决策和最优 后继过程,如V的最优决策是到κ,最优路 线是v2→v→0,最短距离是15.依此 类推,最后可以得到从初始状态V的最优 决策是到v最优路线是→巧v→→Ⅵ0 全程的最短距离是18。图5-1中粗实线表 示各点到的最优路线,每点上方括号内的 数字表示该点到终点的最短路距离
17 1.多阶段决策过程的最优化 同样，当阶段3上所有可能状态的最 优后继过程都已求得后，便可以开始考虑 阶段2上所有可能状态的最优决策和最优 后继过程，如v2的最优决策是到v5,最优路 线是v2→v5→v9→v10 ，最短距离是15…依此 类推，最后可以得到从初始状态v1的最优 决策是到v3最优路线是v1→v3→v7→v9→v10 ， 全程的最短距离是18。图5—1中粗实线表 示各点到的最优路线，每点上方括号内的 数字表示该点到终点的最短路距离
项多阶段决歌过程的圾优化 综上所述可见,全枚举法虽可找出最优 方案,但不是个好算法,局部最优法则完全 是个错误方法,只有动态规划方法属较科学 有效的算法。它的基本思規是,把一个比较 度杂的问题分解为一系列同类型的更易求解 的子问题,便于应用计算机。整个求解过程 分为两个阶段,先按整体最优的思想逆序地 求出各个子问题中所有可能状态的最优决策 与最优路线值,然后再顺序地求出整个问题 的最优策略和最优路线。计算过程中,系统 地删去了所有中间非最优的方案组合,从而 使计算工作量比穷举法大为諴少
18 1.多阶段决策过程的最优化 综上所述可见，全枚举法虽可找出最优 方案，但不是个好算法，局部最优法则完全 是个错误方法，只有动态规划方法属较科学 有效的算法。它的基本思想是，把一个比较 复杂的问题分解为一系列同类型的更易求解 的子问题，便于应用计算机。整个求解过程 分为两个阶段，先按整体最优的思想逆序地 求出各个子问题中所有可能状态的最优决策 与最优路线值，然后再顺序地求出整个问题 的最优策略和最优路线。计算过程中，系统 地删去了所有中间非最优的方案组合，从而 使计算工作量比穷举法大为减少
自2.动忘规划的基本概龙 动规划的基本概念 使用动态规划方法解决多阶段 决策问题,首先要将实际问题写成 态规捌模型。同时也为了今后叙 述和讨论方便,这里嚣要对动态规 灲的下述一些基本术语进一步加以 说明和定义
19 2.动态规划的基本概念 一 、动态规划的基本概念 使用动态规划方法解决多阶段 决策问题，首先要将实际问题写成 动态规划模型，同时也为了今后叙 述和讨论方便，这里需要对动态规 划的下述一些基本术语进一步加以 说明和定义：
自2.动变规划的基本概念 (一)阶段和阶段变量 为了便于求解和表示决策及过程的发展顺 序,而把所给问题恰当地划分为若干个相互联系 又有区别的子问题,称之为多段决策冋题的阶段。 个阶段,就是需要作出一个决策的子问题。通 常,阶段是按决策进行的时间或空间上先后顺序 划分的。用以描述阶段的变量叫作阶段变量, 般以k表示阶段变量,阶段数等于多段决策过程 从开始到结束所需作出决策的数目,图5-1所示 的最短路问题就是一个四阶段决策过程
20 2.动态规划的基本概念 (一) 阶段和阶段变量 为了便于求解和表示决策及过程的发展顺 序，而把所给问题恰当地划分为若干个相互联系 又有区别的子问题，称之为多段决策问题的阶段。 一个阶段，就是需要作出一个决策的子问题，通 常，阶段是按决策进行的时间或空间上先后顺序 划分的。用以描述阶段的变量叫作阶段变量， 一 般以k表示阶段变量．阶段数等于多段决策过程 从开始到结束所需作出决策的数目，图5—1所示 的最短路问题就是一个四阶段决策过程