基于改進A星算法的城市交通尋徑的研究.pdf

1、隨著網絡時代的來臨和城市規(guī)模的日益擴大，人們在出行之前，往往會查詢出行的路線。現(xiàn)在各種各樣的出行路線查詢系統(tǒng)很多，但是優(yōu)質的出行路線查詢功能還有待提高，還需要進一步對出行路線的路徑搜索算法進行優(yōu)化。
　　A星算法是目前最廣泛使用的城市出行路徑搜索算法之一。它是一種啟發(fā)式搜索算法，其采用的估價函數(shù)是：F(n)=G(n)+H(n)，其中G(n)表示從起始頂點到當前頂點的距離的實際值，H(n)表示從當前頂點到目標頂點的距離的估算值。兩者

2、相加的結果為估價函數(shù)的估價值，選擇估價值最小的頂點作為下一步要選擇的頂點，如此循環(huán)運行估價函數(shù)從而生成最優(yōu)路徑。
　　本文結合實際應用，對標準A算法進行了以下兩方面改進：
　　?使用最小二叉堆技術優(yōu)化0PEN表的查找速度，提高尋徑效率。
　　?對于A星算法的估價函數(shù)，筆者在如下方面進行了改進：
　　1.選擇合適的啟發(fā)函數(shù)。
　　2.增加啟發(fā)函數(shù)在估價函數(shù)中的比重。
　　3.使用向量內積值改進啟發(fā)函數(shù)在

3、估價函數(shù)的比重。
　　4.過濾內積值進一步優(yōu)化估價函數(shù)。
　　從而減少尋徑過程中遍歷的頂點數(shù)，在保證尋徑質量整體不變的前提下，較大幅度的提高了尋徑效率。
　　本文在Visual Studio2010開發(fā)平臺上，使用C++語言分別實現(xiàn)了標準A星和改進A星的路徑搜索算法，在此基礎上統(tǒng)計它們的尋徑長度、尋徑時間、尋徑過程中遍歷的頂點數(shù)量，以此驗證改進后的A星算法的可行性和有效性。
　　經過本篇論文第四章仿真實驗驗證證明