$2动态规划的基本概念和基本方程例1所示的线路网络是一个多阶段决策。由于所选路线不同，会有若干个不同策略，用穷举法可求出其最短路线，从A到G共有C,1C31C,1C,1C,1C,1=48条路径，每条路径要做5次加法，这样就要做240次加法运算。比较48条不同路线的距离值,D最短为F一G当问题的阶段数很多时，其计算量就增加，这种方法就不可能现实
§2 动态规划的基本概念和基本方程 例1所示的线路网络是一个多阶段决策。由于所选 路线不同，会有若干个不同策略，用穷举法可求出 其最短路线，从A到G共有 C2 1C3 1C2 1C2 1C2 1C1 1=48条路径，每条路径要做5 次加法，这样就要做240次加法运算。比较48条 不同路线的距离值，最短为 A G B1 C2 D1 E2 F2 当问题的阶段数很多时，其计算量就增加，这种 方法就不可能现实
动态规划的基本概念和基本方程一口使用动态规划方法求解决策问题首先要将问题改造成符合动态规划求解要求的形式，要涉及以下概念：阶段√状态√决策与策略√状态转移/指标函数
使用动态规划方法求解决策问题首先要将问题 改造成符合动态规划求解要求的形式，要涉及 以下概念： 阶段 状态 决策与策略 状态转移 指标函数 一、动态规划的基本概念和基本方程
划分阶段把一个复杂决策问题按照时间或空间特征分解为若于（n）个相互联系的阶段（stage），以便按照顺序求解阶段一般用下标k表示......-1阶段2阶段3阶段4阶段5阶段6阶段62DE33B5F1DE8B6F32DDE33
1、划分阶段 把一个复杂决策问题按照时间或空间特征分解为若干 （n）个相互联系的阶段（stage）,以便按照顺序求解 阶段一般用下标 k 表示 1阶段 2阶段 3阶段 4阶段 5阶段 6阶段 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 6 8 4 3 5 3 3 8 2 2 2 1 3 3 3 5 2 5 6 6 4 3
确定状态2.第三阶段状态的可达状态集合为点集合{Ci,C2,C3,C4], 记为 S3= {Ci,C2,C3,C]每阶段有若干状态(stat件，k阶段的状态特征可用状描述；状态有起始、中间、最终壮分，每一阶段的全部状态构成该阶段的可达状态集用S,表示。StES1阶段2阶段3阶段4阶段5阶段6阶段6C8DE32B5C1DE3X123N7SB631F32bD3)4E3Ca
2、确定状态 每阶段有若干状态（state）,表示某一阶段决策所面临的条 件，k 阶段的状态特征可用状态变量sk 描述； 状态有起始、中间、最终状态之分，每一阶段的全部状态 构成该阶段的可达状态集合，用Sk 表示。sk Sk S1 S2 S3 S4 S5 S6 S7 第三阶段状态的可达状态集合为点集合 {C1 ,C2 ,C3 ,C4 },记为 S3= {C1 ,C2 ,C3 ,C4 } 1阶段 2阶段 3阶段 4阶段 5阶段 6阶段 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 6 8 4 3 5 3 3 8 2 2 2 1 3 3 3 5 2 5 6 6 4 3
3、决策从第二阶段状态B出发，有三种不同的决策其允许决策集为D，（B,)={C1，C2，C}。若选取行的每阶段都要做出的点位C，则C,是状态B,在决策u,(B,)下的一选择。个新的状态，记作u（B）=C2·在k阶段s状态的庆呆衣小外阶段，EuRk状态为S,时对方案的选又值范围由允许决策集合Dk(表示，即uk（sk）S1EE26F3DE33
3、决策 每阶段都要做出决策，表示从某一阶段的某一状态出发进行的 选择。 在 k 阶段 sk 状态的决策由决策变量uk (sk ）描述，表示第k阶段 状态为 sk 时对方案的选择。其取值范围由允许决策集合 Dk （ sk ）表示，即uk （sk ） Dk （sk ）。 从第二阶段状态B1出发，有三种不同的决策， 其允许决策集为D2 (B1 )={C1 ,C2 ,C3 }。若选取 的点位C2，则C2是状态B1在决策u2 (B1 )下的一 个新的状态，记作u2 (B1 ) =C2 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 6 8 4 3 5 3 3 8 2 2 2 1 3 3 3 5 2 5 6 6 4 3