算法合集之《淺談最短徑路問題中的分層思想》-預覽頁
【正文】 主要內(nèi)容 利用分層思想建立模型 拯救大兵瑞恩 fence cow relay 應用分層思想優(yōu)化算法 bic roads 例題一 拯救大兵瑞恩 (CTSC99) 有一個長方形的迷宮，被分成了 N行 M列，共 N M個單元。只有對應的鑰匙才能打開對應的門。 分析 — 簡化問題 忽略門和鑰匙。 分析 — 邊（ 1） 根據(jù)鑰匙的狀態(tài)改造每層圖 ， 使相鄰的連通節(jié)點間有長度為 1的邊。 小結 將圖進行分層是因為在同一層圖上難以準確地表現(xiàn)出圖在不同條件下的狀況或圖的其他因素。 路徑上的費用不大于 k。 本題與一般求最短路的問題相比，不同之處在于邊上有費用、距離兩個權值。 圖是稠密的，優(yōu)先隊列直接使用一維數(shù)組。 每一層求最短路的時間復雜度為 O(n2+m)。 可以以道路長度進行分層，然后使用動態(tài)規(guī)劃。 算法三的時間復雜度為 O(nLm)，效率有所提高。 總結 建立模型 把難以表現(xiàn)同一層圖上的因素用分層圖表示 優(yōu)化算法 挖掘分層圖的特殊性質(zhì)，有針對性地利用分層性質(zhì) Email
教學課件相關推薦
鄂ICP備17016276號-1