A＊尋路算法的并行化設(shè)計(jì)及改進(jìn)

徐唐劍

（江西財(cái)經(jīng)大學(xué)軟件與物聯(lián)網(wǎng)工程學(xué)院，南昌330013）

0 引言

啟發(fā)式搜索算法是一種在人工智能等領(lǐng)域中常用的方法。對于人工智能系統(tǒng)來說，問題可能的狀態(tài)隨著搜索的深入呈現(xiàn)指數(shù)遞增或者階乘遞增，啟發(fā)式搜索通過模擬人腦的認(rèn)知模式，對部分可能的狀態(tài)而不是每個(gè)可能的狀態(tài)進(jìn)行權(quán)衡，找到一個(gè)或幾個(gè)可能性最大的路徑排除其他可能性較小或?yàn)榱愕穆窂剑档退惴◤?fù)雜性。具體的搜索方法就是在搜索過程中不斷評估狀態(tài)空間中的每一個(gè)狀態(tài)，根據(jù)其評估值有選擇性地得到相對最優(yōu)的狀態(tài)，然后以這個(gè)狀態(tài)繼續(xù)擴(kuò)展至最終狀態(tài)。常用的搜索算法包括三種：深度優(yōu)先搜索（Depth-First Search）、廣度優(yōu)先搜索（Breadth-First Search）、以及最佳優(yōu)先搜索（Best-First Search）。A*算法是一種基于最佳優(yōu)先搜索的啟發(fā)式搜索算法，其應(yīng)用取得了不錯(cuò)的效果。

算法就是一個(gè)定義明確的計(jì)算過程，在這個(gè)計(jì)算過程中取一個(gè)值或者值的集合作為程序的輸入并產(chǎn)生一個(gè)值或者值的集合作為程序的輸出。同時(shí)為了更好地解決在生活、工作中遇到的某些問題，有些時(shí)候需要對所設(shè)計(jì)的算法做出優(yōu)化，如時(shí)間復(fù)雜度、空間復(fù)雜度、正確性和健壯性等方面。而為了讓計(jì)算機(jī)每秒執(zhí)行更多的計(jì)算，計(jì)算機(jī)芯片通常被設(shè)計(jì)成具有多個(gè)處理“核”，可以把這些多核計(jì)算機(jī)當(dāng)做工作在某一芯片上的幾臺計(jì)算機(jī)，即“并行計(jì)算機(jī)”。隨著多核處理器的普及，為了使多核計(jì)算機(jī)獲得最佳的性能的同時(shí)提高程序的運(yùn)行速度，在設(shè)計(jì)算法時(shí)必須考慮算法的并行性。

1 Dijkstra算法

1.1 算法概述

Dijkstra算法是在1959年的時(shí)候由荷蘭的科學(xué)家Edsger Wybe Dijkstra提出，它能夠有效解決單源最短路徑問題，該算法要求有向圖中邊的權(quán)重都為非負(fù)。算法的主要特點(diǎn)是從起點(diǎn)開始不斷向外搜索和擴(kuò)展，直至達(dá)到目標(biāo)為止，同時(shí)在擴(kuò)展的過程中通過“松弛”操作不斷更新shortest值和pred值，最后在結(jié)果中可以得到起點(diǎn)到圖中其他所有結(jié)點(diǎn)的最短路徑及其權(quán)重和。通過簡單的數(shù)組實(shí)現(xiàn)的Dijkstra算法，那么它的時(shí)間復(fù)雜度是O（n2）。但采用更優(yōu)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的話，如使用斐波那契堆實(shí)現(xiàn)的Dijkstra算法，它的時(shí)間復(fù)雜度可以達(dá)到O（nlgn+m）。

1.2 算法思想

Dijkstra算法中最關(guān)鍵的部分是維護(hù)結(jié)點(diǎn)集S。算法不斷從結(jié)點(diǎn)集Q中選取具有shortest最小的結(jié)點(diǎn)u，將結(jié)點(diǎn)u加入到結(jié)點(diǎn)集S，然后對所有與該結(jié)點(diǎn)有關(guān)的邊進(jìn)行松弛操作。Dijkstra算法每次都是從結(jié)點(diǎn)集Q中選取與結(jié)點(diǎn)u“最近”的結(jié)點(diǎn)加入到結(jié)點(diǎn)集S中，這是一種典型的貪心策略。但不是使用貪心策略一定能夠獲得最優(yōu)解，但是可以通過一些定理和推論可以證明Dijkstra算法的解確實(shí)是最優(yōu)解。

（1）松弛操作

首先將從起點(diǎn)到結(jié)點(diǎn)u的所花費(fèi)最短路徑的值與邊（u,v）的權(quán)重之和與起點(diǎn)到當(dāng)前結(jié)點(diǎn)v所花費(fèi)的最短路徑值進(jìn)行比較。如果加上邊（u,v）的權(quán)重得到的值更小，那么需要將shortest[v]的值更新為當(dāng)前shortest[u]+weight（u,v），并且將最短路徑上結(jié)點(diǎn)v的前驅(qū)設(shè)置為結(jié)點(diǎn)u。

程序RELAX（u,v）

輸入：邊（u,v）的頂點(diǎn) u,v

結(jié)果：

如果shortest[v]的值減小了，那么令pred[v]取u。

如 果 shortest[u]+weight（u,v）＜shorest[v]，那 么 將shortest[v]賦值為shortest[u]+weight（u,v），同時(shí)將pred[v]賦值為u。

（2）算法步驟

Dijkstra算法通過重復(fù)對具有最小shortest值的結(jié)點(diǎn)相關(guān)聯(lián)的每條邊執(zhí)行松弛操作來工作。首先，需要將有向圖中所有結(jié)點(diǎn)加入結(jié)點(diǎn)集Q，然后還需要唯一確定一個(gè)源點(diǎn)s，并將shortest[s]的值初始化為0，對于圖中其他所有頂點(diǎn)v的shortest[v]值設(shè)為無窮大，對所有結(jié)點(diǎn)的pred[v]值將其設(shè)為NULL，算法不斷從結(jié)點(diǎn)集Q中選取具有shortest最小值的結(jié)點(diǎn)u，并將該結(jié)點(diǎn)從結(jié)點(diǎn)集Q中移除，再對所有與結(jié)點(diǎn)u相關(guān)的邊執(zhí)行松弛操作。

程序DIJKSTRA（G,s）

輸入：有向圖G、源點(diǎn)s

結(jié)果：對于有向圖G中的任何一個(gè)非源點(diǎn)v，shortest[v]的值指的是從源點(diǎn)s到結(jié)點(diǎn)v的最短路徑上所有邊的權(quán)重和。pred[v]表示在最短路徑上結(jié)點(diǎn)v的父結(jié)點(diǎn)。對于源點(diǎn)，將其shortest[s]的值置為0,pred[s]的值置為NULL。規(guī)定如果從源點(diǎn)s與結(jié)點(diǎn)v不存在路徑，那么shortest[v]的值是無窮大，而pred[v]的值是NULL。

①初始化。將除起點(diǎn)s以外的任何結(jié)點(diǎn)v的shortest[v]值設(shè)為無窮大，其pred[v]的值設(shè)為NULL。然后將 shortest[s]的值置為 0，pred[s]置為 NULL。

②將所有的結(jié)點(diǎn)加入結(jié)點(diǎn)集Q。

③只要結(jié)點(diǎn)集Q不為空：

A.在結(jié)點(diǎn)集Q中選取一個(gè)具有shortest[u]最小值的結(jié)點(diǎn)u，然后將這個(gè)結(jié)點(diǎn)從結(jié)點(diǎn)集Q中移除。

B.找出每個(gè)與頂點(diǎn)u鄰接的結(jié)點(diǎn)v：

執(zhí)行松弛操作，即調(diào)用RELAX（u,v）。

圖1 Dijkstra算法運(yùn)行流程圖

（3）核心代碼

Python是一種面向?qū)ο蟮慕忉屝陀?jì)算機(jī)程序設(shè)計(jì)語言，于1989年由Guido van Rossum發(fā)明。Python具有豐富庫而且這些庫的功能強(qiáng)大，由于它可以與其他語言很好的合作所以常被稱為“膠水語言”。近些年來，尤其是人工智能逐漸成為人們關(guān)注的重點(diǎn)，而其首選編程語言就是Python。其次Python在網(wǎng)絡(luò)爬蟲方面的運(yùn)用也是非常廣泛的，加上其“優(yōu)雅”、“明確”、“簡單”的設(shè)計(jì)特點(diǎn)，Python得到了大多數(shù)人的青睞。Python于2017年7月在IEEE發(fā)布的編程語言排行版位居首位。為了適應(yīng)互聯(lián)網(wǎng)時(shí)代發(fā)展的要求，本文使用了Python作為算法實(shí)現(xiàn)的主要編程語言，以下是Dijkstra算法實(shí)現(xiàn)的核心代碼：

2 A＊算法

2.1 算法概述

2.2 算法思想

A*算法是建立在經(jīng)典Best-First Search和Dijkstra算法的基礎(chǔ)上的一種啟發(fā)式搜索算法，算法通過引入評估函數(shù)減少搜索范圍和降低空間復(fù)雜度。通常將評估函數(shù)定義為：

g（n）表示從起點(diǎn)到當(dāng)前點(diǎn)n的實(shí)際移動距離，即從起點(diǎn)移動到當(dāng)前點(diǎn)n所花費(fèi)的移動代價(jià)。h（n）表示從當(dāng)前點(diǎn)n到終點(diǎn)或目標(biāo)點(diǎn)的估算距離，即對當(dāng)前點(diǎn)n移動到終點(diǎn)的估算移動代價(jià)。通過比較評估函數(shù)f（n），選取具有最優(yōu)值的結(jié)點(diǎn)用作下一次的擴(kuò)展。

（1）算法特性

①當(dāng)只計(jì)算g（n）時(shí)，即只計(jì)算和考慮起點(diǎn)到當(dāng)前點(diǎn)n的實(shí)際耗費(fèi)距離，不考慮當(dāng)前點(diǎn)n到終點(diǎn)的估算耗費(fèi)距離。那么算法就會被轉(zhuǎn)換為經(jīng)典的Dijkstra算法，此時(shí)需要考慮所有位置的狀態(tài)。

②當(dāng)只計(jì)算h（n）時(shí)，即只計(jì)算和考慮當(dāng)前點(diǎn)n到終點(diǎn)的估算耗費(fèi)距離，不考慮起點(diǎn)到當(dāng)前點(diǎn)n的實(shí)際耗費(fèi)距離。那么算法就會被轉(zhuǎn)化為使用貪心策略的Best-First Search，速度最快，但是可能得不到實(shí)際最優(yōu)的解。

③如果估算距離不高于實(shí)際距離，即h（n）不高于g（n），那么算法則一定可以得到最優(yōu)解。常見的估算方法有：歐幾里得距離、曼哈頓距離以及切比雪夫距離。

（2）算法步驟

A*算法一般通過Open和Closed兩張表維護(hù)在搜索過程中擴(kuò)展得到的結(jié)點(diǎn)。將擴(kuò)展得到的且有效的結(jié)

A*算法是目前來說最有效的一種直接搜索算法，同時(shí)也是目前常用的一種啟發(fā)式搜索算法（Heuristically Search）。該算法由 Peter Hart、Nils Nilsson和 Bert ram Raphael三人于1968年在斯坦福研究院提出。A*算法是對Dijkstra算法的一個(gè)擴(kuò)展，同時(shí)也是一種高效的搜索算法。A*算法運(yùn)用非常廣泛，可以在游戲領(lǐng)域看到它的身影，如NPC移動計(jì)算。點(diǎn)置入Open表，將已經(jīng)搜索過的結(jié)點(diǎn)置入Closed表。具體算法可描述如下：

步驟1初始化Open表和Closed表；

步驟2將起點(diǎn)A加入到Open表，此時(shí)待搜索的結(jié)點(diǎn)只有一個(gè)，即起點(diǎn)A的估價(jià)值肯定為最優(yōu)值；

步驟3若Open表非空，則取出具有評估最優(yōu)值的結(jié)點(diǎn)，進(jìn)行下一步操作，否則跳轉(zhuǎn)至步驟8；

步驟4將具有評估最優(yōu)值的結(jié)點(diǎn)n取出，并將這個(gè)結(jié)點(diǎn)加入到Closed表中，如果結(jié)點(diǎn)n就是終點(diǎn)B或者就是最終狀態(tài)，那么跳轉(zhuǎn)至步驟8，否則進(jìn)行下一步操作；

步驟5對結(jié)點(diǎn)n進(jìn)行擴(kuò)展，即取與結(jié)點(diǎn)n相鄰且滿足未在Closed表中、非不可操作等條件的結(jié)點(diǎn)N1至Nt；

步驟6對結(jié)點(diǎn)N1至Nt進(jìn)行評估，即計(jì)算起點(diǎn)A到當(dāng)前結(jié)點(diǎn)的實(shí)際移動距離和當(dāng)前結(jié)點(diǎn)到終點(diǎn)B的估算距離之和；

步驟7將結(jié)點(diǎn)n作為N1至Nt的父結(jié)點(diǎn)，并將N1至Nt加入到Open表中，跳轉(zhuǎn)至步驟3；

步驟8根據(jù)父結(jié)點(diǎn)進(jìn)行回溯生成最短路徑，銷毀Open表和Closed表，程序結(jié)束。

圖2 A*算法運(yùn)行結(jié)果圖

（3）核心代碼

根據(jù)實(shí)際的需求選擇選擇下一步可以移動的位置，通常在2D游戲中下一步通常可以有八個(gè)可以移動的方向，當(dāng)然也可以設(shè)置只有四個(gè)可以移動的方向。同時(shí)根據(jù)障礙物，可以設(shè)置相應(yīng)的規(guī)則，如當(dāng)前結(jié)點(diǎn)的右鄰有障礙物時(shí)，規(guī)定當(dāng)前結(jié)點(diǎn)的右上、右、右下三個(gè)方向是不可行的。

3 雙向A＊算法

3.1 算法概述

通過對傳統(tǒng)A*算法進(jìn)行實(shí)現(xiàn)和分析，發(fā)現(xiàn)其實(shí)際運(yùn)行時(shí)間性能較差且存在一些缺點(diǎn)，很難滿足實(shí)際運(yùn)用的需求?？梢酝ㄟ^對其搜索方式進(jìn)行改進(jìn)和設(shè)計(jì)，使其滿足實(shí)際需求。與傳統(tǒng)A*算法不同的是，傳統(tǒng)A*算法使用的搜索方式為從起點(diǎn)一直搜索擴(kuò)展到終點(diǎn)為止，由在此過程中生成一條最短路徑。而雙向A*算法采取的搜索方式是從兩個(gè)方向同時(shí)進(jìn)行搜索，即一個(gè)從起點(diǎn)向終點(diǎn)擴(kuò)展，另一個(gè)從終點(diǎn)向起點(diǎn)擴(kuò)展。當(dāng)兩個(gè)搜索路線匯合到同一個(gè)位置時(shí)，就可以得到一條最短路徑。

3.2 算法思想

雙向A*算法的主要思想是：傳統(tǒng)A*算法的搜索結(jié)果會在圖上呈現(xiàn)為一個(gè)扇形展開的樹結(jié)構(gòu)。而一個(gè)大的搜索樹的搜索展開速度遠(yuǎn)遠(yuǎn)不如兩個(gè)較小的搜索樹，使用兩個(gè)較小的搜索樹在一定情況下可以加快算法的運(yùn)行速度。同時(shí)對傳統(tǒng)A*算法引入并行化設(shè)計(jì)，滿足時(shí)代發(fā)展要求，即符合如今多核計(jì)算機(jī)已經(jīng)非常普及的現(xiàn)狀。

在理想情況下，雙向A*算法的運(yùn)行速度相比于傳統(tǒng)A*算法的運(yùn)行速度將會提高一倍，理想運(yùn)行過程如圖3所示：

圖3 雙向A*算法理想情況下的運(yùn)行流程圖

（1）核心代碼

雙向A*算法通過開啟兩個(gè)線程執(zhí)行兩個(gè)不完全相同的搜索過程，即一個(gè)線程處理從起點(diǎn)到終點(diǎn)的搜索過程，另一個(gè)線程處理從終點(diǎn)到起點(diǎn)的搜索過程。當(dāng)兩個(gè)線程處理到同一個(gè)結(jié)點(diǎn)時(shí)，以此可以判定算法已經(jīng)找到一條最短路徑。

（2）雙向A*算法實(shí)際運(yùn)行情況

通過實(shí)際運(yùn)行對比，可以發(fā)現(xiàn)雙向A*算法的運(yùn)行速度在復(fù)雜路徑問題的求解中的運(yùn)行效率是高于傳統(tǒng)A*算法的。另外，傳統(tǒng)A*算法在求解復(fù)雜路徑問題是往往只能得到一個(gè)固定的解，而雙向A*算法在某些路徑問題的求解過程中可以得到實(shí)際存在的多個(gè)不同最優(yōu)解。

傳統(tǒng)A*算法和雙向A*算法在某個(gè)特定路徑問題中求解情況如下（小括號內(nèi)為算法運(yùn)行時(shí)間）：

圖4

4 其他改進(jìn)方法

4.1 定向搜索

在傳統(tǒng)A*算法的搜索過程，Open列表用于保存可能需要被擴(kuò)展的結(jié)點(diǎn)。定向搜索是在傳統(tǒng)A*算法的基礎(chǔ)上，通過限制Open列表的大小而得到一種改進(jìn)方法。這種改進(jìn)方法的好處是，當(dāng)Open列表太大時(shí)即待搜索的結(jié)點(diǎn)太多時(shí)，會將可能性最小的即評估值最低的節(jié)點(diǎn)排除，從而一定程度上減少了算法的搜索空間。但這種改進(jìn)方法會帶來一定的缺陷，即需要對Open列表進(jìn)行篩選所以對數(shù)據(jù)結(jié)構(gòu)的選擇增加了限制條件，同時(shí)這種改進(jìn)方法可能會得到不到最優(yōu)解，即無法找到實(shí)際最短路徑。

4.2 動態(tài)加權(quán)

該改進(jìn)方法假定需要在搜索開始時(shí)快速達(dá)到某個(gè)狀態(tài)或位置。通過一個(gè)權(quán)值w（w＞=1）和估算函數(shù)相關(guān)聯(lián)。在不斷接近終點(diǎn)時(shí)，權(quán)重w的值也不斷減少，通過這種改進(jìn)方法可以降低在對某個(gè)狀態(tài)評估時(shí)估算函數(shù)的重要性，提高實(shí)際花費(fèi)代價(jià)的重要性。算法的思想為搜索前期以搜索速度為重點(diǎn)，搜索后期重點(diǎn)考慮搜索正確率。

4.3 雙向搜索變體

為了繼續(xù)對雙向A*算法的性能等方面進(jìn)行優(yōu)化和改進(jìn)，眾多文獻(xiàn)討論了不同的方法。

重定向方法不同于一般雙向搜索算法，這種方法放棄了完整的前向搜索或者后向搜索，首先從起點(diǎn)開始進(jìn)行一次短暫的前向搜索并選取一個(gè)最佳的前向候選結(jié)點(diǎn)。然后進(jìn)行后向搜索，不同于完整的后向搜索。此次后向搜索的起始結(jié)點(diǎn)為終點(diǎn)，目標(biāo)點(diǎn)為上一步選擇的前向候選結(jié)點(diǎn)，這個(gè)搜索過程也不是完整的，同樣也可以得到一個(gè)最佳的后向候選結(jié)點(diǎn)。接著從前向候選結(jié)點(diǎn)向后向搜索結(jié)點(diǎn)繼續(xù)進(jìn)行擴(kuò)展，重復(fù)這個(gè)過程，直到前向搜索結(jié)點(diǎn)與后向搜索結(jié)點(diǎn)匯合。

面對面方法通過將前向搜索的結(jié)果和后向搜索的結(jié)果整合在一起。即評估函數(shù)滿足以下公式：

5 結(jié)語

A*算法是廣泛應(yīng)用在圖論、人工智能、智能控制領(lǐng)域的一種啟發(fā)式搜索算法。但是由于在很多情況下它的搜索狀態(tài)空間非常龐大從而導(dǎo)致其運(yùn)行及搜索效率不高，所以傳統(tǒng)的A*算法并不能在實(shí)際生活和工作中得到有效的應(yīng)用。通過對A*算法引入并行化技術(shù)，可以有效減少其運(yùn)行時(shí)間。目前有很多文獻(xiàn)對A*算法的優(yōu)化提出了解決方案，這些方案也成功運(yùn)用在各個(gè)領(lǐng)域，改進(jìn)后的A*算法可以更好地解決在工作和生活中遇到的路徑問題。