人工智能-一般搜索算法原理

人工智能_一般搜索算法原理第一頁(yè)，共154頁(yè)。盲目搜索圖搜索策略深度優(yōu)先搜索寬度優(yōu)先搜索等代價(jià)搜索第二頁(yè)，共154頁(yè)。一些基本概念節(jié)點(diǎn)深度： 根節(jié)點(diǎn)深度=0 其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+10123第三頁(yè)，共154頁(yè)。一些基本概念（續(xù)1）路徑 設(shè)一節(jié)點(diǎn)序列為(n0,n1,…,nk)，對(duì)于i=1,…,k，若節(jié)點(diǎn)ni-1具有一個(gè)后繼節(jié)點(diǎn)ni，則該序列稱(chēng)為從n0到nk的路徑。路徑的耗散值 一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用C(ni,nj)表示從ni到nj的路徑的耗散值。第四頁(yè)，共154頁(yè)。一些基本概念（續(xù)1）擴(kuò)展一個(gè)節(jié)點(diǎn) 生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出它們之間的耗散值。這一過(guò)程稱(chēng)為“擴(kuò)展一個(gè)節(jié)點(diǎn)”。第五頁(yè)，共154頁(yè)。一般的圖搜索算法（GRAPHSEARCH）1,G=G0(G0=s),OPEN=(s);2,CLOSED=();3,LOOP:IFOPEN=()EXIT(FAIL);4,n=FIRST(OPEN),REMOVE(n,OPEN), ADD(n,CLOSED);5,IFGOAL(n)EXIT(SUCCESS);6,EXPAND(n)→{mi},G=ADD(mi,G);第六頁(yè)，共154頁(yè)。一般的圖搜索算法（續(xù)）7,標(biāo)記和修改指針： ADD(mj,OPEN),并標(biāo)記mj到n的指針； 計(jì)算是否要修改mk、ml到n的指針； 計(jì)算是否要修改ml到其后繼節(jié)點(diǎn)的指針；8,對(duì)OPEN中的節(jié)點(diǎn)按某種原則重新排序；9,GOLOOP；第七頁(yè)，共154頁(yè)。深度優(yōu)先搜索在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的(最深的)節(jié)點(diǎn)，深度相等的節(jié)點(diǎn)可以任意排列?！白钔懋a(chǎn)生的節(jié)點(diǎn)最先擴(kuò)展”第八頁(yè)，共154頁(yè)。深度優(yōu)先搜索算法1,G=G0(G0=s),OPEN=(s),CLOSED=();2,LOOP:IFOPEN=()EXIT(FAIL);3,n=FIRST(OPEN);4,IFGOAL(n)EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,IFDEPTH(n)≥DmGOLOOP;7,EXPAND(n)→{mi},G=ADD(mi,G);8,IF目標(biāo)在{mi}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并標(biāo)記mj到n的指針;10,GOLOOP;第九頁(yè)，共154頁(yè)。231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標(biāo)第十頁(yè)，共154頁(yè)。深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制最壞情況時(shí)，搜索空間等同于窮舉與回溯法的差別：圖搜索是一個(gè)通用的與問(wèn)題無(wú)關(guān)的方法第十一頁(yè)，共154頁(yè)。寬度優(yōu)先搜索如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索。這種搜索使逐層進(jìn)行的，在對(duì)下一層的任意節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)?！跋犬a(chǎn)生的節(jié)點(diǎn)先擴(kuò)展”第十二頁(yè)，共154頁(yè)。寬度優(yōu)先搜索算法1,G=G0(G0=s),OPEN=(s),CLOSED=();2,LOOP:IFOPEN=()EXIT(FAIL);3,n=FIRST(OPEN);4,IFGOAL(n)EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{mi},G=ADD(mi,G);7,IF目標(biāo)在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并標(biāo)記mj到n的指針;9,GOLOOP;第十三頁(yè)，共154頁(yè)。23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標(biāo)8234187654第十四頁(yè)，共154頁(yè)。寬度優(yōu)先搜索的性質(zhì)當(dāng)問(wèn)題有解時(shí)，一定能找到解當(dāng)問(wèn)題為單位耗散值，且問(wèn)題有解時(shí)，一定能找到最優(yōu)解方法與問(wèn)題無(wú)關(guān)，具有通用性效率較低屬于圖搜索方法第十五頁(yè)，共154頁(yè)。等代價(jià)搜索寬度優(yōu)先搜索可被推廣用來(lái)解決尋找從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)具有最小代價(jià)路徑問(wèn)題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價(jià)搜索算法。第十六頁(yè)，共154頁(yè)。等代價(jià)搜索算法算法1,G=G0(G0=s),OPEN=(s),CLOSED=(),g(s)=0;2,LOOP:IFOPEN=()EXIT(FAIL);3,從OPEN表中選擇一個(gè)節(jié)點(diǎn)i,使其g(i)為最小。如果有幾個(gè)節(jié)點(diǎn)都合格，那么就要選擇一個(gè)目標(biāo)節(jié)點(diǎn)作為i(要是有目標(biāo)節(jié)點(diǎn)的話)；否則，就從中選一個(gè)作為節(jié)點(diǎn)I;REMOVE(i,OPEN),ADD(i,CLOSED);4,IFGOAL(i)EXIT(SUCCESS);5,EXPAND(i)→{j},G=ADD(j,G);6,對(duì)每個(gè)后繼節(jié)點(diǎn)j,計(jì)算g(j)=g(i)+c(i,j)且ADD(OPEN,j),并標(biāo)記j到i的指針;7,GOLOOP;第十七頁(yè)，共154頁(yè)。啟發(fā)式圖搜索利用知識(shí)來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問(wèn)題復(fù)雜度的目的。啟發(fā)信息的強(qiáng)度強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最 優(yōu)解弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)?盲目搜索，但可能可以找到最優(yōu)解第十八頁(yè)，共154頁(yè)。希望：引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。第十九頁(yè)，共154頁(yè)?；舅枷攵x一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來(lái)擴(kuò)展。第二十頁(yè)，共154頁(yè)。1，啟發(fā)式搜索算法A（A算法）評(píng)價(jià)函數(shù)的格式： f(n)=g(n)+h(n) f(n)：評(píng)價(jià)函數(shù) h(n)：?jiǎn)l(fā)函數(shù)第二十一頁(yè)，共154頁(yè)。符號(hào)的意義g*(n)：從s到n的最短路徑的耗散值h*(n)：從n到g的最短路徑的耗散值f*(n)=g*(n)+h*(n)：從s經(jīng)過(guò)n到g的最短路徑的耗散值g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計(jì)值第二十二頁(yè)，共154頁(yè)。A算法1,OPEN=(s),f(s)=g(s)+h(s);2,LOOP:IFOPEN=()EXIT(FAIL);3,n=FIRST(OPEN);4,IFGOAL(n)EXIT(SUCCESS);5,REMOVE(n,OPEN),ADD(n,CLOSED);6,EXPAND(n)→{Mi},

計(jì)算f(n,mi)=g(n,mi)+h(mi);

第二十三頁(yè)，共154頁(yè)。A算法（續(xù)）

ADD(mj,OPEN),標(biāo)記mj到n的指針； IFf(n,mk)<f(mk)f(mk)=f(n,mk),

標(biāo)記mk到n的指針； IFf(n,ml)<f(ml,)f(ml)=f(n,ml), 標(biāo)記ml到n的指針, ADD(ml,OPEN);7,OPEN中的節(jié)點(diǎn)按f值從小到大排序；8,GOLOOP；第二十四頁(yè)，共154頁(yè)。一個(gè)A算法的例子定義評(píng)價(jià)函數(shù)： f(n)=g(n)+h(n) g(n)為從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗散值 h(n)為當(dāng)前節(jié)點(diǎn)“不在位”的將牌數(shù)

2831647512384765第二十五頁(yè)，共154頁(yè)。h計(jì)算舉例 h(n)=42

831

647512345768第二十六頁(yè)，共154頁(yè)。2831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標(biāo)123456定義評(píng)價(jià)函數(shù)： f(n)=g(n)+h(n) g(n)為從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗散值 h(n)為當(dāng)前節(jié)點(diǎn)“不在位”的將牌數(shù)第二十七頁(yè)，共154頁(yè)。最佳圖搜索算法A*（A*算法）在A算法中，如果滿(mǎn)足條件： h(n)≤h*(n) 則A算法稱(chēng)為A*算法。第二十八頁(yè)，共154頁(yè)。A*條件舉例8數(shù)碼問(wèn)題h(n)=“不在位”的將牌數(shù)h(n)=將牌“不在位”的距離和2831647512345768將牌1：1將牌2：1將牌6：1將牌8：2第二十九頁(yè)，共154頁(yè)。A*算法的性質(zhì)定理1： 對(duì)有限圖，如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。第三十頁(yè)，共154頁(yè)。A*算法的性質(zhì)（續(xù)1）引理2.1： 對(duì)無(wú)限圖，若有從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑，則A*不結(jié)束時(shí)，在OPEN表中即使最小的一個(gè)f值也將增到任意大，或有f(n)>f*(s)。第三十一頁(yè)，共154頁(yè)。A*算法的性質(zhì)（續(xù)2）引理2.2： A*結(jié)束前，OPEN表中必存在f(n)≤f*(s)。第三十二頁(yè)，共154頁(yè)。A*算法的性質(zhì)（續(xù)3）定理2： 對(duì)無(wú)限圖，若從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則A*一定成功結(jié)束。第三十三頁(yè)，共154頁(yè)。A*算法的性質(zhì)（續(xù)4）推論2.1： OPEN表上任一具有f(n)<f*(s)的節(jié)點(diǎn)n，最終都將被A*選作擴(kuò)展的節(jié)點(diǎn)。第三十四頁(yè)，共154頁(yè)。A*算法的性質(zhì)（續(xù)5）定理3(可采納性定理)： 若存在從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑，則A*必能找到最佳解結(jié)束。第三十五頁(yè)，共154頁(yè)。A*算法的性質(zhì)（續(xù)6）推論3.1： A*選作擴(kuò)展的任一節(jié)點(diǎn)n，有f(n)≤f*(s)。第三十六頁(yè)，共154頁(yè)。A*算法的性質(zhì)（續(xù)7）定理4：設(shè)對(duì)同一個(gè)問(wèn)題定義了兩個(gè)A*算法A1和A2，若A2比A1有較多的啟發(fā)信息，即對(duì)所有非目標(biāo)節(jié)點(diǎn)有h2(n)>h1(n)，則在具有一條從s到t的路徑的隱含圖上，搜索結(jié)束時(shí)，由A2所擴(kuò)展的每一個(gè)節(jié)點(diǎn)，也必定由A1所擴(kuò)展，即A1擴(kuò)展的節(jié)點(diǎn)數(shù)至少和A2一樣多。簡(jiǎn)寫(xiě)：如果h2(n)>h1(n),則A1擴(kuò)展的節(jié)點(diǎn)數(shù)≥A2擴(kuò)展的節(jié)點(diǎn)數(shù)第三十七頁(yè)，共154頁(yè)。A*算法的改進(jìn)問(wèn)題的提出： 因A算法第6步對(duì)ml類(lèi)節(jié)點(diǎn)可能要重新放回到OPEN表中，因此可能會(huì)導(dǎo)致多次重復(fù)擴(kuò)展同一個(gè)節(jié)點(diǎn)，導(dǎo)致搜索效率下降。第三十八頁(yè)，共154頁(yè)。s(10)A(1)B(5)C(8)G目標(biāo)631118一個(gè)例子：OPEN表CLOSED表s(10)s(10)A(7)B(8)C(9)A(7)s(10)B(8)C(9)G(14)A(5)C(9)G(14)C(9)G(12)B(7)G(12)A(4)G(12)G(11)A(7)B(8)s(10)A(5)B(8)s(10)C(9)A(5)B(8)s(10)A(5)B(7)C(9)s(10)A(4)B(7)C(9)s(10)第三十九頁(yè)，共154頁(yè)。出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因在前面的擴(kuò)展中，并沒(méi)有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑，如節(jié)點(diǎn)A。第四十頁(yè)，共154頁(yè)。解決的途徑對(duì)h加以限制能否對(duì)h增加適當(dāng)?shù)南拗?，使得第一次擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，就找到了從s到該節(jié)點(diǎn)的最短路徑。對(duì)算法加以改進(jìn)能否對(duì)算法加以改進(jìn)，避免或減少節(jié)點(diǎn)的多次擴(kuò)展。第四十一頁(yè)，共154頁(yè)。改進(jìn)的條件可采納性不變不多擴(kuò)展節(jié)點(diǎn)不增加算法的復(fù)雜性第四十二頁(yè)，共154頁(yè)。對(duì)h加以限制定義：一個(gè)啟發(fā)函數(shù)h，如果對(duì)所有節(jié)點(diǎn)ni和nj，其中nj是ni的子節(jié)點(diǎn)，滿(mǎn)足 h(ni)-h(nj)≤c(ni,nj) h(t)=0 則稱(chēng)h是單調(diào)的。h(ni)ninjh(nj)c(ni,nj)第四十三頁(yè)，共154頁(yè)。h單調(diào)的性質(zhì)定理5： 若h(n)是單調(diào)的，則A*擴(kuò)展了節(jié)點(diǎn)n之后，就已經(jīng)找到了到達(dá)節(jié)點(diǎn)n的最佳路徑。 即：當(dāng)A*選n擴(kuò)展時(shí)，有g(shù)(n)=g*(n)。第四十四頁(yè)，共154頁(yè)。h單調(diào)的性質(zhì)（續(xù)）定理6： 若h(n)是單調(diào)的，則由A*所擴(kuò)展的節(jié)點(diǎn)序列其f值是非遞減的。第四十五頁(yè)，共154頁(yè)。h單調(diào)的例子8數(shù)碼問(wèn)題：h為“不在位”的將牌數(shù)1 h(ni)-h(nj)=0 (nj為ni的后繼節(jié)點(diǎn))-1 h(t)=0 c(ni,nj)=1滿(mǎn)足單調(diào)的條件。 第四十六頁(yè)，共154頁(yè)。對(duì)算法加以改進(jìn)一些結(jié)論：OPEN表上任一具有f(n)<f*(s)的節(jié)點(diǎn)定會(huì)被擴(kuò)展。A*選作擴(kuò)展的任一節(jié)點(diǎn)，定有f(n)≤f*(s)。第四十七頁(yè)，共154頁(yè)。改進(jìn)的出發(fā)點(diǎn)OPEN=(…………)f*(s)f值小于f*(s)的節(jié)點(diǎn)f值大于等于f*(s)的節(jié)點(diǎn)fm：到目前為止已擴(kuò)展節(jié)點(diǎn)的最大f值，用fm代替f*(s)第四十八頁(yè)，共154頁(yè)。修正過(guò)程A1,OPEN=(s),f(s)=g(s)+h(s),fm=0;2,LOOP:IFOPEN=()EXIT(FAIL);3,NEST={ni|f(ni)<fm} IFNEST≠()n=NEST中g(shù)最小的節(jié)點(diǎn) ELSEn=FIRST(OPEN), fm=f(n);4,…,8:同過(guò)程A。第四十九頁(yè)，共154頁(yè)。s(10)A(1)B(5)C(8)G目標(biāo)631118前面的例子：OPEN表CLOSED表fms(0+10)s(0+10)10A(6+1)B(3+5)C(1+8)s(0+10)C(1+8)10A(6+1)B(2+5)s(0+10)C(1+8)B(2+5)10A(3+1)s(0+10)C(1+8)B(2+5)A(3+1)10G(11+0)第五十頁(yè)，共154頁(yè)。例子：傳教士與野人問(wèn)題

設(shè)有3個(gè)傳教士和3個(gè)野人來(lái)到河邊，打算乘一只船從右岸渡到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過(guò)傳教士人數(shù)，那么野人就會(huì)把傳教士吃掉。他們?cè)鯓硬拍苡眠@條船安全地把所有人都渡河過(guò)去？

第五十一頁(yè)，共154頁(yè)。問(wèn)題表示：需要考慮兩岸的修道士人數(shù)和野人人數(shù)，船的位置。用三元式表示狀態(tài)：

S=(m,c,b)

其中，m表示左岸修道士人數(shù)，c表示左岸野人人數(shù)，b表示左岸船的數(shù)目。解：確定估價(jià)函數(shù)。

f(n)=g(n)＋h(n)=d(n)＋m＋c－2b

其中，d(n)為節(jié)點(diǎn)深度。h(n)＜h*(n)，滿(mǎn)足A*算法的限制條件。第五十二頁(yè)，共154頁(yè)。(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=4,f=4f(n)=d(n)+m+c-2bhh=5,f=6h=4,f=5h=4,f=5(3,2,1)h=3,f=5(2,1,0)(3,0,0)h=3,f=6h=3,f=6(2,2,1)(3,1,1)h=2,f=6h=2,f=6h=2,f=7h=2,f=7傳教士和野人問(wèn)題的A*搜索圖(0,0,0)(0,3,1)h=1,f=7(0,1,0)h=1,f=8(0,2,1)h=0,f=8(0,2,0)(1,1,0)第五十三頁(yè)，共154頁(yè)。4.5AO*算法搜索與或圖的A*算法節(jié)點(diǎn)評(píng)價(jià)方法

A*算法中，對(duì)節(jié)點(diǎn)n的評(píng)價(jià)，實(shí)際上是對(duì)“初始節(jié)點(diǎn)--節(jié)點(diǎn)n--目標(biāo)節(jié)點(diǎn)”這一條路徑的評(píng)價(jià)AO*算法中，由于與節(jié)點(diǎn)的存在，解對(duì)應(yīng)的不是一條路徑，而是一個(gè)子圖，因此對(duì)節(jié)點(diǎn)的評(píng)價(jià)，實(shí)際是對(duì)局部解圖的評(píng)價(jià)第五十四頁(yè)，共154頁(yè)。

A(6)

B

C

D(3)(4)(5)f(A)=min{(B)+(C)+2,(D)+1}

G

H

E

F(4)(4)(5)(7)(10)(9)(6)(11)與或圖節(jié)點(diǎn)擴(kuò)展與評(píng)價(jià)第五十五頁(yè)，共154頁(yè)。算法的兩個(gè)階段第一階段：自上而下的圖生成過(guò)程

對(duì)于每一個(gè)已經(jīng)擴(kuò)展過(guò)的節(jié)點(diǎn)，都對(duì)應(yīng)一個(gè)指針，指向該節(jié)點(diǎn)后繼節(jié)點(diǎn)中，代價(jià)值小的那條邊。圖生成過(guò)程，就是從初始節(jié)點(diǎn)出發(fā)，按照該指針向下搜索，一直到找到一個(gè)未擴(kuò)展的節(jié)點(diǎn)為止。然后擴(kuò)展該節(jié)點(diǎn)。第二階段：自下而上的代價(jià)值計(jì)算過(guò)程

設(shè)n為最新被擴(kuò)展的節(jié)點(diǎn)，計(jì)算節(jié)點(diǎn)n對(duì)應(yīng)的最小代價(jià)值，并標(biāo)記一個(gè)指針指向?qū)?yīng)最小代價(jià)的邊。對(duì)于n的父節(jié)點(diǎn)，進(jìn)行同樣的計(jì)算。重復(fù)這一過(guò)程，直到初始節(jié)點(diǎn)s為止。這時(shí)，從s出發(fā)，選擇那些指針?biāo)赶虻倪叺玫降木植繄D，為當(dāng)前代價(jià)值最小的局部圖。第五十六頁(yè)，共154頁(yè)。具體步驟Step1建立一個(gè)僅由初始節(jié)點(diǎn)s構(gòu)成的搜索圖G，計(jì)算h(s)Step2在以下兩過(guò)程間循環(huán)，直到s標(biāo)記為可解或不可解，或其代價(jià)值大于閾值：

2.1選擇節(jié)點(diǎn)進(jìn)行擴(kuò)展

2.2根據(jù)擴(kuò)展情況修改節(jié)點(diǎn)的可解性與代價(jià)值

第五十七頁(yè)，共154頁(yè)。Step2.1選擇節(jié)點(diǎn)進(jìn)行擴(kuò)展：1根據(jù)指針找出待擴(kuò)展的局部解圖G′。

2選擇G′中的一個(gè)非終節(jié)點(diǎn)n作為當(dāng)前節(jié)點(diǎn)。

3擴(kuò)展節(jié)點(diǎn)n，如不能擴(kuò)展，則標(biāo)記為不可解，否則生成子節(jié)點(diǎn)集，如子節(jié)點(diǎn)為非終節(jié)點(diǎn)，計(jì)算其代價(jià)值，若為終節(jié)點(diǎn)，標(biāo)注其可解。將所有子節(jié)點(diǎn)添加到G中。4建立含n的單一節(jié)點(diǎn)集合S，S:＝{n}第五十八頁(yè)，共154頁(yè)。Step2.2修改節(jié)點(diǎn)的可解性與代價(jià)值

重復(fù)以下步驟，直到S為空：

1從S中挑選一個(gè)子孫節(jié)點(diǎn)都不在S中的節(jié)點(diǎn)m2計(jì)算始于m的每條連接線的代價(jià)，取其中最小值為m對(duì)應(yīng)的代價(jià)，并在對(duì)應(yīng)于最小代價(jià)的連接線上加指針。3如果連接于最小代價(jià)連接線上的所有節(jié)點(diǎn)都可解，則標(biāo)注m可解。4如果m的可解性或代價(jià)值發(fā)生改變，則把m的所有祖先節(jié)點(diǎn)添加到S中。第五十九頁(yè)，共154頁(yè)。AO*算法舉例目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2

h(n7)=0h(n8)=0連接線的代價(jià)=后繼節(jié)點(diǎn)個(gè)數(shù)第六十頁(yè)，共154頁(yè)。n0n1n2n3n4n5n6n7n8n0(3)n1(2)n4(1)n5(1)紅色代價(jià)：4藍(lán)色代價(jià)：3第六十一頁(yè)，共154頁(yè)。n0n1n2n3n4n5n6n7n8n4(1)n5(1)紅色代價(jià)：4藍(lán)色代價(jià)：6n1(2->5)n2(4)n3(4)n0(3)n0(3->4)第六十二頁(yè)，共154頁(yè)。n0n1n2n3n4n5n6n7n8n4(1)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4)n5(1)n5(1->2)第六十三頁(yè)，共154頁(yè)。n0n1n2n3n4n5n6n7n8紅色代價(jià)：5藍(lán)色代價(jià)：6n0(4)n4(1)n5(1->2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4->5)第六十四頁(yè)，共154頁(yè)。n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)第六十五頁(yè)，共154頁(yè)。目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)第六十六頁(yè)，共154頁(yè)。目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8初始節(jié)點(diǎn)可解n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)第六十七頁(yè)，共154頁(yè)。歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制第六十八頁(yè)，共154頁(yè)。歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制第六十九頁(yè)，共154頁(yè)。概述歸結(jié)原理由J.A.Robinson由1965年提出。與演繹法完全不同，新的邏輯演算算法。一階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在有限步內(nèi)給以判定。語(yǔ)義網(wǎng)絡(luò)、框架表示、產(chǎn)生式規(guī)則等等都是以推理方法為前提的。即，有了規(guī)則已知條件，順藤摸瓜找到結(jié)果。而歸結(jié)方法是自動(dòng)推理、自動(dòng)推導(dǎo)證明用的。（“數(shù)學(xué)定理機(jī)器證明”）本課程只討論一階謂詞邏輯描述下的歸結(jié)推理方法，不涉及高階謂詞邏輯問(wèn)題。

第七十頁(yè)，共154頁(yè)。歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制第七十一頁(yè)，共154頁(yè)。歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制第七十二頁(yè)，共154頁(yè)。命題邏輯的歸結(jié)法基本單元：簡(jiǎn)單命題（陳述句）例：

命題：A1、A2、A3和B求證：A1ΛA2ΛA3成立，則B成立，即：A1ΛA2ΛA3→B反證法：證明A1ΛA2ΛA3Λ～B是矛盾式（永假式）

第七十三頁(yè)，共154頁(yè)。命題邏輯的歸結(jié)法建立子句集合取范式：命題、命題和的與，如： PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：PΛ（P∨Q）Λ（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}

第七十四頁(yè)，共154頁(yè)。命題邏輯的歸結(jié)法歸結(jié)式消除互補(bǔ)對(duì)，求新子句→得到歸結(jié)式。如子句：C1=C1′∨L,C2=C2′∨

歸結(jié)式：R(C1,C2)=C1′∨

C2′

注意：C1ΛC2→R(C1,C2)，反之不一定成立。假言推理:由合適公式W1和W1

→W2產(chǎn)生合適公式W2,如何用歸結(jié)法證明?第七十五頁(yè)，共154頁(yè)。命題邏輯的歸結(jié)法歸結(jié)過(guò)程

對(duì)結(jié)論作否定,并加入前提中將命題寫(xiě)成合取范式求出子句集對(duì)子句集使用歸結(jié)推理規(guī)則歸結(jié)式作為新子句參加歸結(jié)歸結(jié)式為空子句□，S是不可滿(mǎn)足的（矛盾），原命題成立。?（證明完畢）謂詞的歸結(jié)：除了有量詞和函數(shù)以外，其余和命題歸結(jié)過(guò)程一樣。第七十六頁(yè)，共154頁(yè)。命題邏輯的歸結(jié)法例證明先將化為合取范式建立子句集S=對(duì)S做歸結(jié)PNIL第七十七頁(yè)，共154頁(yè)。歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制第七十八頁(yè)，共154頁(yè)。歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制第七十九頁(yè)，共154頁(yè)。子句形引用Herbrand定理，以說(shuō)明歸結(jié)原理的意義及一個(gè)原理形成的根基與背景SKOLEM標(biāo)準(zhǔn)形前束范式：把所有的量詞都提到前面去，然后消掉所有量詞。

定義：說(shuō)公式A是一個(gè)前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。即(Q1x1)…(Qnxn)M(x1,…,xn),其中Qixi為存在量詞或全稱(chēng)量詞,M(x1,…,xn)為合取范式(由一些子句的合取組成)。第八十頁(yè)，共154頁(yè)。子句形(Skolem標(biāo)準(zhǔn)形)

量詞消去原則： 消去存在量詞“”，略去全程量詞“”。

注意：左邊有全稱(chēng)量詞的存在量詞，消去時(shí)該變量改寫(xiě)成為全稱(chēng)量詞的函數(shù)(Skloem函數(shù))；如沒(méi)有，改寫(xiě)成為常量。

例子：見(jiàn)《人工智能及其應(yīng)用》P75第八十一頁(yè)，共154頁(yè)。子句形(Skolem標(biāo)準(zhǔn)形)定理： 謂詞邏輯的任意公式都可以化為與之等價(jià)的前束范式，但其前束范式不唯一。SKOLEM標(biāo)準(zhǔn)形定義： 消去量詞后的謂詞公式。注意：謂詞公式G的SKOLEM標(biāo)準(zhǔn)形同G并不等值。第八十二頁(yè)，共154頁(yè)。子句形(Skolem標(biāo)準(zhǔn)形)例:G=(x)(y)(z)(u)P(x,y,z,u)Skolem標(biāo)準(zhǔn)形為：

(y)(z)P(a,y,z,f(y,z))其中，x=a(常量)，u=f(y.z)

第八十三頁(yè)，共154頁(yè)。子句形子句與子句集文字：不含任何連接詞的謂詞公式。子句：一些文字的析?。ㄖ^詞的和）。子句集S的求?。篏→SKOLEM標(biāo)準(zhǔn)形 →消去存在變量 →以“，”取代“Λ”，并表示為集合形式。第八十四頁(yè)，共154頁(yè)。子句形

G是不可滿(mǎn)足的<=>S是不可滿(mǎn)足的G與S不等價(jià)，但在不可滿(mǎn)足的意義下是一致的。

定理： 若G是給定的公式，而S是相應(yīng)的子句集，則G是不可滿(mǎn)足的<=>S是不可滿(mǎn)足的。

注意：G真不一定S真，而S真必有G真。 即：S=>G第八十五頁(yè)，共154頁(yè)。子句形G=G1ΛG2ΛG3Λ…ΛGn的子句形G的子句集可以分解成幾個(gè)單獨(dú)處理。

有SG=S1US2US3U…USn 則SG

與S1US2US3U…USn在不可滿(mǎn)足的意義上是一致的。 即SG不可滿(mǎn)足<=>S1US2US3U…USn不可滿(mǎn)足

第八十六頁(yè)，共154頁(yè)。歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制第八十七頁(yè)，共154頁(yè)。歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制第八十八頁(yè)，共154頁(yè)。Herbrand定理問(wèn)題： 一階邏輯公式的永真性（永假性）的判定是否能在有限步內(nèi)完成？第八十九頁(yè)，共154頁(yè)。Herbrand定理1936年圖靈(Turing)和邱吉(Church)互相獨(dú)立地證明了：“沒(méi)有一般的方法使得在有限步內(nèi)判定一階邏輯的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步內(nèi)判定它是永真（或永假）。對(duì)于非永真（或永假）的公式就不一定能在有限步內(nèi)得到結(jié)論。判定的過(guò)程將可能是不停止的?！钡诰攀?yè)，共154頁(yè)。Herbrand定理Herbrand的思想定義： 公式G永真：對(duì)于G的所有解釋?zhuān)珿都為真。思想：

尋找一個(gè)已給的公式是真的解釋。然而，如果所給定的公式的確是永假的，就沒(méi)有這樣的解釋存在，并且算法在有限步內(nèi)停止。第九十一頁(yè)，共154頁(yè)。Herbrand定理H域H解釋語(yǔ)義樹(shù)結(jié)論：Herbrand定理第九十二頁(yè)，共154頁(yè)。Herbrand定理H域H解釋語(yǔ)義樹(shù)結(jié)論：Herbrand定理第九十三頁(yè)，共154頁(yè)。Herbrand定理（H域）基本方法：因?yàn)榱吭~是任意的，所討論的個(gè)體變量域D是任意的，所以解釋的個(gè)數(shù)是無(wú)限、不可數(shù)的。簡(jiǎn)化討論域。建立一個(gè)比較簡(jiǎn)單、特殊的域，使得只要在這個(gè)論域上，該公式是不可滿(mǎn)足的。此域稱(chēng)為H域：H0為G中所出現(xiàn)的常量的集合，若G中沒(méi)有常量，就任取常量，H0={a}。

規(guī)定為H域

※

例題請(qǐng)參考教科書(shū)P27第九十四頁(yè)，共154頁(yè)。H域舉例例1S={P(a),～P(x)∨P(f(x))}依定義有 H0={a} H1={a}U{f(a)}={a,f(a)} H2={a,f(a)}U{f(a),f(f(a))}={a,f(a),f(f(a))} … H∞={a,f(a),f(f(a))，…}第九十五頁(yè)，共154頁(yè)。Herbrand定理（H域）幾個(gè)基本概念f（t1,t2,…tn）：f為子句集S中的所有函數(shù)變量。t1,t2,…tn為S的H域的元素。通過(guò)它們來(lái)討論永真性。原子集A：謂詞套上H域的元素組成的集合。如

A={所有形如P(t1,t2,…tn)的元素}

即把H中的東西填到S的謂詞里去。S中的謂詞是有限的，H是可數(shù)的，因此，A也是可數(shù)的。一旦原子集內(nèi)真值確定好（規(guī)定好），則S在H上的真值可確定。成為可數(shù)問(wèn)題。第九十六頁(yè)，共154頁(yè)。原子集舉例例1S={P(a),～P(x)∨P(f(x))}H∞={a,f(a),f(f(a))，…}S的原子集為A={P(a),P(f(a)),P(f(f(a))),…}第九十七頁(yè)，共154頁(yè)。Herbrand定理（H域）沒(méi)有變量出現(xiàn)的原子、文字、子句和子句集，分別稱(chēng)作基原子、基文字、基子句和基子句集。它們?cè)谟懻撟泳浼疭的不可滿(mǎn)足性時(shí)占有重要置。第九十八頁(yè)，共154頁(yè)。Herbrand定理H域H解釋語(yǔ)義樹(shù)結(jié)論：Herbrand定理第九十九頁(yè)，共154頁(yè)。Herbrand定理H域H解釋語(yǔ)義樹(shù)結(jié)論：Herbrand定理第一百頁(yè)，共154頁(yè)。Herbrand定理（H解釋?zhuān)┙忉孖*：取一個(gè)值得到一個(gè)結(jié)論I映射S中到所有常量符號(hào)到它們本身。(即原子集)令f是n元函數(shù)，I是f下的一個(gè)指派，即H中的元素到f的一個(gè)映射（函數(shù)值）。簡(jiǎn)單地說(shuō)(P29)，A中的各元素真假組合都是H的解釋。（或真或假只取一個(gè)）問(wèn)題：對(duì)于所有的解釋?zhuān)羌俨趴膳卸āＲ驗(yàn)樗薪忉尨砹怂械那闆r，如可窮舉，問(wèn)題便可解決。

第一百零一頁(yè)，共154頁(yè)。H解釋-舉例例1S={P(a),～P(x)∨P(f(x))}

S的H域H∞={a,f(a),f(f(a))，…}S的原子集為A={P(a),P(f(a)),P(f(f(a))),…}S的H解釋?zhuān)?/p>

I1*={P(a),P(f(a)),P(f(f(a))),…} S|I1*=T

I2*={～P(a),P(f(a)),P(f(f(a))),…} S|I2*=F

I3*={P(a),～P(f(a)),P(f(f(a))),…} S|I3*=F我們關(guān)心的是：對(duì)論域上的任一解釋I，若有S|I=T,如何求得一個(gè)相應(yīng)的H解釋I*,使得S|I*=T成立。第一百零二頁(yè)，共154頁(yè)。Herbrand定理（H解釋?zhuān)┤缦氯齻€(gè)定理保證了歸結(jié)法的正確性：定理1：

設(shè)I是S的論域D上的解釋?zhuān)嬖趯?duì)應(yīng)于I的H解釋I*，使得若有S|I=T，必有S|I*=T。定理2： 子句集S是不可滿(mǎn)足的，當(dāng)且僅當(dāng)所有的S的H解釋下為假。定理3： 子句集S是不可滿(mǎn)足的，當(dāng)且僅當(dāng)對(duì)每一個(gè)解釋I下，至少有S的某個(gè)子句的某個(gè)基例為假。第一百零三頁(yè)，共154頁(yè)。Herbrand定理（H解釋?zhuān)┗齋中某子句中所有變?cè)?hào)均以S的H域中的元素代入時(shí)，所得的基子句C’稱(chēng)為C的一個(gè)基例。若一個(gè)子句為假，則此解釋為假。一般來(lái)說(shuō)，D是無(wú)窮不可列的，因此，子句集S也是無(wú)窮不可列的。但S確定后H是無(wú)窮可列的。不過(guò)在H上證明S的不可滿(mǎn)足性仍然是不可能的。解決問(wèn)題的方法：語(yǔ)義樹(shù)第一百零四頁(yè)，共154頁(yè)。Herbrand定理H域H解釋語(yǔ)義樹(shù)結(jié)論：Herbrand定理第一百零五頁(yè)，共154頁(yè)。Herbrand定理H域H解釋語(yǔ)義樹(shù)結(jié)論：Herbrand定理第一百零六頁(yè)，共154頁(yè)。Herbrand定理（語(yǔ)義樹(shù)）構(gòu)成方法原子集中所有元素逐層添加的一棵二叉樹(shù)。將元素的是與非分別標(biāo)記在兩側(cè)的分枝上（可不完全畫(huà)完）。(P34)特點(diǎn)一般情況H是可數(shù)集，S的語(yǔ)義樹(shù)是無(wú)限樹(shù)。第一百零七頁(yè)，共154頁(yè)。Herbrand定理（語(yǔ)義樹(shù)）意義SHA語(yǔ)義樹(shù)可以理解語(yǔ)義樹(shù)為H域的圖形解釋。目的：把每個(gè)解釋都攤開(kāi)。語(yǔ)義樹(shù)中包含原子集的全部元素，因此，語(yǔ)義樹(shù)是完全的。每一個(gè)直到葉子節(jié)點(diǎn)的分支對(duì)應(yīng)S的一個(gè)解釋?？梢酝ㄟ^(guò)對(duì)語(yǔ)義樹(shù)每一個(gè)分支來(lái)計(jì)算S的真值。如果每個(gè)基例都為假，則可認(rèn)為是不可滿(mǎn)足的。第一百零八頁(yè)，共154頁(yè)。語(yǔ)義樹(shù)-舉例例1設(shè)子句集S的原子集A={P,Q,R}

語(yǔ)義樹(shù)：

N0

N11N12N21N22N23N24N31N32N33N34N35N36N37N38P～QQR～R～PI(N)表示從根節(jié)點(diǎn)到節(jié)點(diǎn)N分枝上所標(biāo)記的所有文字的并集。如I(N34)={P,～Q,～R}第一百零九頁(yè)，共154頁(yè)。Herbrand定理（語(yǔ)義樹(shù)）幾個(gè)概念失敗結(jié)點(diǎn)： 當(dāng)（由上）延伸到點(diǎn)N時(shí)，I(N)已表明了S的某子句的某基例假。但N以前尚不能判斷這事實(shí)。就稱(chēng)N為失敗結(jié)點(diǎn)。完全語(yǔ)義樹(shù)：如果對(duì)語(yǔ)義樹(shù)的所有葉結(jié)點(diǎn)N來(lái)說(shuō)，I(N)包含了S的原子集A={A1,A2,…}中的所有元素Ai或～Ai，I=1…n。封閉語(yǔ)義樹(shù)： 如果S的完全語(yǔ)義樹(shù)的每個(gè)分枝上都有一個(gè)失敗結(jié)點(diǎn)，就稱(chēng)它是一棵封閉語(yǔ)義樹(shù)。第一百一十頁(yè)，共154頁(yè)。封閉語(yǔ)義樹(shù)-舉例例子句集S={～P(x)∨Q(x),P(f(y)),～Q(f(y))}H={a,f(a),f(f(a)),…}A={P(a),Q(a),P(f(a)),Q(f(a)),…}

語(yǔ)義樹(shù)：

N0

N11N12N21N22N23N24N31N32N33N34N35N36N37N38P(a)Q(a)P(f(a))N41N42N43N44N45N46N47N48N49N410N411N413N415N412N414N416這是一個(gè)無(wú)限樹(shù)，然而它是否是一個(gè)封閉樹(shù)？Q(f(a))ΧΧΧΧΧΧΧΧΧΧI(N41)={P(a),Q(a),P(f(a)),Q(f(a))},它使S的子句～Q(f(y))的基例～Q(f(a))為假，而N41的父輩不能使子句的基例為假第一百一十一頁(yè)，共154頁(yè)。封閉語(yǔ)義樹(shù)-舉例例子句集S={～P(x)∨Q(x),P(f(y)),～Q(f(y))}H={a,f(a),f(f(a)),…}A={P(a),Q(a),P(f(a)),Q(f(a)),…}

封閉語(yǔ)義樹(shù)：

N0

N11N12N21N22N23N24N31N32N36N37N38P(a)Q(a)P(f(a))N41N42N49N410N413N414Q(f(a))ΧΧΧΧΧΧΧΧΧΧ第一百一十二頁(yè)，共154頁(yè)。Herbrand定理H域H解釋語(yǔ)義樹(shù)結(jié)論：Herbrand定理第一百一十三頁(yè)，共154頁(yè)。Herbrand定理H域H解釋語(yǔ)義樹(shù)結(jié)論：Herbrand定理第一百一十四頁(yè)，共154頁(yè)。Herbrand定理（結(jié)論）Herbrand定理：子句集S是不可滿(mǎn)足的，當(dāng)且僅當(dāng)對(duì)應(yīng)于S的完全語(yǔ)義數(shù)是棵有限封閉樹(shù)。

子句集S是不可滿(mǎn)足的，當(dāng)且僅當(dāng)存在不可滿(mǎn)足的S的有限基例集。

第一百一十五頁(yè)，共154頁(yè)。Herbrand定理（結(jié)論）定理的意義Herbrand定理已將證明問(wèn)題轉(zhuǎn)化成了命題邏輯問(wèn)題。由此定理保證，可以放心的用機(jī)器來(lái)實(shí)現(xiàn)自動(dòng)推理了。（歸結(jié)原理）注意Herbrand定理給出了一階邏輯的半可判定算法，即僅當(dāng)被證明定理是成立時(shí)，使用該算法可以在有限步得證。而當(dāng)被證定理并不成立時(shí)，使用該算法得不出任何結(jié)論。但是

第一百一十六頁(yè)，共154頁(yè)。例S={P(x,g(x),y,h(x,y),z,k(x,y,z)),～P(u,v,e(v),w,f(v,w)),x)}有H0={a},S0′={P(a,g(a),a,h(a,a),a,k(a,a,a)),～P(a,a,e(a),a,f(a,a)),a)}

H1={a,g(a),h(a,a),k(a,a,a),e(a),f(a,a)}共6個(gè)元素S1′：

63+64=1512個(gè)元素

H2：元素個(gè)數(shù)有63數(shù)量級(jí)（由于變量最多的函數(shù)是k(x,y,z),三個(gè)變量都可能取值于H1的六個(gè)元素）S2′：元素個(gè)數(shù)有(63)

4數(shù)量級(jí)建立S3′，S4′，直到S5′才是不可滿(mǎn)足。然而

S5′元素個(gè)數(shù)已達(dá)（1064）4=10256Herbrand定理（結(jié)論）仍存在的問(wèn)題：基例集序列元素的數(shù)目隨子句基的元素?cái)?shù)目成指數(shù)地增加。因此，Herbrand定理是30年代提出的，始終沒(méi)有顯著的成績(jī)。直至1965年Robinson提出了歸結(jié)原理。第一百一十七頁(yè)，共154頁(yè)。歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制第一百一十八頁(yè)，共154頁(yè)。歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制第一百一十九頁(yè)，共154頁(yè)。歸結(jié)原理歸結(jié)原理正確性的根本在于，找到矛盾可以肯定不真。方法：和命題邏輯一樣。但由于有函數(shù)，所以要考慮合一和置換。(定義與例題參考教科書(shū)P41)第一百二十頁(yè)，共154頁(yè)。歸結(jié)原理置換和合一的注意事項(xiàng)：謂詞的一致性，P()與Q()，不可以常量的一致性，P(a,…)與P(b,….)，不可以 常量與變量，P(a,….)與P(x,…)，可以變量與函數(shù)，P(a,x,….)與P(x,f(x),…)，不可以；但P(a,x,…)與P(x,f(y),…)，可以是不能同時(shí)消去兩個(gè)互補(bǔ)對(duì)，P∨Q與～P∨～Q的空，不可以先進(jìn)行內(nèi)部簡(jiǎn)化（置換、合并）第一百二十一頁(yè)，共154頁(yè)。歸結(jié)原理歸結(jié)的過(guò)程(P48)寫(xiě)出謂詞關(guān)系公式→用反演法寫(xiě)出謂詞表達(dá)試→SKOLEM標(biāo)準(zhǔn)形→子句集S→對(duì)S中可歸結(jié)的子句做歸結(jié)→歸結(jié)式仍放入S中，反復(fù)歸結(jié)過(guò)程→得到空子句

?得證第一百二十二頁(yè)，共154頁(yè)。歸結(jié)原理歸結(jié)法的實(shí)質(zhì)：歸結(jié)法是僅有一條推理規(guī)則的推理方法。歸結(jié)的過(guò)程是一個(gè)語(yǔ)義樹(shù)倒塌的過(guò)程。(P51)歸結(jié)法的問(wèn)題子句中有等號(hào)或不等號(hào)時(shí)，完備性不成立?！鵋erbrand定理的不實(shí)用性引出了可實(shí)用的歸結(jié)法。第一百二十三頁(yè)，共154頁(yè)。歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制第一百二十四頁(yè)，共154頁(yè)。歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制第一百二十五頁(yè)，共154頁(yè)。歸結(jié)過(guò)程的控制策略要解決的問(wèn)題：歸結(jié)方法的知識(shí)爆炸?？刂撇呗缘哪康臍w結(jié)點(diǎn)盡量少控制策略的原則給出控制策略，以使僅對(duì)選擇合適的子句間方可做歸結(jié)。避免多余的、不必要的歸結(jié)式出現(xiàn)?；蛘哒f(shuō)，少做些歸結(jié)仍能導(dǎo)出空子句。第一百二十六頁(yè)，共154頁(yè)。歸結(jié)過(guò)程的控制策略盲目歸結(jié)

例S={P∨Q,

～P∨Q,P∨～Q,～P∨～Q}是不可滿(mǎn)足。證明從S0=S開(kāi)始，依次構(gòu)造Si={C1,C2的歸結(jié)式|C1∈S0∪S1∪…∪Si-1,C2∈Si-1},i=1,2,…,直至得到空子句。具體過(guò)程如下：S0(1)

P∨Q(2)～P∨Q(3)P∨～Q(4)～P∨～QS1(5)Q(1)(2)(6)P(1)(3)(7)Q∨～Q(1)(4)(8)P∨～P(1)(4)(9)Q∨～Q(2)(3)(10)P∨～P(2)(3)(11)～P(2)(4)(12)～Q(3)(4)第一百二十七頁(yè)，共154頁(yè)。歸結(jié)過(guò)程的控制策略(盲目歸結(jié))S2(13)P(1)(7)(14)P∨Q(1)(8)(15)P∨Q(1)(9)(16)P∨Q(1)(10)(17)Q(1)(11)(18)P(1)(12)(19)Q

(2)(6)(20)～P∨Q(3)(4)(21)～P∨Q(2)(8)(22)～P∨Q(2)(9)(23)～P∨Q(2)(10)(24)～P(2)(12)(25)P(3)(5)(26)P∨～Q(3)(7)(27)P∨～Q(3)(8)(28)P∨～Q(3)(9)(29)P∨～Q(3)(10)(30)～Q(3)(11)(31)～P(4)(5)(32)～Q(4)(6)(33)～P∨～Q(4)(7)(34)～P∨～Q(4)(8)(35)～P∨～Q(4)(9)(36)～P∨～Q(4)(10)(37)Q

(5)(7)(38)Q(5)(9)(39)?(5)(12)產(chǎn)生過(guò)多不必要的歸結(jié)式。一類(lèi)是重言式（7）-（10）由它們又產(chǎn)生了（13）-（16），（20）-（23），(26)-(29),(33)-(39)。另一類(lèi)是重復(fù)的，如P,Q,～P,～Q.第一百二十八頁(yè)，共154頁(yè)。歸結(jié)過(guò)程的控制策略刪除策略

設(shè)有兩個(gè)子句C和D，若有置換ó使得Có?D成立，便說(shuō)子句C把子句D歸類(lèi)。例C=P(X)D=P(a)∨Q(a)

取ó={a/x},便有Có=P(a)?{P(a),Q(a)}。刪除策略：若對(duì)s使用歸結(jié)推理過(guò)程中，當(dāng)歸結(jié)式Cj是重言式或Cj被S中子句或歸結(jié)式Ci(i<j)歸類(lèi)時(shí)，便將Cj刪除。第一百二十九頁(yè)，共154頁(yè)。歸結(jié)過(guò)程的控制策略支持集策略

支持集：設(shè)S的子集T，說(shuō)T是支持集，如果S-T是可滿(mǎn)足。（目標(biāo)公式的否定或由它們的后裔產(chǎn)生的子句）策略：每次歸結(jié)時(shí)，至少有一個(gè)子句來(lái)自于T或由T導(dǎo)出的歸結(jié)式。例S={P∨Q,～P∨R,～Q∨R,～R}取T={～R}第一百三十頁(yè)，共154頁(yè)。歸結(jié)過(guò)程的控制策略語(yǔ)義歸結(jié)策略

將子句集S分成兩部分，約定每部分內(nèi)的子句間不允許做歸結(jié)。還引入文字次序，約定歸結(jié)時(shí)其中的一個(gè)子句被歸結(jié)文字只能是該子句中“最大”的文字。例S={～P∨～Q∨R,P∨R,Q∨R,～R}文字次序：P>Q>R解釋I={～P,～Q,～R}第一百三十一頁(yè)，共154頁(yè)。歸結(jié)過(guò)程的控制策略線性歸結(jié)策略首先從子句集S中選取一個(gè)稱(chēng)為頂子句的子句C0開(kāi)始做歸結(jié)，其次是歸結(jié)過(guò)程中所得到的歸結(jié)式Ci立即同另一個(gè)子句Bi進(jìn)行歸結(jié)得歸結(jié)式Ci+1。而B(niǎo)i屬于S或是已出現(xiàn)的歸結(jié)式Cj(j<i)。第一百三十二頁(yè)，共154頁(yè)。歸結(jié)過(guò)程的控制策略單元?dú)w結(jié)：在歸結(jié)過(guò)程中，每次歸結(jié)都有一個(gè)子句是單元（只含一個(gè)文字）子句或單元因子時(shí)的歸結(jié)過(guò)程。第一百三十三頁(yè)，共154頁(yè)。歸結(jié)過(guò)程的控制策略輸入歸結(jié)：在歸結(jié)過(guò)程中，對(duì)兩個(gè)子句所做的每一次歸結(jié)，其中必須有一個(gè)是S的子句時(shí)，便稱(chēng)作輸入歸結(jié)。第一百三十四頁(yè)，共154頁(yè)。歸結(jié)過(guò)程的控制策略控制策略的方法刪除 => 完備采用支撐集 <=>完備語(yǔ)義歸結(jié) <=> 完備線性歸結(jié) <=>完備單元?dú)w結(jié) => 完備輸入歸結(jié) => 完備第一百三十五頁(yè)，共154頁(yè)。謂詞邏輯的歸結(jié)方法對(duì)于子句C1L1和C2L2，如果L1與~L2可合一，且s是其合一者，則(C1C2)s是其歸結(jié)式。例：P(x)Q(y),~P(f(z))R(z) =>Q(y)R(z)第一百三十六頁(yè)，共154頁(yè)。歸結(jié)舉例設(shè)公理集： (x)(R(x)L(x)) (x)(D(x)~L(x)) (x)(D(x)I(x))求證：(x)(I(x)~R(x))化子句集：

(x)(R(x)L(x))=>(x)(~R(x)L(x))=>~R(x)L(x)(1)第一百三十七頁(yè)，共154頁(yè)。 (x)(D(x)~L(x))=>(x)(~D(x)~L(x))=>~D(x)~L(x)(2) (x)(D(x)I(x))=>D(A)I(A)=>D(A)(3) I(A)(4)第一百三十八頁(yè)，共154頁(yè)。目標(biāo)求反：

~(x)(I(x)~R(x))=>(x)~(I(x)~R(x))=>(x)(~I(x)R(x))=>~I(x)R(x)(5)換名后得字句集：

~R(x1)L(x1) ~D(x2)~L(x2) D(A)I(A)~I(x5)R(x5)第一百三十九頁(yè)