l多阶段决策过程的最优化 同样,当阶段3上所有可能状态的最 优后继过程都已求得后,便可以开始考虑 阶段2上所有可能状态的最优决策和最优 后继过程,如v的最优决策是到v,最优路 线是n2→V 0,最短距离是15.依此 类推,最后可以得到从初始状态v的最优 决策是到最优路线是n→→吃 全程的最短距离是18。图51中粗实线表 示各点到的最优路线,每点上方括号内的 数字表示该点到终点的最短路距离
17 1.多阶段决策过程的最优化 同样，当阶段3上所有可能状态的最 优后继过程都已求得后，便可以开始考虑 阶段2上所有可能状态的最优决策和最优 后继过程，如v2的最优决策是到v5,最优路 线是v2→v5→v9→v10 ，最短距离是15…依此 类推，最后可以得到从初始状态v1的最优 决策是到v3最优路线是v1→v3→v7→v9→v10 ， 全程的最短距离是18。图5—1中粗实线表 示各点到的最优路线，每点上方括号内的 数字表示该点到终点的最短路距离
l多阶段决策过程的最优化 综上所述可见,全枚举法虽可找出最优 方案,但不是个好算法,局部最优法则完全 是个错误方法,只有动态规划方法属较科学 有效的算法。它的基本思想是,把一个比较 复杂的间题分解为一系列同类型的更易求解 的孑问题,便于应用计算机。整个求解过程 分为两个阶段,先按整体最优的思想逆序地 求出各个子问题中所有可能状态的最优决策 与最优路线值,然后再顺序地求出整个问题 的最优策略和最优路线。计算过程中,系统 地删去了所有中间非最优的方案组合,从而 使计算工作量比穷举法大为减少
18 1.多阶段决策过程的最优化 综上所述可见，全枚举法虽可找出最优 方案，但不是个好算法，局部最优法则完全 是个错误方法，只有动态规划方法属较科学 有效的算法。它的基本思想是，把一个比较 复杂的问题分解为一系列同类型的更易求解 的子问题，便于应用计算机。整个求解过程 分为两个阶段，先按整体最优的思想逆序地 求出各个子问题中所有可能状态的最优决策 与最优路线值，然后再顺序地求出整个问题 的最优策略和最优路线。计算过程中，系统 地删去了所有中间非最优的方案组合，从而 使计算工作量比穷举法大为减少
2动态规划的基本概念 动态规划的基本概念 使用动态规划方法解决多阶段 决策问题,首先要将实际问题写成 动态规划模型,同时也为了今后叙 述和讨论方便,这里需要对动态规 划的下述一些基本术语进一步加以 说明和定义
19 2.动态规划的基本概念 一 、动态规划的基本概念 使用动态规划方法解决多阶段 决策问题，首先要将实际问题写成 动态规划模型，同时也为了今后叙 述和讨论方便，这里需要对动态规 划的下述一些基本术语进一步加以 说明和定义：
2.动态规划的基本概念 (一)阶段和阶段变量 为了便于求解和表示决策及过程的发展顺 序,而把所给问题恰当地划分为若干个相互联系 又有区别的子问题,称之为多段决策问题的阶段 个阶段,就是需要作出一个决策的子问题,通 常,阶段是按决策进行的时间或空间上先后顺序 划分的。用以描述阶段的变量叫作阶段变量, 般以k表示阶段变量.阶段数等于多段决策过程 从开始到结束所需作出决策的数目,图5-1所示 的最短路问题就是一个四阶段决策过程
20 2.动态规划的基本概念 (一) 阶段和阶段变量 为了便于求解和表示决策及过程的发展顺 序，而把所给问题恰当地划分为若干个相互联系 又有区别的子问题，称之为多段决策问题的阶段。 一个阶段，就是需要作出一个决策的子问题，通 常，阶段是按决策进行的时间或空间上先后顺序 划分的。用以描述阶段的变量叫作阶段变量，一 般以k表示阶段变量．阶段数等于多段决策过程 从开始到结束所需作出决策的数目，图5—1所示 的最短路问题就是一个四阶段决策过程
学2.动态规划的基本概念 二)状态、状态变量和可能状态集 1.状态与状态变量。用以描述事物 或系统)在某特定的时间与空间域中所处 位置及运动特征的量,称为状态。反映状 态变化的量叫做状态变量。状态变量必 包含在给定的阶段上确定全部允许决策所 需要的信息。按照过程进行的先后,每个 阶段的状态可分为初始状态和终止状态, 或称输入状态和输出状态,阶段k的初如 状态记作S,终止状态记为。但为了 清楚起见,通常定义阶段的状态即指其初 始状态
21 2.动态规划的基本概念 （二）状态、状态变量和可能状态集 1.状态与状态变量。用以描述事物 (或系统)在某特定的时间与空间域中所处 位置及运动特征的量，称为状态。反映状 态变化的量叫做状态变量。状态变量必须 包含在给定的阶段上确定全部允许决策所 需要的信息。按照过程进行的先后，每个 阶段的状态可分为初始状态和终止状态， 或称输入状态和输出状态，阶段k的初始 状态记作sk，终止状态记为sk+1。但为了 清楚起见，通常定义阶段的状态即指其初 始状态