第四章一般搜索原理

第四章

知識表示的目的是為了便于計算機求解，是為了解決問題。從問題的描述（表示）到問題的解決，有個求解的過程，也就是搜索過程。在這一過程中采用適當的搜索技術，包括各種規則、過程和算法等推理技術，力求找到問題的解答。本章討論一些早期的搜索技術或用于解決比較簡單問題的搜索原理（啟發式搜索、寬度優先、深度優先、有序搜索）。知識表示的目的是為了便于計算機求解，是為了解決問題4.1盲目搜索盲目搜索又叫做無信息搜索。一般只適用于求解比較簡單的問題。

4.1盲目搜索

O

規則庫

搜索樹：R1R2A.B.R1:

如X/12為整，則X/6為整。R2R3R1R4C.D.E..R2:

如X/20為整，則X/10為整R3R4R2R3R4S

F..G.HIR3:

如X/6為整，則X/2為整。R4SR4R4SR4:

如X/10為整，則X/5為整。S

S

S

輸入數據庫：N/12，N/20S=success

判斷是否N/5

這是一個產生式系統的例子。節點用表示。每一個節點對應于一個狀態，反映當時數據庫的情況。如節點O：N/12，N/20；節點A：N/12，N/20，N/6；節點D：N/12，N/20，N/6，N/2。每條連線對應于一個操作符。

棋局對應走步，這里對應于一條產生式規則。

這是一個產生式系統的例子。

該搜索樹給出了所有可能的求解證明渠道。抽象地描述：給定初始節點和目標節點，求圖中的一條合理路徑（所謂合理有的指只要找到就行；有的要求搜索步驟最少或路徑最短等等）。就這個例子，我們看一下寬度優先搜索、深度優先搜索是如何進行的。當然，并不是所有問題都可以畫出圖示的搜索樹（深度不深、每條支路都有解且支路不多）。

該搜索樹給出了所有可能的求解證明渠道。抽象地描述：4.1.1寬度優先搜索

如果搜索是以接近起始節點的程度依次擴展節點的，那么這種搜索就叫做寬度優先搜索。也就是說，這種搜索是逐層進行的。在對下一層的任一節點進行搜索之前，必須搜索完本層的所有節點。寬度優先搜索算法（流程框圖）如下：（1）把起始節點放到OPEN表中（如果該起始節點為目標節點，則求得一個解答）。OPENCLOSED

O4.1.1寬度優先搜索O（2）如果OPEN表是個空表，則沒有解，失敗退出。否則繼續。（3）把第一個節點從OPEN表中移出，并把它放入CLOSED的擴展節點表中。（4）擴展該節點。如果沒有后繼節點，則轉向上述第（2）步。（5）把該節點的所有后繼節點放到OPEN表的末端，并提供這些后繼節點返回該節點的指針。（6）如果該節點的任一個后繼節點是個目標節點，則找到一個解答，成功退出；否則轉向（2）。（2）如果OPEN表是個空表，則沒有解，失敗退出。否則繼續。人工智能原理ppt課件O

規則庫

搜索樹：

R1R2A.B.R1:

如X/12為整，則X/6為整。R2R3R1R4C.D.E..R2:

如X/20為整，則X/10為整R3R4R2R3R4S

F..G.HIR3:

如X/6為整，則X/2為整。R4SR4R4SR4:

如X/10為整，則X/5為整。S

S

S

輸入數據庫：N/12，N/20S=success

判斷是否N/5OOABOOABCDOABCDESOPEN表CLOSED表OBSR2R4(回溯)

寬度優先搜索方法能夠保證在搜索樹中找到一條通向目標節點的最短途徑。注：1、在OPEN表中已有的節點，新擴展有關節點不放OPEN表中。

2、CLOSED表中所放節點位置前后不重要。OABOOABCDOABCDESOPEN表CLOSED表O人工智能原理ppt課件64644.1.2深度優先搜索另一種盲目（無信息）搜索叫做深度優先搜索。在深度優先搜索中，我們首先擴展最新產生的（即最深的）節點。節點深度定義如下：(1)起始節點（即根節點）的深度為0。(2)任何其它節點的深度等于其父輩節點深度加1。首先、擴展最深的節點的結果使得搜索沿著狀態空間某條單一的路徑從起始節點向下進行下去；只有當搜索到達一個沒有后裔的狀態時，它才考慮另一條替代的路徑。4.1.2深度優先搜索

對于許多問題，其狀態空間搜索樹的深度可能為無限深，或者可能至少要比某個可接收的解答序列的已知深度上限還要深。為了避免考慮太長的路徑（防止搜索過程沿著無益的路徑擴展下去），往往給出一個節點擴展的最大深度—深度界限。任何節點如果達到了深度界限，那么都將它們作為沒有后繼節點處理。和寬度優先法不同之處在于：擴展的節點，其后繼節點放入OPEN表的前端對于許多問題，其狀態空間搜索樹的深度可能為無限深

O

規則庫

搜索樹：

R1R2A.B.R1:

如X/12為整，則X/6為整。R2R3R1R4C.D.E..R2:

如X/20為整，則X/10為整R3R4R2R3R4S

F..G.HIR3:

如X/6為整，則X/2為整。R4SR4R4SR4:

如X/10為整，則X/5為整。S

S

S

輸入數據庫：N/12，N/20S=success

判斷是否N/5

OABOOACDBOACFSDBOPEN表CLOSED表OACSR1R2R4(回溯)

三步操作，不是最短。如知道最短2步，深度界限定為2，肯定有解且可找到最短路徑。但有些情況下（多數），不限定深度不好。

OABOOACDBOACFSDBOPEN表CLOSED表O4.2

啟發式搜索

盲目搜索的效率低，耗費過多的計算空間與時間。如果能夠找到一種用于排列待擴展節點的順序，即選擇最有希望的節點加以擴展，那么，搜索效率將會大大提高。“啟發”（heuristic）是關于發現和發明規則及方法的研究。在狀態空間搜索中，啟發式被定義為一系列規則，它從狀態空間中選擇最有希望到達問題解的路徑。4.2啟發式搜索

人工智能求解者在兩種基本情況下運用啟發式策略：(1)一個問題由于問題陳述和數據獲取方面固有的模糊性可能使它沒有一個確定的解。醫療診斷即是一例：所給出的一系列癥狀可能有多個原因，醫生運用啟發式搜索來選擇最有可能的論斷，并依此產生治療計劃。視覺問題又是一例。看到的景物經常是模糊的。各方面原因造成。河和橋、馬路。海面上船、鯨魚或潛水艇。視覺系統可運用啟發式策略選擇一給定景像的最有可能的解釋。人工智能求解者在兩種基本情況下運用啟發式策略：

(2)一個問題可能有確定解，但是求解過程中的計算機的代價令人難以接收。

在很多問題上（如象棋）中，狀態空間的增長特別快，可能的狀態數隨著搜索的深度呈指數級增長、分解。在這種情況下，用盲目搜索的辦法就不行了（不象前面所舉的簡單例子）。給定棋局，可能的下一狀態、對手可能的應對步驟太多。這時需用啟發式策略通過指導搜索向最有希望的方向前進，以降低復雜性。通過刪除某些狀態及其延伸，以消除組合爆炸，并得到令人能接收的解。(2)一個問題可能有確定解，但是求解過程中的計算機的

然而，和發明創造的所有規則一樣，啟發式策略也是極易出錯的。在解決問題的過程中，啟發僅僅是下一步將要采取措施的一個猜想。常常根據經驗和直覺來判斷。由于只利用有限信息，一個啟發式搜索可能得到一個次最佳解，也有可能一無所獲。上述兩種情況第一種多出現在專家系統中，第二種情況多出現在博奕和定理證明中。下面的討論主要限制在第二種情況。在這種情況下，一般都是：初始狀態、算符和目標狀態的定義都是完全確定的，然后決定一個搜索空間。進行搜索時，一般需要某些有關具體領域的特性信息。我們把這種信息叫做啟發信息，并把利用啟發信息的搜索方法叫做啟發性搜索方法。然而，和發明創造的所有規則一樣，啟發式策略也是

在本節中，我們介紹一種有序搜索（也稱為最好優先搜索）方法。這種搜索總是選擇“最有希望”的節點作為下一個被擴展的節點。何為“最有希望”，取決于你所選的估價函數f(n)（性能指標）。有序搜索算法中，一個節點的希望程度越大，其估價函數值就越小。被選為擴展的節點，是估價函數最小的節點。給定一個問題后，根據問題的特性和解的特性，可以有多種方法定義估價函數，用不同的估價函數指導搜索，其效果可以相差很遠。如果選得不好，那么有序搜索就可能失去一個最好的解，甚至全部的解。

在本節中，我們介紹一種有序搜索（也稱為最好優先搜人工智能原理ppt課件人工智能原理ppt課件

對于八數碼難題，我們采用了簡單的估價函數

f(n)=d(n)+w(n)其中：d(n)是搜索樹中節點n的深度

w(n)用來計算對應于節點n的數據庫中錯放的棋子個數。也就是說，該估價函數考慮了兩個因數。第一個因數考慮希望節點距根節點（起始節點）越近越好，第二個因數考慮希望節點距目標節點看上去越近越好。考慮八數碼難題，其搜索過程見圖。

對于八數碼難題，我們采用了簡單的估價函數55第五章高級求解技術

第五章

上一章我們介紹了幾個基本的（早期的）搜索技術，如寬度優先、深度優先（盲目搜索）、有序搜索（啟發式搜索、最好優先）。對于許多比較復雜的系統和問題，用這些方法就很難甚至無法使問題獲得解決。這時，就需要應用一些更先進的推理求解技術。本章討論規則演繹系統、不確定性推理。上一章我們介紹了幾個基本的（早期的）搜索技術，如寬5.1規則演繹系統我們通常習慣用ifthen規則形式表示知識求解問題。基于規則的問題求解系統運用下述規則來建立，IF-THEN,即：

IFIF1 IF2

THENTHEN1 THEN2

其中：IF部分可能由幾個IF組成，而THEN部分可能由一個或一個以上的THEN組成。

5.1規則演繹系統

通常稱每個IF部分為前項（條件、斷言），THEN部分為后項（新斷言）。這種基于規則的系統叫做規則演繹系統。有時，THEN部分用于規定動作，這時稱這種基于規則的系統為反應式系統或產生式系統。通常稱每個IF部分為前項（條件、斷言），THE5.1.1規則正向演繹系統

(事實、規則、目標)

在基于規則的系統中，無論是規則演繹系統或規則產生式系統，均有兩種推理方式，即正向推理和逆向推理。從IF部分向THEN部分推理的過程，叫做正向推理。也就是說，正向推理是從事實或狀況向目標或動作進行操作的。反之，對于從THEN部分向IF部分推理的過程，叫做逆向推理。逆向推理是從目標或動作向事實或狀況進行操作的。1.事實表達式的與或形變換通常用謂詞演算公式來表示事實（用作事實表達式）。如事實表達式：(U)(V){Q(V,U)∧[(R(V)∨P(V))∧S(U,V)]}

通常還存在蘊含關系。

5.1.1規則正向演繹系統(事實、規則、目標)

在基于規則的正向演繹系統中，所要做的第一步是將其變換（或叫化成）非蘊含形式的與或形。要把一個公式化成與或形，可利用以下恒等式或方法：

(1)W1=>W2=W1∨W2（利用恒等式，去蘊含符號），在事實表達式中，很少有=>符號出現

(2)用德.摩根公式（定律）把否定符號移進括號內，直到每個否定符號都只含一個謂詞為止。在基于規則的正向演繹系統中，所要做

(3)對所得表達式進行skelem化，消除存在性量詞。XYmother(Y,X)Xmother(f(X),X)(4)刪去全稱量詞，而余下的變量都被認為具有全稱量化作用。

Q(V,f(V))∧{[(R(V)∧P(V))]∨S(f(V),V)}

(3)對所得表達式進行skelem化，消除存在性量詞。2.事實表達式的與或圖表示根節點

Q(V,f(V))∧{[(R(V)∧P(V))]∨S(f(V),V)}

與、合取

Q(V,f(V)) [(R(V)∧P(V))]∨S(f(V),V)

或、析取

R(V)∧P(V) S(f(V),V)葉節點

文字 R(V) P(V)2.事實表達式的與或圖表示

通常，把事實表達式的與或圖表示倒過來畫，即把根節點畫在最下面，而把其后繼節點往上畫。

3.與或圖的F規則變換我們把允許用作規則的公式類型限制為下列形式：

L=>W

式中，L是單文字；W是與或形表達式通常，把事實表達式的與或圖表示倒例如：事實表達式：P∨[S∧(T∨U)]

規則：S=>(X∧Y)∨Z

P∨[S∧(T∨U)]

P析取 S∧(T∨U)

S合取T∨U

S TU

Z X∧Y應用一條F規則L=>W

XY得到的與或圖例如：事實表達式：P∨[S∧(T∨U)]4.作為終止條件的目標公式應用F規則的目的在于從某個事實公式和某個規則集出發來證明某個目標公式。在正向推理系統中，這種目標表達式只限于可證明的表達式，尤其是可證明的文字析取形的目標公式表達式。

結論是：當正向演繹系統產生一個含有目標節點作為終止的解圖時，此系統就成功地終止。(目標可由葉節點析取得到)

對上圖，若目標為：P∨Z∨X或P∨Z∨Y時，就算證出。

4.作為終止條件的目標公式例：事實A∨B

規則A=>C∧D，B=>E∧G

目標C∨G（C∨E，D∨G，D∨E）

A∨B消解否證法

ABA∨CCGB∨G

ABA∨BAB

CDEGB

CG空

把規則化為子句形式：A∨C，A∨D，B∨E，B∨G

目標否定：C∨G，其子句形式為C，G例：事實A∨B把規則化為子句形式：A∨C，A∨5.1.2規則逆向演繹系統基于規則的逆向演繹系統，其操作過程與正向演繹系統相反，即為從目標到事實的操作過程，從then到if的推理過程。1.目標表達式的與或形式逆向演繹系統能夠處理任意形式的目標表達式。首先，采用與變換事實表達式同樣的過程，把目標表達式化成與或形、即消去蘊含符號，把否定符號移進括號內，消去存在性量詞（skelem化）等。例：目標表達式

YX{P(X)=>[Q(X,Y)∧[R(X)∧S(Y)]]}

化成與或形

P(f(Y))∨{Q(f(Y),Y)∧[R(f(Y))∨S(Y)]}5.1.2規則逆向演繹系統

與事實表達式的與或圖不同的是，對于目標表達式，與或圖中的連接符用來區分合取關系的子表達式。

P(f(Y))∨{Q(f(Y),Y)∧[R(f(Y))∨S(Y)]}

或、析取

P(f(Y)) Q(f(Y),Y)∧[R(f(Y))∨S(Y)]

與、合取

Q(f(Y),Y) R(f(Y))∨S(Y) R(f(Y))S(Y)

該目標公式的子句集為：P(f(Y))，Q(f(Y),Y)∧R(f(Y))，Q(f(Y),Y)∧S(Y)

可從終止在葉節點上的解圖集讀出。目標子句是文字的合取，目標表達式就是這些子句的析取。

與事實表達式的與或圖不同的是，對于目標表達式，2.與或圖的B規則變換現在把這些B規則限制為：W=>LW為任一與或形表達式，L為文字。

W=>(L1∧L2)可以化為兩個規則：

W=>L1和(∧)W=>L23.作為終止條件的事實節點的一致解圖逆向系統中的事實表達式均限制為文字合取形。逆向系統成功的終止條件是與或圖包含有某個終止在事實節點上的一致解圖。下面討論一個簡單的例子，看看基于規則的逆向演繹系統是怎樣工作的。2.與或圖的B規則變換例：事實F1：狗（FD）；F2：叫（FD）；

F3：搖尾（FD）；F4：貓（MT）規則：R1：搖尾（X）∧狗（X）=>溫順（X）

R2:溫順（X）∧叫（X）=>可怕（X）

問題：是否存在這樣的一只貓和一只狗，使得這只貓不怕這條狗。用目標表達式表示為：

XY[貓（Y）∧狗（X）∧可怕(Y，X)]例：事實F1：狗（FD）；F2：叫（FD）；

貓（Y）∧狗（X）∧可怕(Y，X)

貓（Y） 狗（X） 可怕(Y，X){MT/Y}{FD/X}

貓（MT）

狗（FD） 可怕(Y，X) R2

叫（X）溫順(X) {FD/X}

叫（FD） 溫順(X)

逆向系統的一致解圖 R1

紅色節點為事實節點 搖尾(X)狗（X）

{FD/X}{FD/X}

搖尾(FD)狗（FD）終止在事實節點前的置換為{MT/Y}，{FD/X}。把它應用到目標表達式，就得到了該問題的解答。

貓（Y）∧狗（X）∧可怕5.1.3規則雙向演繹系統

在上兩節中，我們所討論的基于規則的正向演繹系統和逆向演繹系統都具有局限性（正向L=>W，逆向W=>L）。我們希望能夠構成一個組合的系統，使它具有正向和逆向兩系統的優點，以克服各自的缺點（局限性）。這個系統就是我們所要研究的規則雙向演繹系統。不斷用F規則和B規則對與或圖進行擴展，進行適當的置換與合一。一個簡單的終止條件是某個判定與或圖根節點是否為可解過程的直接歸納。這個終止條件是建立在事實節點和目標節點的一種叫做CANCEL的對稱關系的基礎上的。

5.1.3規則雙向演繹系統5.2不確定性推理對于許多比較復雜的人工智能系統，往往含有復雜性、不完全性、模糊性和不確定性。當采用產生式系統或專家系統的結構時，要求設計者建立某種不確定性的計算和推理過程。有兩種不確定性，即關于證據的不確定性和關于規則的不確定性。5.2不確定性推理5.2.1關于證據的不確定性觀察事物時，所看到的事實經常具有某種不確定性。例如，當你觀察某種動物的顏色時，你可能說這種動物的顏色看起來是白色的，但也可能是灰色的。這就是說，你的觀察帶有某種程度的不確定性，導致證據的不確定性。一般，通過對事實賦于一個介于0和1之間的系數來表示事實的不確定性。1代表完全確定，0代表完全不確定。這個系數被稱為可信度。當規則具有一個以上的條件時，就需要根據各條件的可信度求得總條件部分的可信度。已有的方法有兩類：

5.2.1關于證據的不確定性1.以模糊集理論為基礎的方法按這種方法，把所有條件中最小的可信度作為總條件的可信度，看起來好像是符合模糊集理論的。CT=minCT0.90.70.71.0

有時把這種處理可信度的方法，稱之為以模糊集理論為基礎的方法。在MYCIN系統中主要采用這種方法。這種方法類似于當把幾根繩子連接起來使用時，總的繩子強度與強度最差的繩子的強度相同。1.以模糊集理論為基礎的方法2.以概率為基礎的方法

總的證據可信度為各證據可信度的乘積。CT=CT1*…*CTn0.90.70.631.0

探礦專家系統PROSPECTOR就采用這種方法。

2.以概率為基礎的方法5.2.2關于規則和結論的不確定性規則的不確定性，它表示當規則的條件被完全滿足時，產生某種結論的不確定程度。它也是以賦予規則在0和1之間的系數的方法來表示的。

例如：規則：如果啟動器發出刺耳的噪聲 那么這個啟動器壞的可能性是0.8

該規則表示，如果事實完全肯定（1.0），那么結論的可信度為0.8。如果規則的條件部分不完全確定，即條件可信度不為1，此時求結論的可信度簡單方法：

5.2.2關于規則和結論的不確定性結論的可信度為條件可信度與規則可信度的乘積

CJ=CG*CT0.50.80.4

Cout

規則不確定性

5.2.3多個規則支持同一結論的不確定性當多個規則支持同一結論時，如何根據這些規則結論的可信度求得該結論的可信度呢，同樣有兩種方法。規則：如果該動物有毛發那么它是哺乳動物規則：如果該動物能產乳那么它是哺乳動物結論的可信度為條件可信度與規則可信度的乘積1.基于模糊集理論的方法

取支持該結論的各規則的結論可信度的最大值作為結論的可信度。（規則1的結論可信度CJ1為0.9，規則2的結論可信度CJ2為0.25，則總的結論可信度CJ為0.9）

CJ=maxCJii

1.基于模糊集理論的方法2.基于概率論的方法定義：規則i的結論可信度為CJi，可信性比例為RJi。一組規則支持結論的可信度，可用以下方法求得：（1）首先把各規則結論的可信度CJi轉換成可信性比例RJi。可信性比例RJi和可信度CJi之間的關系為：

RJi=CJi/(1-CJi)， CJi=RJi/(1+RJi)（2）把各規則結論的可信性比例RJi相乘以求得這些規則所支持結論的可信性比例。

RJ=RJ1*RJ2*…*RJn

（3）按公式求結論的可信度CJ:CJ=RJ/(1+RJ)

2.基于概率論的方法

當條件不確定性、規則不確定性、多個規則支持同一結論時，可按順序依次解決。

MYCIN醫療專家系統采用反向推理和深度優先搜索的方法，用到不確定性推理方法，它用于診斷和治療感染性疾病。步驟4個：1.確定患者有無需要治療的細菌性感染。2.確定可能引起感染的有機體。3.確定對引起感染的有機體有抑制作用的藥物。4.選擇一種或幾種對治療患者的感染是最合適的藥物。前兩步診斷，后兩步治療。有咨詢模塊、動態數據庫（推理記錄）、解釋模塊、知識庫等。

當條件不確定性、規則不確定性、多個規則支持同一結論第四章一般搜索原理

第四章

知識表示的目的是為了便于計算機求解，是為了解決問題。從問題的描述（表示）到問題的解決，有個求解的過程，也就是搜索過程。在這一過程中采用適當的搜索技術，包括各種規則、過程和算法等推理技術，力求找到問題的解答。本章討論一些早期的搜索技術或用于解決比較簡單問題的搜索原理（啟發式搜索、寬度優先、深度優先、有序搜索）。知識表示的目的是為了便于計算機求解，是為了解決問題4.1盲目搜索盲目搜索又叫做無信息搜索。一般只適用于求解比較簡單的問題。

4.1盲目搜索

O

規則庫

搜索樹：R1R2A.B.R1:

如X/12為整，則X/6為整。R2R3R1R4C.D.E..R2:

如X/20為整，則X/10為整R3R4R2R3R4S

F..G.HIR3:

如X/6為整，則X/2為整。R4SR4R4SR4:

如X/10為整，則X/5為整。S

S

S

輸入數據庫：N/12，N/20S=success

判斷是否N/5

這是一個產生式系統的例子。節點用表示。每一個節點對應于一個狀態，反映當時數據庫的情況。如節點O：N/12，N/20；節點A：N/12，N/20，N/6；節點D：N/12，N/20，N/6，N/2。每條連線對應于一個操作符。

棋局對應走步，這里對應于一條產生式規則。

這是一個產生式系統的例子。

該搜索樹給出了所有可能的求解證明渠道。抽象地描述：給定初始節點和目標節點，求圖中的一條合理路徑（所謂合理有的指只要找到就行；有的要求搜索步驟最少或路徑最短等等）。就這個例子，我們看一下寬度優先搜索、深度優先搜索是如何進行的。當然，并不是所有問題都可以畫出圖示的搜索樹（深度不深、每條支路都有解且支路不多）。

該搜索樹給出了所有可能的求解證明渠道。抽象地描述：4.1.1寬度優先搜索

如果搜索是以接近起始節點的程度依次擴展節點的，那么這種搜索就叫做寬度優先搜索。也就是說，這種搜索是逐層進行的。在對下一層的任一節點進行搜索之前，必須搜索完本層的所有節點。寬度優先搜索算法（流程框圖）如下：（1）把起始節點放到OPEN表中（如果該起始節點為目標節點，則求得一個解答）。OPENCLOSED

O4.1.1寬度優先搜索O（2）如果OPEN表是個空表，則沒有解，失敗退出。否則繼續。（3）把第一個節點從OPEN表中移出，并把它放入CLOSED的擴展節點表中。（4）擴展該節點。如果沒有后繼節點，則轉向上述第（2）步。（5）把該節點的所有后繼節點放到OPEN表的末端，并提供這些后繼節點返回該節點的指針。（6）如果該節點的任一個后繼節點是個目標節點，則找到一個解答，成功退出；否則轉向（2）。（2）如果OPEN表是個空表，則沒有解，失敗退出。否則繼續。人工智能原理ppt課件O

規則庫

搜索樹：

R1R2A.B.R1:

如X/12為整，則X/6為整。R2R3R1R4C.D.E..R2:

如X/20為整，則X/10為整R3R4R2R3R4S

F..G.HIR3:

如X/6為整，則X/2為整。R4SR4R4SR4:

如X/10為整，則X/5為整。S

S

S

輸入數據庫：N/12，N/20S=success

判斷是否N/5OOABOOABCDOABCDESOPEN表CLOSED表OBSR2R4(回溯)

寬度優先搜索方法能夠保證在搜索樹中找到一條通向目標節點的最短途徑。注：1、在OPEN表中已有的節點，新擴展有關節點不放OPEN表中。

2、CLOSED表中所放節點位置前后不重要。OABOOABCDOABCDESOPEN表CLOSED表O人工智能原理ppt課件64644.1.2深度優先搜索另一種盲目（無信息）搜索叫做深度優先搜索。在深度優先搜索中，我們首先擴展最新產生的（即最深的）節點。節點深度定義如下：(1)起始節點（即根節點）的深度為0。(2)任何其它節點的深度等于其父輩節點深度加1。首先、擴展最深的節點的結果使得搜索沿著狀態空間某條單一的路徑從起始節點向下進行下去；只有當搜索到達一個沒有后裔的狀態時，它才考慮另一條替代的路徑。4.1.2深度優先搜索

對于許多問題，其狀態空間搜索樹的深度可能為無限深，或者可能至少要比某個可接收的解答序列的已知深度上限還要深。為了避免考慮太長的路徑（防止搜索過程沿著無益的路徑擴展下去），往往給出一個節點擴展的最大深度—深度界限。任何節點如果達到了深度界限，那么都將它們作為沒有后繼節點處理。和寬度優先法不同之處在于：擴展的節點，其后繼節點放入OPEN表的前端對于許多問題，其狀態空間搜索樹的深度可能為無限深

O

規則庫

搜索樹：

R1R2A.B.R1:

如X/12為整，則X/6為整。R2R3R1R4C.D.E..R2:

如X/20為整，則X/10為整R3R4R2R3R4S

F..G.HIR3:

如X/6為整，則X/2為整。R4SR4R4SR4:

如X/10為整，則X/5為整。S

S

S

輸入數據庫：N/12，N/20S=success

判斷是否N/5

OABOOACDBOACFSDBOPEN表CLOSED表OACSR1R2R4(回溯)

三步操作，不是最短。如知道最短2步，深度界限定為2，肯定有解且可找到最短路徑。但有些情況下（多數），不限定深度不好。

OABOOACDBOACFSDBOPEN表CLOSED表O4.2

啟發式搜索

盲目搜索的效率低，耗費過多的計算空間與時間。如果能夠找到一種用于排列待擴展節點的順序，即選擇最有希望的節點加以擴展，那么，搜索效率將會大大提高。“啟發”（heuristic）是關于發現和發明規則及方法的研究。在狀態空間搜索中，啟發式被定義為一系列規則，它從狀態空間中選擇最有希望到達問題解的路徑。4.2啟發式搜索

人工智能求解者在兩種基本情況下運用啟發式策略：(1)一個問題由于問題陳述和數據獲取方面固有的模糊性可能使它沒有一個確定的解。醫療診斷即是一例：所給出的一系列癥狀可能有多個原因，醫生運用啟發式搜索來選擇最有可能的論斷，并依此產生治療計劃。視覺問題又是一例。看到的景物經常是模糊的。各方面原因造成。河和橋、馬路。海面上船、鯨魚或潛水艇。視覺系統可運用啟發式策略選擇一給定景像的最有可能的解釋。人工智能求解者在兩種基本情況下運用啟發式策略：

(2)一個問題可能有確定解，但是求解過程中的計算機的代價令人難以接收。

在很多問題上（如象棋）中，狀態空間的增長特別快，可能的狀態數隨著搜索的深度呈指數級增長、分解。在這種情況下，用盲目搜索的辦法就不行了（不象前面所舉的簡單例子）。給定棋局，可能的下一狀態、對手可能的應對步驟太多。這時需用啟發式策略通過指導搜索向最有希望的方向前進，以降低復雜性。通過刪除某些狀態及其延伸，以消除組合爆炸，并得到令人能接收的解。(2)一個問題可能有確定解，但是求解過程中的計算機的

然而，和發明創造的所有規則一樣，啟發式策略也是極易出錯的。在解決問題的過程中，啟發僅僅是下一步將要采取措施的一個猜想。常常根據經驗和直覺來判斷。由于只利用有限信息，一個啟發式搜索可能得到一個次最佳解，也有可能一無所獲。上述兩種情況第一種多出現在專家系統中，第二種情況多出現在博奕和定理證明中。下面的討論主要限制在第二種情況。在這種情況下，一般都是：初始狀態、算符和目標狀態的定義都是完全確定的，然后決定一個搜索空間。進行搜索時，一般需要某些有關具體領域的特性信息。我們把這種信息叫做啟發信息，并把利用啟發信息的搜索方法叫做啟發性搜索方法。然而，和發明創造的所有規則一樣，啟發式策略也是

在本節中，我們介紹一種有序搜索（也稱為最好優先搜索）方法。這種搜索總是選擇“最有希望”的節點作為下一個被擴展的節點。何為“最有希望”，取決于你所選的估價函數f(n)（性能指標）。有序搜索算法中，一個節點的希望程度越大，其估價函數值就越小。被選為擴展的節點，是估價函數最小的節點。給定一個問題后，根據問題的特性和解的特性，可以有多種方法定義估價函數，用不同的估價函數指導搜索，其效果可以相差很遠。如果選得不好，那么有序搜索就可能失去一個最好的解，甚至全部的解。

在本節中，我們介紹一種有序搜索（也稱為最好優先搜人工智能原理ppt課件人工智能原理ppt課件

對于八數碼難題，我們采用了簡單的估價函數

f(n)=d(n)+w(n)其中：d(n)是搜索樹中節點n的深度

w(n)用來計算對應于節點n的數據庫中錯放的棋子個數。也就是說，該估價函數考慮了兩個因數。第一個因數考慮希望節點距根節點（起始節點）越近越好，第二個因數考慮希望節點距目標節點看上去越近越好。考慮八數碼難題，其搜索過程見圖。

對于八數碼難題，我們采用了簡單的估價函數55第五章高級求解技術

第五章

上一章我們介紹了幾個基本的（早期的）搜索技術，如寬度優先、深度優先（盲目搜索）、有序搜索（啟發式搜索、最好優先）。對于許多比較復雜的系統和問題，用這些方法就很難甚至無法使問題獲得解決。這時，就需要應用一些更先進的推理求解技術。本章討論規則演繹系統、不確定性推理。上一章我們介紹了幾個基本的（早期的）搜索技術，如寬5.1規則演繹系統我們通常習慣用ifthen規則形式表示知識求解問題。基于規則的問題求解系統運用下述規則來建立，IF-THEN,即：

IFIF1 IF2

THENTHEN1 THEN2

其中：IF部分可能由幾個IF組成，而THEN部分可能由一個或一個以上的THEN組成。

5.1規則演繹系統

通常稱每個IF部分為前項（條件、斷言），THEN部分為后項（新斷言）。這種基于規則的系統叫做規則演繹系統。有時，THEN部分用于規定動作，這時稱這種基于規則的系統為反應式系統或產生式系統。通常稱每個IF部分為前項（條件、斷言），THE5.1.1規則正向演繹系統

(事實、規則、目標)

在基于規則的系統中，無論是規則演繹系統或規則產生式系統，均有兩種推理方式，即正向推理和逆向推理。從IF部分向THEN部分推理的過程，叫做正向推理。也就是說，正向推理是從事實或狀況向目標或動作進行操作的。反之，對于從THEN部分向IF部分推理的過程，叫做逆向推理。逆向推理是從目標或動作向事實或狀況進行操作的。1.事實表達式的與或形變換通常用謂詞演算公式來表示事實（用作事實表達式）。如事實表達式：(U)(V){Q(V,U)∧[(R(V)∨P(V))∧S(U,V)]}

通常還存在蘊含關系。

5.1.1規則正向演繹系統(事實、規則、目標)

在基于規則的正向演繹系統中，所要做的第一步是將其變換（或叫化成）非蘊含形式的與或形。要把一個公式化成與或形，可利用以下恒等式或方法：

(1)W1=>W2=W1∨W2（利用恒等式，去蘊含符號），在事實表達式中，很少有=>符號出現

(2)用德.摩根公式（定律）把否定符號移進括號內，直到每個否定符號都只含一個謂詞為止。在基于規則的正向演繹系統中，所要做

(3)對所得表達式進行skelem化，消除存在性量詞。XYmother(Y,X)Xmother(f(X),X)(4)刪去全稱量詞，而余下的變量都被認為具有全稱量化作用。

Q(V,f(V))∧{[(R(V)∧P(V))]∨S(f(V),V)}

(3)對所得表達式進行skelem化，消除存在性量詞。2.事實表達式的與或圖表示根節點

Q(V,f(V))∧{[(R(V)∧P(V))]∨S(f(V),V)}

與、合取

Q(V,f(V)) [(R(V)∧P(V))]∨S(f(V),V)

或、析取

R(V)∧P(V) S(f(V),V)葉節點

文字 R(V) P(V)2.事實表達式的與或圖表示

通常，把事實表達式的與或圖表示倒過來畫，即把根節點畫在最下面，而把其后繼節點往上畫。

3.與或圖的F規則變換我們把允許用作規則的公式類型限制為下列形式：

L=>W

式中，L是單文字；W是與或形表達式通常，把事實表達式的與或圖表示倒例如：事實表達式：P∨[S∧(T∨U)]

規則：S=>(X∧Y)∨Z

P∨[S∧(T∨U)]

P析取 S∧(T∨U)

S合取T∨U

S TU

Z X∧Y應用一條F規則L=>W

XY得到的與或圖例如：事實表達式：P∨[S∧(T∨U)]4.作為終止條件的目標公式應用F規則的目的在于從某個事實公式和某個規則集出發來證明某個目標公式。在正向推理系統中，這種目標表達式只限于可證明的表達式，尤其是可證明的文字析取形的目標公式表達式。

結論是：當正向演繹系統產生一個含有目標節點作為終止的解圖時，此系統就成功地終止。(目標可由葉節點析取得到)

對上圖，若目標為：P∨Z∨X或P∨Z∨Y時，就算證出。

4.作為終止條件的目標公式例：事實A∨B

規則A=>C∧D，B=>E∧G

目標C∨G（C∨E，D∨G，D∨E）

A∨B消解否證法

ABA∨CCGB∨G

ABA∨BAB

CDEGB

CG空

把規則化為子句形式：A∨C，A∨D，B∨E，B∨G

目標否定：C∨G，其子句形式為C，G例：事實A∨B把規則化為子句形式：A∨C，A∨5.1.2規則逆向演繹系統基于規則的逆向演繹系統，其操作過程與正向演繹系統相反，即為從目標到事實的操作過程，從then到if的推理過程。1.目標表達式的與或形式逆向演繹系統能夠處理任意形式的目標表達式。首先，采用與變換事實表達式同樣的過程，把目標表達式化成與或形、即消去蘊含符號，把否定符號移進括號內，消去存在性量詞（skelem化）等。例：目標表達式

YX{P(X)=>[Q(X,Y)∧[R(X)∧S(Y)]]}

化成與或形

P(f(Y))∨{Q(f(Y),Y)∧[R(f(Y))∨S(Y)]}5.1.2規則逆向演繹系統

與事實表達式的與或圖不同的是，對于目標表達式，與或圖中的連接符用來區分合取關系的子表達式。

P(f(Y))∨{Q(f(Y),Y)∧[R(f(Y))∨S(Y)]}

或、析取

P(f(Y)) Q(f(Y),Y)∧[R(f(Y))∨S(Y)]

與、合取

Q(f(Y),Y) R(f(Y))∨S(Y) R(f(Y))S(Y)

該目標公式的子句集為：P(f(Y))，Q(f(Y),Y)∧R(f(Y))，Q(f(Y),Y)∧S(Y)

可從終止在葉節點上的解圖集讀出。目標子句是文字的合取，目標表達式就是這些子句的析取。

與事實表達式的與或圖不同的是，對于目標表達式，2.與或圖的B規則變換現在把這些B規則限制為：W=>LW為任一與或形表達式，L為文字。

W=>(L1∧L2)可以化為兩個規則：

W=>L1和(∧)W=>L23.作為終止條件的事實節點的一致解圖逆向系統中的事實表達式均限制為文字合取形。逆向系統成功的終止條件是與或圖包含有某個終止在事實節點上的一致解圖。下面討論一個簡單的例子，看看基于規則的逆向演繹系統是怎樣工作的。2.與或圖的B規則變換例：事實F1：狗（FD）；F2：叫（FD）；

F3：搖尾（FD）；F4：貓（MT）規則：R1：搖尾（X）∧狗（X）=>溫順（X）

R2:溫順（X）∧叫（X）=>可怕（X）

問題：是否存在這樣的一只貓和一只狗，使得這只貓不怕這條狗。用目標表達式表示為：

XY[貓（Y）∧狗（X）∧可怕(Y，X)]例：事實F1：狗（FD）；F2：叫（FD）；

貓（Y）∧狗（X）∧可怕(Y，X)

貓（Y） 狗（X） 可怕(Y，X){MT/Y}{FD/X}

貓（MT）

狗（FD） 可怕(Y，X) R2

叫（X）溫順(X) {FD/X}

叫（FD） 溫順(X)

逆向系統的一致解圖 R1

紅色節點為事實節點 搖尾(X)狗（X）

{FD/X}{FD/X}