地鐵圖快速尋路算法
1.概述
這兩天，博客園里有人談?wù)摰?a >地鐵圖的實(shí)現(xiàn)，而之前我也和NeoRAGEx2002同學(xué)做了一個(gè)Android地鐵圖應(yīng)用，因此，對(duì)于地鐵圖的尋路算法，我覺得有必要專門寫一篇博客來(lái)給出我們的解決方案，供大家參考。本文所述算法的時(shí)間復(fù)雜度為O(|E|log|E|)，其中|E|為邊的數(shù)量。
2.概念
1)點(diǎn)和邊
基礎(chǔ)元素為點(diǎn)(地鐵站)和邊(兩個(gè)相鄰站之間的有向軌道)。
例如，經(jīng)過(guò)莘莊站有1號(hào)線和5號(hào)線，含有莘莊站的邊有4條，經(jīng)過(guò)世紀(jì)大道站有4條線路，含有世紀(jì)大道站的邊有8條。
2)運(yùn)營(yíng)段
在邊的基礎(chǔ)上，還有運(yùn)營(yíng)段的概念，即一組連續(xù)邊的集合。
例如，1號(hào)線有莘莊-富錦路(發(fā)車間隔8分)、莘莊-上海火車站(發(fā)車間隔6分)、上海南站-富錦路(發(fā)車間隔8分)、上海南站-上?；疖囌?發(fā)車間隔6分)、富錦路-莘莊(發(fā)車間隔8分)、上?；疖囌?莘莊(發(fā)車間隔6分)等運(yùn)營(yíng)段。
3)代價(jià)
尋路算法的依據(jù)可以為時(shí)間、換乘次數(shù)、經(jīng)過(guò)邊數(shù)等任意非負(fù)代價(jià)，這里著重對(duì)時(shí)間進(jìn)行建模。
每條邊有一個(gè)乘坐時(shí)間代價(jià)，表示乘坐地鐵經(jīng)過(guò)該邊所需要花費(fèi)的時(shí)間。
每個(gè)運(yùn)營(yíng)段有一個(gè)等車時(shí)間代價(jià)，為通過(guò)該運(yùn)營(yíng)段中的邊乘車需要等車的時(shí)間，通?？梢约僭O(shè)為發(fā)車間隔時(shí)間(等車時(shí)間的最大值)或者發(fā)車間隔時(shí)間的一半(等車時(shí)間的數(shù)學(xué)期望)。
在每個(gè)點(diǎn)有一個(gè)換乘時(shí)間代價(jià)矩陣，表示在任意兩條邊之間換乘所需要花費(fèi)的時(shí)間。兩邊之間的關(guān)系有直接連通、換乘、不連通三種。連通的換乘時(shí)間代價(jià)為0，換乘的換乘時(shí)間代價(jià)為換乘行走時(shí)間+等車時(shí)間，不連通的換乘時(shí)間代價(jià)為+∞。這個(gè)矩陣可以用稀疏矩陣表示，不連通的兩邊不出現(xiàn)。由于地鐵的設(shè)計(jì)使得我們不需要考慮沿著某條線路折返的路線，我們可以將一邊和它的相反邊看做不連通而不是換乘，這樣可以降低圖的復(fù)雜度。
3.算法
1)思路
傳統(tǒng)的最短路徑算法很多，比如
Dijkstra算法，不過(guò)這種算法沒有辦法解決換乘時(shí)間代價(jià)問(wèn)題。
廣度優(yōu)先算法，在加權(quán)圖的時(shí)候無(wú)法得到最優(yōu)解。
受限的深度優(yōu)先算法，能得到結(jié)果，但路徑比較長(zhǎng)時(shí)算法時(shí)間過(guò)長(zhǎng)。
我們可以考慮這樣一個(gè)自然現(xiàn)象，雪水在山峰上融化，然后流經(jīng)各個(gè)山谷。各站點(diǎn)就是山谷中的點(diǎn)，換乘站點(diǎn)就是山谷分成多股的交叉點(diǎn)。
假設(shè)起始點(diǎn)是山峰，水沿著各邊擴(kuò)散，經(jīng)過(guò)一邊的用時(shí)和邊上的乘坐時(shí)間代價(jià)一樣，從一邊到一鄰邊，需要等待換乘時(shí)間代價(jià)。不停往起始點(diǎn)倒水，水不停流動(dòng)，當(dāng)水到達(dá)終止點(diǎn)時(shí)，水流經(jīng)過(guò)的路徑就是我們所需要的最短路徑。
這個(gè)模型的問(wèn)題在于水可以有多股水流同時(shí)流動(dòng)，但是我們的算法應(yīng)該有一個(gè)順序，我們可以假設(shè)有一個(gè)水流切線，表示所有水流的最前端位置。任意邊e，當(dāng)其起點(diǎn)被水流所覆蓋，而終點(diǎn)沒有被水流覆蓋時(shí)，將e加入按代價(jià)排序的切線邊列表C(紅黑樹或平衡樹實(shí)現(xiàn))，并記錄e->水流經(jīng)過(guò)的上一邊。繼續(xù)讓水流動(dòng)，則C中的第一個(gè)邊e的終點(diǎn)最先被水流所覆蓋，從C中移除e。當(dāng)?shù)竭_(dá)尋路的終止點(diǎn)時(shí)，我們可以通過(guò)從最后一條邊開始回溯上一邊，再上一邊的上一邊，直到尋路的起點(diǎn)，這樣就獲得了所需要的路徑。
算法也可以不在終點(diǎn)結(jié)束，而直到水流覆蓋地圖上的所有點(diǎn)，對(duì)性能并沒有明顯的影響。
2)例子
如圖1所示：
圖1(a) 時(shí)間代價(jià) 圖1(b) 搜索順序
為了簡(jiǎn)化問(wèn)題，我們假設(shè)2號(hào)線(綠色)和9號(hào)線(水色)不存在，只考慮4號(hào)線(深藍(lán)色)和6號(hào)線(紫紅色)。
圖1(a)中表示了4號(hào)線和6號(hào)線的邊的時(shí)間代價(jià)，其中白色表示等車時(shí)間，黃色表示乘車時(shí)間。
我們假設(shè)每個(gè)換乘站，換乘時(shí)的行走時(shí)間為4分鐘。
圖1(b)表示了搜索順序，對(duì)于相同的代價(jià)，其搜索順序不定，由切線邊列表C的實(shí)現(xiàn)決定。
例子中的起始點(diǎn)為世紀(jì)大道，終止點(diǎn)為上海兒童醫(yī)學(xué)中心。
切線邊列表C的變化如下
- {1, 2, 3, 5}
- {2, 3, 4, 5}
- {3, 4, 5, 6}
- {4, 5, 6, 9}
- {5, 6, 7, 9}
- {6, 7, 8, 9}
- {7, 8, 9, 10, .., ..}
- {8, 9, 10, .., .., ..}
- {9, 10, .., .., .., ..}
- {10, .., .., .., .., ..}
需要注意到消去6的時(shí)候，增加了10、(藍(lán)村路, 塘橋)、9的反向邊三條邊，消去9的時(shí)候，增加了6的反向邊。
消去9時(shí)，會(huì)再次搜索到10，此時(shí)的時(shí)間代價(jià)為13+4+8=25，但因?yàn)?0已經(jīng)記錄了其上一邊，所以不再加入C。
#p#
3)實(shí)現(xiàn)
偽代碼如下：
- record Vertex //點(diǎn)
- InEdges:List<Edge> //進(jìn)站邊
- OutEdges:List<Edge> //出站邊
- Connection:Map<Tuple<Edge, Edge>, EdgeConnection> //邊連接矩陣，包含換乘行走時(shí)間代價(jià)，當(dāng)不連接時(shí)不存在
- record Edge //邊
- Start:Vertex //起點(diǎn)
- End:Vertex //終點(diǎn)
- Cost:Int //乘坐時(shí)間代價(jià)
- Ranges:List<Range> //運(yùn)營(yíng)段
- record Range //運(yùn)營(yíng)段
- Edges:List<Edge> //邊
- Cost:Int //等車時(shí)間
- taggedunion EdgeConnection
- Connected:Unit //直接連接
- Transferable:Int //換乘，行走時(shí)間代價(jià)
- CalculateRoute(Start:Vertex, End:Vertex):List<Edge>
- if Start == End
- return new List<Edge>() //起始點(diǎn)和終止點(diǎn)重合
- let Previous <- new Map<Edge, Edge>() //邊到上一邊的映射
- let cmp <- (Comparer<Edge>)(...) //路徑代價(jià)比較函數(shù)，將在下面給出
- let CutEdges <- new RedBlackTree<Edge>(cmp) //水流切線邊列表
- foreach o in Start.OutEdges
- CutEdges <- CutEdges + o
- Previous <- Previous + (o, null)
- let e <- (Edge)(null) //終邊
- while CutEdges.Count > 0
- let i <- CutEdges.First
- CutEdges <- CutEdges - i
- let s <- i.End
- if s == End
- e <- i
- break
- foreach o in s.OutEdges
- if !s.Connection.ContainsKey((i, o))
- continue
- if Previous.ContainsKey(o)
- continue
- Previous <- Previous + (o, i)
- CutEdges <- CutEdges + o
- if e == null
- return null //沒有路徑
- let l <- new List<Edge>()
- while e != null
- l <- l + e
- e <- Previous(e)
- return l.Reverse()
下面為當(dāng)尋路依據(jù)為時(shí)間時(shí)的比較函數(shù)
- let Time <- new Map<Edge, Int>()
- let Range <- new Map<Edge, Range>()
- let GetBestRange <- l:List<Range> => l.OrderBy(r => r.Cost).First
- let GetTime <-
- e =>
- if e == null
- return 0
- if Time.ContainsKey(e)
- return Time(e)
- let p <- Previous(e)
- let v <- GetTime(p)
- if p != null
- let c <- e.Start.Connection((p, e))
- if c
- | Connected ->
- let rgOld <- Range(p)
- let rg <- GetBestRange(p.Ranges.Intersect(e.Ranges))
- Range <- Range + (e, rg)
- if rgOld != rg
- v <- v - rgOld.Cost + rg.Cost
- | Transferable t ->
- let rg <- GetBestRange(e.Ranges)
- Range <- Range + (e, rg)
- v <- v + rg.Cost + t
- else
- let rg <- GetBestRange(e.Ranges)
- Range <- Range + (e, rg)
- v <- v + rg.Cost
- v <- v + e.Cost
- Time <- Time + (e, v)
- return v
- let cmp <-
- (l:Edge, r:Edge) =>
- return GetTime(l) - GetTime(r)
下面為當(dāng)尋路依據(jù)為換乘次數(shù)時(shí)的比較函數(shù)
- let TransferCount <- new Map<Edge, Int>()
- let GetTransferCount <-
- e =>
- if e == null
- return 0
- if TransferCount.ContainsKey(e)
- return TransferCount(e)
- let p <- Previous(e)
- let v <- GetTransferCount(p)
- if p != null
- let c <- e.Start.Connection((p, e))
- if c
- | Connected ->
- ()
- | Transferable _ ->
- v += 1
- TransferCount <- TransferCount + (e, v)
- return v
- let cmp <-
- (l:Edge, r:Edge) =>
- return GetTransferCount(l) - GetTransferCount(r)
下面為當(dāng)尋路依據(jù)為經(jīng)過(guò)邊數(shù)時(shí)的比較函數(shù)
- let StopCount <- new Map<Edge, Int>()
- let GetStopCount <-
- e =>
- if e == null
- return 0
- if StopCount.ContainsKey(e)
- return StopCount(e)
- let p <- Previous(e)
- let v <- GetStopCount(p) + 1
- StopCount <- StopCount + (e, v)
- return v
- let cmp <-
- (l:Edge, r:Edge) =>
- return GetStopCount(l) - GetStopCount(r)
4.算法復(fù)雜度
認(rèn)為點(diǎn)的入站邊和出站邊很少，覆蓋每條邊的運(yùn)營(yíng)段很少，并注意到GetTime運(yùn)行時(shí)遞歸的部分總會(huì)在Time變量中緩存，可知時(shí)間比較函數(shù)的復(fù)雜度為O(1)。
CutEdges的紅黑樹插入刪除的復(fù)雜度為O(log|E|)。
所有邊最多進(jìn)出CutEdges一次，可知整個(gè)算法的復(fù)雜度為O(|E|log|E|)。
5.結(jié)果
本文所述算法能夠在O(|E|log|E|)時(shí)間內(nèi)快速得到全局最佳路徑。
在1GHz的單CPU手機(jī)上實(shí)測(cè)得到的上海地鐵(11條線路214站)任意兩站點(diǎn)之間的尋路時(shí)間均為200ms以下。
最后還是介紹下我們的應(yīng)用。
矢量地鐵（上海版）
支持雙指無(wú)極縮放、動(dòng)態(tài)尋徑效果、本地地圖顯示。雖然我們只是一個(gè)小團(tuán)隊(duì)，但我們只做最好的地鐵圖！如果大家有啥問(wèn)題和建議，歡迎給我們留言！
原文鏈接：http://www.cnblogs.com/Rex/archive/2012/08/12/2634401.html
