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

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