給定分群下加快最短路徑計算之時空成本考量 指導教授：魏世杰 老師 研究生：鄭宇辰

大綱 前言 文獻探討 基本方法介紹 延伸方法介紹 實驗結果與討論 結論 圖形定義 分群最短路徑演算法 1.階層圖記錄資訊之省除 2.群間圖之省除 – 只利用群內圖Dijkstra 3.全域地標資訊之省除 – 改用群內邊界點ALT 實驗結果與討論 結論

前言 背景 最短路徑的求解問題，一般可被分為四類： 單一起點到某一節點(Single-Pair Shortest Path，SPSP) 單一起點到所有節點(Single-Source Shortest-Paths，SSSP) 所有節點到所有節點(All-Pairs Shortest-Paths，APSP) 所有節點到某一終點(Single-Destination Shortest-Paths，SDSP) 對於這問題的解決方法，最廣為人知的是Dijkstra演算法[Dijkstra 1959]，它原本用於解決單一起點到所有節點(SSSP)的問題，由於其時間複雜度和點邊數有密切關係，故不適用於包含大量點邊資訊的圖形。其後的研究除了改良它的資料結構外，在演算過程中靠著輔助資訊減少搜尋範圍的各類方法亦被提出。 3

前言 研究動機與目的 藉由輔助資訊求解最短路徑的方法可依有無分群資訊作為分水嶺。通常有分群資訊的最短路徑演算法，其搜尋時間較為優異，但必需承擔極高的空間負荷。 本研究希望提供一個適用於台灣路網，能在數毫秒內完成搜尋、所需記憶體空間可負荷，且有分群資訊輔助的最短路徑演算法，以供相關應用程式使用。並期望能改善其所需記憶體空間過大的情況，又能保持搜尋速度在一定的水平。 4

文獻大綱 最短路徑演算法 無分群資訊 有分群資訊 圖形分割方法 Kd-tree METIS 5

文獻探討– 無分群資訊 Dijkstra [Dijkstra 1959] 節點v的成本估算函數f(v) ： f(v)＝d(s,v) 特性 同心圓狀擴散。 保證展開節點的路徑最短。 對於包含|V|個節點以及|E|個邊的 圖形，原始Dijkstra的時間複雜度 O(|V|2)，資料結構採用Heap， 時間複雜度為O(|E| + |V| log|V|) t d(s,v):起點到v的累計路徑長 S

文獻探討– 無分群資訊 直線距離A* [Hart 1968] f(v)＝d(s,v)+h(v,t) 採用幾何直線估算剩餘距離： d(s,v)為起點s到節點v之目前最短距離。 h(v,t)為節點v到終點t之剩餘距離估算值。 需h(v,t) ≦dist(v,t)才可保証終結時為最短， dist(v,t)為節點v到終點t之真實最短距離。 採用幾何直線估算剩餘距離： h(v,t)=euclidean_dist(v,t) 由於euclidean_dist(v,t) ≦dist(v,t)， 故可保證最短路徑。　

文獻探討– 無分群資訊 有向地標A*(ALT) [Goldberg 2005] 採用地標配合三角不等式估算剩餘距離 h(v,t)=max(dto_m(v,t) , dfrom_m(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) 挑選的地標點越分散於圖形邊界越能有好的搜尋效率。 t t dist(v,m) c c dist(m,v) v b v b a a a ≦c + b => a – b ≦ c b ≦a + c => b – a ≦ c lm lm =dto_m(v,t) =dfrom_m(v,t)

文獻探討– 有分群資訊 Arc-flag [Schulz 2000] HEPV [Huang 1996] 記錄每個有向邊可到達群的集合，以限制展開節點數。Mohring [2005]以兩階層分群改良。 HEPV [Huang 1996] 利用分群資訊對圖形做路徑編碼(Encoded Path View)。 Wang [2006]提出資料結構的修正。 HiTi Graph [Jung 2002] 多階層及部分路徑編碼，但搜尋時間不僅差於HEPV，且將隨著分群數量、階層數目的增加呈現倍數成長。 以道路屬性分群建立階層 Liu [1997]：以主要路網(包含國道、省道、次要道路)將整個路網細分為數個子網路。主要路網及起終點的子網路將形成高階的路網。其演算法只會在高階路網範圍中搜尋最短路徑。 Schultes [2005]：以Dijkstra Rank進行分群建立階層。 Liu:實際最短路徑可能途經其他子網路 9

文獻探討– 有分群資訊 HEPV(Hierarchical Encoded Path View) [Huang 1996] 利用分群對整個路網進行切割。 高層路網：由所有子網與其他子網相鄰的節點(邊界點)組成。 低層路網：各子網內節點各自組成。 Huang認為最短路徑的資訊可被分配到高低路網中記錄—(路徑編碼) 低層路網 終點 往終點下一節點(hop) 區域最短路徑長度(weight) 高層路網 終點所屬群編號(Frag) 全域最短路徑長度(weight) Liu:實際最短路徑可能途經其他子網路

文獻探討– 有分群資訊 Wang [2006] HEPV中對圖形的分群是以點作為兩群間的分界，而Wang則是以邊。因此HEPV所定 義的邊界點會分屬於數 個低層圖形，而Wang的 邊界點則只能屬於一個 低層圖形 。 低階路網 (任兩點記錄路徑資訊) 高階路網 (任兩邊界點間記錄路徑資訊) 缺點 HEPV 區域最短。 全域最短。 所需記憶體大。低層任兩點最短，仍需高層輔助。 Wang 不記錄終點所屬群編號(Frag) 所需記憶體大。高階需執行Dijkstra會比較慢。 Liu:實際最短路徑可能途經其他子網路 11

文獻探討– 圖形分割方法 Habbal等人[Habbal 1994]證實，若能將圖形分割為越多節點數量接近的子圖而且每個子圖間邊界點數量越少的圖形分割方法，越適用於路徑搜尋。 Huang [1996]等人提出了Spatial Partition Clustering(SPC)對較大的圖形進行分割，Kohler[2003]等人則針對arc-flag提出multi-way partition圖形分群演算法。另外還有Schultes[2005]提出Dijkstra Rank來進行分群的方法。 Mohring[2005]等人的研究裡，比較了Grid、Quadtrees、kd-tree、METIS四種分群方法，結果顯示kd-tree與METIS對其改良的Dijkstra在搜尋時間上表現較好。 Wang[2006]等人的研究中，則比對了Spatial Partition Clustering(SPC)與METIS，最後結果仍是METIS較優。 12

文獻探討– 圖形分割方法 Kd-tree [Samet 1989] 2D-tree 節點存放座標x與y，取某座標軸的中位點， 建立新的樹節點，同時將資料集一分為二， 而中位點一般奇數層以x軸來取， 偶數層則為y軸。如此遞迴直到樹的分支 抵達所設定的深度為止。 n次分割後，可得到2n個分群。 且若採取座標中位點分割， 每個分群的節點數將近乎相等。

文獻探討– 圖形分割方法 METIS [Karypis 1998] – 多階層圖形分裂(粗化與去粗化步驟) 各分群內的節點數量近乎相等。 最小化整體與局部分群的連通度(即最小化邊界點數量)。 p19 14

基本方法介紹 基本圖形定義

基本方法介紹 A B C D E F G H J 7 3 2 5 4 I 1 G1 G3 G4 G2 分群概念模型 圖形G及4個分群

基本方法介紹 A B C D E F G H J 7 3 2 5 4 I 1 G1 G3 G4 G2 分群概念模型 A B C D

基本方法介紹 A B C D E F G H J 7 3 2 5 4 I 1 G1 G3 G4 G2 分群概念模型 C G D H

基本方法介紹 最短路徑求解 階層圖最短路徑長度求解 最短路徑重建 演算法架構 p21 19

基本方法介紹 最短路徑長度求解 C D G H A B C D

基本方法介紹 階層圖 群內圖 群間圖 G1 G4 G2 A B C D G1 G3 G4 C G D H G J 5 E 4 C 7 4 G I 5 3 3 1 3 2 F D 3 5 I H 2 B 3 G1 G3 G4 階層圖 群間圖 C D G H

基本方法介紹 ClusterBasedSearch(s,t) Case 1. 根據Lemma 1 Case 2. 根據Lemma 3 Y Case 2. 根據Lemma 3 N Y N：同群 Case 3. 根據Lemma 2 Y N：皆非邊界點 Case 4. p26

基本方法 - pathToBorder 最短路徑重建 s 1 2 3 t

基本方法 – pathBorderToBorder最短路徑重建 s 3 4 5 t

基本方法 - pathFromBorder最短路徑重建 s 5 t

延伸方法介紹 1a.階層圖記錄資訊之省除 群間圖 起點下一邊界點(nextNodeborder) findNextBorderNode(s,t)演算法 窮舉邊界點s所屬群的所有邊界點bs ，滿足下列兩條件者即為所求 (1) d1+d2 = distborder(s,t)，且 (2) d1為最小 bs s ※仍保有群內圖distinner(s,t)及 群間圖distborder(s,t)資訊 d2 d1 t 26

延伸方法介紹 1b.階層圖記錄資訊之省除 群內圖 起點下一節點(nextNodeinner) v t s findNextNode(s,t)演算法 前提： t = nextNodeborder(s,t) 窮舉s的鄰居節點V，滿足下列條件者即為所求 d1+d2 = distinner(s,t) ※仍保有群內圖distinner(s,t) v t d1 d2 s ※另外省除終點上一節點(prevNodeinner)的 findPrevNode(s,t)演算法，前提與需滿足之條件類似於此。 27

延伸方法介紹 2.群間圖之省除 – 只利用群內圖Dijkstra 由於在階層圖的路徑長度資訊中，群內圖記錄了群內各點到同群邊界點的往返資訊，因此形成了另一種類似於階層圖的圖形。 在此圖形上以Dijkstra進行求解。 演算完成可得最短路徑長度，及最短路徑所拜訪的邊界點序列，並保證序列中任兩連續邊界點皆同群。 28

延伸方法介紹 2.群間圖之省除 – 只利用群內圖Dijkstra 由於<s,t>、<s,1,t>、<s,1,2,t>的長度相等，依照Dijkstra節點挑選次序的不同，若選中<s,t>或<s,1,t>將造成路徑重建過程跨越遺漏邊界點1或2時，路徑無法重建。 但由於邊界點遺漏只發生在同群邊界點間，可以下列方式之一修正 (1) findNextBorderNode演算法中，改用群內圖長度資訊distinner(s,t) 窮舉s所屬群的邊界點bs滿足下列兩條件者即為所求 (1) d1+d2 = distinner(s,t)，且 (2) d1為最小 (2) 改在群內圖中記錄起點下一邊界點nextNodeborder (s,t) d1 = distinner(s,1) d2 = distinner(1,t) d1 d2 29

延伸方法介紹 3.全域地標資訊之省除–只利用群內邊界點ALT dist(v,m) dist(m,v) 30

實驗結果與討論 實驗環境 CPU：AMD Opteron 2.2GHz cache 1MB RAM：8 GB OS：Red Hat Enterprise Linux WS release 4 程式開發環境：Java Development Kit 1.6.0_02 地圖資料：交通部運輸研究所路網數值圖1.1版 全台灣節點及路段數：節點-275195個 (其中單進單出節點共46015個) 路段-381172條

實驗結果與討論 前處理 128群 kd-tree METIS 階層圖（群內、群間） 採用Dijkstra以正反地圖資訊求得。 32

實驗結果與討論 前處理 由於METIS與kd-tree的分群結果中，各節點將只會屬於某一群(群間無節點交集)，不符合我們群的定義。在我們群的定義中，群間將有交集，且其交集的節點為「邊界點」。因此我們必需根據群間無交集的分群結果，為其建立邊界點。 邊界點找尋演算法 依照「可到達鄰居節點數」對所有節點排序，可到達不同群鄰居節點數越多的節點越先處理，讓擁有較多跨群邊的節點成為邊界點。 對於所有「起始節點與終端節點不同群」的有向邊，其中一端必為邊界點。

實驗結果與討論 前處理 階層圖（群內、群間） 128群 資料檔 檔案 大小 前處理時間 全台節點128群 kd-tree METIS 採用Dijkstra以正反地圖資訊求得。 資料檔 檔案 大小 前處理時間 原始地圖 31 MB -- 座標 2.5 MB 分群資訊 3.16 MB 群內圖 Kd-tree 625.17 MB 1.66 小時 METIS 359.72 MB 2.59 小時 群間圖 442.3 MB 4.08 小時 174 MB 2.22 小時 有向地標 （from_m / to_m） 41.9 + 41.9 MB 約1小時 全台節點128群 Kd-tree METIS 每群節點數量 8852 5354 邊界點數量 2143~2245 2014~2259 階層圖大小 1.1 (gb) 534 (mb) 階層圖前處理時間 5.74 (hr) 4.81 (hr) 34

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

實驗結果與討論 比較的演算法： 上述分群演算法皆可如下選擇性省除階層圖記錄之資訊 不分群： Dijkstra、直線距離A*(記為A*)、有向地標A*(ALT)、 分群演算法CB：階層圖採用窮舉(CB all-pair)、Dijkstra(CB Dijkstra)、ALT(CB ALT)， 只利用群內圖的Dijkstra(CB inner Dijkstra)， 　 群內邊界點ALT (Cluster ALT)。 上述分群演算法皆可如下選擇性省除階層圖記錄之資訊 (dist,dist)：群內圖記錄dist，群間圖記錄dist (next,dist)：群內圖記錄dist + next/prev，群間圖記錄dist (dist,next)：群內圖記錄dist，群間圖記錄dist + next (next,next)：群內圖記錄dist + next/prev，群間圖記錄dist + next 36

實驗結果與討論 實驗1 起終點同群且皆非邊界點(case 4) 找出群內(case 4)最快的演算法 37

實驗結果與討論 實驗2 起終點不同群且非同時為邊界點(case 2) 比較空間省除方法各項組合的差異(case 3) 38

實驗結果與討論 實驗2 - continue 起終點隨機分佈(case 1-4) 最快組合：「CB all-pair+Cluster ALT」 2.6ms 5.3ms 39

空間省除方法組合的搜尋時間(對數刻度)及所需空間關係圖 實驗結果與討論 實驗2 - continue 起終點隨機分佈(case 1-4) 其中僅省除群內next的DN為表現皆佳的組合 CB inner Dijkstra CB all-pair 空間省除方法組合的搜尋時間(對數刻度)及所需空間關係圖 (METIS 128群) (METIS 128群) 40

實驗結果與討論 實驗3 比較不同分群下的執行差異 41

實驗結果與討論 實驗4 以Dijkstra Rank區分起終點遠近程度 觀察的起終點遠近程度差距Dijkstra Rank範圍： 200*2n，n=0~10 地圖類型 距離成本地圖：以路徑長度作為邊長 時間成本地圖 ：以行經路段所需時間作為邊長 距離與時間成本地圖中，起終點遠近程度對搜尋的影響 道路等級 速限(km/hr) 國道 90 快速道路 70 省道 60 縣道/鄉鎮市區道路/產業道路 50 Dijkstra Rank 42

實驗結果與討論 實驗4 距離成本地圖 距離與時間成本地圖中，起終點遠近程度對搜尋的影響 43

實驗結果與討論 實驗4 時間成本地圖 距離與時間成本地圖中，起終點遠近程度對搜尋的影響 p53 44

與HEPV、Wang之比較 初始參數設定 45

與HEPV、Wang之比較 46

與HEPV、Wang之比較 1.前處理檔案大小比較 47

與HEPV、Wang之比較 1.前處理檔案大小比較 48

與HEPV、Wang之比較 1.前處理檔案大小比較 49

與HEPV、Wang之比較 2.前處理時間複雜度比較 50

與HEPV、Wang之比較 3.最短路徑長度求解時間複雜度比較 51

最短路徑重建時間複雜度整理 52

結論 提出一個適用於台灣路網，能在數毫秒內完成搜尋，所需記憶體空間在1G以下之分群最短路徑演算法，可供相關應用程式使用。其空間需求能較HEPV、Wang少(不採用省除方法的情況下)，且搜尋速度依時間複雜度來看大致仍能保持相同水準。 提供了可以省除空間的多種使用組合，並整理出在METIS 128群之下的搜尋時間、前處理資訊空間關係圖。並歸納出搜尋速度在10ms之下的： 搜尋速度最快組合(NN) 557mb，2.75ms 最省空間組合(DD) 323mb，4.15ms 搜尋時間、空間折衷組合(DN) 377mb，2.87ms CB inner Dijkstra CB all-pair

結論 在起終點同在一群內的情況，提出群內邊界點ALT，由實驗1的結果中，群內邊界點ALT的路徑搜尋時間(5.34~6.19ms)能大幅低於傳統ALT的搜尋時間(81.27ms) 54