2用动态规划的方法分步考虑 ■■■ ■■■国■ (5)求五个阶段最优选择: ) 从B到G有两个出发点B,B, 最优选择为 d(B,C1)+f3(C1) +13 f2(B)=mn{(B,C2)+f(C2)}=mn13+10}=13,B→C2→D→E2→F2→G d(B, C3)+fS(C3 d(B2C2)+f3(C2) 8+10 f(B2)=m{B2,C)+(C)}=m7+9}=16B2→C2→D→E2→F2→G d(B2, C4)+f(CA)) 6+12 所以最短路线为B→C2→D→E2→F2→G 信瞿大学囀廣 2021年2月5日
12 2021年2月5日 (5) 求五个阶段最优选择： 从 B 到 G 有 两 个 出 发 点 1 2 B ,B ： 最 优 选 择 为 B C D E F G d B C f C d B C f C d B C f C f B = → → → → → + + + = + + + = 1 2 1 2 2 1 3 3 3 1 2 3 2 1 1 3 1 2 1 13, 6 9 3 10 1 13 min ( , ) ( ) ( , ) ( ) ( , ) ( ) ( ) min B C D E F G d B C f C d B C f C d B C f C f B = → → → → → + + + = + + + = 2 2 1 2 2 2 4 3 4 2 3 3 3 2 2 3 2 2 2 16, 6 12 7 9 8 10 min ( , ) ( ) ( , ) ( ) ( , ) ( ) ( ) min 所 以 最 短 路 线 为 B1 →C2 → D1 → E2 → F2 →G 2 .用动态规划的方法分步考虑
2用动态规划的方法分步考虑 ■■■ ■■■■■ (6)求六个阶段最优选择:从A到G有一个出发点A:最优选择为 5+13 f(A=min d(A,B1)+f2(B1) d(4)+(B3) min 3+16 A→B1→>C,)D1→E,→F2→G 所以最优路线为 A→B1→C2→D1→E2→F2→G,总距离为18 6 FI 信瞿大学囀廣 13 2021年2月5日
13 2021年2月5日 2 .用动态规划的方法分步考虑 (6) 求六个阶段最优选择: 从 A 到 G 有一个出发点 A：最优选择为 A B C D E F G d A B f B d A B f B f A → → → → → → = + + = + + = 1 2 1 2 2 2 2 2 1 2 1 1 18, 3 16 5 13 min ( , ) ( ) ( , ) ( ) ( ) min 所以最优路线为 A → B1 → C2 → D1 → E2 → F2 → G ，总距离为 18
■■■ cUneo 二.动态规划的基本概念与条件 ■■■国■ 1.动态规划的基本概念 (1)阶段( stage)和阶段变量 阶段是指一个问题需要作出决策的步 骤,即把问题的过程分为若干个相互联系 的阶段,使能按阶段的次序求解。 描述阶段的变量称为阶段变量常用k 表示。 信息大学申 2021年2月5日
14 2021年2月5日 二. 动态规划的基本概念与条件 1 . 动态规划的基本概念 (1)阶段（stage）和阶段变量 阶段是指一个问题需要作出决策的步 骤，即把问题的过程分为若干个相互联系 的阶段，使能按阶段的次序求解。 描述阶段的变量称为阶段变量,常用k 表示
■■■ cUneo (2)状态与状态变 ■■■■■ 在多阶段决策过程中,每一阶段都具有一些特 征(自然状况,或客观条件),这就是状态,用来 描述状态的变量称为状态变量 通常第k阶段的状态变量用s(k=12;,m)表示,它的 取值可以是一个数、一组数或一个向量等。 状态变量可取值的全体所构成的集合称为可达状态集 合(或允许状态集合),用SA(k=12…,m)表示 信息大学申 15 2021年2月5日
15 2021年2月5日 通常第 k 阶段的状态变量用 s (k 1,2, ,n) k = 表示，它的 取值可以是一个数、一组数或一个向量等。 在多阶段决策过程中，每一阶段都具有一些特 征（自然状况，或客观条件），这就是状态，用来 描述状态的变量称为状态变量。 状态变量可取值的全体所构成的集合称为可达状态集 合（或允许状态集合）,用 S (k 1,2, ,n) k = 表示。 (2)状态与状态变量
■■■ cUneo =()决策和快策变量 ■■■国■ 当过程处于某一阶段的某个状态时,可以作出 不同的决定(或选择),从而确定下一阶段的状态, 这种决定称为决策。描述决策的变量称为决策变 量,用x(S)表示第k阶段S(=1,2;,n)状态 的决策变量。 决策变量的取值范围称为允许决策集合,用D(s 表示第k阶段状态S(k=12;,m)的允许决策集合,即 xk(s)∈DA(Sk)k=12;…,n) 信瞿大学囀廣 16 2021年2月5日
16 2021年2月5日 当过程处于某一阶段的某个状态时，可以作出 不同的决定（或选择），从而确定下一阶段的状态， 这种决定称为决 策。描述决策的变量称为决策变 量，用 ( ) k k x s 表示第 k 阶段 s (k 1,2, ,n) k = 状态 的决策变量。 决策变量的取值范围称为允许决策集合，用 ( ) k k D s 表示第 k 阶段状态 s (k 1,2, ,n) k = 的允许决策集合，即 x (s ) D (s )(k 1,2, ,n) k k k k = 。 (3)决策和决策变量