動(dòng)態(tài)規(guī)劃中的最長(zhǎng)路徑問題

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

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

3、則源點(diǎn)，則源點(diǎn)s的編號(hào)為的編號(hào)為0，終點(diǎn)，終點(diǎn)t的編號(hào)為的編號(hào)為n1，并且，對(duì)圖中的任何一條邊，并且，對(duì)圖中的任何一條邊(uv)，頂點(diǎn)，頂點(diǎn)u的編號(hào)小于頂點(diǎn)的編號(hào)小于頂點(diǎn)v的編號(hào)。編號(hào)。2120345678949387684756866537一個(gè)多段圖一個(gè)多段圖=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)最后，得到最長(zhǎng)路徑為最后，得到最長(zhǎng)路徑為0→1→5→7→9，長(zhǎng)度為，長(zhǎng)度為27。下面考慮多段圖的最長(zhǎng)路徑問題的填表形式。下面考慮多段圖的最長(zhǎng)路徑問題的填表形式。用一個(gè)數(shù)組用一個(gè)數(shù)組cost[n]作為存儲(chǔ)子問題解的表格，作為存儲(chǔ)子問題解的表格，cost[i]表示從表示從頂點(diǎn)頂點(diǎn)i到

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