李鵬 周海 閔慧

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

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

DOI：10.11907/rjdk.191017 開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類(lèi)號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2020）006-0035-04

0 引言

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

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

1 問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

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

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

2.1分支定界法

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

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

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

2.2 兩種分支定界法改進(jìn)方法

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

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

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

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

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

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

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

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

3 A*算法

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

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

由此還可以觀察到，用曼哈頓距離作為搜索低估值時(shí)，有時(shí)收斂會(huì)更加快速。其實(shí)，空格的上下左右移動(dòng)類(lèi)似于走彎彎折折似正方胡同的小巷，因此曼哈頓路徑又稱(chēng)為出租車(chē)路徑。盡管A*算法已然是啟發(fā)搜索能力較強(qiáng)的一種方法，但是在面對(duì)多條最小路徑選擇時(shí)有時(shí)也會(huì)存在因?yàn)樗阉鞣秶^(guò)大而導(dǎo)致搜索時(shí)間過(guò)長(zhǎng)的缺點(diǎn)。

4 蒙特卡洛樹(shù)搜索

人和機(jī)器在圍棋中的較量比拼已是試驗(yàn)機(jī)器的試金石，其中核心部分便是蒙特卡洛樹(shù)搜索。該搜索建立于二人零和博弈基礎(chǔ)上，其搜索基礎(chǔ)是最大最小搜索。最大最小搜索的中心思想是輪到我方搜索擴(kuò)展時(shí)選擇最有利于我方的擴(kuò)展;輪到對(duì)方搜索擴(kuò)展時(shí)選擇最不利于我方的擴(kuò)展。最大最小搜索有兩大明顯缺點(diǎn)：①搜索樹(shù)寬度太廣，導(dǎo)致該樹(shù)非?！芭帧?②搜索樹(shù)深度太深，導(dǎo)致該樹(shù)非常長(zhǎng)。

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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