人工智能-啟發(fā)式搜索

人工智能啟發(fā)式搜索問題背景人工智能的宗旨是尋找一種有效的方式把智能的問題求解、規(guī)劃和通信技巧應(yīng)用到更廣泛的實(shí)際問題中，集中于不存在算法解的問題，這也是為什么啟發(fā)式搜索是一種主要的AI問題求解技術(shù)的原因。對于人工智能系統(tǒng)而言，問題可能狀態(tài)的數(shù)量隨搜索的深入呈現(xiàn)指數(shù)或階乘增長，為了明智地找出正解，將沿最有希望的路徑穿越空間來降低這種復(fù)雜性，這便是啟發(fā)式求解。把沒有希望的狀態(tài)及這些狀態(tài)的后代排除，這樣便可以克服組合爆炸，找到可接受的解?；竞喗閱l(fā)式求解對問題求解過程中下一步要采取的措施的一種精明猜測，是建立于強(qiáng)大的知識(shí)庫的由經(jīng)驗(yàn)總結(jié)出的求解方式。簡單的啟發(fā)可以排除搜索空間的絕大部分。啟發(fā)式搜索由兩部分組成：啟發(fā)度量及是有這個(gè)度量進(jìn)行空間搜索的算法。下面介紹兩種算法1.爬山法爬山策略在搜索中現(xiàn)擴(kuò)展當(dāng)前狀態(tài)，然后再評(píng)估它的“孩子”。而后選擇“最佳的”孩子做進(jìn)一步擴(kuò)展；而且過程中既不保留它的兄弟姐妹，也不保留它的雙親。因?yàn)檫@種策略不保存任何歷史記錄，所以它不具有從失敗中恢復(fù)的能力。?Start圖1使用3層預(yù)判的爬山方法遇到的局部最大化問題爬山策略的一個(gè)主要問題是容易陷入局部最大值。如果這種策略達(dá)到了一個(gè)比其他任何孩子都好的狀態(tài)，它便停止。因此為了提高性能，需要局部改進(jìn)評(píng)估多項(xiàng)式。2.最佳優(yōu)先搜索算法最佳優(yōu)先搜索算法使用了優(yōu)先級(jí)隊(duì)列，使得從諸如陷入局部優(yōu)先等情況中恢復(fù)成為可能，從而使啟發(fā)式搜索更加靈活。最佳優(yōu)先搜索算法使用列表來維護(hù)狀態(tài)：用open列表來記錄搜索的當(dāng)前狀態(tài)，用close列表記錄已經(jīng)訪問過的狀態(tài)。在這種算法中新加的一步是對open中的狀態(tài)進(jìn)行排序，排序的依據(jù)是對狀態(tài)與目標(biāo)“接近程度”的某種啟發(fā)性估計(jì)。最佳優(yōu)先搜索算法總是選擇最有希望的狀態(tài)做進(jìn)一步擴(kuò)展。然而由于他正在使用的啟發(fā)可能被證明是錯(cuò)誤的，所以它并不拋棄所有狀態(tài)而是把他們維護(hù)在open中。一旦發(fā)現(xiàn)啟發(fā)將搜索引導(dǎo)到一條證明不正確的路徑，那么算法會(huì)從open中取出一些以前產(chǎn)生的“次優(yōu)先”的狀態(tài)，從而把搜索的焦點(diǎn)轉(zhuǎn)移到空間的另一部分。以8格拼圖游戲?yàn)槔M(jìn)行啟發(fā)式搜索：圖2游戲目標(biāo)構(gòu)造一個(gè)評(píng)估函數(shù)f，它是兩個(gè)分量的和：f(n)=g(n)+h(n)其中：g(n)是從任意狀態(tài)n到起始狀態(tài)的實(shí)際路徑長度，h(n)是對狀態(tài)n到目標(biāo)距離的啟發(fā)性估計(jì)(在此表示錯(cuò)位的牌數(shù))目前該游戲h=4；

狀態(tài)ef(e)=54r … f狀態(tài)Cf(c)=42831647狀態(tài)ef(e)=54r … f狀態(tài)Cf(c)=428316475■ 狀態(tài)ff(f)=528314■765-…一狀態(tài)jf(j)=523■184765狀態(tài)af(a)=4狀態(tài)df(d)=6狀態(tài)gf(g)=6g(n)=og(n)=1g(n)=2g(n)=3狀態(tài)kf(k)=7目標(biāo)圖3對8格拼圖游戲進(jìn)行啟發(fā)式搜索而產(chǎn)生的狀態(tài)空間歸納起來，最佳優(yōu)先算法就是1） 操作當(dāng)前狀態(tài)以產(chǎn)生新的孩子2） 檢查每個(gè)新狀態(tài)，看其是否已經(jīng)（在open或close中）出現(xiàn)過，以防止循環(huán)3） 給出每個(gè)狀態(tài)n的f值，這個(gè)值等于該狀態(tài)在搜索空間中的深度g（n）和它與目標(biāo)距離的啟發(fā)性估計(jì)h（n）的和。4） open中的狀態(tài)是按它們的f值排序的，在分析了所有狀態(tài)或發(fā)現(xiàn)目標(biāo)之前，所有狀態(tài)都被保存在open中，這樣做使算法可以從死端（deadend）恢復(fù)5）從現(xiàn)實(shí)角度來看，可以通過改善維護(hù)open和close列表的方法來提高算法的效率?，F(xiàn)有工作實(shí)際生活中，啟發(fā)式搜索主要應(yīng)用于專家系統(tǒng)，例如“深藍(lán)”與象棋高手之間的博弈、財(cái)務(wù)統(tǒng)計(jì)及顧問、一些復(fù)雜算法的求解......它的內(nèi)容也正逐步擴(kuò)展，從傳統(tǒng)的爬山和動(dòng)態(tài)規(guī)劃算法到最佳優(yōu)先搜索，再到二人游戲中的極小極大和a-p剪枝的預(yù)判來嘗試預(yù)測對手的行為。啟發(fā)式搜素依然存在其弊端，例如博弈過程中，對手改變慣有套路，就難以在智能機(jī)器知識(shí)庫中搜索，從而無法做出正確解答。當(dāng)然，人們對于啟發(fā)式搜索的探索正逐步深入......我的想法在人工智能中，搜索就像紅線將用戶與計(jì)算機(jī)強(qiáng)大的知識(shí)庫相連，而在此，啟發(fā)式