李鵬 周海 閔慧

摘要：啟發(fā)式搜索（Heuristic Search，HS）是目前解決人工智能領域諸多問題的重要手段之一，在啟發(fā)式搜索質(zhì)量和效率評價相關定義的基礎上，對目前幾種典型啟發(fā)式搜索算法原理進行分析，指出其優(yōu)點及不足，并以人機大戰(zhàn)為例提出啟發(fā)式搜索的應用價值及未來研究方向。

關鍵詞：人工智能;啟發(fā)式搜索;評估函數(shù);可接受啟發(fā);At算法

DOI：10.11907/rjdk.191017 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP301文獻標識碼：A 文章編號：1672-7800（2020）006-0035-04

0 引言

人工智能誕生于20世紀中期，曾經(jīng)歷兩起兩落的重要歷程。人工智能技術作為21世紀最前沿技術之一，其重大突破必將影響新一輪產(chǎn)業(yè)革命，目前它已在醫(yī)學、教育、研究等領域得到了深遠應用。

目前，人工智能面臨的問題越來越復雜，其中以非結(jié)構(gòu)化問題居多，以往盲目搜索需要搜索所有節(jié)點消耗了大量時間，這種弊病將會嚴重限制搜索能力，究其原因在于顧及了所有可能性，即一個一個盲目搜索。針對該問題，人們需要運用有知識的生成器避免走一些明顯不可能搜索到正確答案的路徑，即啟發(fā)式搜索。啟發(fā)式搜索已成為實際中求解智能規(guī)劃問題的重要工具，特別是不確定性規(guī)劃問題。近年來，放松規(guī)劃在圖規(guī)劃問題中的探究、基于單值變量的啟發(fā)式研究等均推動著對啟發(fā)式搜索的探索。用啟發(fā)式搜索思維構(gòu)建問題解成為一種常用的思考方式，比如最大權獨立集問題、普遍共享騎行問題等。啟發(fā)式搜索結(jié)合模糊邏輯、頻譜頻率分配等領域技術更是加快了眾多領域搜索發(fā)展的進程。歸根究底，人們還是希望搜索路徑沿著自己認為有希望的方向前進，這樣就可以大大減少搜索時間。本文首先追溯研究起點，再從源頭到人機大戰(zhàn)應用對啟發(fā)式搜索及其啟發(fā)能力等進行探討。

1 問題描述

啟發(fā)式搜索，簡而言之，即一種運用啟發(fā)先驗知識或者信息引導搜索方向的方法。為了評價啟發(fā)式搜索的質(zhì)量和效率，文中給出如下幾個定義：

定義1搜索代價函數(shù)

F（p）=C（p）+H（p）

指算法在一次啟發(fā)式搜索過程中，從搜索起點S（Start.point）到達目標點D（Destination）所耗費的代價（如距離等）。其中，G（p）表示從S出發(fā)到達某一中間節(jié)點p（point）的代價;H（p）表示某一中間節(jié)點p到達D的代價。

其中，當搜索已在節(jié)點p時，需要決定接下來的搜索路徑，然而當前節(jié)點不知道接下來路徑的真實值H（p），于是需要評估得到H*（p）。如果H*（p）的值與真實值存在較大偏差，可能引導節(jié)點向相對錯誤的方向搜索。于是給出如下定義：

定義2可被接受的啟發(fā)搜索

在上述定義l中，對于所有可能經(jīng)過的節(jié)點p，如果滿足G（p）>0，H*（p）≤H（p），即中間任意一點p到S點的距離大于零，中間任意一點p到達D點的距離評估值H*（p）不大于真實值，則認為H*（p）是可以被接受的估計值，并稱滿足這種條件的啟發(fā)搜索是可以被接受的啟發(fā)搜索。

然而僅僅依據(jù)定義2的條件判定的啟發(fā)式搜索并不一定最優(yōu)，因為從S點出發(fā)前往某個未知p點的距離也同樣需要估計。由此繼續(xù)給出如下定義：

定義3搜索算法單調(diào)

在滿足定義2情況下，如果對于任意節(jié)點p，滿足G（p）的估計值C*（p）小于G（p），即從搜索起點S到節(jié)點p的路徑是最優(yōu)路徑，稱滿足上述所有條件的搜索算法是單調(diào)的。

算法單調(diào)雖然是理想目標，但是現(xiàn)實問題中一般較難達到這樣苛刻的條件。以下圍繞搜索代價函數(shù)闡述幾種不同的啟發(fā)式搜索算法。

2 啟發(fā)式搜索算法

2.1分支定界法

首先討論一種特殊且簡單的情況。當H*（p）=H（p）=0，即F（p）=G（p），這就是簡單的分支定界法滿足的條件。這種方法每次都會優(yōu)先選擇當前距離最短的路徑前進，以最少距離為目標進行節(jié)點擴展。這種方法也會拋棄一些不可能得到最優(yōu)解的節(jié)點，以此達到縮短搜索路徑距離的目標。

如圖1所示，（a）是待搜索的二叉樹，（b）表示從起始節(jié)點A開始搜索，沒有達到目的地，繼續(xù)往下搜索，擴展A節(jié)點得到B和C。圖1（c）發(fā)現(xiàn)往B方向路徑距離短，并且沒有達到目的地，繼續(xù)擴展B節(jié)點搜索得到D和E。同理繼續(xù)擴展到達圖l（e），此時已經(jīng)搜索到了一條到達目的地的路徑，其距離為16。因為還可能存在其它路徑的距離比16更小，于是繼續(xù)擴展當前距離花費最小的C點（相等花費條件下遵守從右邊開始擴展的規(guī)則）。直到距離可能比16小的所有路徑搜索完為止，如圖1（f），最終找出距離最短的路徑。

簡單的分支定界法固然滿足定義2中啟發(fā)搜索是可接受的條件，但是實際情況中H*（p）往往會有很多變化，更不可能固定為零，因此該方法顯然存在較大的局限性。

2.2 兩種分支定界法改進方法

2.2.1 使用低估值的分支定界法

易知上述簡單純粹的分支定界法對H（p）處理上存在缺陷，故采用對H（p）低估值的方法改進分支定界法，即H*（p）=underestimate（H（p））。顯然，這種啟發(fā)也是可以被接受的，同時比沒有啟發(fā)搜索能力的分支定界更強。

如圖2所示，設矩形內(nèi)的值表示該節(jié)點到目的地Goal的低估計值。從根節(jié)點開始，發(fā)現(xiàn)不是目標節(jié)點，則擴展該根節(jié)點，如圖2（c）所示，得到兩個評估函數(shù)的值20（6+14）、23（15+8），選擇較小者繼續(xù)擴展，直到找到了一條到達目標節(jié)點的路徑，如圖2（e）所示，之后繼續(xù)搜索其它距離可能更短的路徑，如圖2（f）所示，搜索完所有可能達到最短路徑的節(jié)點。

采用低估值的方法有效提高了搜索質(zhì)量，更加符合實際情況，但是就其搜索速度而論并沒有明顯改觀。

2.2.2 基于最短路徑的分支定界法

由現(xiàn)實生活經(jīng)驗可知，如果兩條或多條路徑到達同一節(jié)點，只需要存儲距離消費最小的那條路徑的距離即可。通過一個抽象處理后的實例對原理加以說明。若要求從S點城市前往D點城市，以下說明存儲最短路徑的分支定界法，如圖3（a）-圖3（f）所示。

從S點出發(fā)，面臨A、C兩點選擇，由于C點距離更短則選擇C點，如圖3（c）所示。到達C點后只能前往B點，此時距離S點距離為2，如圖3（d）。同理繼續(xù)前往正點，如圖3（e），此時距離S點距離為4。接下來擴展距離比4更小的路徑，即S→A→B（其實還有另一種走法S→A→C，基于后經(jīng)過優(yōu)先級更高的原則選擇B點），此段距離到達B時距離S點為3，此時是第二次訪問B點，于是依據(jù)最短路徑原則選擇到達B點最短的距離2，即保證存儲了最短路徑S→A→B。

這類似于動態(tài)規(guī)劃，要記錄下已經(jīng)訪問的節(jié)點，下次繼續(xù)訪問相同節(jié)點時，只需要在已經(jīng)被訪問的節(jié)點中查找到達某點的最小花費取出來使用即可。雖然這種方法僅僅對到達同一節(jié)點的情況進行了優(yōu)化，但也已在許多相關路徑問題解決中見到它的縮影，如快遞物流優(yōu)選路徑問題、城市路徑規(guī)劃問題等。

3 A*算法

上文對簡單的分支定界法提出了兩種優(yōu)化策略，如果將兩者優(yōu)點結(jié)合起來就是A*算法。下面將用經(jīng)典的三數(shù)碼問題說明A*算法，假設采用的低估值為曼哈頓距離，其中用到的算子（簡單理解，算子就是每一步的操作，具體一點也可理解為每一步的步驟）是空格上下左右4種方向的移動，具體實例如圖4所示。

在圖4中，標注有*號的三數(shù)碼塊F（p）=2+4=6的原因說明：*號三數(shù)碼塊距離起點完成了兩個算子操作，由此G（p）=2;與Goal相比，數(shù)字l至少向下移動1步可以到達Goal，同理數(shù)字2、3分別是2步和l步，因此步數(shù)相加為4步，即H*（p）=4。另外，*號數(shù)碼塊與起點數(shù)碼塊狀態(tài)相同，因此通過比較存儲最短距離對路徑進行優(yōu)化。

由此還可以觀察到，用曼哈頓距離作為搜索低估值時，有時收斂會更加快速。其實，空格的上下左右移動類似于走彎彎折折似正方胡同的小巷，因此曼哈頓路徑又稱為出租車路徑。盡管A*算法已然是啟發(fā)搜索能力較強的一種方法，但是在面對多條最小路徑選擇時有時也會存在因為搜索范圍過大而導致搜索時間過長的缺點。

4 蒙特卡洛樹搜索

人和機器在圍棋中的較量比拼已是試驗機器的試金石，其中核心部分便是蒙特卡洛樹搜索。該搜索建立于二人零和博弈基礎上，其搜索基礎是最大最小搜索。最大最小搜索的中心思想是輪到我方搜索擴展時選擇最有利于我方的擴展;輪到對方搜索擴展時選擇最不利于我方的擴展。最大最小搜索有兩大明顯缺點：①搜索樹寬度太廣，導致該樹非?！芭帧?②搜索樹深度太深，導致該樹非常長。

蒙特卡洛樹搜索便是一種解決這兩個問題的有效方法。蒙特卡洛樹中每個節(jié)點表示一種棋面，其搜索步驟如下：

（1）選擇。從某點s向下擴展，根據(jù)啟發(fā)函數(shù)選擇進入s的某一子節(jié)點si。啟發(fā)函數(shù)：

（2）擴展。選擇啟發(fā)函數(shù)最大值的點si_max擴展。

（3）模擬。從si_max開始模擬接下來的輸出，一直到零和博弈結(jié)束為止。

（4）回溯。也稱反向傳播，用模擬的結(jié)果更新節(jié)點參數(shù)信息。

以上4個步驟反復迭代，一直到結(jié)束。列舉一次簡單的迭代過程，如圖5（a）-圖5（d）所示，圓內(nèi)A/B表示O（s）。

通過計算啟發(fā)函數(shù)選擇擴展O為3/3節(jié)點如圖5（a），然后通過模擬更新沿路經(jīng)過的所有節(jié)點的值，即沿路反向傳播的節(jié)點模擬次數(shù)加1，結(jié)果如圖5（d）所示。

蒙特卡洛樹搜索所用的啟發(fā)知識不是固定的先驗知識，而是通過搜索過程中模擬反向傳播得到的帶有概率的知識，具有及時性特征，非常符合圍棋這一類多可能性且實時的特征，然而對于搜索樹不是非常龐大的情況，比如象棋路徑搜索，其效果就不如圍棋好。

5 結(jié)語

啟發(fā)式搜索已在眾多領域得到了落實，比如路徑規(guī)劃、智能機器人等，但是在今后智能規(guī)劃等任務中，仍然需要理論和實踐的創(chuàng)新突破，例如更加精確的搜索代價函數(shù)、機器及時對當前現(xiàn)狀進行動態(tài)更新的啟發(fā)能力、盡量減少時間或空間消耗等?？梢灶A見，有了更加高效且相對低成本的搜索策略，將對許多領域起到巨大推動作用。