動態(tài)規(guī)劃中的最長路徑問題

1、動態(tài)規(guī)劃中的最長路徑問題題目：設(shè)圖設(shè)圖G=(VE)是一個帶權(quán)有向連通圖，如果把頂點集合是一個帶權(quán)有向連通圖，如果把頂點集合V劃分成劃分成k個互不相交的子集個互不相交的子集Vi（2≤k≤n1≤i≤k），使得，使得E中的中的任何一條邊任何一條邊(uv)，必有，必有u∈Vi，v∈Vim（1≤i＜k1＜im≤k），則，則稱圖稱圖G為多段圖，稱為多段圖，稱s∈V1為源點，為源點，t∈Vk為終點。多段圖的最長為終點。多段圖的最長路徑問題是求從源點到

2、終點的最大代價路徑路徑問題是求從源點到終點的最大代價路徑由于多段圖將頂點劃分為由于多段圖將頂點劃分為k個互不相交的子集，所以，多段圖劃個互不相交的子集，所以，多段圖劃分為分為k段，每一段包含頂點的一個子集。不失一般性，將多段圖的段，每一段包含頂點的一個子集。不失一般性，將多段圖的頂點按照段的順序進行編號，同一段內(nèi)頂點的相互順序無關(guān)緊要。頂點按照段的順序進行編號，同一段內(nèi)頂點的相互順序無關(guān)緊要。假設(shè)圖中的頂點個數(shù)為假設(shè)圖中的頂點個數(shù)為n，

3、則源點，則源點s的編號為的編號為0，終點，終點t的編號為的編號為n1，并且，對圖中的任何一條邊，并且，對圖中的任何一條邊(uv)，頂點，頂點u的編號小于頂點的編號小于頂點v的編號。編號。2120345678949387684756866537一個多段圖一個多段圖=max415713=20(3→6)d(29)=maxc24d(49)c25d(59)c26d(69)=max612715813=22(2→5)d(19)=maxc14d(49)

4、c15d(59)=min912815=23(1→5)d(09)=maxc01d(19)c02d(29)c03d(39)=max423222320=27(0→3)最后，得到最長路徑為最后，得到最長路徑為0→1→5→7→9，長度為，長度為27。下面考慮多段圖的最長路徑問題的填表形式。下面考慮多段圖的最長路徑問題的填表形式。用一個數(shù)組用一個數(shù)組cost[n]作為存儲子問題解的表格，作為存儲子問題解的表格，cost[i]表示從表示從頂點頂點i到

5、終點到終點n1的最長路徑，數(shù)組的最長路徑，數(shù)組path[n]存儲狀態(tài)，存儲狀態(tài)，path[i]表示表示從頂點從頂點i到終點到終點n1的路徑上頂點的路徑上頂點i的下一個頂點。則：的下一個頂點。則：cost[i]=maxcijcost[j](i≤j≤n且頂點且頂點j是頂點是頂點i的鄰接點的鄰接點)（式（式6.7）path[i]=使cijcost[j]最大的最大的j（式（式6.8）程序算法多段圖算法：ProcedureFGRAPH（EknP）