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

【文章來源】：軟件導刊. 2020,19(06)

【文章頁數(shù)】：4 頁

【部分圖文】：

低估值的分支定界法

由現(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ù)前往E點，如圖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。

上文對簡單的分支定界法提出了兩種優(yōu)化策略，如果將兩者優(yōu)點結合起來就是A*算法[14]。下面將用經(jīng)典的三數(shù)碼問題[15]說明A*算法，假設采用的低估值為曼哈頓距離[16]，其中用到的算子[17]（簡單理解，算子就是每一步的操作，具體一點也可理解為每一步的步驟）是空格上下左右4種方向的移動，具體實例如圖4所示。在圖4中，標注有*號的三數(shù)碼塊F(p)=2+4=6的原因說明：*號三數(shù)碼塊距離起點完成了兩個算子操作，由此G(p)=2；與Goal相比，數(shù)字1至少向下移動1步可以到達Goal，同理數(shù)字2、3分別是2步和1步，因此步數(shù)相加為4步，即H*(p)=4。另外，*號數(shù)碼塊與起點數(shù)碼塊狀態(tài)相同，因此通過比較存儲最短距離對路徑進行優(yōu)化。

【參考文獻】：
期刊論文
[1]雙人博弈問題中的蒙特卡洛樹搜索算法的改進[J]. 季輝,丁澤軍.  計算機科學. 2018(01)
[2]一種改進的多目標人工蜂群算法[J]. 陳偉棟,童華剛,郜振華,張洪亮.  南華大學學報(自然科學版). 2017(02)
[3]八數(shù)碼問題解法效率比較及改進研究[J]. 付宏杰,王雪瑩,周健,周孫靜,朱珠,張俊余.  軟件導刊. 2016(09)
[4]基于改進A*算法的水下航行器自主搜索航跡規(guī)劃[J]. 榮少巍.  電子科技. 2015(04)
[5]動態(tài)規(guī)劃算法綜述[J]. 張瑩.  科技視界. 2014(28)
[6]基于改進粒子群算法的智能機器人路徑規(guī)劃[J]. 張萬緒,張向蘭,李瑩.  計算機應用. 2014(02)
[7]基于分層的改進A算法在路徑規(guī)劃中的應用[J]. 錢紅昇,葛文鋒,鐘鳴,葛銘.  計算機工程與應用. 2014(07)
[8]圖規(guī)劃框架下的啟發(fā)式搜索的研究與發(fā)展[J]. 谷文祥,王改革,殷明浩,孫焱.  計算機科學. 2009(11)
[9]智能搜索中啟發(fā)函數(shù)的選擇及啟發(fā)能力分析[J]. 許精明.  昆明理工大學學報(理工版). 2007(05)
[10]極小極大值理論的歷史發(fā)展[J]. 尚宇紅.  西北大學學報(自然科學版). 2003(02)

碩士論文
[1]基于單值變量的求解啟發(fā)式方法研究[D]. 柳一君.吉林大學 2017
[2]基于圖規(guī)劃的智能小車的路徑搜索應用研究[D]. 林爾敏.中山大學 2015



本文編號：3058750