啟發式算法在計算機程序搜索中的簡單應用

李曉宇　秦文杰

摘 要：對于不能直接計算求解的問題，往往需要搜索算法在解空間中尋找最優解或更優解。為了高效地搜索，加入了啟發式算法，讓機器程序像人一樣作出更優的決策。闡述了啟發式算法中的作用原理，介紹了啟發式算法與搜索的聯系，講解了啟發式算法在計算機程序搜索中的簡單應用的案例，對比分析了啟發式算法與普通寬度優先搜索或深度優先搜索算法的優勢與不足。

關鍵詞：啟發式算法，解空間，搜索，更優解，估價函數

0、引言 搜索是用計算機解決問題時常用的算法策略。但往往相對于要求的最優解或次優解而言，解空間很大。直接簡單地運用搜索解決問題，往往會花費大量的時間，因為無用的搜索方向或問題狀態相對目標解來說太多。在已知目標狀態或如何衡量待求解的優劣時，利用減枝技巧可以避免搜索部分無用解空間，但是計算機搜索仍然會試探一些無用的解空間。啟發式算法可以估計當前狀態到目標狀態的代價，從而作出好的策略，幫助機器像人一樣聰明地向更優解目標方向搜索。

1、啟發式算法的作用原理

啟發式算法是根據機器計算當前狀態到目標狀態的所有可能性或所需花費，從中選出到達目標狀態可能性最高的或者花費最少的下一步。就這樣不斷地計算概率花費，不斷迭代優化更優解，進而得到更優解或者最優解。計算機程序可能并不會準確地計算出到達目標解的代價，但是可以利用數學計算進行估計。若要得估價接近實際花費，就得設計好評價函數。這也是啟發性的關鍵。

2、啟發式算法應用在搜索中

機械的搜索算法會浪費大量時間等計算機資源在無用狀態轉換上。若要讓計算機程式像人擁有感覺作出合理的判斷，就是給程序使用啟發式算法了。讓機器智能地搜索下一個狀態。本科期間常見或用到的啟發式算法有A*算法，遺傳算法，蟻群算法，BP神經網絡等。BP神經網絡可用于仿真機器人學習上，在大學上機器人競賽中常用。讓機器人不斷地學習，修改參數，作出更優的策略。A*算法可用于ACM大學生程序設計競賽中，比較容易實現，常用于搜索。

3、啟發式算法應用于搜索中的案例

3.1 計算機軟件能力認證-游戲[3]

題目轉述：在N行M列的棋盤上，計算玩家從左上角移動到右下角所需的最少時間，期間某些位置在一段連續時間不能移動到（危險）。詳細描述請參照原題[3]。

分析：這是一道棋盤搜索題，求解最短時間。很容易想到寬度優先搜索，可以利用三維數組來表示棋盤狀態（根據數組在內存中是線性存儲的，所以也可以將三維數組轉化為一維。但是內存消耗是一樣的，所以沒有必要轉化。三維數組的維度分別表示位置橫坐標，縱坐標，時間戳）。直接寬度優先搜索可以解決改問題，只是搜索了大量的無用的棋盤狀態，效率不高。

雖然可以在該題時間限制內解決問題，但是若用了A*算法，加入啟發式思想。從當前搜索過的狀態中選擇到目標狀態的曼哈頓距離最小的位置狀態開始搜索，因為玩家每秒都要移動，所以曼哈頓距離越小的狀態到達目標的用時最少。在保證結果正確的前提下，提高了解決問題的效率。

給出估價函數：

從當前狀態（x， y）到目標狀態（m， n）的估價函數 h = abs（x - m） + abs（y - n），即當前位置到目標位置的曼哈頓距離。

初始狀態到當前狀態的實際代價：每移動一次，該代價g 加1。

初始狀態經當前狀態到達目標狀態的估價：f = h + g。

實際測試用時比較：普通BFS[4]用時109ms， 啟發式算法A*算法[5]用時62ms。可見啟發式算法有方向地搜索比較省時。

具體算法實現見附解（參考文獻）。北大測評系統1077也可用A*算法解答。

3.2 啟發式算法在機器人中的應用

在大學生機器人競賽中，在對機器人進行策略安排時，有的同學是把機器人場地進行劃分，對每個機器人都設計一套策略。根據不同的局面狀態，調整機器人的策略。總的來說就是判斷判斷再判斷，根據判斷作出反應。這樣直接的判斷狀態的策略，機器人下一步該怎樣做，設計者可以預測個大概。這并不能說是人工智能。機器人缺少隨機應變的啟發性決策。

西北工業大學的機器人配合得很好，很好地根據對手機器人的動作作出適當的改變。若不加入啟發性算法、機器學習，很難得到好的策略。

利用BP神經網絡，讓機器人自主學習，不斷地修改參數，做到更優。蟻群算法，模擬自然界中螞蟻尋找食物，在路上留下信息素。信息素在一段時間內逐漸消散。其他螞蟻可以根據信息素的分布情況作出相應的動作。可以運用到11V11機器人輪式足球比賽上面。

其他啟發式算法，例如遺傳算法等也常用到機器人策略編寫上。

4、啟發式搜索與普通寬度優先搜索的比較

啟發式搜索每次有向著更接近目標解的狀態搜索，避免了大量無效解空間的試探。如案例1測試結構，啟發式搜索提高了解決問題的效率。

普通寬度優先搜索相對來說比較容易實現，若對時間要求不是很嚴格，BFS編寫簡單，搜索策略更易理解。而應用啟發式搜索時需要使用數據結構優先隊列，需要重載運算符。

應用啟發式搜索時，需要注意評價函數的選擇，這個直接關系著搜索的效率。估價函數不是一成不變的，不同的問題需要設計不同的估價函數。

5、總結

啟發式算法應用到搜索策略中，可以避免不必要的搜索，大大減小了解空間。程序一直向著有希望的方向搜索，在一定程度上可以解決狀態空間爆炸式增加的現象。解決不同的問題，往往需要不同的估價函數。在機器人策略實現方便，利用啟發式算法不斷地嘗試學習，不斷地修改參數，可以使得機器人做出更好的策略。

注解：

[1] 李曉宇 鄭州大學信息工程學院老師

[2] 秦文杰 鄭州大學信息工程學院軟件工程系2015級2班的一個學生，學號20152480225

[3] 計算機軟件能機認證試題CCF CSP 201604-4 游戲，原題鏈接（需要登錄）

http：//118.190.20.162/view.page？gpid=T39

[4] 普通BFS解法

https：//github.com/zzuwenjie/coding18/blob/master/OJ/CCFCSP201604_4_BFS.cpp

[5] 啟發式算法A*算法解法

https：//github.com/zzuwenjie/coding18/blob/master/OJ/CCFCSP201604_4_Astar.cpp