最短路径演算法课件.ppt

1、1給定分群下加快最短路給定分群下加快最短路徑計算之時空成本考量徑計算之時空成本考量 指導教授：魏世杰 老師 研究生：鄭宇辰2大綱大綱圖形定義分群最短路徑演算法1.階層圖記錄資訊之省除2.群間圖之省除 只利用群內圖Dijkstra3.全域地標資訊之省除 改用群內邊界點ALTn背景最短路徑的求解問題，一般可被分為四類：n單一起點到所有節點(Single-Source Shortest-Paths，SSSP)n所有節點到所有節點(All-Pairs Shortest-Paths，APSP)n所有節點到某一終點(Single-Destination Shortest-Paths，SDSP)對於這問題的

2、解決方法，最廣為人知的是Dijkstra演算法演算法Dijkstra 1959，它原本用於解決單一起點到所有節點(SSSP)的問題，由於其時間複雜度和點邊數有密切關係，故不適用於包含大量點邊資不適用於包含大量點邊資訊的圖形訊的圖形。其後的研究除了改良它的資料結構外，在演算過程中靠著輔助資訊減少搜尋範圍的各類方法亦被提出。3前言n研究動機與目的藉由輔助資訊求解最短路徑的方法可依有無分群資訊有無分群資訊作為分水嶺。通常的最短路徑演算法，其。本研究希望提供一個，能在，且的最短路徑演算法，以供相關應用程式使用。並期望能改善其所需記憶體空間過大的情況，又能保持搜尋速度在一定的水平。4前言5文獻大綱n最短

3、路徑演算法最短路徑演算法無分群資訊n圖形分割方法圖形分割方法Kd-treeMETIS6文獻探討 無分群資訊nDijkstra Dijkstra 1959計算由起點s到終點t所有拜訪節點的最短路徑，並優先展開成本較低的節點。節點v的成本估算函數f(v)：f(v)d(s,v)特性n同心圓狀擴散。n保證展開節點的路徑最短。對於包含|V|個節點以及|E|個邊的 圖形，原始Dijkstra的時間複雜度 O(|V|2)，資料結構採用Heap，時間複雜度為O(|E|+|V|log|V|)7文獻探討 無分群資訊n直線距離A*Hart 1968 f(v)d(s,v)+d(s,v)為起點s到節點v之目前最短距離。

4、h(v,t)為節點v到終點t之剩餘距離估算值。需才可保証終結時為最短，dist(v,t)為節點v到終點t之真實最短距離。採用幾何直線估算剩餘距離：h(v,t)=由於euclidean_dist(v,t)dist(v,t)，故可保證最短路徑。直線距離A*搜尋空間8文獻探討 無分群資訊n有向地標A*(ALT)Goldberg 2005採用地標配合三角不等式估算剩餘距離 h(v,t)=dist(v,t)dto_m(v,t)=dist(v,m)-dist(t,m)dist(v,t)dfrom_m(v,t)=dist(m,t)-dist(m,v)dist(v,t)挑選的地標點越分散於圖形邊界越能有好的搜

5、尋效率。vtlmvtlmcbacbaa c+b=a b cb a+c=b a c=dto_m(v,t)=dfrom_m(v,t)dist(v,m)dist(m,v)9文獻探討 有分群資訊nArc-flag Schulz 2000記錄每個有向邊可到達群的集合，以限制展開節點數。Mohring 2005以兩階層分群改良。Huang 1996利用分群資訊對圖形做路徑編碼(Encoded Path View)。2006提出資料結構的修正。nHiTi Graph Jung 2002多階層及部分路徑編碼，但搜尋時間不僅差於HEPV，且將隨著分群數量、階層數目的增加呈現倍數成長。n以道路屬性分群建立階層Li

6、u 1997：以主要路網(包含國道、省道、次要道路)將整個路網細分為數個子網路。主要路網及起終點的子網路將形成高階的路網。其演算法只會在高階路網範圍中搜尋最短路徑。Schultes 2005：以Dijkstra Rank進行分群建立階層。10文獻探討 有分群資訊nHEPV(Hierarchical Encoded Path View)Huang 1996利用分群對整個路網進行切割。高層路網高層路網：由所有子網與其他子網相鄰的節點(邊界點邊界點)組成。低層路網低層路網：各子網內節點各自組成。nHuang認為最短路徑的資訊可被分配到高低路網中記錄(路徑編碼路徑編碼)低層路網低層路網n終點n往終點下

7、一節點(hop)n區域最短路徑長度(weight)高層路網高層路網n終點n終點所屬群編號(Frag)n往終點下一節點(hop)n全域最短路徑長度(weight)11文獻探討 有分群資訊nWang 2006HEPV中對圖形的分群是以點作為兩群間的分界，而Wang則是以邊。因此HEPV所定所定 義的邊界點會分屬於數義的邊界點會分屬於數 個低層圖形個低層圖形，而，而Wang的的 邊界點則只能屬於一個邊界點則只能屬於一個 低層圖形低層圖形。低階路網低階路網(任兩點記錄路徑資訊任兩點記錄路徑資訊)高階路網高階路網(任兩邊界點間記錄路徑資訊任兩邊界點間記錄路徑資訊)缺點缺點 HEPV 區域最短。全域最短。

8、所需記憶體大。低層任兩點最短，仍需高層輔助。Wang 全域最短。全域最短。全域最短。不記錄終點所屬群編號不記錄終點所屬群編號(Frag)所需記憶體大。高階需執行高階需執行DijkstraDijkstra會比較慢。會比較慢。12文獻探討 圖形分割方法nHabbal等人Habbal 1994證實，若能將圖形分割為越多節點越多節點數量接近數量接近的子圖而且每個子圖間邊界點數量越少邊界點數量越少的圖形分割方法，越適用於路徑搜尋。nHuang 1996等人提出了Spatial Partition Clustering(SPC)對較大的圖形進行分割，Kohler2003等人則針對arc-flag提出mul

9、ti-way partition圖形分群演算法。另外還有Schultes2005提出Dijkstra Rank來進行分群的方法。nMohring2005等人的研究裡，比較了Grid、Quadtrees、kd-tree、METIS四種分群方法，結果顯示kd-tree與與METIS對其改良的Dijkstra在搜尋時間上表現較好。nWang2006等人的研究中，則比對了Spatial Partition Clustering(SPC)與METIS，最後結果仍是METIS較優。13文獻探討 圖形分割方法nKd-tree Samet 19892D-treen節點存放座標x與y，取某座標軸的中位點，建立新

10、的樹節點，同時將資料集一分為二，而中位點一般奇數層以x軸來取，偶數層則為y軸。如此遞迴直到樹的分支 抵達所設定的深度為止。nn次分割後，可得到2n個分群。且若採取座標中位點分割，每個分群的節點數將近乎相等每個分群的節點數將近乎相等。14文獻探討 圖形分割方法nMETIS Karypis 1998 多階層圖形分裂(粗化與去粗化步驟)各分群內的節點數量近乎相等。各分群內的節點數量近乎相等。最小化整體與局部分群的連通度最小化整體與局部分群的連通度(即最小化邊界點數量即最小化邊界點數量)。p1915基本方法介紹n基本圖形定義16基本方法介紹n分群概念模型圖形G及4個分群A B C D E F G H

11、J 7 3 3 2 3 5 5 5 4 4 2 I 1 3 1 3 3 17基本方法介紹n分群概念模型A B C D A B C D E F G H J 7 3 3 2 3 5 5 5 4 4 2 I 1 3 1 3 3 18基本方法介紹n分群概念模型C D G H A B C D E F G H J 7 3 3 2 3 5 5 5 4 4 2 I 1 3 1 3 3 19基本方法介紹n最短路徑求解階層圖最短路徑長度求解階層圖最短路徑長度求解最短路徑重建最短路徑重建演算法架構p2120基本方法介紹n最短路徑長度求解C D G H A B C D 21基本方法介紹G H J I A B C D

12、E F G H J 7 3 3 2 3 5 5 5 4 4 2 I 1 3 1 3 3 C D G H A B C D 22基本方法介紹nClusterBasedSearch(s,t)根據Lemma 1根據Lemma 3根據Lemma 2p2623基本方法-pathToBorder 最短路徑重建st31224基本方法 pathBorderToBorder最短路徑重建st34525基本方法-pathFromBorder最短路徑重建st526延伸方法介紹n1a.階層圖記錄資訊之省除群間圖n起點下一邊界點(nextNodeborder)窮舉邊界點s所屬群的所有邊界點bs，滿足下列兩條件者即為所求(1

13、)d1+d2=distborder(s,t)，且(2)d1為最小stbsd1d2仍保有群內圖distinner(s,t)及 群間圖distborder(s,t)資訊n1b.階層圖記錄資訊之省除群內圖n起點下一節點(nextNodeinner)前提：t=nextNodeborder(s,t)窮舉s的鄰居節點V，滿足下列條件者即為所求 d1+d2=distinner(s,t)27延伸方法介紹vstd1d2仍保有群內圖distinner(s,t)另外省除終點上一節點(prevNodeinner)的 ，前提與需滿足之條件類似於此。28延伸方法介紹n2.群間圖之省除 只利用群內圖Dijkstra由於在階

14、層圖的路徑長度資訊中，群內圖記錄了，因此形成了另一種類似於階層圖的圖形。在此圖形上以Dijkstra進行求解。演算完成可得最短路徑長度，及最短路徑所拜訪的，並保證序列中任兩連續邊界點皆同群序列中任兩連續邊界點皆同群。n2.群間圖之省除 只利用群內圖Dijkstra由於、的長度相等，依照Dijkstra節點挑選次序的不同，若選中或將造成路徑重建過程跨越遺漏邊界點1或2時，路徑無法重建。但由於邊界點遺漏只發生在同群邊界點間同群邊界點間，可以下列方式之一修正n(1)findNextBorderNode演算法中，改用群內圖長度資訊改用群內圖長度資訊distinner(s,t)窮舉s所屬群的邊界點bs滿

15、足下列兩條件者即為所求(1)d1+d2=distinner(s,t)，且(2)d1為最小n(2)改在群內圖中記錄改在群內圖中記錄起點下一邊界點nextNodeborder(s,t)29延伸方法介紹d1d2d2=distinner(1,t)d1=distinner(s,1)30延伸方法介紹n3.全域地標資訊之省除只利用群內邊界點ALT dist(v,m)dist(m,v)31實驗結果與討論n實驗環境CPU：AMD Opteron 2.2GHz cache 1MBRAM：8 GBOS：Red Hat Enterprise Linux WS release 4程式開發環境：Java Developm

16、ent Kit 1.6.0_02地圖資料：交通部運輸研究所路網數值圖交通部運輸研究所路網數值圖1.1版版全台灣節點及路段數：節點節點-275195個個 (其中單進單出節點共46015個)路段-381172條32實驗結果與討論階層圖（群內、群間）n採用Dijkstra以正反地圖資訊求得。128群nkd-treenMETISn前處理n前處理33實驗結果與討論由於METIS與kd-tree的分群結果中，各節點將只會屬於某一群各節點將只會屬於某一群(群間群間無節點交集無節點交集)，不符合我們群的定義，不符合我們群的定義。在我們群的定義中，群間將有交集，且其交集的節點為邊界點。因此我們必需根據群間無交集

17、的分群結果，為其建立邊界點。邊界點找尋演算法邊界點找尋演算法依照可到達鄰居節點數可到達鄰居節點數對所有節點排序節點排序，可到達不同群鄰居節點數越多的節點越先處理，讓擁有較讓擁有較多跨群邊的節點成為邊界點多跨群邊的節點成為邊界點。對於所有起始節點與終端節點不同群的有向邊，其中一端必為邊界點。34實驗結果與討論n前處理資料檔資料檔檔案檔案大小大小前處理時前處理時間間原始地圖31 MB-座標2.5 MB-分群資訊3.16 MB-群內圖Kd-tree625.17 MB1.66 小時METIS359.72 MB2.59 小時群間圖Kd-tree442.3 MB4.08 小時METIS174 MB2.22

18、 小時有向地標（from_m/to_m）41.9+41.9 MB約1小時階層圖（群內、群間）n採用Dijkstra以正反地圖資訊求得。全台節點全台節點128群群Kd-treeMETIS每群節點數量88525354邊界點數量2143224520142259階層圖大小1.1(gb)534(mb)階層圖前處理時間5.74(hr)4.81(hr)128群nkd-treenMETIS35實驗結果與討論n實驗設計(1000筆隨機起終點)實驗1-找出群內找出群內(case 4)最快的演算法最快的演算法實驗2-比較空間省除方法各項組合的差異比較空間省除方法各項組合的差異(case 3)實驗3-比較不同分群下的

19、執行差異比較不同分群下的執行差異實驗4 距離與時間成本地圖中，起終點遠近程度對搜尋的影響距離與時間成本地圖中，起終點遠近程度對搜尋的影響實驗編實驗編號號地圖類型地圖類型起終點分佈起終點分佈(亂數亂數2500筆筆)實驗演算法實驗演算法採用分群採用分群(固定固定128群群)實驗1距離成本起終點同群 且皆非邊界點傳統ALT 與群內邊界點ALTMETIS實驗2距離成本起終點不同群 且 至少一方非邊界點空間省除方法各項組合(如下頁表)METIS實驗3距離成本隨機搜尋速度最快組合 METIS kd-tree實驗4距離成本時間成本起終點間相差的Dijkstra Rank=200*2n，n=010之隨機分佈(

20、各遠近程度只取亂數各遠近程度只取亂數1000筆筆)搜尋速度最快組合METIS36實驗結果與討論n比較的演算法：不分群：Dijkstra、直線距離A*(記為A*)、有向地標A*(ALT)、分群演算法CB：階層圖採用窮舉(CB all-pair)、Dijkstra(CB Dijkstra)、ALT(CB ALT)，只利用群內圖的Dijkstra(CB inner Dijkstra)，群內邊界點ALT(Cluster ALT)。上述分群演算法皆可如下選擇性省除階層圖記錄之資訊n(dist,dist)：群內圖記錄dist，群間圖記錄distn(next,dist)：群內圖記錄dist+next/pre

21、v，群間圖記錄distn(dist,next)：群內圖記錄dist，群間圖記錄dist+nextn(next,next)：群內圖記錄dist+next/prev，群間圖記錄dist+next37實驗結果與討論n實驗實驗1起終點同群且皆非邊界點(case 4)找出群內找出群內(case 4)最快的演算法最快的演算法38實驗結果與討論n實驗實驗2起終點不同群且非同時為邊界點(case 2)比較空間省除方法各項組合的差異比較空間省除方法各項組合的差異(case 3)39實驗結果與討論n實驗實驗2-continue起終點隨機分佈(case 1-4)最快組合：CB all-pair+Cluster AL

22、T5.3ms2.6ms40實驗結果與討論空間省除方法組合的搜尋時間(對數刻度)及所需空間關係圖(METIS 128群)(METIS 128群)n實驗實驗2-continue起終點隨機分佈(case 1-4)n其中僅省除群內next的DN為表現皆佳的組合 CB all-pairCB inner Dijkstra41實驗結果與討論n實驗實驗3比較不同分群下的執行差異比較不同分群下的執行差異42實驗結果與討論n實驗實驗4以以Dijkstra Rank區分起終點遠近程度區分起終點遠近程度觀察的起終點遠近程度差距觀察的起終點遠近程度差距Dijkstra Rank範圍：範圍：n200*2n，n=010 地

23、圖類型地圖類型n距離成本地圖：以路徑長度作為邊長距離成本地圖：以路徑長度作為邊長n時間成本地圖時間成本地圖：以行經路段所需時間作為邊長：以行經路段所需時間作為邊長距離與時間成本地圖中，起終點遠近程度對搜尋的影響距離與時間成本地圖中，起終點遠近程度對搜尋的影響 道路等級道路等級速限速限(km/hr)國道90快速道路70省道60縣道/鄉鎮市區道路/產業道路50Dijkstra Rank43實驗結果與討論n實驗實驗4距離成本地圖距離成本地圖距離與時間成本地圖中，起終點遠近程度對搜尋的影響距離與時間成本地圖中，起終點遠近程度對搜尋的影響44實驗結果與討論n實驗實驗4時間成本地圖時間成本地圖距離與時間成

24、本地圖中，起終點遠近程度對搜尋的影響距離與時間成本地圖中，起終點遠近程度對搜尋的影響p53n初始參數設定初始參數設定45與HEPV、Wang之比較46與HEPV、Wang之比較n1.前處理檔案大小比較前處理檔案大小比較47與HEPV、Wang之比較n1.前處理檔案大小比較前處理檔案大小比較與HEPV、Wang之比較48n1.前處理檔案大小比較前處理檔案大小比較與HEPV、Wang之比較49n2.前處理時間複雜度比較前處理時間複雜度比較與HEPV、Wang之比較50n3.最短路徑長度求解時間複雜度比較最短路徑長度求解時間複雜度比較與HEPV、Wang之比較51n最短路徑重建時間複雜度整理最短路徑

25、重建時間複雜度整理5253結論n提出一個適用於台灣路網，能在數毫秒內完成搜尋，所需記憶體空間在1G以下之分群最短路徑演算法，可供相關應用程式使用。其空間需求能較HEPV、Wang少(不採用省除方法的情況下)，且搜尋速度依時間複雜度來看大致仍能保持相同水準。n提供了可以省除空間的多種使用組合，並整理出在METIS 128群之下的搜尋時間、前處理資訊空間關係圖。並歸納出搜尋速度在10ms之下的：搜尋速度最快組合搜尋速度最快組合(NN)n557mb，2.75ms 最省空間組合最省空間組合(DD)n323mb，4.15ms搜尋時間、空間折衷組合搜尋時間、空間折衷組合(DN)n377mb，2.87msCB all-pairCB inner Dijkstra54結論n在起終點同在一群內的情況，提出群內邊界點群內邊界點ALT，由實驗1的結果中，群內邊界點ALT的路徑搜尋時間(5.346.19ms)能大幅低於傳統ALT的搜尋時間(81.27ms)