文档介绍：利用动态规划数学模型求最短路径.
利用动态规划数学模型求最短路径.
利用动态规划数学模型求最短路径.
利用动向规划数学模型求最短路径
杜彦娟
(黑龙江科技学院蒿山校区 ,黑龙江哈尔滨
11211 次序递推法
K=1 时 ,考虑第一个阶段。第一阶段的最短行程记作 f1(B ii=1,2, 则 f1(B
i=5,f1(B2=8 。
K=2 时 ,结合考虑前两个阶段。第一阶段、第二阶段至 B i 结点的最短行程之和
记为 f2(C ii=1, 2 。 f2(C i=min{d(B1,C1+f1(B1,d(B2,C2+ f1(B2}=min{2+5,1+8}=7, 即
利用动态规划数学模型求最短路径.
利用动态规划数学模型求最短路径.
利用动态规划数学模型求最短路径.
从 A 结点至 C1 结点最短路径为 A —B1— C,f2(C2}=min{d(B1,C2 +f1(B1,d(B1,C2+f1(B2}=min{3+5,2+8}= 8, 即从 A 结点至 C2 结点最短路径为 A —
B1—C2。
K=3 时 ,结合考虑前三个阶段。前三个阶段至 D i 结点的最短行程记作 f3(D ii=1,2,3。 f3(D i= min{d(C1,D i+f2(C1,d(C2,D i+f2(C2}f3(D1 =min{d(C1,D1+f2(C1,d(C2,D1+f2(C2}= min{8+7,4+8}=12, 即从 A 结点至 D1 结点最短路径为 A —B1—C1— D1,f3(D2}=min{d(C1,D2+ f2(C1,d(C1,D2+f2(C3}=min{7+7,2+8}= 10, 即从 A 结点至 D2 结点最短路径为 A — B1—C2—D2,f3(D3}=min{d(C1,D3+f2(C1,d(C2, D3+f2(C3}=min{8+7,4+8}=12, 即从
结点至 D3 结点最短路径为 A —B1—C2—D3。
K=4 时 ,结合考虑前四个阶段。达成前四个阶段至 E 结点的最短行程记作
f4(E,f4(E=min{d (D1,E+f3(D1,d(D2,E+f3(D2,d(D3,E+ f3(D3}=min{4+12,8+10,3+12}=15, 即从 A 到 E 的最短路径为 A— B1— C2—D3—E。也就是说 ,从城市 A 经 B1、C2、 D3 至城市 E 为最短行程。 11212 逆序递推法
K=4 时 ,考虑第四个阶段 ,从 E 结点开始 ,从后向前推导 ,与前面次序递推法类
似。用 f4 ′(D K表示从 E 结点至 D i 结点的最短行程 ,f4 ′(D1=4, f4 ′(D2=8,f4 ′。(D3=3
K=3 时 ,结合考虑后两个阶段。用 f3 ′ (C1表示第四、第三阶段至 C1 结点的最短
行程 ,i=1,2。
f3 ′ (C1=min{d(D1,C1+f4 ′ (D1,d(D2,C1+f4 ′ (D2,d(D3,C1+f4 ′ (D3}=min{8+4,7+8,8+3}
=11,即此阶段至 C1 最短