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

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

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

【部分圖文】：

低估值的分支定界法

由現(xiàn)實(shí)生活經(jīng)驗(yàn)可知，如果兩條或多條路徑到達(dá)同一節(jié)點(diǎn)，只需要存儲(chǔ)距離消費(fèi)最小的那條路徑的距離即可。通過一個(gè)抽象處理后的實(shí)例對(duì)原理加以說明。若要求從S點(diǎn)城市前往D點(diǎn)城市，以下說明存儲(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ù)前往E點(diǎn)，如圖3(e），此時(shí)距離S點(diǎn)距離為4。接下來擴(kuò)展距離比4更小的路徑，即S→A→B（其實(shí)還有另一種走法S→A→C，基于后經(jīng)過優(yōu)先級(jí)更高的原則選擇B點(diǎn)），此段距離到達(dá)B時(shí)距離S點(diǎn)為3，此時(shí)是第二次訪問B點(diǎn)，于是依據(jù)最短路徑原則選擇到達(dá)B點(diǎn)最短的距離2，即保證存儲(chǔ)了最短路徑S→A→B。

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

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

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



本文編號(hào)：3058750