啟發(fā)式算法在計算機程序搜索中的簡單應(yīng)用

李曉宇　秦文杰

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

關(guān)鍵詞：啟發(fā)式算法，解空間，搜索，更優(yōu)解，估價函數(shù)

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

1、啟發(fā)式算法的作用原理

啟發(fā)式算法是根據(jù)機器計算當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的所有可能性或所需花費，從中選出到達目標(biāo)狀態(tài)可能性最高的或者花費最少的下一步。就這樣不斷地計算概率花費，不斷迭代優(yōu)化更優(yōu)解，進而得到更優(yōu)解或者最優(yōu)解。計算機程序可能并不會準(zhǔn)確地計算出到達目標(biāo)解的代價，但是可以利用數(shù)學(xué)計算進行估計。若要得估價接近實際花費，就得設(shè)計好評價函數(shù)。這也是啟發(fā)性的關(guān)鍵。

2、啟發(fā)式算法應(yīng)用在搜索中

機械的搜索算法會浪費大量時間等計算機資源在無用狀態(tài)轉(zhuǎn)換上。若要讓計算機程式像人擁有感覺作出合理的判斷，就是給程序使用啟發(fā)式算法了。讓機器智能地搜索下一個狀態(tài)。本科期間常見或用到的啟發(fā)式算法有A*算法，遺傳算法，蟻群算法，BP神經(jīng)網(wǎng)絡(luò)等。BP神經(jīng)網(wǎng)絡(luò)可用于仿真機器人學(xué)習(xí)上，在大學(xué)上機器人競賽中常用。讓機器人不斷地學(xué)習(xí)，修改參數(shù)，作出更優(yōu)的策略。A*算法可用于ACM大學(xué)生程序設(shè)計競賽中，比較容易實現(xiàn)，常用于搜索。

3、啟發(fā)式算法應(yīng)用于搜索中的案例

3.1 計算機軟件能力認(rèn)證-游戲[3]

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

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

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

給出估價函數(shù)：

從當(dāng)前狀態(tài)（x， y）到目標(biāo)狀態(tài)（m， n）的估價函數(shù) h = abs（x - m） + abs（y - n），即當(dāng)前位置到目標(biāo)位置的曼哈頓距離。

初始狀態(tài)到當(dāng)前狀態(tài)的實際代價：每移動一次，該代價g 加1。

初始狀態(tài)經(jīng)當(dāng)前狀態(tài)到達目標(biāo)狀態(tài)的估價：f = h + g。

實際測試用時比較：普通BFS[4]用時109ms， 啟發(fā)式算法A*算法[5]用時62ms?？梢妴l(fā)式算法有方向地搜索比較省時。

具體算法實現(xiàn)見附解（參考文獻）。北大測評系統(tǒng)1077也可用A*算法解答。

3.2 啟發(fā)式算法在機器人中的應(yīng)用

在大學(xué)生機器人競賽中，在對機器人進行策略安排時，有的同學(xué)是把機器人場地進行劃分，對每個機器人都設(shè)計一套策略。根據(jù)不同的局面狀態(tài)，調(diào)整機器人的策略?？偟膩碚f就是判斷判斷再判斷，根據(jù)判斷作出反應(yīng)。這樣直接的判斷狀態(tài)的策略，機器人下一步該怎樣做，設(shè)計者可以預(yù)測個大概。這并不能說是人工智能。機器人缺少隨機應(yīng)變的啟發(fā)性決策。

西北工業(yè)大學(xué)的機器人配合得很好，很好地根據(jù)對手機器人的動作作出適當(dāng)?shù)母淖儭Ｈ舨患尤雴l(fā)性算法、機器學(xué)習(xí)，很難得到好的策略。

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

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

4、啟發(fā)式搜索與普通寬度優(yōu)先搜索的比較

啟發(fā)式搜索每次有向著更接近目標(biāo)解的狀態(tài)搜索，避免了大量無效解空間的試探。如案例1測試結(jié)構(gòu)，啟發(fā)式搜索提高了解決問題的效率。

普通寬度優(yōu)先搜索相對來說比較容易實現(xiàn)，若對時間要求不是很嚴(yán)格，BFS編寫簡單，搜索策略更易理解。而應(yīng)用啟發(fā)式搜索時需要使用數(shù)據(jù)結(jié)構(gòu)優(yōu)先隊列，需要重載運算符。

應(yīng)用啟發(fā)式搜索時，需要注意評價函數(shù)的選擇，這個直接關(guān)系著搜索的效率。估價函數(shù)不是一成不變的，不同的問題需要設(shè)計不同的估價函數(shù)。

5、總結(jié)

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

注解：

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

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

[3] 計算機軟件能機認(rèn)證試題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] 啟發(fā)式算法A*算法解法

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