人工智能中啟發式搜索研究綜述
「啟發式搜索（Heuristic Search，HS）是目前解決人工智能領域諸多問題的重要手段之一，在啟發式搜索質量和效率評價相關定義的基礎上，對目前幾種典型啟發式搜索算法原理進行分析，指出其優點及不足，并以人機大戰為例提出啟發式搜索的應用價值及未來研究方向。(2023-2-25)」
關鍵詞：人工智能;啟發式搜索;評估函數;可接受啟發;At算法
DOI：10.11907/rjdk.191017 開放科學（資源服務）標識碼（OSID）：
中圖分類號：TP301文獻標識碼：A 文章編號：1672-7800（2020）006-0035-04
0 引言
人工智能誕生于20世紀中期，曾經歷兩起兩落的重要歷程。人工智能技術作為21世紀最前沿技術之一，其重大突破必將影響新一輪產業革命，目前它已在醫學、教育、研究等領域得到了深遠應用。
目前，人工智能面臨的問題越來越復雜，其中以非結構化問題居多，以往盲目搜索需要搜索所有節點消耗了大量時間，這種弊病將會嚴重限制搜索能力，究其原因在于顧及了所有可能性，即一個一個盲目搜索。針對該問題，人們需要運用有知識的生成器避免走一些明顯不可能搜索到正確答案的路徑，即啟發式搜索。啟發式搜索已成為實際中求解智能規劃問題的重要工具，特別是不確定性規劃問題。近年來，放松規劃在圖規劃問題中的探究、基于單值變量的啟發式研究等均推動著對啟發式搜索的探索。用啟發式搜索思維構建問題解成為一種常用的思考方式，比如最大權獨立集問題、普遍共享騎行問題等。啟發式搜索結合模糊邏輯、頻譜頻率分配等領域技術更是加快了眾多領域搜索發展的進程。歸根究底，人們還是希望搜索路徑沿著自己認為有希望的方向前進，這樣就可以大大減少搜索時間。本文首先追溯研究起點，再從源頭到人機大戰應用對啟發式搜索及其啟發能力等進行探討。
1 問題描述
啟發式搜索，簡而言之，即一種運用啟發先驗知識或者信息引導搜索方向的方法。為了評價啟發式搜索的質量和效率，文中給出如下幾個定義：
定義1搜索代價函數
F（p）=C（p）+H（p）
指算法在一次啟發式搜索過程中，從搜索起點S（Start.point）到達目標點D（Destination）所耗費的代價（如距離等）。其中，G（p）表示從S出發到達某一中間節點p（point）的代價;H（p）表示某一中間節點p到達D的代價。
其中，當搜索已在節點p時，需要決定接下來的搜索路徑，然而當前節點不知道接下來路徑的真實值H（p），于是需要評估得到H*（p）。如果H*（p）的值與真實值存在較大偏差，可能引導節點向相對錯誤的方向搜索。于是給出如下定義：
定義2可被接受的啟發搜索
在上述定義l中，對于所有可能經過的節點p，如果滿足G（p）>0，H*（p）≤H（p），即中間任意一點p到S點的距離大于零，中間任意一點p到達D點的距離評估值H*（p）不大于真實值，則認為H*（p）是可以被接受的估計值，并稱滿足這種條件的啟發搜索是可以被接受的啟發搜索。
然而僅僅依據定義2的條件判定的啟發式搜索并不一定最優，因為從S點出發前往某個未知p點的距離也同樣需要估計。由此繼續給出如下定義：
定義3搜索算法單調
在滿足定義2情況下，如果對于任意節點p，滿足G（p）的估計值C*（p）小于G（p），即從搜索起點S到節點p的路徑是最優路徑，稱滿足上述所有條件的搜索算法是單調的。
算法單調雖然是理想目標，但是現實問題中一般較難達到這樣苛刻的條件。以下圍繞搜索代價函數闡述幾種不同的啟發式搜索算法。
2 啟發式搜索算法
2.1分支定界法
首先討論一種特殊且簡單的情況。當H*（p）=H（p）=0，即F（p）=G（p），這就是簡單的分支定界法滿足的條件。這種方法每次都會優先選擇當前距離最短的路徑前進，以最少距離為目標進行節點擴展。這種方法也會拋棄一些不可能得到最優解的節點，以此達到縮短搜索路徑距離的目標。
如圖1所示，（a）是待搜索的二叉樹，（b）表示從起始節點A開始搜索，沒有達到目的地，繼續往下搜索，擴展A節點得到B和C。圖1（c）發現往B方向路徑距離短，并且沒有達到目的地，繼續擴展B節點搜索得到D和E。同理繼續擴展到達圖l（e），此時已經搜索到了一條到達目的地的路徑，其距離為16。因為還可能存在其它路徑的距離比16更小，于是繼續擴展當前距離花費最小的C點（相等花費條件下遵守從右邊開始擴展的規則）。直到距離可能比16小的所有路徑搜索完為止，如圖1（f），最終找出距離最短的路徑。
簡單的分支定界法固然滿足定義2中啟發搜索是可接受的條件，但是實際情況中H*（p）往往會有很多變化，更不可能固定為零，因此該方法顯然存在較大的局限性。
2.2 兩種分支定界法改進方法
2.2.1 使用低估值的分支定界法
易知上述簡單純粹的分支定界法對H（p）處理上存在缺陷，故采用對H（p）低估值的方法改進分支定界法，即H*（p）=underestimate（H（p））。顯然，這種啟發也是可以被接受的，同時比沒有啟發搜索能力的分支定界更強。
如圖2所示，設矩形內的值表示該節點到目的地Goal的低估計值。從根節點開始，發現不是目標節點，則擴展該根節點，如圖2（c）所示，得到兩個評估函數的值20（6+14）、23（15+8），選擇較小者繼續擴展，直到找到了一條到達目標節點的路徑，如圖2（e）所示，之后繼續搜索其它距離可能更短的路徑，如圖2（f）所示，搜索完所有可能達到最短路徑的節點。
采用低估值的方法有效提高了搜索質量，更加符合實際情況，但是就其搜索速度而論并沒有明顯改觀。 2.2.2 基于最短路徑的分支定界法
由現實生活經驗可知，如果兩條或多條路徑到達同一節點，只需要存儲距離消費最小的那條路徑的距離即可。通過一個抽象處理后的實例對原理加以說明。若要求從S點城市前往D點城市，以下說明存儲最短路徑的分支定界法，如圖3（a）-圖3（f）所示。
從S點出發，面臨A、C兩點選擇，由于C點距離更短則選擇C點，如圖3（c）所示。到達C點后只能前往B點，此時距離S點距離為2，如圖3（d）。同理繼續前往正點，如圖3（e），此時距離S點距離為4。接下來擴展距離比4更小的路徑，即S→A→B（其實還有另一種走法S→A→C，基于后經過優先級更高的原則選擇B點），此段距離到達B時距離S點為3，此時是第二次訪問B點，于是依據最短路徑原則選擇到達B點最短的距離2，即保證存儲了最短路徑S→A→B。
這類似于動態規劃，要記錄下已經訪問的節點，下次繼續訪問相同節點時，只需要在已經被訪問的節點中查找到達某點的最小花費取出來使用即可。雖然這種方法僅僅對到達同一節點的情況進行了優化，但也已在許多相關路徑問題解決中見到它的縮影，如快遞物流優選路徑問題、城市路徑規劃問題等。
3 A*算法
上文對簡單的分支定界法提出了兩種優化策略，如果將兩者優點結合起來就是A*算法。下面將用經典的三數碼問題說明A*算法，假設采用的低估值為曼哈頓距離，其中用到的算子（簡單理解，算子就是每一步的操作，具體一點也可理解為每一步的步驟）是空格上下左右4種方向的移動，具體實例如圖4所示。
在圖4中，標注有*號的三數碼塊F（p）=2+4=6的原因說明：*號三數碼塊距離起點完成了兩個算子操作，由此G（p）=2;與Goal相比，數字l至少向下移動1步可以到達Goal，同理數字2、3分別是2步和l步，因此步數相加為4步，即H*（p）=4。另外，*號數碼塊與起點數碼塊狀態相同，因此通過比較存儲最短距離對路徑進行優化。
由此還可以觀察到，用曼哈頓距離作為搜索低估值時，有時收斂會更加快速。其實，空格的上下左右移動類似于走彎彎折折似正方胡同的小巷，因此曼哈頓路徑又稱為出租車路徑。盡管A*算法已然是啟發搜索能力較強的一種方法，但是在面對多條最小路徑選擇時有時也會存在因為搜索范圍過大而導致搜索時間過長的缺點。
4 蒙特卡洛樹搜索
人和機器在圍棋中的較量比拼已是試驗機器的試金石，其中核心部分便是蒙特卡洛樹搜索。該搜索建立于二人零和博弈基礎上，其搜索基礎是最大最小搜索。最大最小搜索的中心思想是輪到我方搜索擴展時選擇最有利于我方的擴展;輪到對方搜索擴展時選擇最不利于我方的擴展。最大最小搜索有兩大明顯缺點：①搜索樹寬度太廣，導致該樹非�！芭帧�;②搜索樹深度太深，導致該樹非常長。
蒙特卡洛樹搜索便是一種解決這兩個問題的有效方法。蒙特卡洛樹中每個節點表示一種棋面，其搜索步驟如下：
�。�1）選擇。從某點s向下擴展，根據啟發函數選擇進入s的某一子節點si。啟發函數：
�。�2）擴展。選擇啟發函數最大值的點simax擴展。
�。�3）模擬。從simax開始模擬接下來的輸出，一直到零和博弈結束為止。
�。�4）回溯。也稱反向傳播，用模擬的結果更新節點參數信息。
以上4個步驟反復迭代，一直到結束。列舉一次簡單的迭代過程，如圖5（a）-圖5（d）所示，圓內A/B表示O（s）。
通過計算啟發函數選擇擴展O為3/3節點如圖5（a），然后通過模擬更新沿路經過的所有節點的值，即沿路反向傳播的節點模擬次數加1，結果如圖5（d）所示。
蒙特卡洛樹搜索所用的啟發知識不是固定的先驗知識，而是通過搜索過程中模擬反向傳播得到的帶有概率的知識，具有及時性特征，非常符合圍棋這一類多可能性且實時的特征，然而對于搜索樹不是非常龐大的情況，比如象棋路徑搜索，其效果就不如圍棋好。
5 結語
啟發式搜索已在眾多領域得到了落實，比如路徑規劃、智能機器人等，但是在今后智能規劃等任務中，仍然需要理論和實踐的創新突破，例如更加精確的搜索代價函數、機器及時對當前現狀進行動態更新的啟發能力、盡量減少時間或空間消耗等�？梢灶A見，有了更加高效且相對低成本的搜索策略，將對許多領域起到巨大推動作用。
(受腔)
DOI：10.11907/rjdk.191017 開放科學（資源服務）標識碼（OSID）：
中圖分類號：TP301文獻標識碼：A 文章編號：1672-7800（2020）006-0035-04
0 引言
人工智能誕生于20世紀中期，曾經歷兩起兩落的重要歷程。人工智能技術作為21世紀最前沿技術之一，其重大突破必將影響新一輪產業革命，目前它已在醫學、教育、研究等領域得到了深遠應用。
目前，人工智能面臨的問題越來越復雜，其中以非結構化問題居多，以往盲目搜索需要搜索所有節點消耗了大量時間，這種弊病將會嚴重限制搜索能力，究其原因在于顧及了所有可能性，即一個一個盲目搜索。針對該問題，人們需要運用有知識的生成器避免走一些明顯不可能搜索到正確答案的路徑，即啟發式搜索。啟發式搜索已成為實際中求解智能規劃問題的重要工具，特別是不確定性規劃問題。近年來，放松規劃在圖規劃問題中的探究、基于單值變量的啟發式研究等均推動著對啟發式搜索的探索。用啟發式搜索思維構建問題解成為一種常用的思考方式，比如最大權獨立集問題、普遍共享騎行問題等。啟發式搜索結合模糊邏輯、頻譜頻率分配等領域技術更是加快了眾多領域搜索發展的進程。歸根究底，人們還是希望搜索路徑沿著自己認為有希望的方向前進，這樣就可以大大減少搜索時間。本文首先追溯研究起點，再從源頭到人機大戰應用對啟發式搜索及其啟發能力等進行探討。
1 問題描述
啟發式搜索，簡而言之，即一種運用啟發先驗知識或者信息引導搜索方向的方法。為了評價啟發式搜索的質量和效率，文中給出如下幾個定義：
定義1搜索代價函數
F（p）=C（p）+H（p）
指算法在一次啟發式搜索過程中，從搜索起點S（Start.point）到達目標點D（Destination）所耗費的代價（如距離等）。其中，G（p）表示從S出發到達某一中間節點p（point）的代價;H（p）表示某一中間節點p到達D的代價。
其中，當搜索已在節點p時，需要決定接下來的搜索路徑，然而當前節點不知道接下來路徑的真實值H（p），于是需要評估得到H*（p）。如果H*（p）的值與真實值存在較大偏差，可能引導節點向相對錯誤的方向搜索。于是給出如下定義：
定義2可被接受的啟發搜索
在上述定義l中，對于所有可能經過的節點p，如果滿足G（p）>0，H*（p）≤H（p），即中間任意一點p到S點的距離大于零，中間任意一點p到達D點的距離評估值H*（p）不大于真實值，則認為H*（p）是可以被接受的估計值，并稱滿足這種條件的啟發搜索是可以被接受的啟發搜索。
然而僅僅依據定義2的條件判定的啟發式搜索并不一定最優，因為從S點出發前往某個未知p點的距離也同樣需要估計。由此繼續給出如下定義：
定義3搜索算法單調
在滿足定義2情況下，如果對于任意節點p，滿足G（p）的估計值C*（p）小于G（p），即從搜索起點S到節點p的路徑是最優路徑，稱滿足上述所有條件的搜索算法是單調的。
算法單調雖然是理想目標，但是現實問題中一般較難達到這樣苛刻的條件。以下圍繞搜索代價函數闡述幾種不同的啟發式搜索算法。
2 啟發式搜索算法
2.1分支定界法
首先討論一種特殊且簡單的情況。當H*（p）=H（p）=0，即F（p）=G（p），這就是簡單的分支定界法滿足的條件。這種方法每次都會優先選擇當前距離最短的路徑前進，以最少距離為目標進行節點擴展。這種方法也會拋棄一些不可能得到最優解的節點，以此達到縮短搜索路徑距離的目標。
如圖1所示，（a）是待搜索的二叉樹，（b）表示從起始節點A開始搜索，沒有達到目的地，繼續往下搜索，擴展A節點得到B和C。圖1（c）發現往B方向路徑距離短，并且沒有達到目的地，繼續擴展B節點搜索得到D和E。同理繼續擴展到達圖l（e），此時已經搜索到了一條到達目的地的路徑，其距離為16。因為還可能存在其它路徑的距離比16更小，于是繼續擴展當前距離花費最小的C點（相等花費條件下遵守從右邊開始擴展的規則）。直到距離可能比16小的所有路徑搜索完為止，如圖1（f），最終找出距離最短的路徑。
簡單的分支定界法固然滿足定義2中啟發搜索是可接受的條件，但是實際情況中H*（p）往往會有很多變化，更不可能固定為零，因此該方法顯然存在較大的局限性。
2.2 兩種分支定界法改進方法
2.2.1 使用低估值的分支定界法
易知上述簡單純粹的分支定界法對H（p）處理上存在缺陷，故采用對H（p）低估值的方法改進分支定界法，即H*（p）=underestimate（H（p））。顯然，這種啟發也是可以被接受的，同時比沒有啟發搜索能力的分支定界更強。
如圖2所示，設矩形內的值表示該節點到目的地Goal的低估計值。從根節點開始，發現不是目標節點，則擴展該根節點，如圖2（c）所示，得到兩個評估函數的值20（6+14）、23（15+8），選擇較小者繼續擴展，直到找到了一條到達目標節點的路徑，如圖2（e）所示，之后繼續搜索其它距離可能更短的路徑，如圖2（f）所示，搜索完所有可能達到最短路徑的節點。
采用低估值的方法有效提高了搜索質量，更加符合實際情況，但是就其搜索速度而論并沒有明顯改觀。 2.2.2 基于最短路徑的分支定界法
由現實生活經驗可知，如果兩條或多條路徑到達同一節點，只需要存儲距離消費最小的那條路徑的距離即可。通過一個抽象處理后的實例對原理加以說明。若要求從S點城市前往D點城市，以下說明存儲最短路徑的分支定界法，如圖3（a）-圖3（f）所示。
從S點出發，面臨A、C兩點選擇，由于C點距離更短則選擇C點，如圖3（c）所示。到達C點后只能前往B點，此時距離S點距離為2，如圖3（d）。同理繼續前往正點，如圖3（e），此時距離S點距離為4。接下來擴展距離比4更小的路徑，即S→A→B（其實還有另一種走法S→A→C，基于后經過優先級更高的原則選擇B點），此段距離到達B時距離S點為3，此時是第二次訪問B點，于是依據最短路徑原則選擇到達B點最短的距離2，即保證存儲了最短路徑S→A→B。
這類似于動態規劃，要記錄下已經訪問的節點，下次繼續訪問相同節點時，只需要在已經被訪問的節點中查找到達某點的最小花費取出來使用即可。雖然這種方法僅僅對到達同一節點的情況進行了優化，但也已在許多相關路徑問題解決中見到它的縮影，如快遞物流優選路徑問題、城市路徑規劃問題等。
3 A*算法
上文對簡單的分支定界法提出了兩種優化策略，如果將兩者優點結合起來就是A*算法。下面將用經典的三數碼問題說明A*算法，假設采用的低估值為曼哈頓距離，其中用到的算子（簡單理解，算子就是每一步的操作，具體一點也可理解為每一步的步驟）是空格上下左右4種方向的移動，具體實例如圖4所示。
在圖4中，標注有*號的三數碼塊F（p）=2+4=6的原因說明：*號三數碼塊距離起點完成了兩個算子操作，由此G（p）=2;與Goal相比，數字l至少向下移動1步可以到達Goal，同理數字2、3分別是2步和l步，因此步數相加為4步，即H*（p）=4。另外，*號數碼塊與起點數碼塊狀態相同，因此通過比較存儲最短距離對路徑進行優化。
由此還可以觀察到，用曼哈頓距離作為搜索低估值時，有時收斂會更加快速。其實，空格的上下左右移動類似于走彎彎折折似正方胡同的小巷，因此曼哈頓路徑又稱為出租車路徑。盡管A*算法已然是啟發搜索能力較強的一種方法，但是在面對多條最小路徑選擇時有時也會存在因為搜索范圍過大而導致搜索時間過長的缺點。
4 蒙特卡洛樹搜索
人和機器在圍棋中的較量比拼已是試驗機器的試金石，其中核心部分便是蒙特卡洛樹搜索。該搜索建立于二人零和博弈基礎上，其搜索基礎是最大最小搜索。最大最小搜索的中心思想是輪到我方搜索擴展時選擇最有利于我方的擴展;輪到對方搜索擴展時選擇最不利于我方的擴展。最大最小搜索有兩大明顯缺點：①搜索樹寬度太廣，導致該樹非�！芭帧�;②搜索樹深度太深，導致該樹非常長。
蒙特卡洛樹搜索便是一種解決這兩個問題的有效方法。蒙特卡洛樹中每個節點表示一種棋面，其搜索步驟如下：
�。�1）選擇。從某點s向下擴展，根據啟發函數選擇進入s的某一子節點si。啟發函數：
�。�2）擴展。選擇啟發函數最大值的點simax擴展。
�。�3）模擬。從simax開始模擬接下來的輸出，一直到零和博弈結束為止。
�。�4）回溯。也稱反向傳播，用模擬的結果更新節點參數信息。
以上4個步驟反復迭代，一直到結束。列舉一次簡單的迭代過程，如圖5（a）-圖5（d）所示，圓內A/B表示O（s）。
通過計算啟發函數選擇擴展O為3/3節點如圖5（a），然后通過模擬更新沿路經過的所有節點的值，即沿路反向傳播的節點模擬次數加1，結果如圖5（d）所示。
蒙特卡洛樹搜索所用的啟發知識不是固定的先驗知識，而是通過搜索過程中模擬反向傳播得到的帶有概率的知識，具有及時性特征，非常符合圍棋這一類多可能性且實時的特征，然而對于搜索樹不是非常龐大的情況，比如象棋路徑搜索，其效果就不如圍棋好。
5 結語
啟發式搜索已在眾多領域得到了落實，比如路徑規劃、智能機器人等，但是在今后智能規劃等任務中，仍然需要理論和實踐的創新突破，例如更加精確的搜索代價函數、機器及時對當前現狀進行動態更新的啟發能力、盡量減少時間或空間消耗等�？梢灶A見，有了更加高效且相對低成本的搜索策略，將對許多領域起到巨大推動作用。
(受腔)