[工學(xué)]動態(tài)規(guī)劃題(編輯修改稿)
2025-02-15 02:51 本頁面
【文章內(nèi)容簡介】 mmm3……mn，分別表示n個砝碼的重量；（1=mi=20） 第三行n個整數(shù)（中間用空格分隔），xxx3……xn，分別表示n個砝碼可取的最大數(shù)量。（1=xi=20）輸出： 僅一行，一個整數(shù)，表示利用給定的砝碼可以稱出的不同的重量數(shù)。分析：階段：按不同琺碼的使用次序來分階段，即：僅用前一種法碼來稱重為第一階段，僅用前兩種法碼稱重為第二階段，依此類推。狀態(tài)：在某個階段，以能稱出的重量為狀態(tài)。 設(shè)：f(w,i)表示在第i階段，能否稱出w的重量，能則為 true，否為false。 f(w,i)僅與第i1階段有關(guān)。若f(wk*wi ,i1)，(0≤k≤xi)中有一個為真，則f(w,i)為真，否為假。狀態(tài)轉(zhuǎn)移方程：f(w,i)=f(w,i1)∨f(w1*wi,i1)∨f(w2*wi,i1)∨……∨f(wxi*wi,i1),wk*wi=0,（0≤i≤最大重，0≤k≤xi）*************************************************************************城市交通——雙重動態(tài)設(shè)計 某城市有n(1≤n≤50)個街區(qū)，某些街區(qū)有公共汽車線路相連，如下圖，圖中邊上的數(shù)字為兩個街區(qū)間汽車的旅行時間（也就是乘客等車時間）。從1到5的最短路線為135用時44分鐘。此主題相關(guān)圖片如下：現(xiàn)市政府要改善交通，決定加開m(1≤m≤10)條線路的公共汽車，并規(guī)定：只有已有了公共汽車線路的才能加開線路，加開一條線路后，等車時間減半，若再加開一條，等車時間再減半，依此類推。如加開兩條線路，1到5的時間最短是22分鐘，加開線路是13，35。求加開哪些線路，可使街區(qū)1到n的時間最短，并輸出出加開的線路。參考FLOYD算法。以加開的公交線路數(shù)為階段。階段：第0階段就是不加開任何線路的情況，即原始狀態(tài)（直接用ＦＬＯＹＤ算法就可求出任何兩點的最短旅行時間）。第1階段就是只加開一條線路的情況，依此類推。第m階段就是加開了m條線路的情況也就是所求。狀態(tài)：在每一階段，任何兩個街區(qū)加開g(1≤g≤m)條線路的后的最短旅行時間，即共n*n個狀態(tài)。決策：在道路ab上增加g條線路可分為以下兩個問題（如果k是最短路上的一點）①在ak的道路上增加t條邊②在kb的道路上增加gt條邊k可取0到m間的任何整數(shù)。問題“在道路ab上增加m條線路”的最優(yōu)解取決于以上兩個問題的最優(yōu)組合。即：“在ak的道路上增加t條邊”后旅行時間和“在kb的道路上增加mt條邊”后旅行時間之和最小值。狀態(tài)移方程：可參考以上的分析。綜合，以上分析可以發(fā)現(xiàn)：上述的動態(tài)規(guī)劃，第一個層次是以“加開的公交線路數(shù)為階段”，進行動態(tài)規(guī)劃，比如要完成加３條公交線路的任務(wù)，就要先要完成加１條和加２條線路的問題。而第二層次是以“允許k為中間結(jié)點”(0=k=n)為階段進行動態(tài)規(guī)劃，比如求解“允許３為中間結(jié)點”時，就要已完成“允許２為中間結(jié)點”的問題。故稱為雙重動態(tài)規(guī)劃 但決策并沒有更復(fù)雜，設(shè)現(xiàn)在要加開發(fā)公交線路數(shù)為g，允許中間結(jié)點為k，可選決策集（也就是狀態(tài)）為ak的線路上加p條線線路，kb而的線路上加gp條線路（g=p=0）。過程詳解：設(shè)map為鄰接表，鄰接表中的0表示沒有通路。如map[i,j]=0表示i,j間沒有通路。val[0..10]是有10個map單元的數(shù)組，val[0]存儲為不加開任何線路任何兩結(jié)點的最短旅行時間，val[p]存儲加開p條線路任何兩結(jié)點的最短旅行時間。way[0..10,1..50,1..50,1..2]記錄i到j(luò)路徑上新增p條線路的最佳方案，其中way[p,i,j,2]存儲ij的路徑的中間結(jié)點k，way[p,i,j,1]存ik的路徑上新增的線路數(shù)。對val[0]運用ＦＬＯＹＤ算法，即可求出不加開線路，任何兩結(jié)點的最短旅行時間。求val[1]（只加開一條線路）val[1]=鄰接表（注意，鄰接表中的0表示沒有通路）； val[1]中各值減半；for k=1 to n do 列舉各個中間結(jié)點 for i=1 to n do for j=1 to n do 列舉所有的兩街區(qū)線路 if(i到k有通路and j到k有通路and ij) then beginfor(列舉q的所有可能) if(Val[p]^[i,j]=0 or Val[p]^[i,j]Val[q]^[i,k]＋Val[1q]^[k,j]) then 記錄較優(yōu)值； end。最后的結(jié)果就是：val[1]^[i,j]={i到k的通路新增q條線路的最短時間＋k到j(luò)的通路新增1q條線路的最短時間}中最優(yōu)值；*************************************************************************方格取數(shù)——多進程
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1