■■■ cUneo 1.引例:最短路线问题 ■■■国■ d.用动态规划的方法分步考虑 (1)求一个阶段最优 从F到G:d(F,G 为()=:0)=(的 以最短路线为F2→>G 3 368 }=7,E→F1→G 7 2021年2月5日
7 2021年2月5日 2 .用动态规划的方法分步考虑 1. 引例：最短路线问题 (1) 求一个阶段最优选择： 从 F 到 G： ( , ) 4, ( , ) 3 d F1 G = d F2 G = ，最优选择 为 ( ) ( , ) 4, ( ) ( , ) 3 f 6 F1 = d F1 G = f 6 F2 = d F2 G = ， 所 以最短路线为 F2 →G ； (2) 求两个阶段最优选择： 从 E 到 G，有三个出发点 1 2 3 E ,E ,E ： E F G d E F f F d E F f F f E = → → + + = + + = 1 1 1 2 6 2 1 1 6 1 5 1 7, 5 3 3 4 min ( , ) ( ) ( , ) ( ) ( ) min
A 2用动态规划的方法分步 迎2 人4 (2)求两个阶段最优选择 从E到G,有三个出发点E1,E2,E3 d(E1,F1)+f6(F1) 3+4 fs (e=min =7.E,→FG d(E1,F2)+f6(F2 5+3 f5(E2)=m d(E2, F)+6(ELms 5+ min 5,E,→F2→G (E2,F2)+f6(F2 2+3 d(E32F1)+f6(F1) 6+4 ∫5(E3)=mn mIn =9E,→F>G (3,F)+(FE) 6+3 所以最短路线为E,→>F,→>G; 信瞿大学囀廣 8 2021年2月5日
8 2021年2月5日 (2) 求两个阶段最优选择： 从 E 到 G，有三个出发点 1 2 3 E ,E ,E ： E F G d E F f F d E F f F f E = → → + + = + + = 1 1 1 2 6 2 1 1 6 1 5 1 7, 5 3 3 4 min ( , ) ( ) ( , ) ( ) ( ) min ， E F G d E F f F d E F f F f E = → → + + = + + = 2 2 2 2 6 2 2 1 6 1 5 2 5, 2 3 5 4 min ( , ) ( ) ( , ) ( ) ( ) min E F G d E F f F d E F f F f E = → → + + = + + = 3 2 3 2 6 2 3 1 6 1 5 3 9, 6 3 6 4 min ( , ) ( ) ( , ) ( ) ( ) min 所以最短路线为 E2 → F2 →G ； 2 .用动态规划的方法分步考虑
2用动态规划的方法分步考虑 ■■■ ■■■■■ (3)求三个阶段最优选择: 2+7 f4(D=min d(D,E)+(E) mIn =7D,→E→F→O d(D1,E2)+f5(E2) 2+5 d(D2,E2)+f(E2 1+5 f(D,)=min dD2,E)+(E) min =6,D,>E,→>F,>G 2+ f4(D3)=m D,E2)+(E2)3 +5 mIn 8.D,→E,→F→)G d(D3,E3)+f5(E3 3+ 所以最短路线为D2→E2→F→G 信息大学申
9 2021年2月5日 2 .用动态规划的方法分步考虑 (3)求三个阶段最优选择： D E F G d D E f E d D E f E f D = → → → + + = + + = 1 2 2 1 2 5 2 1 1 5 1 4 1 7, 2 5 2 7 min ( , ) ( ) ( , ) ( ) ( ) min D E F G d D E f E d D E f E f D = → → → + + = + + = 2 2 2 2 3 5 3 2 2 5 2 4 2 6, 2 9 1 5 min ( , ) ( ) ( , ) ( ) ( ) min ， D E F G d D E f E d D E f E f D = → → → + + = + + = 3 2 2 3 3 5 3 3 2 5 2 4 3 8, 3 9 3 5 min ( , ) ( ) ( , ) ( ) ( ) min 所以最短路线为D2 → E2 → F2 →G ；
2用动态规划的方法分步考虑 ■■■ ■■■■■ (4)求四个阶段最优选择: 从C到G有四个出发点C,C2C3C:最优选择为 d(C1,D1)+f(D) 6+7 f3(C1=mn min =13,C1→D1→>E,→>F2→G d(C,D2)+f4(D2 8+ Jd(, D)+f4(D, mIn min =10,C,→D→E,→F,→G ld(c, D))+SAD,) 信息大学申 2021年2月5日
10 2021年2月5日 2 .用动态规划的方法分步考虑 (4)求四个阶段最优选择： 从 C 到 G 有四个出发点 1 2 3 4 C ,C ,C ,C ：最优选择为 C D E F G d C D f D d C D f D f C = → → → → + + = + + = 1 1 2 2 1 2 4 2 1 1 4 1 3 1 13, 8 6 6 7 min ( , ) ( ) ( , ) ( ) ( ) min C D E F G d C D f D d C D f D f C = → → → → + + = + + = 2 1 2 2 2 2 4 2 2 1 4 1 3 2 10, 5 6 3 7 min ( , ) ( ) ( , ) ( ) ( ) min
2用动态规划的方法分步考虑 ■■■ ■■■国■ (4)求四个阶段最优选择: ) f3(C1)=13,C1→D1→>E2>F2→G f3(C2)=10,C2→D→E2→>F2→G d(C,D2)+f4(D2) f3(C3)=min min =9,C3→>D,→>E,→>F,→>G d(C,D3)+f4(D3) 3+8 d(C4,D2)+f(D2 ∫3(C4) mIn d(C4, D, )+A(D, ) min 12,C4→>D3→>E,→>F,→>G 所以最短路线为C3→D2→E2→F2→G; 信息大学申 11 2021年2月5日
11 2021年2月5日 2 .用动态规划的方法分步考虑 3 1 1 1 2 2 f C C D E F G ( ) 13, = → → → → 3 2 2 1 2 2 f C C D E F G ( ) 10, = → → → → C D E F G d C D f D d C D f D f C = → → → → + + = + + = 3 2 2 2 3 3 4 3 3 2 4 2 3 3 9, 3 8 3 6 min ( , ) ( ) ( , ) ( ) ( ) min C D E F G d C D f D d C D f D f C = → → → → + + = + + = 4 3 2 2 4 3 4 3 4 2 4 2 3 4 12, 4 8 8 6 min ( , ) ( ) ( , ) ( ) ( ) min 所以最短路线为 C3 → D2 → E2 → F2 → G ； （4)求四个阶段最优选择：