徐唐劍

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

0 引言

啟發(fā)式搜索算法是一種在人工智能等領(lǐng)域中常用的方法。對(duì)于人工智能系統(tǒng)來(lái)說(shuō)，問(wèn)題可能的狀態(tài)隨著搜索的深入呈現(xiàn)指數(shù)遞增或者階乘遞增，啟發(fā)式搜索通過(guò)模擬人腦的認(rèn)知模式，對(duì)部分可能的狀態(tài)而不是每個(gè)可能的狀態(tài)進(jìn)行權(quán)衡，找到一個(gè)或幾個(gè)可能性最大的路徑排除其他可能性較小或?yàn)榱愕穆窂剑档退惴◤?fù)雜性。具體的搜索方法就是在搜索過(guò)程中不斷評(píng)估狀態(tài)空間中的每一個(gè)狀態(tài)，根據(jù)其評(píng)估值有選擇性地得到相對(duì)最優(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ì)算過(guò)程，在這個(gè)計(jì)算過(guò)程中取一個(gè)值或者值的集合作為程序的輸入并產(chǎn)生一個(gè)值或者值的集合作為程序的輸出。同時(shí)為了更好地解決在生活、工作中遇到的某些問(wèn)題，有些時(shí)候需要對(duì)所設(shè)計(jì)的算法做出優(yōu)化，如時(shí)間復(fù)雜度、空間復(fù)雜度、正確性和健壯性等方面。而為了讓計(jì)算機(jī)每秒執(zhí)行更多的計(jì)算，計(jì)算機(jī)芯片通常被設(shè)計(jì)成具有多個(gè)處理“核”，可以把這些多核計(jì)算機(jī)當(dāng)做工作在某一芯片上的幾臺(tái)計(jì)算機(jī)，即“并行計(jì)算機(jī)”。隨著多核處理器的普及，為了使多核計(jì)算機(jī)獲得最佳的性能的同時(shí)提高程序的運(yùn)行速度，在設(shè)計(jì)算法時(shí)必須考慮算法的并行性。

1 Dijkstra算法

1.1 算法概述

Dijkstra算法是在1959年的時(shí)候由荷蘭的科學(xué)家Edsger Wybe Dijkstra提出，它能夠有效解決單源最短路徑問(wèn)題，該算法要求有向圖中邊的權(quán)重都為非負(fù)。算法的主要特點(diǎn)是從起點(diǎn)開(kāi)始不斷向外搜索和擴(kuò)展，直至達(dá)到目標(biāo)為止，同時(shí)在擴(kuò)展的過(guò)程中通過(guò)“松弛”操作不斷更新shortest值和pred值，最后在結(jié)果中可以得到起點(diǎn)到圖中其他所有結(jié)點(diǎn)的最短路徑及其權(quán)重和。通過(guò)簡(jiǎ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，然后對(duì)所有與該結(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)解，但是可以通過(guò)一些定理和推論可以證明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算法通過(guò)重復(fù)對(duì)具有最小shortest值的結(jié)點(diǎn)相關(guān)聯(lián)的每條邊執(zhí)行松弛操作來(lái)工作。首先，需要將有向圖中所有結(jié)點(diǎn)加入結(jié)點(diǎn)集Q，然后還需要唯一確定一個(gè)源點(diǎn)s，并將shortest[s]的值初始化為0，對(duì)于圖中其他所有頂點(diǎn)v的shortest[v]值設(shè)為無(wú)窮大，對(duì)所有結(jié)點(diǎn)的pred[v]值將其設(shè)為NULL，算法不斷從結(jié)點(diǎn)集Q中選取具有shortest最小值的結(jié)點(diǎn)u，并將該結(jié)點(diǎn)從結(jié)點(diǎn)集Q中移除，再對(duì)所有與結(jié)點(diǎn)u相關(guān)的邊執(zhí)行松弛操作。

程序DIJKSTRA（G,s）

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

結(jié)果：對(duì)于有向圖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)。對(duì)于源點(diǎn)，將其shortest[s]的值置為0,pred[s]的值置為NULL。規(guī)定如果從源點(diǎn)s與結(jié)點(diǎn)v不存在路徑，那么shortest[v]的值是無(wú)窮大，而pred[v]的值是NULL。

①初始化。將除起點(diǎn)s以外的任何結(jié)點(diǎn)v的shortest[v]值設(shè)為無(wú)窮大，其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ì)語(yǔ)言，于1989年由Guido van Rossum發(fā)明。Python具有豐富庫(kù)而且這些庫(kù)的功能強(qiáng)大，由于它可以與其他語(yǔ)言很好的合作所以常被稱為“膠水語(yǔ)言”。近些年來(lái)，尤其是人工智能逐漸成為人們關(guān)注的重點(diǎn)，而其首選編程語(yǔ)言就是Python。其次Python在網(wǎng)絡(luò)爬蟲(chóng)方面的運(yùn)用也是非常廣泛的，加上其“優(yōu)雅”、“明確”、“簡(jiǎn)單”的設(shè)計(jì)特點(diǎn)，Python得到了大多數(shù)人的青睞。Python于2017年7月在IEEE發(fā)布的編程語(yǔ)言排行版位居首位。為了適應(yīng)互聯(lián)網(wǎng)時(shí)代發(fā)展的要求，本文使用了Python作為算法實(shí)現(xiàn)的主要編程語(yǔ)言，以下是Dijkstra算法實(shí)現(xiàn)的核心代碼：

2 A＊算法

2.1 算法概述

2.2 算法思想

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

g（n）表示從起點(diǎn)到當(dāng)前點(diǎn)n的實(shí)際移動(dòng)距離，即從起點(diǎn)移動(dòng)到當(dāng)前點(diǎn)n所花費(fèi)的移動(dòng)代價(jià)。h（n）表示從當(dāng)前點(diǎn)n到終點(diǎn)或目標(biāo)點(diǎn)的估算距離，即對(duì)當(dāng)前點(diǎn)n移動(dòng)到終點(diǎn)的估算移動(dòng)代價(jià)。通過(guò)比較評(píng)估函數(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)距離。那么算法就會(huì)被轉(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)距離。那么算法就會(huì)被轉(zhuǎn)化為使用貪心策略的Best-First Search，速度最快，但是可能得不到實(shí)際最優(yōu)的解。

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

（2）算法步驟

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

A*算法是目前來(lái)說(shuō)最有效的一種直接搜索算法，同時(shí)也是目前常用的一種啟發(fā)式搜索算法（Heuristically Search）。該算法由 Peter Hart、Nils Nilsson和 Bert ram Raphael三人于1968年在斯坦福研究院提出。A*算法是對(duì)Dijkstra算法的一個(gè)擴(kuò)展，同時(shí)也是一種高效的搜索算法。A*算法運(yùn)用非常廣泛，可以在游戲領(lǐng)域看到它的身影，如NPC移動(dòng)計(jì)算。點(diǎn)置入Open表，將已經(jīng)搜索過(guò)的結(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表非空，則取出具有評(píng)估最優(yōu)值的結(jié)點(diǎn)，進(jìn)行下一步操作，否則跳轉(zhuǎn)至步驟8；

步驟4將具有評(píng)估最優(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對(duì)結(jié)點(diǎn)n進(jìn)行擴(kuò)展，即取與結(jié)點(diǎn)n相鄰且滿足未在Closed表中、非不可操作等條件的結(jié)點(diǎn)N1至Nt；

步驟6對(duì)結(jié)點(diǎn)N1至Nt進(jìn)行評(píng)估，即計(jì)算起點(diǎn)A到當(dāng)前結(jié)點(diǎn)的實(shí)際移動(dòng)距離和當(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í)際的需求選擇選擇下一步可以移動(dòng)的位置，通常在2D游戲中下一步通常可以有八個(gè)可以移動(dòng)的方向，當(dāng)然也可以設(shè)置只有四個(gè)可以移動(dòng)的方向。同時(shí)根據(jù)障礙物，可以設(shè)置相應(yīng)的規(guī)則，如當(dāng)前結(jié)點(diǎn)的右鄰有障礙物時(shí)，規(guī)定當(dāng)前結(jié)點(diǎn)的右上、右、右下三個(gè)方向是不可行的。

3 雙向A＊算法

3.1 算法概述

通過(guò)對(duì)傳統(tǒng)A*算法進(jìn)行實(shí)現(xiàn)和分析，發(fā)現(xiàn)其實(shí)際運(yùn)行時(shí)間性能較差且存在一些缺點(diǎn)，很難滿足實(shí)際運(yùn)用的需求?？梢酝ㄟ^(guò)對(duì)其搜索方式進(jìn)行改進(jìn)和設(shè)計(jì)，使其滿足實(shí)際需求。與傳統(tǒng)A*算法不同的是，傳統(tǒng)A*算法使用的搜索方式為從起點(diǎn)一直搜索擴(kuò)展到終點(diǎn)為止，由在此過(guò)程中生成一條最短路徑。而雙向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é)果會(huì)在圖上呈現(xiàn)為一個(gè)扇形展開(kāi)的樹(shù)結(jié)構(gòu)。而一個(gè)大的搜索樹(shù)的搜索展開(kāi)速度遠(yuǎn)遠(yuǎn)不如兩個(gè)較小的搜索樹(shù)，使用兩個(gè)較小的搜索樹(shù)在一定情況下可以加快算法的運(yùn)行速度。同時(shí)對(duì)傳統(tǒng)A*算法引入并行化設(shè)計(jì)，滿足時(shí)代發(fā)展要求，即符合如今多核計(jì)算機(jī)已經(jīng)非常普及的現(xiàn)狀。

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

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

（1）核心代碼

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

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

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

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

圖4

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

4.1 定向搜索

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

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

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

4.3 雙向搜索變體

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

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

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

5 結(jié)語(yǔ)

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