城市交通費(fèi)用PASCAL程序解.doc

動(dòng)態(tài)規(guī)劃問(wèn)題的PASCAL程序解例 下圖表示城市之間的交通路網(wǎng)，線段上的數(shù)字表示費(fèi)用，單向通行由A-E。試用動(dòng)態(tài)規(guī)劃的最優(yōu)化原理求出A-E的最省費(fèi)用。解題過(guò)程如下：頂點(diǎn)圖矩陣圖下面，給出例的程序題解。Program Short(input,output);Const Max=100;VarN,St,En, 頂點(diǎn)數(shù)，起點(diǎn)，終點(diǎn) I,J,X : Integer;way : Array1.Max,1.Max of Integer; 線路網(wǎng)絡(luò)的帶權(quán)矩陣 NetDot : Array1.Max of RecordNetDotj.Ne-從J點(diǎn)出發(fā)的決策NetDotj.CostSt-從J點(diǎn)至En點(diǎn)的最短距離Ne,Cost:IntegerEnd;F : Text; 文件變量 Str : String; 文件名串 BeginWrite(File name=,Str); 讀入文件名串 Readln(Str);Assign(F,Str); 文件名與文件變量連接 Reset(F); 讀文件準(zhǔn)備 Readln(F,N,St,En); 讀入頂點(diǎn)數(shù)，起點(diǎn)，終點(diǎn) (*writeln(N=,N:4,St=,St:4,En=,En:4);*)For I:= 1 to N Do 讀入各點(diǎn)間連線的距離 For J:= 1 to N Do Read(F,WayI,J);Close(F);For I:= 1 to N Do NetDotI.Cost:=Maxint; St至各點(diǎn)的最短路線長(zhǎng)度初始化 NetDotEn.Cost:=0; NetDotEn.Ne :=0; 從最后一段開始，由后何前逐步遞推 以下兩句倒推的求解。 For J:= N Downto 1 DoFor X:= N Downto J DoIf ( WayJ,X 0 ) And ( NetDotX.Cost Maxint )And(WayJ,X+NetDotX.CostNetDotJ.Cost ) Then 若En至x點(diǎn)的最短路己經(jīng)求出，且加入邊(j，x)后使得En至j的路線目前最短 BeginNetDotJ.Cost:=NetDotX.Cost+WayJ,X ; 則記下最短路線長(zhǎng)度 NetDotJ.Ne:=X; jXEnd;If NetDotSt.Cost=Maxint ThenWriteln(NoWay)ElseBegin 否則從起點(diǎn)出發(fā)，按計(jì)算順序反推最短路線 X:=St;While X0 Do BeginWrite(X:3, );X:=NetDotX.Ne;End;End;(*read(Str);*)End.輸入文件名為Q01.TXT其內(nèi)容如下：10 1 100 2 5 1 -1 -1 -1 -1 -1 -1-1 0 -1 -1 12 14 -1 -1 -1 -1-1 -1 0 -1 6 10 4 -1 -1 -1-1 -1 -1 0 -1 12 11 -1 -1 -1-1 -1 -1 -1 0 -1 -1 3 9 -1-1 -1 -1 -1 -1 0 -1 6 5 -1-1 -1 -1 -1 -1 -1 0 -1 10 -1-1 -1 -1 -1 -1 -1 -1 0 -1 5-1 -1 -1 -1 -1 -1 -