算法合集之《淺談最短徑路問題中的分層思想》.ppt

淺談最短徑路問題中的分層思想 福建省泉州市第七中學(xué)呂子鉷 引言 最短路徑問題 分層思想 城市規(guī)劃交通導(dǎo)航網(wǎng)絡(luò)尋優(yōu) 動(dòng)態(tài)規(guī)劃中的階段劃分基于求阻塞流的最大流算法 強(qiáng)強(qiáng)聯(lián)合 主要內(nèi)容 利用分層思想建立模型拯救大兵瑞恩fencecowrelay 應(yīng)用分層思想優(yōu)化算法bicroads 例題一拯救大兵瑞恩 CTSC99 有一個(gè)長方形的迷宮 被分成了N行M列 共N M個(gè)單元 南北或東西方向相鄰的兩個(gè)單元之間可以互通 或者存在一扇鎖著的門 又或者存在一堵不可逾越的墻 迷宮中有一些單元存放著鑰匙 總共有P類鑰匙 對(duì)應(yīng)P類門 只有對(duì)應(yīng)的鑰匙才能打開對(duì)應(yīng)的門 例題一拯救大兵瑞恩 CTSC99 從一個(gè)單元移動(dòng)到另一個(gè)相鄰單元的時(shí)間為1 拿取所在單元的鑰匙的時(shí)間以及用鑰匙開門的時(shí)間忽略不計(jì) 求從 1 1 到 N M 的最短時(shí)間 N M不大于15 P不大于10 分析 簡(jiǎn)化問題 忽略門和鑰匙 把每個(gè)單元看成頂點(diǎn) 相互連通的單元之間連一條邊權(quán)為1的邊 分析 分層 考慮鑰匙狀態(tài)對(duì)門的影響 把圖分成2P層 分別對(duì)應(yīng)持有鑰匙的2P種狀態(tài) 分析 邊 1 根據(jù)鑰匙的狀態(tài)改造每層圖 使相鄰的連通節(jié)點(diǎn)間有長度為1的邊 分析 邊 2 對(duì)于存有鑰匙的頂點(diǎn) 向表示得到鑰匙后鑰匙狀態(tài)的層的對(duì)應(yīng)頂點(diǎn)連一條長度為0的邊 分析 復(fù)雜度 使用寬度優(yōu)先搜索求最短路 時(shí)間復(fù)雜度和空間復(fù)雜度均為O 2PNM 小結(jié) 將圖進(jìn)行分層是因?yàn)樵谕粚訄D上難以準(zhǔn)確地表現(xiàn)出圖在不同條件下的狀況或圖的其他因素 分層的圖分別表示不同的條件 加強(qiáng)了圖的性質(zhì) 使得在分層圖能夠使用基本的最短路算法求解原來的復(fù)雜問題 例題二roads CEOI98 n個(gè)城市有單向道路連接 每條路有固定的長度和費(fèi)用 路徑上的費(fèi)用不大于k 求從城市1出發(fā)到達(dá)城市n的最短路徑 例題二roads CEOI98 費(fèi)用k是不大于10000的非負(fù)整數(shù)城市數(shù)n是不大于100的正整數(shù)道路數(shù)m是不大于10000的正整數(shù)每條道路的長度是不大于100的正整數(shù)每條道路的通行稅是不大于100的非負(fù)整數(shù) 分析 圖 我們把城市看成節(jié)點(diǎn) 城市之間的道路看成邊 本題與一般求最短路的問題相比 不同之處在于邊上有費(fèi)用 距離兩個(gè)權(quán)值 分析 算法一 分層 把圖拆分成k 1層 表示到達(dá)該層頂點(diǎn)所需的費(fèi)用分別為0到k 分析 算法一 邊 每條邊拆成O k 條邊 邊的兩個(gè)頂點(diǎn)的所在層的費(fèi)用之差表示費(fèi)用 邊的權(quán)值表示道路長度 分析 算法一 復(fù)雜度 由于道路長度是正整數(shù) 采用Dijkstra算法求最短路 圖是稠密的 優(yōu)先隊(duì)列直接使用一維數(shù)組 時(shí)間復(fù)雜度為O k kn2 m 分析 算法二 由于費(fèi)用是非負(fù)的 這意味著邊只能從一個(gè)節(jié)點(diǎn)指向同一層的節(jié)點(diǎn)或費(fèi)用更大的層的節(jié)點(diǎn) 按照費(fèi)用從低到高的順序?qū)γ繉忧笞疃搪?而非一次性對(duì)所有點(diǎn)求最短路 每一層求最短路的時(shí)間復(fù)雜度為O n2 m 時(shí)間復(fù)雜度降為O k n2 m 分析 算法三 由于題目已經(jīng)給定費(fèi)用的最大值 所以我們很自然地直接以費(fèi)用的多少進(jìn)行分層 但是我們忽略了一個(gè)條件 道路長度是正整數(shù) 而不僅是非負(fù)整數(shù) 可以以道路長度進(jìn)行分層 然后使用動(dòng)態(tài)規(guī)劃 分析 算法三 轉(zhuǎn)移方程 令f i j 表示到達(dá)城市j長度為i的所有路徑所花費(fèi)的最少費(fèi)用 轉(zhuǎn)移方程為 f 0 1 0f 0 j j 2 n f i j max f i len j0 fee 城市j0到城市j有一條長度為len 費(fèi)用為fee的道路 分析 算法三 復(fù)雜度 設(shè)每條道路長度的最大值為L 那么總共有O nL 個(gè)階段 每個(gè)階段的轉(zhuǎn)移的復(fù)雜度O m 算法三的時(shí)間復(fù)雜度為O nLm 效率有所提高 小結(jié) 分層圖的層是我們構(gòu)建模型時(shí)復(fù)制的 許多圖的元素都是相同或相似的 不需要增加額外的空間或操作 分