给我一个PASCAL语言的动态规划教程下载,谢拉

来源:百度知道 编辑:UC知道 时间:2024/05/20 22:12:37

多阶段决策过程最优化问题
——动态规划的基本模型
在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要作出决策,从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定,它依赖于当前面临的状态,又影响以后的发展。当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线。这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题称为多阶段决策最优化问题。
【例题1】最短路径问题。图中给出了一个地图,地图中每个顶点代表一个城市,两个城市间的连线代表道路,连线上的数值代表道路的长度。现在,想从城市A到达城市E,怎样走路程最短,最短路程的长度是多少?

【分析】把从A到E的全过程分成四个阶段,用k表示阶段变量,第1阶段有一个初始状态A,两条可供选择的支路ABl、AB2;第2阶段有两个初始状态B1、 B2,B1有三条可供选择的支路,B2有两条可供选择的支路……。用dk(xk,xk+1)表示在第k阶段由初始状态xk到下阶段的初始状态xk+1的路径距离,Fk(xk)表示从第k阶段的xk到终点E的最短距离,利用倒推方法求解A到E的最短距离。具体计算过程如下:

S1:K=4,有:F4(D1)=3,F4(D2)=4,F4(D3)=3
S2: K=3,有:F3(C1)=min{d3(C1,D1)+F4(D1),d3(C1,D2)+F4(d2)}=min{8,10}=8
F3(C2)=d3(C2,D1)+f4(D1)=5+3=8
F3(C3)=d3(C3,D3)+f4(D3)=8+3=11
F3(C4)=d3(C4,D3)+f4(D3)=3+3=6
S2: K=2,有:F2(B1)=min{d2(B1,C1)+F3(C1),d2(B1,C2)+f3(C2),d2(B1,C3)+F3(C3)}=min{9,12,14}=9
F2(m)=min{d2(B2,c2)+f3(C2),d2(B2,C4)+F3(C4)}=min{16,10}=10
S4:k=1,有:F1(A)=min{d1(A,B1)+F2(B1),d1