动态规划问题的解题思路 (2)联合考虑两个阶段的最优选择。 当旅行者离终点还有两站时，他必然处在C1,C2或C3的某一点上。 C1到终点的路有两条：C1→D1→E,C1→D2→E,旅行者从这两条 路线中选最短的一条，并且不管是经过D或D2,到达该点后，他应 循着从D1或D2到E的最短路线继续走。因此 从C,到E的最短路程为： (d(C,D)+f(D) 1+3 min =min d(C1,D2)+f(D2) 4+4 即从C1到的最短路线为C1→D,→E,记f(C,)三45 如果从C2出发 d(C2,D)+f(D) 6+3 min min =7 dC2,D2)+f(D2) 3+4 fC2)=7 如果从C3出发 「dC3,D)+f(D) 3+3 min min =6 fC3)=6 6 dC3,D2)+f(D2) 3+4
6 (2)联合考虑两个阶段的最优选择。 当旅行者离终点还有两站时，他必然处在C1，C2或C3的某一点上。 C1到终点的路有两条：C1D1E， C1D2E，旅行者从这两条 路线中选最短的一条，并且不管是经过D1或D2，到达该点后，他应 循着从D1或D2到E的最短路线继续走。因此 从C1到E的最短路程为： 1 2 2 1 1 1 min min 4 ( , ) ( ( , ) ( 3 4 ) ) 4 d C D D 1 C D f D f d 即从C1到E的最短路线为C1D1E，记 1 f C( ) 4 如果从C2出发 2 1 1 2 2 2 2 ( , ) ( ) ( , ) ( ) 3 4 6 3 min min 7 ( ) 7 d C D d C D f D f C f D 如果从C3出发 3 1 3 1 3 2 2 min min 6 ( ) 6 ( , ( ) ( ) 3 3 4 d C D f , ) ( ) 3 f C C f D D d D 动态规划问题的解题思路 A B 1 B 2 B 3 C 3 C 2 C 1 D 1 D 2 E 2 5 3 7 5 6 3 2 4 5 1 5 1 4 6 3 3 3 3 4
动态规划问题的解题思路 (3)再联合起来考虑三个阶段的最优选择。 从B,点出发的最优选择为 「d(B,C)+f(C) 7+4 mind(B,C2)+f(C2) =min{5+7 11 f(B)÷115 d(B,C3)+f(C3) 6+6 从B2点出发的最优选择为 [d(B,C)+f(C) 3+4 min d(B2,C2)+f(C2) min 2+7}=7 fB2)=7 d(B2,C3)+fC3) 4+6 从B3点出发的最优选择为 d(B3,C)+f(C) [5+4 min d(B3,C2)+f(C2) =min{1+7=8 f(B3)=8 d(B,C3)+f(C3) 5+6 2014-12-15
2014-12-15 7 （3）再联合起来考虑三个阶段的最优选择。 从B1点出发的最优选择为 1 1 1 2 2 1 1 3 1 3 min ( , ) ( ) min 5 7 11 ( ) 11 ( , ) ( ) ( , ) ( ) 7 4 6 6 d B C f C f d B C f C B d B C f C 从B2点出发的最优选择为 2 2 2 2 2 3 3 2 1 1 min ( , ) ( ) min 2 7 7 ( ) 7 ( ( , ) ( ) 3 , ) ( ) 4 6 d 4 d B C f C f B B d f C f B C C C 从B3点出发的最优选择为 3 1 1 3 3 3 3 3 2 2 ( , ) ( ) 5 4 min min 8 ( ) 8 ( , ( , ) ( ) 5 6 d B C ) ( ) 1 7 d B C f C f B d B C C C f f 动态规划问题的解题思路 A B 1 B 2 B 3 C 3 C 2 C 1 D 1 D 2 E 2 5 3 7 5 6 3 2 4 5 1 5 1 4 6 3 3 3 3 4
动态规划问题的解题思路 (4)四个阶段联合考虑时从A到E的最优选择。 d(A,B)+f(B) [2+11 min d(A,B2)+f(B2)=min5+7 =11 f(A)=11 d(A,B3)+f(B3) 3+8 从A到E的最短路线为A→B3→C2→D2→E,距离为11。 以上计算过程可以在图上通过标号法实现 11 A 3 0 11 A 3 5 2014-12-15
2014-12-15 8 （4）四个阶段联合考虑时从A到E的最优选择。 3 1 2 2 3 1 ( , ) ( ) 2 11 min ( , ) ( ) min 5 7 11 ( ) 11 ( , ) ( ) 3 8 d A B f B d A B f B f A d A B f B 从A到E的最短路线为AB3C2D2E，距离为11。 1 A B1 B2 B3 C3 C2 C1 D1 D2 E 2 5 3 7 5 6 3 2 4 5 1 5 4 6 3 3 3 3 4 3 4 4 7 6 11 7 8 11 以上计算过程可以在图上通过标号法实现 动态规划问题的解题思路 0
动态规划的基本概念 1.阶段(stage):指一个问题需要作出决策的步数。 通常用k表示问题的阶段数。阶段一般是根据时间和空间的自然特征 来划分的。 2.状态(state):表示每个阶段开始所处的自然状况或客观条 件，它描述了研究问题过程的状况，是动态规划中最关键的 一个参数。 它既反映前面各个阶段决策的结局，又是本阶段决策的出发点和依据。 它是动态规划问题各个阶段信息的传递点和结合点。通常一个阶段有 多个状态。如例1中第一阶段有1个状态，A.第三阶段有三个状态 C1,C2,C3。 状态变量：描述状态的变量。 可以是数、数组或向量。通常用$k表示k阶段的状态集。如例1中 s3={C1,C2,C3}. 状态的性质：无后效性。 2014-12-15
2014-12-15 9 动态规划的基本概念 1. 阶段(stage)：指一个问题需要作出决策的步数。 通常用k表示问题的阶段数。阶段一般是根据时间和空间的自然特征 来划分的。 2. 状态(state)：表示每个阶段开始所处的自然状况或客观条 件，它描述了研究问题过程的状况，是动态规划中最关键的 一个参数。 它既反映前面各个阶段决策的结局，又是本阶段决策的出发点和依据。 它是动态规划问题各个阶段信息的传递点和结合点。通常一个阶段有 多个状态。如例1中第一阶段有1个状态，A. 第三阶段有三个状态 C1,C2,C3。 状态变量：描述状态的变量。 可以是数、数组或向量。通常用sk表示k阶段的状态集。 如例1中 s3={C1,C2,C3}. 状态的性质：无后效性
动态规划的基本概念 3.决策(de cision)是指某阶段初从给定的状态出发，决 策者在面临的若干种不同方案中做出的选择。 决策变量Xk(Sk)表示第k阶段状态为$k时对方案的选择。 用Dk(Sk)表示在第k阶段状态为Sk时决策允许的取值范围， 称为允许决策集合。即xk(Sk)∈Dk(Sk)。 D2(B1)={B1→C1,B1→C2,B1→C3} (Sk)表示第k阶段状态为Sk时的最优决策。 决策的性质：第k阶段某一状态下的决策直接决定第k+1 阶段的状态。 2014-12-15 10
2014-12-15 10 3.决策(decision) 是指某阶段初从给定的状态出发，决 策者在面临的若干种不同方案中做出的选择。 决策变量 xk (sk ) 表示第k阶段状态为sk时对方案的选择。 用Dk (sk ) 表示在第k阶段状态为sk时决策允许的取值范围， 称为允许决策集合。即xk (sk )Dk (sk )。 D2 (B1 )={B1→ C1 , B1→ C2 , B1→C3 } xk * (sk )表示第k阶段状态为sk时的最优决策。 决策的性质：第k阶段某一状态下的决策直接决定第k+1 阶段的状态。 动态规划的基本概念