本文觀點翻譯至Ron Gutman和Andrew V.Goldberg的兩篇論文。經過實際中國地圖測試，對于dijkstra和A*算法均能大大的減少edge探索數目(探索范圍沒有明顯減少，但稀疏度大大提高)，能相對與不使用Reach-V剔除90%以上的節點。
定義：
定義頂點reach值：一條通過該頂點的最短路徑中的被該點分割的較短那部分路徑的長度。
定義頂點reach估計值(reach-v)：所有通過該點的最短路徑中的reach值的最大值。
舉例：
對于如圖所示的雙向圖
reach-v(B) = 12,其余各個頂點的reach-v全為0。
算法中的用法：
以dijkstra為例，假設當前算路的起點終點分別為S，T。當前探索點為V，記m(p)為從S到V的最短路徑長度，記d(V,T)為從V到T的歐幾里得距離。
如果reach-v(V) < m(p) && reach-v(V) < d(V,T)則排除掉V點(不探索)。
對于A*算法同理，m(p)對應于A*中的G，d(V,T)對應于A*的H。
Reach-V值的計算:
由于對所有節點都做全圖的dijkstra規模過于龐大，對于幾千萬上億個節點的地圖運算時間會達到幾年，所以實際中一般都是選取一個合適的Reach-V值上界，以在預處理時間和時間剔除效果間做一個平衡。 以下將著重介紹一種P-Tree思想來對每個節點做dijkstra。P-Tree顧名思義就是對每個節點不做全圖的dijkstra，而是設定一個停止條件以產生一棵局部最短路徑樹。(待續)
posted on 2011-05-13 11:10
saha 閱讀(796)
評論(0) 編輯 收藏 引用