基于改進(jìn)A星算法的城市交通尋徑的研究.pdf

1、隨著網(wǎng)絡(luò)時(shí)代的來(lái)臨和城市規(guī)模的日益擴(kuò)大，人們?cè)诔鲂兄埃鶗?huì)查詢出行的路線?，F(xiàn)在各種各樣的出行路線查詢系統(tǒng)很多，但是優(yōu)質(zhì)的出行路線查詢功能還有待提高，還需要進(jìn)一步對(duì)出行路線的路徑搜索算法進(jìn)行優(yōu)化。
　　A星算法是目前最廣泛使用的城市出行路徑搜索算法之一。它是一種啟發(fā)式搜索算法，其采用的估價(jià)函數(shù)是：F(n)=G(n)+H(n)，其中G(n)表示從起始頂點(diǎn)到當(dāng)前頂點(diǎn)的距離的實(shí)際值，H(n)表示從當(dāng)前頂點(diǎn)到目標(biāo)頂點(diǎn)的距離的估算值。兩者

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

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