最短路徑搜索中的A算法改進(jìn)應(yīng)用

段明瑋

摘 要 最短路徑搜索中的A算法，多用于導(dǎo)航、路線動(dòng)態(tài)規(guī)劃等領(lǐng)域。而在最短路徑搜索時(shí)，傳統(tǒng)A、Dihkstra算法，因不同場(chǎng)景內(nèi)標(biāo)記結(jié)點(diǎn)數(shù)量存在差異性，使得算法實(shí)現(xiàn)速率難以保障。因此，本文基于最短路徑搜索中的A算法改進(jìn)思路，對(duì)A算法的內(nèi)部?jī)?yōu)化、應(yīng)用展開(kāi)研究，借此明確最短路徑的最優(yōu)求解方式，提高A算法使用水平。

關(guān)鍵詞 最短路徑;A算法;標(biāo)記結(jié)點(diǎn)

引言

A算法屬于高效率、高精度的啟發(fā)式搜索算法，在應(yīng)用A算法時(shí)，相關(guān)人員需預(yù)先搜索圖內(nèi)的最短路徑，以獲取數(shù)據(jù)信息。為進(jìn)一步優(yōu)化改進(jìn)A算法。提高其在最短路徑搜索時(shí)的搜索效率，創(chuàng)新其數(shù)據(jù)結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)。本文對(duì)最短路徑搜索中的A算法改進(jìn)應(yīng)用展開(kāi)分析，希望給予相關(guān)從業(yè)者建議與參考。

1最短路徑搜索中的A算法改進(jìn)思路

原始Dihkstra算法，可將網(wǎng)絡(luò)結(jié)點(diǎn)劃分為臨時(shí)性、未標(biāo)記、永久性等標(biāo)記結(jié)點(diǎn)。其中算法網(wǎng)絡(luò)中初始結(jié)點(diǎn)屬于未標(biāo)記結(jié)點(diǎn)，而搜索期間，以及與最短路徑向銜接的端口屬于臨時(shí)性的標(biāo)記點(diǎn)[1]。其中，不同時(shí)期的循環(huán)可在搜索距源點(diǎn)時(shí)，從臨時(shí)標(biāo)記結(jié)點(diǎn)，選出路徑長(zhǎng)度較短的結(jié)點(diǎn)出，作為永久性標(biāo)記結(jié)點(diǎn)，同時(shí)結(jié)束算法。但在原有Dihkstra算法中，由于臨時(shí)標(biāo)記節(jié)點(diǎn)多存儲(chǔ)與無(wú)須表內(nèi)，使得該算法在實(shí)際應(yīng)用中，所經(jīng)標(biāo)記結(jié)點(diǎn)較多，影響算法實(shí)現(xiàn)效率。因此，可將網(wǎng)絡(luò)內(nèi)臨時(shí)標(biāo)記結(jié)點(diǎn)，以最短路徑進(jìn)行排序，可避免在搜索過(guò)程中，歷經(jīng)多個(gè)標(biāo)記結(jié)點(diǎn)，進(jìn)而在保障算法質(zhì)量的基礎(chǔ)上，提高算法實(shí)現(xiàn)效率。

2A算法在最短路徑搜索中的改進(jìn)應(yīng)用

2.1 算法實(shí)現(xiàn)

A算法是現(xiàn)階段，較為流行的搜索算法，可基于估價(jià)函數(shù)，靈活選擇最優(yōu)、最短路徑的搜索算法。而在最短路徑搜索中，A算法改進(jìn)思路，在于將現(xiàn)存臨時(shí)標(biāo)記結(jié)點(diǎn)、源點(diǎn)之間的最短路徑，以及標(biāo)記結(jié)點(diǎn)的最小費(fèi)用，和算法中臨時(shí)標(biāo)記結(jié)點(diǎn)中，存在的屬性值。然后將該屬性值作為該標(biāo)記點(diǎn)集合中，永久標(biāo)記點(diǎn)的選擇依據(jù)。此種創(chuàng)新手段，屬于A算法的改進(jìn)應(yīng)用思路，其中臨時(shí)標(biāo)記結(jié)點(diǎn)函數(shù)可定義為：F（j）=g（j）+h（j-1）[2]。A算法在最短路徑搜索中優(yōu)化改進(jìn)后，可基于該函數(shù)，從A算法搜索方向中，減少算法中結(jié)點(diǎn)歷經(jīng)次數(shù)，提高整體搜索速度

其一，運(yùn)行結(jié)構(gòu)。最短路徑搜索中，A算法改進(jìn)應(yīng)用時(shí)，可借助“優(yōu)先級(jí)”隊(duì)列組成實(shí)現(xiàn)。而該隊(duì)列的產(chǎn)生是通過(guò)刪除所有元素中，優(yōu)先級(jí)最高的某一元素。在此期間，為避免搜索過(guò)程中，反復(fù)搜索部分為標(biāo)記的弧，可在各弧算法過(guò)程中，通過(guò)一些重復(fù)被松弛，且距離起點(diǎn)最短的路徑指數(shù)，構(gòu)造優(yōu)先級(jí)隊(duì)列，同時(shí)去除算法累積權(quán)值中的最小元素。

其二，存儲(chǔ)結(jié)構(gòu)。A算法優(yōu)化后，可將臨接表作為算法的主要存儲(chǔ)場(chǎng)所，在優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)后。相關(guān)人員能夠使用鄰接表。針對(duì)圖中各弧段，可通過(guò)表頭、表結(jié)點(diǎn)分別設(shè)計(jì)單鏈表。而第n個(gè)單鏈表中的y表結(jié)點(diǎn)，可表示與第n各弧段存在作用關(guān)系的y弧。其中鏈表表頭區(qū)域內(nèi)的結(jié)點(diǎn)，可將弧段本身的標(biāo)識(shí)號(hào)指導(dǎo)升序排列，便于相關(guān)任意結(jié)合算法需求，實(shí)時(shí)訪問(wèn)各弧段鏈表[3]。因此，A算法在最短路徑搜索中改進(jìn)應(yīng)用時(shí)，將鄰接表作為存儲(chǔ)結(jié)構(gòu)的主要構(gòu)件，有利于算法實(shí)踐中，以最快速度查找相應(yīng)弧段。

2.2 應(yīng)用分析

相較于傳統(tǒng)Dihkstra算法、A算法，優(yōu)化改進(jìn)后的A算法是基于算法網(wǎng)絡(luò)本身在空間中的分布特征，靈活控制搜索空間。在原有的A算法與Dihkstra算法中，由于永久標(biāo)記點(diǎn)數(shù)較多，影響算法實(shí)現(xiàn)效率，目標(biāo)達(dá)成效果。而改進(jìn)后的A算法在具體應(yīng)用中，其永久標(biāo)記點(diǎn)數(shù)量在可控范圍內(nèi)，可確保數(shù)據(jù)分析效果。在路網(wǎng)結(jié)點(diǎn)數(shù)增加時(shí)，A、Dihkstra算法，均會(huì)導(dǎo)致最短路徑搜索時(shí)，最優(yōu)路徑的結(jié)點(diǎn)數(shù)數(shù)量較多。本文針對(duì)最優(yōu)數(shù)據(jù)結(jié)點(diǎn)多的問(wèn)題，在改進(jìn)A算法時(shí)，通過(guò)動(dòng)態(tài)化管理數(shù)據(jù)，調(diào)整結(jié)點(diǎn)與弧段結(jié)構(gòu)。

相關(guān)人員在算法初步實(shí)施中，結(jié)合算法實(shí)現(xiàn)需求，在網(wǎng)絡(luò)結(jié)點(diǎn)、弧段數(shù)據(jù)的搜索時(shí)，適當(dāng)生成某結(jié)點(diǎn)。并非在網(wǎng)絡(luò)創(chuàng)建時(shí)，改變弧段與結(jié)點(diǎn)數(shù)據(jù)的基本結(jié)構(gòu)[4]。之后，可通過(guò)刪除部分結(jié)點(diǎn)，以更新數(shù)據(jù)結(jié)構(gòu)，節(jié)約各永久、臨時(shí)性結(jié)點(diǎn)存儲(chǔ)空間。比如在算法過(guò)程中，可借助明確起始結(jié)點(diǎn)范圍，分析該圖幅分布范圍，從而整理圖內(nèi)數(shù)據(jù)，在圖幅范圍內(nèi)設(shè)計(jì)鄰接表。例如在某地區(qū)交通網(wǎng)絡(luò)數(shù)據(jù)計(jì)算中，改進(jìn)后的A算法，可在結(jié)點(diǎn)逐一標(biāo)記后，隨機(jī)選出部分核心區(qū)域，計(jì)算該區(qū)域范圍內(nèi)的結(jié)點(diǎn)數(shù)量。進(jìn)而節(jié)約最短路徑搜索中，標(biāo)記結(jié)點(diǎn)梳理時(shí)間。因此，動(dòng)態(tài)化管理數(shù)據(jù)的過(guò)程中，可在算法施行期間，發(fā)揮數(shù)據(jù)存儲(chǔ)版塊的可利用率，及時(shí)將無(wú)效數(shù)據(jù)篩除?；谠摂?shù)據(jù)管理思路的A算法改進(jìn)，可在路網(wǎng)中結(jié)點(diǎn)數(shù)量增加時(shí)，解決最短路徑搜索是，結(jié)點(diǎn)過(guò)多的問(wèn)題。

3結(jié)束語(yǔ)

綜上所述，本文基于傳統(tǒng)A、Dihkstra算法在最短路徑搜索時(shí)，存在的不足之處，對(duì)借助運(yùn)行、存儲(chǔ)結(jié)構(gòu)優(yōu)化，以及數(shù)據(jù)動(dòng)態(tài)化管理的改進(jìn)后的A算法應(yīng)用要點(diǎn)做出分析。為此，相關(guān)人員在不同情境中，使用A算法時(shí)，可結(jié)合A算法實(shí)現(xiàn)需求，靈活控制數(shù)網(wǎng)內(nèi)標(biāo)記結(jié)點(diǎn)數(shù)量，強(qiáng)化A算法應(yīng)用效果。

參考文獻(xiàn)

[1] 何夢(mèng)男，付瑜玲，陳誠(chéng)，等.基于元胞自動(dòng)機(jī)的應(yīng)急疏散最短路徑優(yōu)化算法[J].中國(guó)安全科學(xué)學(xué)報(bào)，2019，（4）：51-57.

[2] 石峰，陳旭，尹飛，等.基于S3變換的TriBA-Net最短路徑路由機(jī)制[J].中國(guó)科學(xué)：信息科學(xué)，2018，（1）：100-114.

[3] 劉蘭芬，楊信豐，劉林忠.基于標(biāo)號(hào)算法搜索過(guò)程的K最短路算法設(shè)計(jì)[J].蘭州交通大學(xué)學(xué)報(bào)，2019，（4）：66-69.

[4] 張默.Dijkstra最短路徑算法的研究[J].數(shù)學(xué)學(xué)習(xí)與研究，2018，（16）： 13-15.