人工智能經(jīng)典推理第一頁，共九十八頁，編輯于2023年，星期五3.1圖搜索策略圖搜索控制策略

一種在圖中尋找路徑的方法。

圖中每個節(jié)點對應一個狀態(tài)，每條連線對應一個操作符。這些節(jié)點和連線(即狀態(tài)與操作符)又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫和規(guī)則來標記。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價于求得圖中的一條路徑問題。第二頁，共九十八頁，編輯于2023年，星期五一般圖搜索過程

狀態(tài)空間搜索的基本思想是：先把問題的初始狀態(tài)作為當前擴展節(jié)點對其進行擴展，生成一組子節(jié)點，然后檢查問題的目標狀態(tài)是否出現(xiàn)在這些子節(jié)點中。若出現(xiàn)，則搜索成功，找到了該問題的解；若沒出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點中選擇一個節(jié)點作為當前擴展節(jié)點。重復上述過程，直到目標狀態(tài)出現(xiàn)在子節(jié)點中或沒有可供擴展的節(jié)點為止。搜索術語（用圖來描述狀態(tài)空間）節(jié)點：對應于狀態(tài)描述節(jié)點深度：根節(jié)點的深度為0,其他節(jié)點的深度規(guī)定為父節(jié)點深度加1,即dn+1=dn+1。第三頁，共九十八頁，編輯于2023年，星期五擴展節(jié)點：應用操作符將上一狀態(tài)（節(jié)點ni）變遷到下一狀態(tài)（節(jié)點nj），ni表示被擴展節(jié)點，nj

即是由ni

擴展出的子節(jié)點。路徑：從節(jié)點ni到nk的路徑是由相鄰節(jié)點間的弧線構成的折線，通常要求路徑是無環(huán)的，否則會導致搜索過程進入死循環(huán)。搜索圖：在搜索解答路徑的過程中只畫出搜索時直接涉及到的節(jié)點和弧線，構成所謂的搜索圖。Open表：存放已經(jīng)生成但未擴展節(jié)點Close表：存放已擴展或?qū)⒁獢U展的節(jié)點S0表示問題的初始狀態(tài)G表示搜索過程所得到的搜索圖M表示當前擴展節(jié)點新生成的且不為自己先輩的子節(jié)點集。第四頁，共九十八頁，編輯于2023年，星期五開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表n為目標節(jié)點嗎？把n的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針修改指針方向重排OPEN表失敗成功圖3.1

圖搜索過程框圖是是否否圖搜索過程圖樹/不修改指針;圖/修改指針;修改指針:找最優(yōu)解第五頁，共九十八頁，編輯于2023年，星期五3.2

盲目搜索特點：不需重排OPEN表種類：寬度優(yōu)先、深度優(yōu)先、等代價搜索等。3.2.1

寬度優(yōu)先搜索定義以接近起始節(jié)點的程度逐層擴展節(jié)點的搜索方法。特點：一種高代價搜索，但若有解存在，則必能找到它。算法第六頁，共九十八頁，編輯于2023年，星期五開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表是否有后繼節(jié)點為目標節(jié)點？擴展n，把n的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針失敗成功圖3.2寬度優(yōu)先算法框圖是否是否3.2盲目搜索第七頁，共九十八頁，編輯于2023年，星期五例：八數(shù)碼難題

3×3九宮棋盤，放置數(shù)碼為1-8的8個棋牌，剩下一個空格，只能通過棋牌向空格的移動來改變棋盤的布局。求解的問題——給定初始布局（即初始狀態(tài)）和目標布局（即目標狀態(tài)），如何移動棋牌才能從初始布局到達目標布局解答路徑——就是一個合法的走步序列用寬度優(yōu)先搜索方法解決該問題：

為問題狀態(tài)的表示建立數(shù)據(jù)結構：3×3的一個矩陣，*矩陣元素Sij∈{0,1,…,8}；其中1≤i,j≤3，*數(shù)字0指示空格，*數(shù)字1-8指示相應棋牌。第八頁，共九十八頁，編輯于2023年，星期五制定操作算子集：*直觀方法——為每個棋牌制定一套可能的走步：左、上、右、下四種移動。這樣就需32個操作算子。*簡易方法——僅為空格制定這4種走步，因為只有緊靠空格的棋牌才能移動。*空格移動的唯一約束是不能移出棋盤。初始狀態(tài)S0：23目標狀態(tài)Sg：123 184 804 765765第九頁，共九十八頁，編輯于2023年，星期五23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標8234187654寬度優(yōu)先搜索91011121314151617從圖中得，解的路徑是：S0→→→3817第十頁，共九十八頁，編輯于2023年，星期五3.2.2

深度優(yōu)先搜索定義首先擴展最新產(chǎn)生的(即最深的)節(jié)點。算法防止搜索過程沿著無益的路徑擴展下去，往往給出一個節(jié)點擴展的最大深度——深度界限。與寬度優(yōu)先搜索算法最根本的不同在于：將擴展的后繼節(jié)點放在OPEN表的前端。（算法框圖見教材）3.2盲目搜索第十一頁，共九十八頁，編輯于2023年，星期五例：八數(shù)碼難題

231847652318476528314765231847652831476528316475283147652831647528316475123784651238476528364175123412384765目標深度優(yōu)先搜索…………第十二頁，共九十八頁，編輯于2023年，星期五2318476523184765283147652318476528314765283164752831476528316475283164752837146583214765281437652831457612378465123847652836417528316754832147652837146528143765283145761234567891011121312384765目標設深度界限dm=4例：八數(shù)碼難題

第十三頁，共九十八頁，編輯于2023年，星期五3.2.3

等代價搜索定義

是寬度優(yōu)先搜索的一種推廣，不是沿著等長度路徑斷層進行擴展，而是沿著等代價路徑斷層進行擴展。搜索樹中每條連接弧線上的有關代價,表示時間、距離等花費。算法若所有連接弧線具有相等代價，則簡化為寬度優(yōu)先搜索算法。3.2盲目搜索第十四頁，共九十八頁，編輯于2023年，星期五3.3

啟發(fā)式搜索特點：重排OPEN表，選擇最有希望的節(jié)點加以擴展種類：有序搜索(A算法)、A*算法等3.3.1啟發(fā)式搜索策略和估價函數(shù)盲目搜索可能帶來組合爆炸啟發(fā)式信息

用來加速搜索過程的有關問題領域的特征信息。包括：用于決定要擴展的下一個節(jié)點的信息；在擴展一個節(jié)點時，用于決定要生成哪一個或哪幾個后繼節(jié)點的信息；用于決定某些應該從搜索樹中拋棄或修剪的節(jié)點的信息；啟發(fā)式搜索使用啟發(fā)式信息指導的搜索過程稱為啟發(fā)式搜索.第十五頁，共九十八頁，編輯于2023年，星期五

估價函數(shù)用來估算節(jié)點處于最佳求解路徑上的希望程度的函數(shù)f(n)=g(n)+h(n)n——搜索圖中的某個當前被擴展的節(jié)點；f(n)——從初始狀態(tài)節(jié)點s,經(jīng)由節(jié)點n到達目標節(jié)點ng，估計的最小路徑代價；g(n)——從s到n的實際路徑代價；h(n)——從n到ng,估計的最小路徑代價。例——八數(shù)碼難題估價函數(shù)：f(n)=d(n)+w(n) 其中：d(n)為n的深度 w(n)為不在位的棋子數(shù)

如起始節(jié)點 283 164 705 則起始節(jié)點S0的估價函數(shù)值為：f( S0)=0+4=4

第十六頁，共九十八頁，編輯于2023年，星期五3.3.2

有序搜索實質(zhì)

選擇OPEN表上具有最小f值的節(jié)點作為下一個要擴展的節(jié)點。3.3啟發(fā)式搜索(1)全局擇優(yōu)搜索：選擇OPEN表上具有最小f值的節(jié)點作為下一個要擴展的節(jié)點，即總是選擇最有希望的節(jié)點作為下一個要擴展的節(jié)點。(2)局部擇優(yōu)搜索：從剛生成的子節(jié)點中選擇具有最小f值的節(jié)點作為下一個要擴展的節(jié)點。第十七頁，共九十八頁，編輯于2023年，星期五開始把S放入OPEN表，計算估價函數(shù)f(s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點i放入CLOSED表i為目標節(jié)點嗎？擴展i，得后繼節(jié)點j，計算f(j)，提供返回節(jié)點i的指針，利用f(j)對OPEN表重新排序，調(diào)整親子關系及指針失敗成功圖3.9有序搜索算法框圖是否是否3.3啟發(fā)式搜索算法第十八頁，共九十八頁，編輯于2023年，星期五例子八數(shù)碼難題（8-puzzleproblem）12384567（目標狀態(tài)）12384567（初始狀態(tài)）八數(shù)碼難題的有序搜索樹見下圖：3.3啟發(fā)式搜索第十九頁，共九十八頁，編輯于2023年，星期五5714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（5）（7）圖3.10八數(shù)碼難題的有序搜索樹123846（4）73.3啟發(fā)式搜索5第二十頁，共九十八頁，編輯于2023年，星期五3.3.3A*算法估價函數(shù)的定義：

對節(jié)點n定義f*(n)=g*(n)+h*(n),表示從S開始約束通過節(jié)點n的一條最佳路徑的代價。

希望估價函數(shù)f定義為：f(n)=g(n)+h(n)

——g是g*的估計，h是h*的估計3.3啟發(fā)式搜索g*(n)：從s到n的最小路徑代價值h*(n)：從n到g的最小路徑代價值f*(n)=g*(n)+h*(n)：從s經(jīng)過n到g的最小路徑的總代價值g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計值g(n)通常選擇為當前所找到的從初始節(jié)點S到節(jié)點n的“最佳”路徑的代價值，顯然有g(n)g*(n)第二十一頁，共九十八頁，編輯于2023年，星期五在A算法中，如果滿足條件：

(1)

g(n)是對g*(n)的估計，且g(n)>0；(2)h(n)是h*(n)的下界，即對任意節(jié)點n均有 0≤h(n)≤h*(n)

則A算法稱為A*算法A*算法的定義：

定義1在GRAPHSEARCH過程中，如果第8步的重排OPEN表是依據(jù)f(n)=g(n)+h(n)進行的，則稱該過程為A算法。定義2在A算法中，如果對所有的n存在h(n)≤h*(n),則稱h(n)為h*(n)的下界，它表示某種偏于保守的估計。定義3采用h*(n)的下界h(n)為啟發(fā)函數(shù)的A算法，稱為A*算法。當h=0時，A*算法就變?yōu)橛行蛩阉魉惴ā?/p>

第二十二頁，共九十八頁，編輯于2023年，星期五

A*算法的可納性

對任一個圖，存在從S到目標的路徑，如果一個搜索算法總是結束在一條從S到目標的最佳路徑上，則稱此算法是可采納的。算法A*保證只要最短路徑存在，就一定能找出這條路徑，所以算法A*是可納的。

A*算法應用舉例八數(shù)碼難題估價函數(shù)：f(n)=d(n)+w(n) 其中：d(n)為n的深度 w(n)為不在位的棋子數(shù)取h(n)=w(n),則有w(n)≤h*(n),h(n)滿足A*算法的限制條件。第二十三頁，共九十八頁，編輯于2023年，星期五1238476528316475初始狀態(tài)目標狀態(tài)

在八數(shù)碼難題中,令估價函數(shù)

f(n)=d(n)+p(n)啟發(fā)函數(shù)h(n)=p(n),p(n)為不在位的棋子與其目標位置的距離之和，則有p(n)≤h*(n),滿足A*算法的限制條件。第二十四頁，共九十八頁，編輯于2023年，星期五283164752831476528316475283164752318476528314765283147652318476523184765123847651238476512378465目標12345h=5,g=0,f=5h=6,g=1,f=7h=4,g=1,f=5h=6,g=1,f=7h=5,g=2,f=7h=3,g=2,f=5h=5,g=2,f=7h=2,g=3,f=5h=4,g=3,f=7h=1,g=4,f=5h=0,g=5,f=5第二十五頁，共九十八頁，編輯于2023年，星期五w(n)——不在位的棋子數(shù)，不夠貼切，錯誤選用節(jié)點加以擴展。p(n)——更接近于h*(n)的h(n)，其值是節(jié)點n與目標狀態(tài)節(jié)點相比較，每個錯位棋子在假設不受阻攔的情況下，移動到目標狀態(tài)相應位置所需走步的總和。p(n)比w(n)更接近于h*(n)，因為p(n)不僅考慮了錯位因素，還考慮了錯位的距離（移動次數(shù)）。說明h值越大,啟發(fā)功能越強,搜索效率越高.特別地(1)h(n)=h*(n)

搜索僅沿最佳路徑進行,效率最高.(2)h(n)=0

無啟發(fā)信息,盲目搜索,效率低.(3)h(n)>h*(n)

是一般的A算法,效率高,但不能保證找到最佳路徑.有時為求解難題取h(n)>h*(n),以提高效率.第二十六頁，共九十八頁，編輯于2023年，星期五3.4博弈樹的啟發(fā)式搜索參與搜索的不只是一個主體，而包括對抗的多方(對弈)任何一方在選擇自己的行為時，都要將對方可能采取的對策考慮在內(nèi)由此而產(chǎn)生的搜索樹稱為博弈樹(博弈圖)博奕:兩棋手按一定規(guī)則輪流走步,雙方都知道對方的走步,當滿足一定條件時,走步結束,這時,或一方取勝,或為和局.1.博弈問題第二十七頁，共九十八頁，編輯于2023年，星期五

我方（指程序方，叫MAX）每走一著棋（半回合），都力圖使自己通向取勝的目標。輪到MAX走棋時，由于它掌握著出棋的主動權，只要此時的各種走法中有一個能通向勝局，它就會毫不客氣地出這一著。因此由MAX方出棋的結點具有或結點的性質(zhì)。對手（叫MIN，是一個回合的對棋者）每走一著棋（半回合），都力圖干擾MAX的選擇，使其偏離取勝的目標。輪到MIN走棋時，由于它掌握著對棋的主動權，因此只要此時的全部著法中有一個能導致敗局，它就會毫不客氣地出這一著。因此由MIN對棋的結點具有與終點的性質(zhì)。所以-博弈樹一般都是與／或樹。博弈樹的特點：（1）初始格局是初始節(jié)點（2）博弈樹中或節(jié)點和與節(jié)點逐層交替出現(xiàn)（3）所有能使自己一方獲勝的終局都是本原問題，而相應使對方獲勝的棋局均為不可解節(jié)點。第二十八頁，共九十八頁，編輯于2023年，星期五例分火柴游戲

設一堆火柴有7根，由MAX（我方）和MIN（對手）兩人輪流來分它們，要求每次都要把某一堆火柴分成不相等的兩部分，最后不能分下去的人為負，對方為勝。如果MIN先走，可以有三種選擇：（6，1）、（5，2）、（4，3）在每一種選擇下，MAX又可以有兩種走法，整個博弈過程的狀態(tài)空間如圖所示。結點中的數(shù)字表示各堆火柴的根數(shù)分布，名字表示輪到他繼續(xù)向下走棋。第二十九頁，共九十八頁，編輯于2023年，星期五(5,1,1,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(3,2,2,MIN)(4,2,1,MIN)(7,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(2,1,1,1,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)第三十頁，共九十八頁，編輯于2023年，星期五2.極大極小過程

極大極小搜索策略是考慮雙方對弈若干步之后,從可能的走步中選一步相對好棋的走法來走,即在有限的搜索深度范圍內(nèi)進行求解。定義一個靜態(tài)估計函數(shù)f,以便對棋局的勢態(tài)(節(jié)點)作出優(yōu)劣估值。一般規(guī)定有利于MAX的勢態(tài),f(p)取正值,有利于MIN的勢態(tài),f(p)取負值,勢均力敵的勢態(tài),f(p)取0值,若f(o)=+∞,則表示MAX贏,若f(o)=-∞,則表示MIN贏。在輪到MAX走時,選擇f(p)大的節(jié)點走;而輪到MIN走時,應考慮對方會選f(p)最小的節(jié)點走.因此,在博奕圖搜索時,可采用一步走f(p)值極大的節(jié)點(MAX走),一步走f(p)值極小的節(jié)點(MIN走),這樣交替前進的方法.這種搜索過程稱為極大極小過程.第三十一頁，共九十八頁，編輯于2023年，星期五例:一字棋 棋局中,我方(MAX)棋子用表示,對方(MIN)棋子用°表示.開始由我方先走,估價函數(shù):

我方獲勝e(p)=- 對方獲勝

e(+p)-e(-p)其他情況

空格視為時我方三連子數(shù)-空格視為°時對方三連子數(shù)°e(p)=6-4=2為了計算非葉節(jié)點的值，必須從葉節(jié)點向上倒推，叫倒推值。MAX的倒推值是其后繼節(jié)點估值的最大值。MIN的倒推值是其后繼節(jié)點估值的最小值。

第三十二頁，共九十八頁，編輯于2023年，星期五°°°°°°°°°°°°1-1-211010-1-10-10-2

12第三十三頁，共九十八頁，編輯于2023年，星期五°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°11213121010201112231221100第三十四頁，共九十八頁，編輯于2023年，星期五°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°111212-101001122111-------ABCD第三十五頁，共九十八頁，編輯于2023年，星期五3.

-剪枝

極大極小過程是把搜索樹的生成和格局估值這兩個過程分開來進行,即先生成全部搜索樹,然后再進行端節(jié)點靜態(tài)估值和倒推值計算,這顯然會導致低效率。如果把生成和倒推估值結合起來進行,再根據(jù)一定條件判定,有可能盡早修剪掉一些無用的分枝,即α-β剪枝過程的思想。α-β剪枝方法：（1）MAX節(jié)點的值為當前子節(jié)點的最大倒推值；MAX節(jié)點的值在搜索過程中永不減少（2）MIN節(jié)點的值為當前子節(jié)點的最小倒推值；MIN節(jié)點的值在搜索過程中永不增加第三十六頁，共九十八頁，編輯于2023年，星期五

（3）α-β剪枝規(guī)則：①任何MAX節(jié)點n的值大于或等于它的任一先輩節(jié)點MIN的值,則可終止該MAX節(jié)點以下的搜索,并可將其最終倒推值設為它的值.這種剪枝稱為β剪枝②任何MIN節(jié)點n的值小于或等于它的任一先輩節(jié)點MAX的值,則可終止該MIN節(jié)點以下的搜索,并可將其最終倒推值設為它的值。這種剪枝稱為α剪枝。

α剪枝：α（先輩節(jié)點）≥β（后繼節(jié)點）β剪枝：α（后繼節(jié)點）≥β（先輩節(jié)點）第三十七頁，共九十八頁，編輯于2023年，星期五05-333-302-23523α≥0β≤0α≥00-303α≥330β≤52α≥2β≤-5-5-522ααββα剪枝：α（先輩節(jié)點）≥β（后繼節(jié)點）β剪枝：α（后繼節(jié)點）≥β（先輩節(jié)點）β≤-3α剪枝β剪枝2α剪枝第三十八頁，共九十八頁，編輯于2023年，星期五481*5P80**α≥4β≤4α≥4414α≥554β≤00α≥0β≤-6-6-6004ααβββ≤1α剪枝β剪枝S0KLM6FNGQ5HD*ABRISJEα剪枝α剪枝C第三十九頁，共九十八頁，編輯于2023年，星期五3.5消解原理回顧：

原子公式（atomicformulas）

文字—一個原子公式及其否定。P(x),

P(x)

子句—由文字的析取組成的合適公式。P(x)Q(x)

空子句---不包含任何子句的文字。用NIL表示

子句集---由子句或空子句所構成的集合.

消解—對謂詞演算公式進行分解和化簡，消去一些符號，以求得導出子句。3.5.1

子句集的求取步驟：共9步。第四十頁，共九十八頁，編輯于2023年，星期五例子:將下列謂詞演算公式化為一個子句集(x)｛P(x)｛(y)［P(y)P(f(x,y))］∧～(y)［Q(x,y)P(y)］｝｝開始：消去蘊涵符號只應用∨和～符號，以～A∨B替換AB。(1)(x)｛～P(x)∨{(y)［~P(y)∨P(f(x,y))］∧～(y)［~Q(x,y)∨P(y)］}}3.5消解原理第四十一頁，共九十八頁，編輯于2023年，星期五(2)減少否定符號的轄域每個否定符號～最多只用到一個謂詞符號上，并反復應用狄·摩根定律。(3)對變量標準化對啞元（虛構變量）改名，以保證每個量詞有其自己唯一的啞元。3.5消解原理(2)(x)｛～P(x)∨｛(y)［～P(y)∨P(f(x,y))］∧(y)［Q(x,y)∧～P(y)］｝｝(3)(x)｛～P(x)∨｛(y)［～P(y)∨P(f(x,y))］∧(w)［Q(x,w)∧～P(w)］｝｝第四十二頁，共九十八頁，編輯于2023年，星期五(4)消去存在量詞以Skolem函數(shù)代替存在量詞內(nèi)的約束變量，然后消去存在量詞化為前束形把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。前束形={前綴}{母式}

全稱量詞串無量詞公式(4)(x)｛～P(x)∨{(y)[~P(y)∨P(f(x,y))］∧［Q(x,g(x)）∧～P(g(x))］｝｝式中，w=g(x)為一Skolem函數(shù)。(5)(x)(y)｛～P(x)∨｛［～P(y)∨P(f(x,y))］∧［Q(x,g(x))∧～P(g(x))］｝｝3.5消解原理第四十三頁，共九十八頁，編輯于2023年，星期五把母式化為合取范式任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。(7)消去全稱量詞所有余下的量詞均被全稱量詞量化了。消去前綴，即消去明顯出現(xiàn)的全稱量詞。3.5消解原理(6)(x)(y)｛［～P(x)∨～P(y)∨P(f(x,y))］∧［～P(x)∨Q(x,g(x))］∧［～P(x)∨～P(g(x))］｝(7)｛［～P(x)∨～P(y)∨P(f(x,y))］∧［～P(x)∨Q(x,g(x))］∧［～P(x)∨～P(g(x))］｝第四十四頁，共九十八頁，編輯于2023年，星期五(8)消去連詞符號∧用{A,B}代替(A∧B)，消去符號∧。最后得到一個有限集，其中每個公式是文字的析取。(9)更換變量名稱可以更換變量符號的名稱，使一個變量符號不出現(xiàn)在一個以上的子句中。3.5消解原理(8)

～P(x)∨～P(y)∨P(f(x,y))

～P(x)∨Q(x,g(x))

～P(x)∨～P(g(x))(9)

～P(x1)∨～P(y)∨P［f(x1,y)］～P(x2)∨Q［x2,g(x2)］～P(x3)∨～P［g(x3)］第四十五頁，共九十八頁，編輯于2023年，星期五3.5.2

消解推理規(guī)則消解式的定義

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

消解式求法取各子句的析取，然后消去互補對。3.5消解原理第四十六頁，共九十八頁，編輯于2023年，星期五幾種從父輩子句求消解式的例子假言推理AAB則B合并P∨QPQ則Q重言式P∨Q～

P∨

～

Q空子句～PP鏈式PQQR則PR第四十七頁，共九十八頁，編輯于2023年，星期五3.5.3含有變量的消解式

要把消解推理規(guī)則推廣到含有變量的子句，必須找到一個作用于父輩子句的置換，使父輩子句含有互補文字。

含有變量的子句之消解式例子P[x,f(y)]∨Q(x)∨R[f(a),y] ～P[f(f(a)),z]∨R(z，w)Q[f(f(a))]∨R(f(a)，y)∨R(f(y)，w)σ={f(f(a))/x,f(y)/z}3.5消解原理第四十八頁，共九十八頁，編輯于2023年，星期五3.5.4

消解反演求解過程消解反演

給出{S}，L否定L，得～L；把～L添加到S中去；把新產(chǎn)生的集合｛～L，S｝化成子句集；應用消解原理，力圖推導出一個表示矛盾的空子句例1—儲蓄問題前提：每個儲蓄錢的人都獲得利息。結論：如果沒有利息，那么就沒有人去儲蓄錢3.5消解原理第四十九頁，共九十八頁，編輯于2023年，星期五(1）規(guī)定原子公式：

S(x,y)表示“x儲蓄y”

M(x)表示“x是錢”

I(x)表示“x是利息”

E(x，y)表示“x獲得y”(2）用謂詞公式表示前提和結論：前提：(x)[(y)(S(x,y))∧M(y)][(y)(I(y)∧E(x,y))]結論：～(x)I(x)(x)(y)(M(y)→～S(x,y))(3)

化為子句形證明：3.5消解原理第五十頁，共九十八頁，編輯于2023年，星期五把前提化為子句形：1)

～S(x,y)∨～M(y)∨I(f(x))2)

～S(x,y)∨～M(y)∨E(x,f(x))把結論化為子句形：3)

～I(z)4)S(a,b)5)M(b)(4)

消解反演求NIL圖3.12儲蓄問題反演樹子句（1）子句（3）f(x)/z～M(b)NIL子句（5）子句（7）子句（4）{a/x,b/y}～S(x,y)∨～M(y)子句（6）3.5消解原理第五十一頁，共九十八頁，編輯于2023年，星期五例2：“快樂學生”問題

假設：任何通過計算機考試并獲獎的人都是快樂的。任何肯學習或幸運的人都可以通過所有考試，張不肯學習但他是幸運的，任何幸運的人都能獲獎。求證：張是快樂的。解：將問題用謂詞表示如下：“任何通過計算機考試并獲獎的人都是快樂的”

(x)(Pass(x,computer)Win(x,prize))Happy(x))“任何肯學習或幸運的人都可以通過所有考試”(x)(

y)(Study(x)Lucky(x)Pass(x,y))“張不肯學習但他是幸運的”Study(zhang)Lucky(zhang)“任何幸運的人都能獲獎”(x)(Lucky(x)Win(x,prize))

結論“張是快樂的”的否定Happy(zhang)第五十二頁，共九十八頁，編輯于2023年，星期五將謂詞轉(zhuǎn)化為子句集：

P1:

Pass(x,computer)

Win(x,prize)Happy(x)P2:

Study(y)

Pass(y,z)P3:

Lucky(u)

Pass(u,v)P4:Study(zhang)P5:Lucky(zhang)P6:

Lucky(w)Win(w,prize)

Q:Happy(zhang)所以：S’={P1,

P2,

P3,

P4,

P5,

P6},S’’=

{P1,

P2,

P3,

P4,

P5,

P6,

Q}對S’’進行歸結操作，直至推出NIL。歸結反演過程如下：第五十三頁，共九十八頁，編輯于2023年，星期五P6

Pass(x,computer)

Win(x,prize)Happy(x)

Lucky(w)Win(w,prize)

Pass(w,computer)

Happy(w)

Lucky(w)置換{w/x}

P1Happy(zhang)

Q

Pass(zhang,computer)

Lucky(zhang)置換{zhang/w}Lucky(zhang)

P5

Pass(zhang,computer)

Lucky(u)

Pass(u,v)

P3

Lucky(zhang)置換{zhang/u,computer/v}Lucky(zhang)

P5NIL

歸結出NIL，證明結論為真。第五十四頁，共九十八頁，編輯于2023年，星期五從反演樹求取問題的答案步驟1.把問題的已知條件用謂詞公式表達出來，并轉(zhuǎn)換成子句集S’；2.把問題的目標的否定用謂詞公式表達出來，并轉(zhuǎn)換成子句集Q；3.對Q中的每個子句，構造其重言式（包含互補文字對的子句），代替相應的目標否定子句，加入到S’中，得到S’’；4.對S’’應用消解原理求出消解樹，該消解樹的根子句為所求答案。實質(zhì)把一棵根部有NIL的反演樹變換為根部帶有回答語句的一棵證明樹。第五十五頁，共九十八頁，編輯于2023年，星期五例3：已知：李和張是同班同學，如果x和y是同班同學，則x的教室也是y的教室，現(xiàn)在張在302教室上課，問：李現(xiàn)在在哪里上課？解：定義謂詞：C(x,y)x和y是同班同學

At(x,u)x在u教室上課已知前提謂詞公式表示如下：

C(zhang,li)(x)(

y)(u)(C(x,y)At(x,u)At(y,u))At(zhang,302)目標的否定用謂詞公式表示如下：(v)At(li,v)將謂詞轉(zhuǎn)化為子句集：

P1:C(zhang,li)P2:C(x,y)

At(x,u)

At(y,u)P3:

At(zhang,302)第五十六頁，共九十八頁，編輯于2023年，星期五把目標的否定化為子句，用重言式Q:At(li,z)

At(li,z)代替所以：S’={P1,

P2,

P3,

},S’’=

{P1,

P2,

P3,

Q}對S’’進行歸結操作，歸結反演過程如下：

P3

C(x,y)

At(x,u)

At(y,u)At(li,z)

At(li,z)

QAt(li,z)

C(x,li)At(x,z)C(zhang,li)

P1At(li,z)

At(zhang,z)置換{li/y,z/u}At(zhang,302)

P2At(li,302)置換{zhang/x}置換{302/z}答案：李在302教室。第五十七頁，共九十八頁，編輯于2023年，星期五正向演繹系統(tǒng)的基本思想邏輯蘊涵式與子句的區(qū)別：上面二個表達式在邏輯上是等價的，但所表達的概念有區(qū)別：：強調(diào)推理性(即：前件為真時后件為真)

：只是表示了A、B、C中有一個為真，則公式為真可見：將蘊涵式寫成與其等價的子句形式會損失一些邏輯信息。直接利用蘊涵式所做的證明系統(tǒng)就是基于規(guī)則的演繹系統(tǒng)。3.6規(guī)則演繹系統(tǒng)第五十八頁，共九十八頁，編輯于2023年，星期五

定義

基于規(guī)則的問題求解系統(tǒng)運用If→Then規(guī)則來建立，每個if可能與某斷言(assertion)集中的一個或多個斷言匹配。有時把該斷言集稱為工作內(nèi)存，then部分用于規(guī)定放入工作內(nèi)存的新斷言。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng)。在這種系統(tǒng)中，通常稱每個if部分為前項，稱每個then部分為后項。IFATHENBIFBTHENCIFCTHEND已知A

第五十九頁，共九十八頁，編輯于2023年，星期五3.6.1規(guī)則正向演繹系統(tǒng)定義正向規(guī)則演繹系統(tǒng)是從事實到目標進行操作的，即從狀況條件到動作進行推理的，也就是從if到then的方向進行推理的。

3.6規(guī)則演繹系統(tǒng)第六十頁，共九十八頁，編輯于2023年，星期五正向規(guī)則演繹的求解過程事實表達式的與或形變換

在基于規(guī)則的正向演繹系統(tǒng)中，我們把事實表示為非蘊涵形式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫。方法：將規(guī)則前件的事實表達式從規(guī)則中分離出來，單獨變換成與或形式的表達式，但是不必化簡成子句。第六十一頁，共九十八頁，編輯于2023年，星期五例如：一個事實表達式：消去存在量詞，由常量代替變元x，得到一個與或表達式：利用等價變換，得到：對第一個合取項進行變量換名(w/y)，目的是保證每個合取項的變量名都不相同得到公式：上式不是子句，但是一個與或表達式，可以直接用于正向推理系統(tǒng)。第六十二頁，共九十八頁，編輯于2023年，星期五2.用與或圖表示一個與或表達式：與或圖中的節(jié)點代表子表達式當表達式為析取式(E1∨E2∨

…∨Ek)時，則每個子表達式表示為原表達式的一個后繼節(jié)點，且用一個K連接符連接每個Ei

，表示為與關系。當表達式為合取式(E1∧E2∧

…∧Ek)時，則每個子表達式單獨作為原表達式的一個子節(jié)點，用1連接符連接，表示為或關系。第六十三頁，共九十八頁，編輯于2023年，星期五上例的事實表達式用與或圖表示如下：可以看出，每個端節(jié)點都是一個文字，所以與或圖相當于把一個表達式按照與或關系拆分成文字表示。第六十四頁，共九十八頁，編輯于2023年，星期五討論：利用與或圖求解圖：方法與可分解系統(tǒng)中的解圖求法相同。不同的是與或圖中的節(jié)點之間的合取、析取關系是相反的。因此，求解圖是按照K連接方式求解，而不是按照真值求解。上圖中的三個解圖分別構成三個子句：

Q(w,A),~R(y)∨~S(A,y),~P(y)∨~S(A,y)基于規(guī)則正向推理系統(tǒng)中的與或圖是一種知識表達方式；可分解系統(tǒng)中的與或圖是一種圖搜索方式，二者是不同的。第六十五頁，共九十八頁，編輯于2023年，星期五3.與或圖的F規(guī)則變換

這些規(guī)則是建立在某個問題轄域中普通陳述性知識的蘊涵公式基礎上的。我們把允許用作規(guī)則的公式類型限制為下列形式：

LW 式中：L是單文字；W為與或形的唯一公式。3.6規(guī)則演繹系統(tǒng)如果規(guī)則為(L1∨L2)→W形式，即前提是析取形式，則將其分解成二條規(guī)則

L1→W，L2→W如果規(guī)則為(L1∧L2)→W形式，即前提是合取形式，不予討論。第六十六頁，共九十八頁，編輯于2023年，星期五例：初始數(shù)據(jù)庫的與或表達式為：

[(P∨Q)∧R]∨[S∧(T∨U)]

規(guī)則：S→(X∧Y)∨Z推理過程：①用與或圖表示初始條件表達式②尋找與規(guī)則前提匹配的文字③用匹配弧連接上述兩個文字④將規(guī)則結論的與或圖連接到前提上，擴充與或圖⑤正向系統(tǒng)的推理樹根節(jié)點在下部上面例題的推理樹見下頁。第六十七頁，共九十八頁，編輯于2023年，星期五從上圖的事實表達式部分可以得到四個子句：(1)(P∨Q)∨S(2)(P∨Q)∨(T∨U)(3)(R∨S)(4)R∨(T∨U)[(P∨Q)∧R]∨[S∧(T∨U)]X∧YXYZSSTUT∨US∧(T∨U)(P∨Q)∧RP∨QRPQ規(guī)則：S→(X∧Y)∨Z第六十八頁，共九十八頁，編輯于2023年，星期五從上圖的規(guī)則結論部分可以得到二個子句：(1)X∨Z(2)Y∨Z用這二個子句代替前提中的S，得到四個新子句(1)(P∨Q)∨(X∨Z)(2)(P∨Q)∨(Y∨Z)(3)R∨(X∨Z)(4)R∨(Y∨Z)下面說明這四個子句就是用事實表達式和規(guī)則構成的子句集進行歸結所得到的全部歸結式。X∧YXYZS第六十九頁，共九十八頁，編輯于2023年，星期五首先將事實表達式和規(guī)則寫成子句形式：事實表達式[(P∨Q)∧R]∨[S∧(T∨U)](P∨Q∨S)∧(P∨Q∨T∨U)∧(R∨S)∧(R∨T∨U)規(guī)則S→(X∧Y)∨Z~S∨(X∧Y)∨Z(~S∨X∨Z)∧(~S∨Y∨Z)得到子句集：{P∨Q∨S,P∨Q∨T∨U,R∨S,R∨T∨U,~S∨X∨Z,~S∨Y∨Z}①②③④⑤⑥由上面的子句集求出歸結式：①與⑤式：P∨Q∨X∨Z①與⑥式：P∨Q∨Y∨Z③與⑤式：R∨X∨Z③與⑥式：R∨Y∨Z由此可見，用歸結方法與用與或樹方法得到的歸結式是相同的。第七十頁，共九十八頁，編輯于2023年，星期五例：事實表達式A∨B

規(guī)則R1：A→(C∧D)R2：B→(E∧G)

目標C∨G推理樹：由此解圖得到子句集：{C∨E,C∨G,D∨E,D∨G}其中：C∨G是目標A∨BCGCDEGABABR1R2第七十一頁，共九十八頁，編輯于2023年，星期五3.6.2規(guī)則逆向演繹系統(tǒng)定義

逆向規(guī)則演繹系統(tǒng)是從then向if進行推理的，即從目標或動作向事實或狀況條件進行推理的。

求解過程目標表達式的與或形式與或圖的B規(guī)則變換作為終止條件的事實節(jié)點的一致解圖3.6規(guī)則演繹系統(tǒng)第七十二頁，共九十八頁，編輯于2023年，星期五1目標表達式的與或表示逆向推理系統(tǒng)從目標開始，與正向系統(tǒng)相反，規(guī)則的使用是反向的。目標表達式的與或形式：(1)利用skolem函數(shù)對目標公式進行標準化（同以前講的標準化過程相同）(2)各析取項之間變元要各不相同（變量換名）(3)子表達式之間為析取關系時，使用1連接符連接子表達式之間為合取關系時，使用K連接符連接(4)與或圖的根節(jié)點在上面例：目標公式：第七十三頁，共九十八頁，編輯于2023年，星期五標準化，得到：變量換名，得到：第七十四頁，共九十八頁，編輯于2023年，星期五2逆向推理系統(tǒng)關于規(guī)則的限制：B規(guī)則的形式：W→L其中：W：任何與或公式L：單文字結論①規(guī)則中的變元全部是全稱量詞約束②如果規(guī)則為W→(L1∧L2)形式，則分解為兩條規(guī)則：

W→L1

和W→L2推理過程：(1)用與或圖表示目標表達式(2)尋找與規(guī)則結論匹配的文字(3)用匹配弧連接上述的二個匹配文字(4)將規(guī)則的結論與前提連接，擴充與或圖，直至出現(xiàn)事實表達式的文字(5)反向推理樹的根節(jié)點在上面第七十五頁，共九十八頁，編輯于2023年，星期五反向推理例題：P83事實表達式：F1：D(FIDO)F2：~B(FIDO)F3：W(FIDO)F4：M(MR)規(guī)則：R1：（W(x1)∧D(x1))→F(x1)R2：(F(x2)∧~B(x2))→~A(y2,x2)R3：M(x3)→C(x3)目標公式：()()（C(x)∧D(y)∧~A(x,y)）第七十六頁，共九十八頁，編輯于2023年，星期五得到一個解圖：M(MR)∧D(FIDO)∧W(FIDO)∧D(FIDO)∧~B(FIDO)判斷是否是一致解圖：C(x)~A(x,y)D(y)~A(y2,x2)M(x3)F(x2)~B(x2){x3/x}{y2/x,x2/y}{FIDO/y}逆向推理樹C(x)∧D(y)∧~A(x,y)C(x3)D(FIDO)M(MR){MR/x3}F(x1)~B(FIDO){FIDO/x2}{x1/x2}D(x1)W(x1)W(FIDO)D(FIDO){FIDO/x1}{FIDO/x1}第七十七頁，共九十八頁，編輯于2023年，星期五(1)由反向推理樹得到所有置換：{{x3/x},{MR/x3},{{FIDO/y},{y2/x,x2/y},{x1/x2},{FIDO/x2},

{FIDO/x1},{FIDO/x1}}(2)求出：

U1=(x,x3,y,x,y,x2,x2,x1,x1)U2=(x3,MR,FIDO,y2,x2,x1,FIDO,FIDO,FIDO)(3)求出合一復合：

U=(MR/x,FIDO/y)(4)利用合一復合對目標公式作置換，得到置換例：

C(MR)∧D(FIDO)∧~A(MR,FIDO)該置換例就是推理結果

第七十八頁，共九十八頁，編輯于2023年，星期五

正向和逆向組合系統(tǒng)是建立在兩個系統(tǒng)相結合的基礎上的。此組合系統(tǒng)的總數(shù)據(jù)庫由表示目標和表示事實的兩個與或圖結構組成。這些與或圖結構分別用正向系統(tǒng)的F規(guī)則和逆向系統(tǒng)的B規(guī)則來修正。3.6.3規(guī)則雙向演繹系統(tǒng)3.6規(guī)則演繹系統(tǒng)第七十九頁，共九十八頁，編輯于2023年，星期五3.7產(chǎn)生式系統(tǒng)定義：用來描述若干個不同的以一個基本概念為基礎的系統(tǒng)。這個基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對的概念。實質(zhì)：在產(chǎn)生式系統(tǒng)中，論域的知識分為兩部分：用事實表示靜態(tài)知識，如事物、事件和它們之間的關系；用產(chǎn)生式規(guī)則表示推理過程和行為。由于這類系統(tǒng)的知識庫主要用于存儲規(guī)則，因此又把此類系統(tǒng)稱為基于規(guī)則的系統(tǒng)。第八十頁，共九十八頁，編輯于2023年，星期五3.7.1產(chǎn)生式系統(tǒng)的組成圖3.22產(chǎn)生式系統(tǒng)的主要組成控制策略總數(shù)據(jù)庫規(guī)則庫3.7產(chǎn)生式系統(tǒng)第八十一頁，共九十八頁，編輯于2023年，星期五規(guī)則庫用于存放與求解問題有關的某個領域知識的規(guī)則集。在建立規(guī)則庫時，應注意如下問題：

（1）規(guī)則庫知識的完整性、一致性、準確性、靈活性。（2）對知識進行合理的組織與管理：目的是使得推理避免訪問與所求解的問題無關的知識，以提高問題求解效率。第八十二頁，共九十八頁，編輯于2023年，星期五總數(shù)據(jù)庫總數(shù)據(jù)庫又稱為事實庫、上下文、黑板等。它是一個用于存放問題求解過程中各種當前信息的數(shù)據(jù)結構，例如：問題的初始狀態(tài)、原始證據(jù)、推理中得到的中間結論、最終結論等。 當規(guī)則庫中某條產(chǎn)生式的前提可與總數(shù)據(jù)庫中的某些已知事實匹配時，該產(chǎn)生式就被激活，并把其結論放入總數(shù)據(jù)庫中，作為后面推理的已知事實。顯然，總數(shù)據(jù)庫的內(nèi)容是在不斷變化的，是動態(tài)的。總數(shù)據(jù)庫中的已知事實通常用字符串、向量、集合、矩陣、表等數(shù)據(jù)結構表示。第八十三頁，共九十八頁，編輯于2023年，星期五控制策略控制策略又稱推理機構，由一組程序組成，負責整個產(chǎn)生式系統(tǒng)的運行，實現(xiàn)對問題的求解。主要包括推理策略和搜索策略兩部分。

推理策略：主要解決推理方向、沖突消解等問題。搜索策略：主要解決搜索線路、推理效果、推理效率等問題。控制策略的主要工作：（1）按一定的策略從規(guī)則庫中選擇與總數(shù)據(jù)庫中的已知事實相匹配的規(guī)則。（2）當發(fā)生沖突（即匹配成功的規(guī)則不止一條）時，調(diào)用相應的沖突解決策略予以消解。（3）在執(zhí)行某條規(guī)則時，若該規(guī)則的右部是一個或多個結論，則把這些結論加到總數(shù)據(jù)庫中；若規(guī)則的右部是一個或多個操作，則執(zhí)行這些操作。第八十四頁，共九十八頁，編輯于2023年，星期五（4）對于不確定性知識，在執(zhí)行每一條規(guī)則時，還要按一定的算法計算結論的不確定性。（5）對要執(zhí)行的規(guī)則，如果該規(guī)則的后件滿足問題的結束條件，則停止推理。（6）在問題的求解過程中，記住應用過的規(guī)則序列，以便最終能夠給出問題的解路徑。第八十五頁，共九十八頁，編輯于2023年，星期五選擇規(guī)則到執(zhí)行操作的步驟

1匹配把當前數(shù)據(jù)庫與規(guī)則的條件部分相匹配。

2沖突當有一條以上規(guī)則的條件部分和當前數(shù)據(jù)庫相匹配時，就需要決定首先使用哪一條規(guī)則，這稱為沖突解決。

3操作操作就是執(zhí)行規(guī)則的操作部分。3.7產(chǎn)生式系統(tǒng)第八十六頁，共九十八頁，編輯于2023年，星期五選取規(guī)則的原則稱為控制策略（沖突消解）不可撤回方式：屬盲目性搜索,