算法合集之淺談最短徑路問題中的分層思想-資料下載頁
2024-10-18 18:37本頁面
【正文】 但是我們忽略了一個條件：道路長度是正整數(shù)，而不僅是非負(fù)整數(shù)。 可以以道路長度進(jìn)行分層，然后使用動態(tài)規(guī)劃。 分析 — 算法三 — 轉(zhuǎn)移方程 令 f[i,j]表示到達(dá)城市 j長度為 i的所有路徑所花費(fèi)的最少費(fèi)用。 轉(zhuǎn)移方程為： f[0,1]=0 f[0,j]=∞ (j=2… n) f[i,j]=max{f[ilen,j0]+fee} (城市 j0到城市 j有一條長度為 len， 費(fèi)用為 fee的道路 ) 分析 — 算法三 — 復(fù)雜度 設(shè)每條道路長度的最大值為 L。 那么總共有 O(nL)個階段，每個階段的轉(zhuǎn)移的復(fù)雜度 O(m)。 算法三的時(shí)間復(fù)雜度為 O(nLm)，效率有所提高。 小結(jié) 分層圖的層是我們構(gòu)建模型時(shí)復(fù)制的，許多圖的元素都是相同或相似的，不需要增加額外的空間或操作。 分層圖中往往層與層之間拓?fù)溆行?，可以逐層求最短路? 特別地，當(dāng)同層的節(jié)點(diǎn)拓?fù)錈o關(guān)時(shí) ， 就可以使用動態(tài)規(guī)劃代替最短路算法。 總結(jié) 建立模型 把難以表現(xiàn)同一層圖上的因素用分層圖表示 優(yōu)化算法 挖掘分層圖的特殊性質(zhì)，有針對性地利用分層性質(zhì) Email
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1