基于小世界模型的啟發(fā)式尋路算法研究.pdf

1、隨著經(jīng)濟的發(fā)展，最優(yōu)路徑應用領域漸廣，如路網(wǎng)導航、游戲行業(yè)、物流行業(yè)等。其中，路網(wǎng)導航備受廣大學者的關注。隨著路網(wǎng)數(shù)據(jù)的日益龐大，常規(guī)尋路算法的尋路性能稍顯不足，不能快速地解決在龐大的路網(wǎng)中尋找任意兩點間路徑的問題。當前使用較廣的尋路算法為分層算法。分層的思想是將詳細路網(wǎng)中權重較高的節(jié)點和路徑段抽象成一個新的交通路網(wǎng)，通過合理地切換詳細路網(wǎng)和新路網(wǎng)使得尋路算法獲得較好的時空性能。雖然分層算法優(yōu)化了在龐大的地圖數(shù)據(jù)中尋路的性能，但是其尋路

2、的質量較A*算法相比有所下降。
　　針對這個問題，本文借鑒了分層的思想、小世界網(wǎng)絡模型和路由理論等理論，給出了一種在保證路徑質量的前提下提升尋路效率的尋路策略:基于小世界模型的啟發(fā)式尋路算法（Heuristic path finding algorithm based on small world model，簡稱HPAS算法）。第一，路網(wǎng)分區(qū)。借鑒于分層算法中分層的思想和小世界網(wǎng)絡模型，通過對交通路網(wǎng)進行聚類分析，將聚類結果中的

3、各個簇劃分成不同區(qū)。第二，設置邊界路由節(jié)點和內部路由節(jié)點，并將相鄰路由節(jié)點之間的最優(yōu)路徑預存到緩存中。借鑒路由理論中的外部網(wǎng)關協(xié)議中路由器的功能，將各區(qū)中符合條件的節(jié)點設置成邊界路由節(jié)點或內部路由節(jié)點，相鄰路由節(jié)點之間的路徑可通過預處理階段求解出來并進行緩存。第三，尋路階段。利用A*算法在各個分區(qū)中的邊界路由節(jié)點和內部路由節(jié)點之間尋找最優(yōu)路徑。
　　實驗由路徑計算模塊、緩存模塊、地圖數(shù)據(jù)庫存取模塊和用戶請求處理模塊等組成。通過對美