录阶段夹菜过程的提花化 综上所述可见。全枚举法虽可找出最优 方案,但不是个好算法,局部最优法则完全 是个错误方法,只有动态规坩方法属较科学 有效的算法。它的基本思想是,把一个比较 复条的问题分解为一系列同类型的更易求解 的子问题,便于应用计算杋。整个求解过程 分为两个阶段。先按整体最优的思想逆序地 求出各个子问题中所有可能状态的最优决策 与最优路线值,然后再顺序地求岀整个问题 的最优策略和最优路线。讣算过程中,系统 地删去了所有中间非最优的方案组合,从而 使计算工作量比穷举法大为减少
22 1.多阶段决策过程的最优化 综上所述可见，全枚举法虽可找出最优 方案，但不是个好算法，局部最优法则完全 是个错误方法，只有动态规划方法属较科学 有效的算法。它的基本思想是，把一个比较 复杂的问题分解为一系列同类型的更易求解 的子问题，便于应用计算机。整个求解过程 分为两个阶段，先按整体最优的思想逆序地 求出各个子问题中所有可能状态的最优决策 与最优路线值，然后再顺序地求出整个问题 的最优策略和最优路线。计算过程中，系统 地删去了所有中间非最优的方案组合，从而 使计算工作量比穷举法大为减少
角2.欲变规划的基本概心 动恋规圳的基本概念 使用动态规灲方法解决多阶段 决策问题。首先要将实际问题写成 动态规灲模型,同时也为了今后叙 述和讨论方便,这里需要对动态规 灲的下述一些基本术语进一步加以 说明和定义
23 2.动态规划的基本概念 一 、动态规划的基本概念 使用动态规划方法解决多阶段 决策问题，首先要将实际问题写成 动态规划模型，同时也为了今后叙 述和讨论方便，这里需要对动态规 划的下述一些基本术语进一步加以 说明和定义：
2.动变规划的基本概论 (一)阶段和阶段变量 为了便于求解和表示决策及过程的发展顺 序,而把所给问题恰当地划分为若干个相互联系 又有区别的子问题,称之为多段决策问题的阶段。 个阶段。就是需要作出一个决策的子问题,通 常,阶段是按决策进行的时间或空间上先后顺序 划分的。用以描述阶段的变量叫作阶段变量,一 般以k表示阶段变量,阶段数等于多段决策过程 从开始到结束所需作出决策的数目,图5-1所示 的最短路问题就是一个四阶段决萆过程
24 2.动态规划的基本概念 (一) 阶段和阶段变量 为了便于求解和表示决策及过程的发展顺 序，而把所给问题恰当地划分为若干个相互联系 又有区别的子问题，称之为多段决策问题的阶段。 一个阶段，就是需要作出一个决策的子问题，通 常，阶段是按决策进行的时间或空间上先后顺序 划分的。用以描述阶段的变量叫作阶段变量， 一 般以k表示阶段变量．阶段数等于多段决策过程 从开始到结束所需作出决策的数目，图5—1所示 的最短路问题就是一个四阶段决策过程
2.动恋规划的基本概 (二)状态、状态变量和可能状态集 1.状态与状态变量。用以描述事物 (或系统)在某特定的时间与空间域中所处 位置及运动特征的量,称为状态。反映状 态变化的量叫做状态变量。状态变量必须 包含在给定的阶段上确定全部允许决策所 需要的信息。按照过程进行的先后,每个 阶段的状态可分为初始状态和终止状态, 或称输入状态和输出状态,阶段k的初始 状态记作S,终止状态记为S1。但为了 清楚起见。通常定义阶段的状态即指其初 始状态
25 2.动态规划的基本概念 （二）状态、状态变量和可能状态集 1.状态与状态变量。用以描述事物 (或系统)在某特定的时间与空间域中所处 位置及运动特征的量，称为状态。反映状 态变化的量叫做状态变量。状态变量必须 包含在给定的阶段上确定全部允许决策所 需要的信息。按照过程进行的先后，每个 阶段的状态可分为初始状态和终止状态， 或称输入状态和输出状态，阶段k的初始 状态记作sk，终止状态记为sk+1。但为了 清楚起见，通常定义阶段的状态即指其初 始状态
动恋规划的基不概 2.可能状态集 般状态变量的取值有一定的范围或允许集 ,称为可能状态集,或可达状态集。可能状态 集实际上是关于状态的约東奈件。通常可能状态 集用相应阶段状态S的大写字母S表示,S∈S, 可能状态集可以是一离散取值的集合,也可以为 连续的取值区间。视具体问题而定,在图5-1 所示的最短路问题中,第一阶段状态为闪,状态 变量s的状态集合S={h};第二阶段则有三个状 态 V?,V/,状态变量S的状态集合 v;第三阶段也有三个状 态 状态变量S的状态集合 3={v,V6,V;第四阶段则有二个状态 ,VG,状态变量S的状态集合S={vs,V9 26
26 2.动态规划的基本概念 2．可能状态集 一般状态变量的取值有一定的范围或允许集 合，称为可能状态集，或可达状态集。可能状态 集实际上是关于状态的约束条件。通常可能状态 集用相应阶段状态sk的大写字母Sk表示，sk∈Sk， 可能状态集可以是一离散取值的集合，也可以为 一连续的取值区间，视具体问题而定．在图5—1 所示的最短路问题中，第一阶段状态为v1，状态 变量s1的状态集合S1={v1}；第二阶段则有三个状 态 ： v2 ,v3 ,v4 , 状态变量 s2 的 状 态 集 合 S2={v2 ,v3 ,v4} ； 第 三 阶 段 也 有 三 个 状 态 :v5 ,v6 ,v7 ， 状 态 变 量 s3 的 状 态 集 合 S3={v5 ,v6 ,v7} ； 第 四 阶 段 则 有 二 个 状 态 ： v8 ,v9 , 状态变量s4的状态集合S4={v8 ,v9} ；