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

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

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

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