第四章搜索求解策略人工智能概論目錄啟發式搜索盲目搜索搜索人工智能相關概念狀態空間搜索與或樹搜索搜索搜索搜索就是根據問題的實際情況，按照一定的策略或規則，從知識庫中尋找可利用的知識，從而構造一條使問題得到解決的代價最小的推理路徑的過程。搜索包含兩層含義：一是要找到從初始事實到問題最終答案的一條推理路徑，二是找到的這條路徑是時間和空間復雜度最小的推理路徑。人工智能基礎搜索中需要解決的基本問題（1）搜索過程是否一定能找到一個解。（2）當搜索過程找到一個解時，找到的是否是最佳解。（3）搜索過程的時間與空間復雜度如何。（4）搜索過程是否終止運行或是否會陷入一個死循環。搜索搜索的主要過程（1）從初始或目標狀態出發，并將它作為當前狀態。（2）掃描操作算子集，將適用當前狀態的一些操作算子作用在其上來得到新的狀態，并建立指向其父節點的指針。（3）檢查所生成的新狀態是否滿足結束狀態，如果滿足，則得到解，并可沿著有關指針從結束狀態反向到達開始狀態，給出一推理路徑；否則，將新狀態作為當前狀態，返回第2步再進行搜索。搜索策略的分類：搜索盲目搜索不考慮給定問題所具有的特定知識，系統根據事先確定好的某種固定排序依次調用規則或隨機調用規則。根據是否使用啟發式信息啟發式搜索根據問題的表示方法狀態空間搜索與或樹搜索啟發式搜索考慮問題領域可應用的知識，動態地確定規則的排序，優先調用較合適的規則加速問題的求解過程，使搜索朝著最有希望的方向前進，找到最優解。是指用狀態空間法來求解問題所進行的搜索用問題歸約法來求解問題時進行的搜索。回溯策略盲目搜索帶回溯策略的搜索是從初始狀態出發，不停地、試探性地尋找路徑，直到到達目標狀態或遇到不可解節點，即“死胡同”為止。如果到達目標狀態，就成功退出搜索，返回解題路徑。若遇到不可解節點，就回溯到路徑中最近的父節點上，查看該節點是否還有其他的子節點未被擴展。若有，則沿這些子節點繼續搜索。回溯是狀態空間搜索的基本算法思想。各種圖搜索算法，包括寬度優先搜索、深度優先搜索、最好優先搜索，都含有回溯的思想。寬度優先搜索

盲目搜索深度優先搜索

盲目搜索最好優先搜索最好優先搜索（best-firstsearch）是一種基于估價函數的啟發式搜索算法。最好優先搜索通過啟發式函數來估計擴展節點的“價值”，并優先搜索“價值”最高的節點。最好優先搜索通常應用于圖搜索等問題中。在執行搜索操作時，最好優先搜索會先評估初始節點，并計算出每一個相鄰節點的優先級。由于最好優先搜索只選擇優先級最高的節點進行擴展，因此可以在搜索過程中盡早發現最優解。盲目搜索啟發式搜索啟發式策略啟發式策略就是利用與問題有關的啟發信息進行搜索。啟發式策略也是極易出錯的。在解決問題的過程中，啟發僅僅是對下一步將要采取的措施的一個猜想，它常常根據經驗和直覺來判斷。由于啟發式搜索只利用特定問題的有限的信息，要想準確地預測下一步在狀態空間中采取的具體的搜索行為是很難辦到的。問題求解系統可在兩種基本情況下運用啟發式策略（1）由于一個問題在問題陳述和數據獲取方面固有的模糊性，可能沒有一個確定的解，這就要求系統能運用啟發式策略做出最有可能的解釋。（2）雖然一個問題可能有確定解，但是其狀態空間特別大，搜索中生成擴展的狀態數會隨著搜索深度的加大呈指數級增長。窮盡式搜索策略（如寬度優先搜索或深度優先搜索）在給定的較實際的時間和空間復雜度內很可能得不到最終的解，而啟發式策略通過引導搜索向最有希望的方向進行來降低搜索復雜度。啟發式搜索啟發信息啟發信息是對每個狀態的估計，表示從當前狀態到目標狀態的預期成本或距離。這種估計幫助搜索算法優先考慮那些看起來更接近目標的路徑。啟發式搜索使用啟發信息（或啟發函數）來指導搜索過程，以更有效地達到目標狀態。啟發式實際上是一種大拇指準則（thumbrule）：在大多數情況下是成功的，但不能保證一定成功。估價函數

A搜索算法

啟發式搜索如何能夠保證搜索到最優解呢？這就需要A*搜索算法A*搜索算法

啟發式搜索啟發式搜索A*搜索算法的有關特性可采納性單調性信息性

啟發式搜索A*搜索算法的有關特性可采納性單調性信息性

狀態空間搜索用搜索技術來求解問題的系統均會定義一個狀態空間，并通過適當的搜索算法在狀態空間中搜索解答或解答路徑。狀態空間搜索的研究焦點在于設計高效的搜索算法，以降低搜索代價并解決組合爆炸問題。狀態空間搜索問題的狀態空間表示法狀態空間表示法是指用“狀態”和“操作”組成的“狀態空間”來表示問題求解的一種方法。（1）狀態是指為了描述問題求解過程中不同時刻下狀況（例如初始狀況、事實等敘述性知識）間的差異，而引入的最少的一組變量的有序組合。它常用矢量形式表示，例如：（2）操作也被稱為運算符或算符，它使狀態中的某些分量發生改變，從而使問題由一個具體狀態改變到另一個具體狀態。操作可以是一個機械的步驟、過程、規則或算子，并能指出狀態之間的關系。操作用于反映過程性知識。（3）狀態空間是指一個由問題的全部可能狀態及其相互關系（即操作）所構成的有限集合。狀態空間搜索狀態空間搜索的基本思想狀態空間搜索的基本思想就是通過搜索引擎尋找一個操作算子的調用序列，使問題從初始狀態轉變到目標狀態，而轉變過程中的狀態序列或相應的操作算子調用序列稱為從初始狀態到目標狀態的解答路徑。通常，狀態空間的解答路徑有多條，但最短的只有1條或少數幾條。一個狀態可以有多個可供選擇的操作算子會導致多條待搜索的解答路徑，這種選擇在邏輯上稱為“或”關系，意指只要其中有一條路徑通往目標狀態，就能獲得成功解答。由此，這樣的有向圖稱為或圖。在搜索解答路徑的過程中，只畫出搜索時直接涉及的節點和弧線，構成所謂的搜索圖。搜索空間的壓縮程度主要取決于搜索引擎釆用的搜索算法。與或樹搜索與或樹搜索是一種計算機搜索算法，用于在決策樹或狀態空間中搜索最優解。它將搜索問題的狀態表示為不同節點，每個節點都有一個布爾值，即“真”或“假”，然后從根節點開始依次向下擴展每個節點，同時根據節點的布爾值來決定是否進一步擴展其下一級子節點。如果當前節點的布爾值為“真”，則只需要向下擴展其所有子節點，直到找到一個最優解；反之，如果當前節點的布爾值為“假”，則只需停止搜索這個子樹，返回其父節點，繼續搜索其他子樹。與或樹搜索算法的目標是通過最小化搜索成本來找到最優解。它適用于解決很多問題，例如棋盤游戲、自動規劃、語言理解和計算機視覺等。小結開發人工智能技術的一個主要目的就是解決非平凡問題，即難以用常規技術（數值計算、數據庫應用等）直接解決的問題。這些問題的求解依賴于問題本身的描述和應用領域相關知識的應用方式。廣義地說，人工智能問題都可以看作一個