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

1、第三章 一般搜索原理 盲目搜索 啟發(fā)式搜索 歸結(jié)原理盲目搜索 圖搜索策略 深度優(yōu)先搜索 寬度優(yōu)先搜索 等代價搜索一些基本概念 節(jié)點深度：根節(jié)點深度=0其它節(jié)點深度=父節(jié)點深度+10123一些基本概念（續(xù)1） 路徑設(shè)一節(jié)點序列為(n0, n1,nk)，對于i=1,k，若節(jié)點ni-1具有一個后繼節(jié)點ni，則該序列稱為從n0到nk的路徑。 路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。用C(ni, nj)表示從ni到nj的路徑的耗散值。一些基本概念（續(xù)1） 擴(kuò)展一個節(jié)點生成出該節(jié)點的所有后繼節(jié)點，并給出它們之間的耗散值。這一過程稱為“擴(kuò)展一個節(jié)點”。一般的圖搜索算法（GRAP

2、HSEARCH）1, G=G0 (G0=s), OPEN=(s);2, CLOSED=( );3, LOOP: IF OPEN=( ) EXIT(FAIL);4, n=FIRST(OPEN), REMOVE(n, OPEN),ADD(n, CLOSED);5, IF GOAL(n) EXIT(SUCCESS);6, EXPAND(n)mi, G=ADD(mi, G);一般的圖搜索算法（續(xù)）7, 標(biāo)記和修改指針：ADD(mj, OPEN), 并標(biāo)記mj到n的指針；計算是否要修改mk、ml到n的指針；計算是否要修改ml到其后繼節(jié)點的指針；8, 對OPEN中的節(jié)點按某種原則重新排序；9, GO LO

3、OP；深度優(yōu)先搜索 在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的(最深的)節(jié)點，深度 相等的節(jié)點可以任意排列。“最晚產(chǎn)生的節(jié)點最先擴(kuò)展”深度優(yōu)先搜索算法1, G=G0(G0=s), OPEN=(s), CLOSED=( );2, LOOP: IF OPEN=( ) EXIT (FAIL);3, n=FIRST(OPEN);4, IF GOAL(n) EXIT (SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, IF DEPTH(n)Dm GO LOOP;7, EXPAND(n) mi, G=ADD(mi, G);8, IF 目標(biāo)在目標(biāo)在mi中中 THEN E

4、XIT(SUCCESS);9, ADD(mj, OPEN), 并標(biāo)記并標(biāo)記mj到到n的指針的指針;10, GO LOOP;2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47

5、6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789abcd1 2 3 8 47 6 5目標(biāo)深度優(yōu)先搜索的性質(zhì) 一般不能保證找到最優(yōu)解 當(dāng)深度限制不合理時，可能找不到解，可以將算法改為可變深度限制 最壞情況時，搜索空間等同于窮舉 與回溯法的差別：圖搜索 是一個通用的與問題無關(guān)的方法寬度優(yōu)先搜索 如果搜索是以接近起始節(jié)點的程度依次擴(kuò)展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索。這種搜索使逐層進(jìn)行的，在對下一層的任意節(jié)點進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點。“先產(chǎn)生的節(jié)點先擴(kuò)展”寬度優(yōu)先搜索算法1, G=G0(G0=s), OPEN=(s), CLO

6、SED=( );2, LOOP: IF OPEN=( ) EXIT (FAIL);3, n=FIRST(OPEN);4, IF GOAL(n) EXIT (SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) mi, G=ADD(mi, G);7, IF 目標(biāo)在目標(biāo)在mi中中 THEN EXIT(SUCCESS);8, ADD(OPEN, mj), 并標(biāo)記并標(biāo)記mj到到n的指針的指針;9, GO LOOP;2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6

7、52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目標(biāo)82 3 41 8 7 6 54寬度優(yōu)先搜索的性質(zhì) 當(dāng)問題有解時，一定能找到解 當(dāng)問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解 方法與問題無關(guān)，具有通用性 效率較低 屬于圖搜索方法等代價搜索 寬度優(yōu)先搜索可被推廣用來解決尋找從起始節(jié)點到目標(biāo)節(jié)點具有最小代價路徑問題，這種推廣了的

8、寬度優(yōu)先搜索算法叫做等代等代價搜索算法價搜索算法。等代價搜索算法 算法1,G=G0(G0=s), OPEN=(s), CLOSED=( ),g(s)=0;2, LOOP: IF OPEN=( ) EXIT (FAIL);3, 從從OPEN表中選擇一個節(jié)點表中選擇一個節(jié)點i,使其使其g(i)為最小。如果有幾個節(jié)點都合格，為最小。如果有幾個節(jié)點都合格，那么就要選擇一個目標(biāo)節(jié)點作為那么就要選擇一個目標(biāo)節(jié)點作為i(要是有目標(biāo)節(jié)點的話要是有目標(biāo)節(jié)點的話)；否則，就從；否則，就從中選一個作為節(jié)點中選一個作為節(jié)點I; REMOVE(i, OPEN), ADD(i, CLOSED);4, IF GOAL(i)

9、 EXIT (SUCCESS);5, EXPAND(i) j, G=ADD(j, G);6, 對每個后繼節(jié)點對每個后繼節(jié)點j,計算計算g(j)=g(i)+c(i,j)且且ADD(OPEN, j), 并標(biāo)記并標(biāo)記j到到i的的指針指針;7, GO LOOP;啟發(fā)式圖搜索 利用知識來引導(dǎo)搜索，達(dá)到減少搜索范圍，降低問題復(fù)雜度的目的。 啟發(fā)信息的強(qiáng)度 強(qiáng)：降低搜索工作量，但可能導(dǎo)致找不到最 優(yōu)解 弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)?盲目搜索，但可能可以找到最優(yōu)解希望： 引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率?；舅枷?定義一個評價函數(shù)f，對當(dāng)前的搜索狀態(tài)進(jìn)行評估，

10、找出一個最有希望的節(jié)點來擴(kuò)展。1，啟發(fā)式搜索算法A（A算法） 評價函數(shù)的格式：f(n) = g(n) + h(n)f(n)：評價函數(shù)h(n)：啟發(fā)函數(shù)符號的意義 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)的估計值A(chǔ)算法1, OPEN=(s), f(s)=g(s)+h(s);2, LOOP: IF OPEN=( ) EXIT(FAIL);3, n=FIRST(OPEN);4, IF GOAL(n) EXIT(SUCCESS

11、);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) Mi, 計算f(n, mi)=g(n, mi)+h(mi);A算法（續(xù)）ADD(mj, OPEN), 標(biāo)記mj到n的指針；IF f(n, mk)f(mk) f(mk)=f(n, mk), 標(biāo)記mk到n的指針；IF f(n, ml)f*(s)。A*算法的性質(zhì)（續(xù)2）引理2.2：A*結(jié)束前，OPEN表中必存在f(n)f*(s)。A*算法的性質(zhì)（續(xù)3）定理2：對無限圖，若從初始節(jié)點s到目標(biāo)節(jié)點t有路徑存在，則A*一定成功結(jié)束。A*算法的性質(zhì)（續(xù)4）推論2.1：OPEN表上任一具有f(n) h1(n)，

12、則在具有一條從s到t的路徑的隱含圖上，搜索結(jié)束時，由A2所擴(kuò)展的每一個節(jié)點，也必定由A1所擴(kuò)展，即A1擴(kuò)展的節(jié)點數(shù)至少和A2一樣多。簡寫：如果h2(n) h1(n), 則A1擴(kuò)展的節(jié)點數(shù)A2擴(kuò)展的節(jié)點數(shù)A*算法的改進(jìn) 問題的提出：因A算法第6步對ml類節(jié)點可能要重新放回到OPEN表中，因此可能會導(dǎo)致多次重復(fù)擴(kuò)展同一個節(jié)點，導(dǎo)致搜索效率下降。s(10)A(1)B(5)C(8)G 目標(biāo)631118一個例子：一個例子：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

13、(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)出現(xiàn)多次擴(kuò)展節(jié)點的原因 在前面的擴(kuò)展中，并沒有找到從初始節(jié)點到當(dāng)前節(jié)點的最短路徑，如節(jié)點A。解決的途徑 對h加以限制 能否對h增加適當(dāng)?shù)南拗疲沟玫谝淮螖U(kuò)展一個節(jié)點時，就找到了從s到該節(jié)點的最短路徑。 對算法加以改進(jìn) 能否對算法加以改進(jìn)，避免或減少節(jié)點的多次擴(kuò)展。改進(jìn)的條件 可采納性不變 不多擴(kuò)展節(jié)點 不增加算法的復(fù)雜性對h加以限制 定義：一個啟發(fā)函數(shù)h，如果對所有節(jié)點ni和nj，其中

14、nj是ni的子節(jié)點，滿足h(ni) - h(nj) c(ni, nj)h(t) = 0則稱h是單調(diào)的。h(ni)ninjh(nj)c(ni,nj)h單調(diào)的性質(zhì) 定理5：若h(n)是單調(diào)的，則A*擴(kuò)展了節(jié)點n之后，就已經(jīng)找到了到達(dá)節(jié)點n的最佳路徑。即：當(dāng)A*選n擴(kuò)展時，有g(shù)(n)=g*(n)。h單調(diào)的性質(zhì)（續(xù)） 定理6：若h(n)是單調(diào)的，則由A*所擴(kuò)展的節(jié)點序列其f值是非遞減的。h單調(diào)的例子 8數(shù)碼問題： h為“不在位”的將牌數(shù) 1h(ni) - h(nj) = 0(nj為ni的后繼節(jié)點) -1 h(t) = 0c(ni, nj) = 1 滿足單調(diào)的條件。對算法加以改進(jìn) 一些結(jié)論： OPEN表

15、上任一具有f(n) f*(s)的節(jié)點定會被擴(kuò)展。 A*選作擴(kuò)展的任一節(jié)點，定有f(n)f*(s)。改進(jìn)的出發(fā)點OPEN = ( )f*(s)f值小于f*(s)的節(jié)點f值大于等于f*(s)的節(jié)點fm：到目前為止已擴(kuò)展節(jié)點的最大f值，用fm代替f*(s)修正過程A1, OPEN=(s), f(s)=g(s)+h(s), fm=0;2, LOOP: IF OPEN=( ) EXIT(FAIL);3, NEST=ni|f(ni)5)n2(4)n3(4)n0(3)n0(3-4)n0n1n2n3n4n5n6n7n8n4(1)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4)n5(1)n

16、5(1-2)n0n1n2n3n4n5n6n7n8紅色代價紅色代價：5藍(lán)色藍(lán)色代價代價：6n0(4)n4(1)n5(1-2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4-5)n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)目標(biāo)目標(biāo)初始節(jié)點n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)目標(biāo)目標(biāo)初始節(jié)點n0n1n2n3n4n5n6n7n8初始節(jié)點可解初始節(jié)點可解n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)

17、n6(2)n7(0)n8(0)歸結(jié)原理 概述 命題邏輯的歸結(jié)法 子句形 Herbrand定理 歸結(jié)原理 歸結(jié)過程的策略控制歸結(jié)原理 概述 命題邏輯的歸結(jié)法 子句形 Herbrand定理 歸結(jié)原理 歸結(jié)過程的策略控制概述 歸結(jié)原理由J.A.Robinson由1965年提出。 與演繹法完全不同，新的邏輯演算算法。 一階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在有限步內(nèi)給以判定。 語義網(wǎng)絡(luò)、框架表示、產(chǎn)生式規(guī)則等等都是以推理方法為前提的。即，有了規(guī)則已知條件，順藤摸瓜找到結(jié)果。 而歸結(jié)方法是自動推理、自動推導(dǎo)證明用的。（“數(shù)學(xué)定理機(jī)器證明”） 本課程

18、只討論一階謂詞邏輯描述下的歸結(jié)推理方法，不涉及高階謂詞邏輯問題。 歸結(jié)原理 概述 命題邏輯的歸結(jié)法 子句形 Herbrand定理 歸結(jié)原理 歸結(jié)過程的策略控制歸結(jié)原理 概述 命題邏輯的歸結(jié)法 子句形 Herbrand定理 歸結(jié)原理 歸結(jié)過程的策略控制命題邏輯的歸結(jié)法 基本單元：簡單命題（陳述句）例： 命題： A1、A2、A3 和 B求證： A1A2A3成立，則B成立，即：A1A2A3 B反證法：證明A1A2A3B 是矛盾式 （永假式） 命題邏輯的歸結(jié)法建立子句集 合取范式：命題、命題和的與， 如：P（ PQ）（ PQ）子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：P（ PQ）（

19、PQ） 子句集 S：S = P, PQ, PQ 命題邏輯的歸結(jié)法 歸結(jié)式消除互補(bǔ)對，求新子句得到歸結(jié)式。如子句：C1= C1L, C2 = C2 歸結(jié)式：R(C1, C2) = C1 C2 注意：C1C2 R(C1, C2) ， 反之成立。 L假言推理: 由合適公式W1和W1 W2產(chǎn)生合適公式W2 ,如何用歸結(jié)法證明?命題邏輯的歸結(jié)法 歸結(jié)過程 對結(jié)論作否定,并加入前提中 將命題寫成合取范式 求出子句集 對子句集使用歸結(jié)推理規(guī)則 歸結(jié)式作為新子句參加歸結(jié) 歸結(jié)式為空子句 ，S是不可滿足的（矛盾），原命題成立。 （證明完畢） 謂詞的歸結(jié)：除了有量詞和函數(shù)以外，其余和命題歸結(jié)過程一樣。 命題邏輯的

20、歸結(jié)法命題邏輯的歸結(jié)法 例 證明先將化為合取范式 建立子句集 S=對S做歸結(jié) P NILPQQP)( PQQPPQQPQQP PQQP, , P歸結(jié)原理 概述 命題邏輯的歸結(jié)法 子句形 Herbrand定理 歸結(jié)原理 歸結(jié)過程的策略控制歸結(jié)原理 概述 命題邏輯的歸結(jié)法 子句形 Herbrand定理 歸結(jié)原理 歸結(jié)過程的策略控制子句形 引用Herbrand定理，以說明歸結(jié)原理的意義及一個原理形成的根基與背景 SKOLEM標(biāo)準(zhǔn)形 前束范式：把所有的量詞都提到前面去，然后消掉所有量詞。定義：說公式A是一個前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末

21、端。 即(Q1x1)(Qnxn)M(x1, , xn),其中Qixi為存在量詞或全稱量詞, M(x1, , xn) 為合取范式(由一些子句的合取組成)。子句形( Skolem 標(biāo)準(zhǔn)形) 量詞消去原則：消去存在量詞“”，略去全程量詞“”。注意：左邊有全稱量詞的存在量詞，消去時該變量改寫成為全稱量詞的函數(shù)(Skloem函數(shù))；如沒有，改寫成為常量。 例子：見人工智能及其應(yīng)用P75子句形( Skolem 標(biāo)準(zhǔn)形) 定理：謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。 SKOLEM標(biāo)準(zhǔn)形定義：消去量詞后的謂詞公式。注意：謂詞公式G的SKOLEM標(biāo)準(zhǔn)形同G并不等值。 子句形( Sk

22、olem 標(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)子句形 子句與子句集 文字：不含任何連接詞的謂詞公式。 子句：一些文字的析取（謂詞的和）。 子句集S的求取： G SKOLEM標(biāo)準(zhǔn)形 消去存在變量 以“，”取代“”，并表示為集合形式 。子句形 G是不可滿足的 S是不可滿足的 G與S不等價，但在不可滿足的意義下是一致的。 定理：若G是給定的公式，而S是相應(yīng)的子句集，則G是不可滿足的 S是不可滿足的。 注意：G真不一定S真，而S真必有G真。即： S = G子句形 G = G

23、1 G2 G3 Gn 的子句形G的子句集可以分解成幾個單獨處理。 有 SG = S1 U S2 U S3 U U Sn則SG 與 S1 U S2 U S3 U U Sn在不可滿足的意義上是一致的。即SG 不可滿足 S1 U S2 U S3 U U Sn不可滿足歸結(jié)原理 概述 命題邏輯的歸結(jié)法 子句形 Herbrand定理 歸結(jié)原理 歸結(jié)過程的策略控制歸結(jié)原理 概述 命題邏輯的歸結(jié)法 子句形 Herbrand定理 歸結(jié)原理 歸結(jié)過程的策略控制Herbrand定理 問題：一階邏輯公式的永真性（永假性）的判定是否能在有限步內(nèi)完成？Herbrand定理 1936年圖靈(Turing)和邱吉(Churc

24、h)互相獨立地證明了： “沒有一般的方法使得在有限步內(nèi)判定一階邏輯的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步內(nèi)判定它是永真（或永假）。對于非永真（或永假）的公式就不一定能在有限步內(nèi)得到結(jié)論。判定的過程將可能是不停止的。” Herbrand定理 Herbrand的思想 定義：公式G永真：對于G的所有解釋，G都為真。 思想：尋找一個已給的公式是真的解釋。然而，如果所給定的公式的確是永假的，就沒有這樣的解釋存在，并且算法在有限步內(nèi)停止。 Herbrand定理 H域 H解釋 語義樹 結(jié)論：Herbrand定理Herbrand定理 H域 H解釋 語義樹 結(jié)論：Her

25、brand定理Herbrand定理（H域） 基本方法： 因為量詞是任意的，所討論的個體變量域D是任意的，所以解釋的個數(shù)是無限、不可數(shù)的 。 簡化討論域。建立一個比較簡單、特殊的域，使得只要在這個論域上，該公式是不可滿足的。 此域稱為H域：H0為G中所出現(xiàn)的常量的集合，若G中沒有常量，就任取常量 ，H0=a。 規(guī)定 為H域 例題請參考教科書P27),.,(11niittfHHDaHHH域舉例 例1 S=P(a), P(x)P(f(x)依定義有H0=aH1=a Uf(a)=a,f(a)H2=a,f(a)Uf(a),f(f(a)=a,f(a),f(f(a)H= a,f(a),f(f(a)，Herbr

26、and定理（H域） 幾個基本概念f（t1, t2, tn）：f為子句集S中的所有函數(shù)變量。t1, t2, tn為S的H域的元素。通過它們來討論永真性。 原子集A：謂詞套上H域的元素組成的集合。如A = 所有形如 P(t1, t2, tn)的元素即把H中的東西填到S的謂詞里去。S中的謂詞是有限的，H是可數(shù)的，因此，A也是可數(shù)的。 一旦原子集內(nèi)真值確定好（規(guī)定好），則S在H上的真值可確定。成為可數(shù)問題。 原子集舉例 例1 S=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), Herbrand定理（H域） 沒有變量出現(xiàn)

27、的原子、文字、子句和子句集，分別稱作基原子、基文字、基子句和基子句集。它們在討論子句集S的不可滿足性時占有重要置。Herbrand定理 H域 H解釋 語義樹 結(jié)論：Herbrand定理Herbrand定理 H域 H解釋 語義樹 結(jié)論：Herbrand定理Herbrand定理（H解釋） 解釋I*：取一個值得到一個結(jié)論I映射S中到所有常量符號到它們本身。(即原子集) 令f是n元函數(shù)，I是f下的一個指派，即H中的元素到f的一個映射（函數(shù)值）。簡單地說(P29)，A中的各元素真假組合都是H的解釋。（或真或假只取一個） 問題：對于所有的解釋，全是假才可判定。因為所有解釋代表了所有的情況，如可窮舉，問題便

28、可解決 。H解釋-舉例 例1 S=P(a), P(x)P(f(x) S S的的H H域域 H= a,f(a),f(f(a)， S S的原子集為的原子集為 A=P(a),P(f(a),P(f(f(a), S S的的H H解釋：解釋：I1*= P(a),P(f(a),P(f(f(a), S| I1*=TI2*= 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)心的是：對論域上的任一解釋I，若有 S| I=T,如何求得一個相應(yīng)的H解釋I*,使得S| I*=T成立。Herbrand定理（H解釋） 如下三個定理保

29、證了歸結(jié)法的正確性： 定理1：設(shè)I是S的論域D上的解釋，存在對應(yīng)于I的H解釋I*，使得若有S|I = T，必有 S|I* = T。 定理2：子句集S是不可滿足的，當(dāng)且僅當(dāng)所有的S的H解釋下為假。 定理3：子句集S是不可滿足的，當(dāng)且僅當(dāng)對每一個解釋I下，至少有S的某個子句的某個基例為假。 Herbrand定理（H解釋） 基例S中某子句中所有變元符號均以S的H域中的元素代入時，所得的基子句C稱為C的一個基例。 若一個子句為假，則此解釋為假。 一般來說，D是無窮不可列的，因此，子句集S也是無窮不可列的。但S確定后H是無窮可列的。不過在H上證明S的不可滿足性仍然是不可能的。 解決問題的方法：語義樹He

30、rbrand定理 H域 H解釋 語義樹 結(jié)論：Herbrand定理Herbrand定理 H域 H解釋 語義樹 結(jié)論：Herbrand定理Herbrand定理（語義樹） 構(gòu)成方法 原子集中所有元素逐層添加的一棵二叉樹。將元素的是與非分別標(biāo)記在兩側(cè)的分枝上（可不完全畫完） 。(P34) 特點 一般情況H是可數(shù)集，S的語義樹是無限樹。 Herbrand定理（語義樹） 意義 S H A 語義樹 可以理解語義樹為H域的圖形解釋。 目的：把每個解釋都攤開。語義樹中包含原子集的全部元素，因此，語義樹是完全的。每一個直到葉子節(jié)點的分支對應(yīng)S的一個解釋?？梢酝ㄟ^對語義樹每一個分支來計算S的真值。如果每個基例都為

31、假，則可認(rèn)為是不可滿足的。語義樹-舉例 例1 設(shè)子句集S的原子集 A=P,Q,R 語義樹： N0 N11N12N21N22N23N24N31N32N33N34N35N36N37N38P QQR R PI(N)表示從根節(jié)點到節(jié)點N分枝上所標(biāo)記的所有文字的并集。如 I(N34)=P, Q, RHerbrand定理（語義樹） 幾個概念 失敗結(jié)點失敗結(jié)點： 當(dāng)（由上）延伸到點當(dāng)（由上）延伸到點N N時，時，I(N)I(N)已表明了已表明了S S的某子句的某基例假。的某子句的某基例假。但但N N以前尚不能判斷這事實。就稱以前尚不能判斷這事實。就稱N N為失敗結(jié)點。為失敗結(jié)點。 完全語義樹完全語義樹： 如

32、果對語義樹的所有葉結(jié)點如果對語義樹的所有葉結(jié)點NN來說，來說， I(N)I(N)包含了包含了S S的原子集的原子集 A=A1,A2,A=A1,A2, 中的所有元素中的所有元素A Ai i或或 A Ai i，I=1 I=1 n n。 封閉語義樹封閉語義樹：如果如果S S的完全語義樹的每個分枝上都有一個失敗結(jié)點，就稱它是的完全語義樹的每個分枝上都有一個失敗結(jié)點，就稱它是一棵封閉語義樹。一棵封閉語義樹。封閉語義樹-舉例例 子句集S=P(x)Q(x),P(f(y), P(x)Q(x),P(f(y), Q(f(y)Q(f(y) H=a,f(a),f(f(a), A=P(a),Q(a),P(f(a),Q(

33、f(a), 語義樹： N0 N11N12N21N22N23N24N31N32N33N34N35N36N37N38P(a)Q(a)P(f(a)N41N42N43N44N45N46N47N48N49N410N411N413N415N412N414N416這是一個無限樹，然而它是否是一個封閉樹？Q(f(a)I(N41)=P(a),Q(a),P(f(a),Q(f(a),它使S的子句Q(f(y)Q(f(y)的的基例Q(f(a)Q(f(a)為假，而而N41的父輩不能使子句的基例為假封閉語義樹-舉例例 子句集S=P(x)Q(x),P(f(y), P(x)Q(x),P(f(y), Q(f(y)Q(f(y) H

34、=a,f(a),f(f(a), A=P(a),Q(a),P(f(a),Q(f(a), 封閉語義樹： N0 N11N12N21N22N23N24N31N32N36N37N38P(a)Q(a)P(f(a)N41N42N49N410N413N414Q(f(a)Herbrand定理 H域 H解釋 語義樹 結(jié)論：Herbrand定理Herbrand定理 H域 H解釋 語義樹 結(jié)論：Herbrand定理Herbrand定理（結(jié)論）Herbrand定理：1. 子句集S是不可滿足的，當(dāng)且僅當(dāng)對應(yīng)于S的完全語義數(shù)是棵有限封閉樹。 2. 子句集S是不可滿足的，當(dāng)且僅當(dāng)存在不可滿足的S的有限基例集。 Herbran

35、d定理（結(jié)論） 定理的意義 Herbrand定理已將證明問題轉(zhuǎn)化成了命題邏輯問題。 由此定理保證，可以放心的用機(jī)器來實現(xiàn)自動推理了。（歸結(jié)原理） 注意 Herbrand定理給出了一階邏輯的半可判定算法，即僅當(dāng)被證明定理是成立時，使用該算法可以在有限步得證。而當(dāng)被證定理并不成立時，使用該算法得不出任何結(jié)論。但是 例 S=P(x,g(x),y,h(x,y),z,k(x,y,z), P(u,v,e(v),w,f(v,w),x)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)P(a,

36、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個元素 S1： 63 + 64 = 1512個元素 H2 ： 元素個數(shù)有 63 數(shù)量級（由于變量最多的函數(shù)是k(x,y,z),三個變 量都可能取值于H1的六個元素） S2 ：元素個數(shù)有 ( (63) ) 4 數(shù)量級建立S3 ， S4 ，直到S5才是不可滿足。然而 S5元素個數(shù)已達(dá)（ 10 64）4=10256Herbrand定理（結(jié)論） 仍存在的問題：基例集序列元素的數(shù)目隨子句基的元素數(shù)目成指數(shù)地增加。因此，Herbrand定理是30年代提出的，始終沒有顯著的成績。 直至196

37、5年Robinson提出了歸結(jié)原理。歸結(jié)原理 概述 命題邏輯的歸結(jié)法 子句形 Herbrand定理 歸結(jié)原理 歸結(jié)過程的策略控制歸結(jié)原理 概述 命題邏輯的歸結(jié)法 子句形 Herbrand定理 歸結(jié)原理 歸結(jié)過程的策略控制歸結(jié)原理 歸結(jié)原理正確性的根本在于，找到矛盾可以肯定不真。 方法： 和命題邏輯一樣。 但由于有函數(shù)，所以要考慮合一和置換。 (定義與例題參考教科書P41)歸結(jié)原理 置換和合一的注意事項：1.謂詞的一致性，P()與Q()， 不可以2.常量的一致性，P(a, )與P(b,.)， 不可以 常量與變量，P(a, .)與P(x, )， 可以3.變量與函數(shù)，P(a, x, .)與P(x,

38、f(x), )，不可以；但P(a, x, )與P(x, f(y), )，可以1.是不能同時消去兩個互補(bǔ)對，PQ與PQ的空，不可以n先進(jìn)行內(nèi)部簡化（置換、合并） 歸結(jié)原理 歸結(jié)的過程(P48)寫出謂詞關(guān)系公式 用反演法寫出謂詞表達(dá)試 SKOLEM標(biāo)準(zhǔn)形 子句集S 對S中可歸結(jié)的子句做歸結(jié) 歸結(jié)式仍放入S中，反復(fù)歸結(jié)過程 得到空子句 得證歸結(jié)原理 歸結(jié)法的實質(zhì)： 歸結(jié)法是僅有一條推理規(guī)則的推理方法。 歸結(jié)的過程是一個語義樹倒塌的過程。 (P51) 歸結(jié)法的問題 子句中有等號或不等號時，完備性不成立。 Herbrand定理的不實用性引出了可實用的歸結(jié)法。歸結(jié)原理 概述 命題邏輯的歸結(jié)法 子句形 He

39、rbrand定理 歸結(jié)原理 歸結(jié)過程的策略控制歸結(jié)原理 概述 命題邏輯的歸結(jié)法 子句形 Herbrand定理 歸結(jié)原理 歸結(jié)過程的策略控制歸結(jié)過程的控制策略 要解決的問題： 歸結(jié)方法的知識爆炸。 控制策略的目的 歸結(jié)點盡量少 控制策略的原則給出控制策略，以使僅對選擇合適的子句間方可做歸結(jié)。避免多余的、不必要的歸結(jié)式出現(xiàn)?；蛘哒f，少做些歸結(jié)仍能導(dǎo)出空子句。歸結(jié)過程的控制策略 盲目歸結(jié) 例 S=PQQ, PQ,PQ,PQ, Q, PQ Q是不可滿足。 證明從S0=S開始，依次構(gòu)造 Si=C1,C2的歸結(jié)式|C1S0S1 Si-1,C2 Si-1 ,i=1,2, ,直至得到空子句。具體過程如下：S0

40、 (1) PQ (2)Q (2) PQQ (3)P (3)PQ (4)Q (4) PQ QS S1 1 (5)Q (5)Q (1)(2)(1)(2) (6)P (6)P (1)(3)(1)(3) (7)Q (7)QQ Q (1)(4)(1)(4) (8)P (8)PP P (1)(4)(1)(4) (9)Q (9)Q Q Q (2)(3)(2)(3) (10)P (10)PP P (2)(3)(2)(3) (11) (11)P P (2)(4)(2)(4) (12) (12)Q Q (3)(4)(3)(4)歸結(jié)過程的控制策略(盲目歸結(jié))S S2 2 (13)P (13)P (1)(7)(1)(

41、7) (14)PQ (14)PQ (1)(8)(1)(8) (15)PQ (15)PQ (1)(9)(1)(9) (16)PQ (16)PQ (1)(10)(1)(10) (17)Q (17)Q (1)(11)(1)(11) (18)P (18)P (1)(12)(1)(12) (19) (19)Q (2)(6)(2)(6) (20) (20)PQ PQ (3)(4)(3)(4) (21) (21)PQ PQ (2)(8)(2)(8) (22) (22)PQ PQ (2)(9)(2)(9) (23) (23)PQ PQ (2)(10)(2)(10) (24) (24)P P (2)(12)(2

42、)(12) (25) P (25) P (3)(5)(3)(5) (26)P (26)PQ Q (3)(7)(3)(7) (27) P (27) PQ Q (3)(8)(3)(8) (28) P (28) PQ Q (3)(9)(3)(9) (29) P (29) PQ Q (3)(10)(3)(10) (30) (30)Q Q (3)(11)(3)(11) (31) (31)P P (4)(5)(4)(5) (32) (32)Q Q (4)(6)(4)(6) (33) (33)PPQ Q (4)(7)(4)(7) (34) (34)PPQ Q (4)(8)(4)(8) (35) (35)PP

43、Q Q (4)(9)(4)(9) (36) (36)PPQ Q (4)(10)(4)(10) (37) (37)Q (5)(7)(5)(7) (38)Q (38)Q (5)(9)(5)(9) (39) (39) (5)(12)(5)(12)產(chǎn)生過多不必要的歸結(jié)式。一類是重言式（產(chǎn)生過多不必要的歸結(jié)式。一類是重言式（7 7）- -（1010）由它們又產(chǎn)）由它們又產(chǎn)生了（生了（1313）- -（1616），（），（2020）- -（2323），），(26)-(29),(33)-(39)(26)-(29),(33)-(39)。另一。另一類是重復(fù)的，如類是重復(fù)的，如P,Q, P,Q, P, P, Q.

44、Q.歸結(jié)過程的控制策略刪除策略 設(shè)有兩個子句設(shè)有兩個子句C C和和D D，若有置換，若有置換使得使得 C C D D成立，便說子句成立，便說子句C C把子把子句句D D歸類。歸類。例例 C=P(X) D=P(a)C=P(X) D=P(a)Q(a)Q(a) 取取=a/x,=a/x,便有便有C =P(a) C =P(a) P(a),P(a),Q(a)Q(a)。刪除策略：若對s使用歸結(jié)推理過程中，當(dāng)歸結(jié)式Cj是重言式或Cj被S中子句或歸結(jié)式Ci(iQR 解釋解釋I= P, Q, R 歸結(jié)過程的控制策略 線性歸結(jié)策略 首先從子句集S中選取一個稱為頂子句的子句C0開始做歸結(jié)，其次是歸結(jié)過程中所得到的歸結(jié)

45、式Ci立即同另一個子句Bi進(jìn)行歸結(jié)得歸結(jié)式Ci+1。而Bi屬于S或是已出現(xiàn)的歸結(jié)式Cj(j完備 采用支撐集 完備 語義歸結(jié)完備 線性歸結(jié) 完備 單元歸結(jié)=完備 輸入歸結(jié) =完備謂詞邏輯的歸結(jié)方法 對于子句C1L1和C2L2，如果L1與L2可合一，且s是其合一者，則(C1C2)s是其歸結(jié)式。 例： P(x)Q(y), P(f(z)R(z) = Q(y)R(z)歸結(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) (x)(D(x)L(x

46、)= (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) 目標(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)例題得歸結(jié)樹R(x1) L(x1)D(x2) L(x2)D(A) I(A) I(x5) R(x5)I(A) I(x5)R(x5) R(A) A/x5 R(x1)L(x1) L(A) A/x1 D(x2)L(x2) D(A

47、) A/x2 D(A) nil歸結(jié)反演求解歸結(jié)反演求解-提取回答的過程提取回答的過程 先進(jìn)行歸結(jié)，證明結(jié)論的正確性； 用重言式代替結(jié)論求反得到的子句； 按照證明過程，進(jìn)行歸結(jié)； 最后，在原來為空的地方，得到的就是提取的回答。 修改后的證明樹稱為修改證明樹歸結(jié)反演求解歸結(jié)反演求解-舉例舉例“如果無論John到哪里去，F(xiàn)ido也就去那里，那么如果John在學(xué)校，F(xiàn)ido在哪里？”已知：(x)AT(John, x) AT(Fido, x) AT(John, School)求證：(x)AT(Fido, x)如果我們首先證明公式 (x)AT(Fido, x) 在邏輯上遵循前提公式集，然后尋求一個存在x的例，那么就能解決“Fido在哪里”的問題。歸結(jié)反演求解歸結(jié)反演求解-基于歸結(jié)的問答系統(tǒng)已知：(x)AT(John, x) AT(Fido, x) AT