最短路徑搜索中的A算法改進應用

段明瑋

摘 要 最短路徑搜索中的A算法，多用于導航、路線動態規劃等領域。而在最短路徑搜索時，傳統A、Dihkstra算法，因不同場景內標記結點數量存在差異性，使得算法實現速率難以保障。因此，本文基于最短路徑搜索中的A算法改進思路，對A算法的內部優化、應用展開研究，借此明確最短路徑的最優求解方式，提高A算法使用水平。

關鍵詞 最短路徑;A算法;標記結點

引言

A算法屬于高效率、高精度的啟發式搜索算法，在應用A算法時，相關人員需預先搜索圖內的最短路徑，以獲取數據信息。為進一步優化改進A算法。提高其在最短路徑搜索時的搜索效率，創新其數據結點存儲結構。本文對最短路徑搜索中的A算法改進應用展開分析，希望給予相關從業者建議與參考。

1最短路徑搜索中的A算法改進思路

原始Dihkstra算法，可將網絡結點劃分為臨時性、未標記、永久性等標記結點。其中算法網絡中初始結點屬于未標記結點，而搜索期間，以及與最短路徑向銜接的端口屬于臨時性的標記點[1]。其中，不同時期的循環可在搜索距源點時，從臨時標記結點，選出路徑長度較短的結點出，作為永久性標記結點，同時結束算法。但在原有Dihkstra算法中，由于臨時標記節點多存儲與無須表內，使得該算法在實際應用中，所經標記結點較多，影響算法實現效率。因此，可將網絡內臨時標記結點，以最短路徑進行排序，可避免在搜索過程中，歷經多個標記結點，進而在保障算法質量的基礎上，提高算法實現效率。

2A算法在最短路徑搜索中的改進應用

2.1 算法實現

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

其一，運行結構。最短路徑搜索中，A算法改進應用時，可借助“優先級”隊列組成實現。而該隊列的產生是通過刪除所有元素中，優先級最高的某一元素。在此期間，為避免搜索過程中，反復搜索部分為標記的弧，可在各弧算法過程中，通過一些重復被松弛，且距離起點最短的路徑指數，構造優先級隊列，同時去除算法累積權值中的最小元素。

其二，存儲結構。A算法優化后，可將臨接表作為算法的主要存儲場所，在優先級隊列實現后。相關人員能夠使用鄰接表。針對圖中各弧段，可通過表頭、表結點分別設計單鏈表。而第n個單鏈表中的y表結點，可表示與第n各弧段存在作用關系的y弧。其中鏈表表頭區域內的結點，可將弧段本身的標識號指導升序排列，便于相關任意結合算法需求，實時訪問各弧段鏈表[3]。因此，A算法在最短路徑搜索中改進應用時，將鄰接表作為存儲結構的主要構件，有利于算法實踐中，以最快速度查找相應弧段。

2.2 應用分析

相較于傳統Dihkstra算法、A算法，優化改進后的A算法是基于算法網絡本身在空間中的分布特征，靈活控制搜索空間。在原有的A算法與Dihkstra算法中，由于永久標記點數較多，影響算法實現效率，目標達成效果。而改進后的A算法在具體應用中，其永久標記點數量在可控范圍內，可確保數據分析效果。在路網結點數增加時，A、Dihkstra算法，均會導致最短路徑搜索時，最優路徑的結點數數量較多。本文針對最優數據結點多的問題，在改進A算法時，通過動態化管理數據，調整結點與弧段結構。

相關人員在算法初步實施中，結合算法實現需求，在網絡結點、弧段數據的搜索時，適當生成某結點。并非在網絡創建時，改變弧段與結點數據的基本結構[4]。之后，可通過刪除部分結點，以更新數據結構，節約各永久、臨時性結點存儲空間。比如在算法過程中，可借助明確起始結點范圍，分析該圖幅分布范圍，從而整理圖內數據，在圖幅范圍內設計鄰接表。例如在某地區交通網絡數據計算中，改進后的A算法，可在結點逐一標記后，隨機選出部分核心區域，計算該區域范圍內的結點數量。進而節約最短路徑搜索中，標記結點梳理時間。因此，動態化管理數據的過程中，可在算法施行期間，發揮數據存儲版塊的可利用率，及時將無效數據篩除。基于該數據管理思路的A算法改進，可在路網中結點數量增加時，解決最短路徑搜索是，結點過多的問題。

3結束語

綜上所述，本文基于傳統A、Dihkstra算法在最短路徑搜索時，存在的不足之處，對借助運行、存儲結構優化，以及數據動態化管理的改進后的A算法應用要點做出分析。為此，相關人員在不同情境中，使用A算法時，可結合A算法實現需求，靈活控制數網內標記結點數量，強化A算法應用效果。

參考文獻

[1] 何夢男，付瑜玲，陳誠，等.基于元胞自動機的應急疏散最短路徑優化算法[J].中國安全科學學報，2019，（4）：51-57.

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

[3] 劉蘭芬，楊信豐，劉林忠.基于標號算法搜索過程的K最短路算法設計[J].蘭州交通大學學報，2019，（4）：66-69.

[4] 張默.Dijkstra最短路徑算法的研究[J].數學學習與研究，2018，（16）： 13-15.