最优性原理 ◎无论决策过程的初始状态和初始决策是什么,其 余的决策都必须相对于初始决策所产生的当前状 态,构成一个最优决策序列。 ●在多阶段决策中,一个子问题的解只与它前面的子 问题的解相关 各子问题的解都是相对于当前状态的最优解 整个问题的最优解是由各个子问题的最优解构成
最优性原理 无论决策过程的初始状态和初始决策是什么，其 余的决策都必须相对于初始决策所产生的当前状 态，构成一个最优决策序列。 在多阶段决策中，一个子问题的解只与它前面的子 问题的解相关 各子问题的解都是相对于当前状态的最优解 整个问题的最优解是由各个子问题的最优解构成
最短路径问题一一阶段1 用di(x1x1)表示在第阶介段由初始 C1 状态x到下阶段的初始状态X1的 B1/C25D1 路径距离,Fi(x表示从第昕段的 x到终点E的最短距离,利用倒推 方法求解A到E的最短距离。 D2E 3B2{c3 3 C4 D3F401)=3,F4(D2)=4,F4(D3)=3, s1:i=4, 有:F4(D1)=3,F4(D2)=4,F4(D3)=3
最短路径问题——阶段1 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E 5 3 1 6 3 8 4 5 5 6 8 3 3 4 3 用di(xi , xi+1)表示在第i阶段由初始 状态xi到下阶段的初始状态xi+1的 路径距离，Fi(xi )表示从第i阶段的 xi到终点E的最短距离，利用倒推 方法求解A到E的最短距离。 F4(D1) = 3, F4(D2) = 4, F4(D3) = 3, S1: i = 4, 有：F4(D1) = 3, F4(D2) = 4, F4(D3) = 3
最短路径问题一一阶段2 用di(x1x1)表示在第阶介段由初始 C1 状态x到下阶段的初始状态x+的 B1/C25D1 路径距离,Fi(x表示从第昕段的 x到终点E的最短距离,利用倒推 方法求解A到E的最短距离。 D2E 3B2{c3 3 C4 D31F401)=3,F4(D2)=4,F4(D3)=3 F3(c1)=8,F3(C2)=9,F3(C3)=11 F3(c4)=6 s2:i=3, 有:F3(c1)=min{d3(c1,D1)+F4(D1),d3(C1,D2)+ F4(d2)}=min{839}=8 F3(c2)=d3(c2,D1)+F4(D1)=6+3=9 F3(C3)=d3(c3,D3)+F4(D3)=8+3=11 F3(C4)=d3(c4,D3)+F4(D3)=3+3=6
最短路径问题——阶段2 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E 5 3 1 6 3 8 4 5 5 6 8 3 3 4 3 用di(xi , xi+1)表示在第i阶段由初始 状态xi到下阶段的初始状态xi+1的 路径距离，Fi(xi )表示从第i阶段的 xi到终点E的最短距离，利用倒推 方法求解A到E的最短距离。 F4(D1) = 3, F4(D2) = 4, F4(D3) = 3, F3(C1) = 8, F3(C2) = 9, F3(C3) = 11, F3(C4) = 6, S2: i = 3, 有：F3(C1) = min{d3(C1, D1) + F4(D1), d3(C1, D2) + F4(d2)} = min{8, 9} = 8 F3(C2) = d3(C2, D1) + F4(D1) = 6 + 3 = 9 F3(C3) = d3(C3, D3) + F4(D3) = 8 + 3 = 11 F3(C4) = d3(C4, D3) + F4(D3) = 3 + 3 = 6
最短路径问题一一阶段3 用d(x1x)表示在第阶段由初始 C1 状态x到下阶段的初始状态x+的 B1/C25D1 路径距离,Fi(x表示从第昕段的 x到终点E的最短距离,利用倒推 方法求解A到E的最短距离。 D2E 3B2{c3 3 C4 D31F401)=3,F4(D2)=4,F4(D3)=3 F3C1)=8,F3(C2)=9,F3(C3)=11 F3(c4)=6,F2(B1)=9,F2(B2)=10 s3:i=2, 有:F2(B1)=min{d2(B1,c1)+F3c1),d2(B1, c2)+F3(c2),d2(B1,c3)+F3(C3)}=min{9,15, 14}=9 F2(B2)=mind2(B2,C2)+F3(C2),d2(B2,c4)+ F3(C4)}=min{17,10}=10
最短路径问题——阶段3 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E 5 3 1 6 3 8 4 5 5 6 8 3 3 4 3 用di(xi , xi+1)表示在第i阶段由初始 状态xi到下阶段的初始状态xi+1的 路径距离，Fi(xi )表示从第i阶段的 xi到终点E的最短距离，利用倒推 方法求解A到E的最短距离。 F4(D1) = 3, F4(D2) = 4, F4(D3) = 3, F3(C1) = 8, F3(C2) = 9, F3(C3) = 11, F3(C4) = 6, F2(B1) = 9, F2(B2) = 10, S3: i = 2, 有：F2(B1) = min{d2(B1, C1) + F3(C1), d2(B1, C2) + F3(C2), d2(B1, C3) + F3(C3)} = min{9, 15, 14} = 9 F2(B2) = min{d2(B2, C2) + F3(C2), d2(B2, C4) + F3(C4)} = min{17, 10} = 10
最短路径问题一一阶段4 用di(x1x1)表示在第阶介段由初始 C1 状态x到下阶段的初始状态x+的 B1/C25D1 路径距离,Fi(x表示从第昕段的 x到终点E的最短距离,利用倒推 方法求解A到E的最短距离。 D2E 3B2{c3 3 C4 D3F401)=3,F4(D2)=4,F4D3=3, F3C1)=8,F3(C2)=9,F3(C3)=11 F3(c4)=6,F2(B1)=9,F2(B2)=10 F1(A)=13 s4:i=1, 有:F1(A)=mn{d(A,B1)+F2(B1), d1(A,B2)+F2(B2)}=min{14,13}=13
最短路径问题——阶段4 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E 5 3 1 6 3 8 4 5 5 6 8 3 3 4 3 用di(xi , xi+1)表示在第i阶段由初始 状态xi到下阶段的初始状态xi+1的 路径距离，Fi(xi )表示从第i阶段的 xi到终点E的最短距离，利用倒推 方法求解A到E的最短距离。 F4(D1) = 3, F4(D2) = 4, F4(D3) = 3, F3(C1) = 8, F3(C2) = 9, F3(C3) = 11, F2(B1) = 9, F2(B2) = 10, F1(A) = 13 F3(C4) = 6, S4: i = 1, 有：F1(A) = min{d1(A, B1) + F2(B1), d1(A, B2) + F2(B2)} = min{14, 13} = 13