目錄

本章內容

3.1 圖搜索策略

3.2 盲目搜索

3.2.1 搜索策略的對比

3.2.2 深度優先搜索-有限深度+迭代深度

3.3 啟發式搜索

3.3.1 啟發式搜索策略和估價函式

3.3.2 有序搜索

1、A演算法

2、A*演算法

3.4 消解原理

3.4.1 子句集的求取

3.4.2 消解推理規則

3.4.3 含有變數的消解式

3.4.4 消解反演求解程序

3.5 規則演繹系統

3.6 產生式系統

3.6.1 產生式系統的組成

3.6.2 產生式系統的推理

3.7 非單調推理

本章內容

掌握圖搜索的基本概念

掌握盲目搜索和啟發式搜索的區別

掌握消解原理的含義及實際問題解決程序

了解規則演繹系統的基本知識

了解產生式系統的基本知識

了解非單調推理的基本知識

3.1 圖搜索策略

圖搜索控制策略：一種在圖中尋找路徑的方法，

圖中每個節點對應一個狀態，每條連線對應一個運算子，這些節點和連線又分別由產生式系統的資料庫和規則來標記，求得把一個資料庫變換為另一資料庫的規則序列問題就等價于求得圖中的一條路徑問題

圖搜索程序：

OPEN表（記錄還沒有擴展的表）

CLOSED表（記錄已經擴展的點）

每個狀態的節點結構中必須有指向父節點的指標

評價搜索演算法性能的4種途徑：

完備性、最優性、時間復雜度、空間復雜性

圖的一般搜索策略：

無資訊搜索（盲目搜索）：寬度優先搜索、深度優先搜索

有資訊搜索（啟發式搜索）：A演算法、A*演算法

3.2 盲目搜索

分類：寬度優先搜索、深度優先搜索、等代價搜索

特點：（1）搜索程序中不適用與問題又算的經驗資訊

（2）不需要重排OPEN表

（3）搜索效率低

（4）不適合大空間的實際問題求解

3.2.1 搜索策略的對比

假設每個狀態有 b 個后繼，目標節點所在深度為d：

	完備性	時間復雜度	空間復雜度	最優性
寬度優先搜索（BFS） 逐層擴展	總可以找到解	根節點有b個后繼，這b個節點每個又有b個后繼，即b2 最壞的情況：擴展除d層最后一個節點外的所有節點 總共擴展操作的次數：	每個節點都需要存盤，共需要：	如果每步擴展的代價相同，能找到最優解
深度優先搜索（DFS） 往深處擴展	并不總可以找到解，除非搜索空間有界且沒有環	搜索樹的最大深度為m，最壞的情況：m比d大的多 總共擴展操作的次數：O()	只需保存從根到葉的單條路徑，每個層次上都有(b-1)個未擴展的節點，總的記憶體需要量為m(b-1)+1，因此深度優先搜索的空間復雜度是b的線性函式O(bm)
迭代加深搜索（IDS） 每次改變限制深度，多次呼叫深度優先搜索	總可以找到解，如果不存在無限路徑		與DFS相同，O(bd)	路徑代價是節點深度的非遞增函式時是最優的
等代價搜索（UCS） 沿著等代價路徑逐層擴展	總可以找到			能找到最優解

3.2.2 深度優先搜索-有限深度+迭代深度

優先深度： 深度搜索的最大深度為l，等價于深度為l 的節點沒有后繼節點，解決了深度優先搜索的無限路徑問題，如果 l< d 那么結果不完整，如果 l > d 那么程序不是最優的

迭代加深：每次改變限制深度，多次呼叫深度有限搜索演算法，求最優深度極限 l 的一般策略，結合了DFS與BFS的優點

3.3 啟發式搜索

特點：重排OPEN表，選擇最優希望的節點加以拓展，

種類：有序搜索、A*演算法等

3.3.1 啟發式搜索策略和估價函式

啟發式資訊：用來加速搜索程序的有關問題領域的特征資訊，

啟發式搜索：利用啟發資訊的搜索方法，

估價函式：為獲得某些節點“希望”的啟發資訊，提供一個評定侯選擴展節點的方法，以便確定哪個節點最有可能在通向目標的最佳路徑上

f(n)——表示節點n的估價函式值

一個節點的希望程度越大，其f值就越小

3.3.2 有序搜索

三類搜索問題：最優路徑，較優路徑，一條路徑（唯一路徑）

1、A演算法

1964年，尼爾遜提出A1演算法，1967年拉斐爾改進了A1演算法，稱為A2演算法

實質：選擇OPEN表上具有最小f值的節點作為下一個要擴展的節點

特征：估價函式 f (n) = g (n) + h (n)

性能：不完備，不最優

2、A*演算法

1968年，彼得·哈特對A演算法進行了很小的改進，并證明了當估價函式滿足一定的限制條件時，演算法一定可以找到最優解，

A*演算法的限制條件：f (x) = g (x) + h (x) (g(x)＞0，h(x)不大于x到目標的實際代價h*(x))

3.4 消解原理

消解式是親本子句的邏輯結論

消解只能在僅含否定和析取聯接詞的公式（子句）間進行

必須先把公式化成規范的形式（范式，子句集）

方法：不斷求子句的消解式，直到得到空子句為止

相關概念

文字：一個原子公式及其否定

子句：由文字的析取組成的合式公式

消解：對謂詞演算公式進行分解和花間，消去一些符號，以求得匯出子句

3.4.1 子句集的求取

例如：將下列謂詞演算公式化為一個子句集

1、消去蘊含符號

只應用∨和～符號，以～A∨B替換A→B，

2、減少否定符號的轄域

將 ~ 內移,每個否定符號～最多只用到一個謂詞符號上，并反復應用狄·摩根定律，

3、變數標準化

不同的量詞使用不同的變數名，對啞元(虛構變數)改名，以保證每個量詞有其自己唯一的啞元

4、去掉存在量詞

兩種情況：

①“” 在某些 “”的作用域內，例如：

②“” 不在 “”的作用域內，直接去掉存在量詞，將對應的變數寫成一個常量運算式

5、化為前束形

將所有的“” 移到公式的最前面,并使每個量詞的轄域包括這個量詞后面公式的整個部分

6、把母式寫成合取范式的形式

任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取，

7、去掉全稱量詞

所有余下的量詞均被全稱量詞量化了，消去前綴，即消去明顯出現的全稱量詞，

8、消去合取詞 ∧

用{A,B}代替(A∧B)，消去符號∧，最后得到一個有限集，其中每個公式是文字的析取

9、更換變數名稱

使相同的變元不會出現在不同的子句中

3.4.2 消解推理規則

命題邏輯的消解：設有 {λ} ∨ C1 和 {? λ} ∨ C2, 其中 C1 , C2 是子句，λ 是原子, 則可推出C12 =C1 ∨ C2 , C12稱為C1 , C2的resolvent(消解式，歸結式), 這個程序稱為消解resolution，

謂詞邏輯的消解：假設 C1 和C2 是子句, 如果C1中有文字L1，C2中有文字L2 ，且L1 與 ? L2 有最一般合一者σ，則這兩個子句有消解式 C12： C12=(C1σ - {L1σ})∪(C2σ - {L2σ})

消解式的定義：令L1，L2為兩任意原子公式；L1和L2具有相同的謂詞符號，但一般具有不同的變數，已知兩子句L1∨α和～L2∨β,如果L1和L2具有最一般合一σ，那么通過消解可以從這兩個父輩子句推匯出一個新子句(α∨β)σ，這個新子句叫做消解式，

消解式的例子：

（1）假言推理

（2）合并

（3）重言式

（4）空子句（矛盾）

（5）鏈式（三段論）

3.4.3 含有變數的消解式

要把消解推理規則推廣到含有變數的子句，必須找到一個作用于親本子句的置換，使親本子句含有互補文字，

當子句之間可以找到一個項對變數的置換使其變成相同的形式時，就稱這些子句是可合一的，

例如：

注意： 所有的 父輩都要進行置換

置換的目的：使用置換使得原子公式能夠變得一致

置換的復合：

S = {u1/s1,..,um/sm} T = {t1/v1,...,tn/vn}

他們的復合仍是一個置換，ST = {u1T /s1,..,umT /sm , t1/v1,...,tn/vn}

置換的復合運算時做結合的，不滿足交換律

例如：

合一：尋找項對變數的置換，以使兩運算式一致的程序，合一者不唯一

例如：

最一般合一者：給定公式集S, 設S的最一般合一者為θ, 則對S的所有其他合一者 , 都存在一個置換 使得

3.4.4 消解反演求解程序

1、采用消解反演從已知條件集合S證明結論G的步驟

①將 S 化為子句集

②將G的否定~G化為子句集

③將通過步驟1和2得到的子句合并成一個集合T.

④不斷進行消解，并將得到的消解式加入T中，直到產生一個空子句NIL為止

2、反演求解程序：

①把由目標公式的否定產生的每個子句添加到目標公式否定之否定的子句中去，

②按照反演樹，執行和以前相同的消解，直至在根部得到某個子句止，

③用根部的子句作為一個回答陳述句，

3.5 規則演繹系統

正向規則演繹系統是從事實到目標進行操作的，即從狀況條件到動作進行推理的，也就是從if到then的方向進行推理的，

逆向規則演繹系統是從then向if進行推理的，即從目標或動作向事實或狀況條件進行推理的，

雙向規則演繹：此組合系統的總資料庫由表示目標和表示事實的兩個與或圖結構組成，這些與或圖結構分別用正向系統的F規則和逆向系統的B規則來修正，

3.6 產生式系統

定義：用來描述若干個不同的以一個基本概念為基礎的系統，這個基本概念就是產生式規則或產生式條件和操作對的概念，

實質：在產生式系統中，論域的知識分為兩部分：用事實表示靜態知識，如事物、事件和它們之間的關系；用產生式規則表示推理程序和行為，由于這類系統的知識庫主要用于存盤規則，因此又把此類系統稱為基于規則的系統

3.6.1 產生式系統的組成

總資料庫、產生式規則、控制策略

3.6.2 產生式系統的推理

選擇規則到執行操作的步驟：

1、匹配：把當前資料庫與規則的條件部分相匹配

2、沖突解決：當有一條以上規則的條件部分和當前資料庫相匹配時，就需要決定首先使用哪一條規則，這稱為沖突解決，

3、操作：就是執行規則的操作部分

正向推理、逆向推理、雙向推理

3.7 非單調推理

單調推理：建立在謂詞邏輯基礎上的傳統系統是單調的，即已知為真的命題數目隨時間而嚴格增加，因為：新的命題可加入系統，新的定理可被證明，but：這種加入和被證明決不會導致前面已知為真或已被證明的命題變成無效，缺點：不能很好處理三類情況：不完全資訊、不斷變化情況，求解復雜問題程序中產生假設，

預設推理：當缺乏資訊時，只要不出現相反的證據，就可以作一些有益的猜想

真值維持系統：用以協助其它推理程式維持系統的正確性，所以它的作用不是生成新的推理，而是在其它程式所產生的命題之間保持相容性，一旦發現某個不相容，它就調出自己的推理機制，面向從屬關系的回溯，并通過修改最小的信念集來消除不相容