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

1、2022-6-8人工智能講義1第三章 一般搜索原理 盲目搜索 啟發(fā)式搜索 歸結原理2022-6-8人工智能講義2盲目搜索 圖搜索策略 深度優(yōu)先搜索 寬度優(yōu)先搜索 等代價搜索2022-6-8人工智能講義3一些基本概念 節(jié)點深度：根節(jié)點深度=0其它節(jié)點深度=父節(jié)點深度+101232022-6-8人工智能講義4一些基本概念（續(xù)1） 路徑設一節(jié)點序列為(n0, n1,nk)，對于i=1,k，若節(jié)點ni-1具有一個后繼節(jié)點ni，則該序列稱為從n0到nk的路徑。 路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。用C(ni, nj)表示從ni到nj的路徑的耗散值。2022-6-8人工智

2、能講義5一些基本概念（續(xù)1） 擴展一個節(jié)點生成出該節(jié)點的所有后繼節(jié)點，并給出它們之間的耗散值。這一過程稱為“擴展一個節(jié)點”。2022-6-8人工智能講義6一般的圖搜索算法（GRAPHSEARCH）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);2022-6-8人工智能講義7一般的圖搜索算法（續(xù)

3、）7, 標記和修改指針：ADD(mj, OPEN), 并標記mj到n的指針；計算是否要修改mk、ml到n的指針；計算是否要修改ml到其后繼節(jié)點的指針；8, 對OPEN中的節(jié)點按某種原則重新排序；9, GO LOOP；2022-6-8人工智能講義8深度優(yōu)先搜索 在深度優(yōu)先搜索中，首先擴展最新產(chǎn)生的(最深的)節(jié)點，深度 相等的節(jié)點可以任意排列?！白钔懋a(chǎn)生的節(jié)點最先擴展”2022-6-8人工智能講義9深度優(yōu)先搜索算法1, G=G0(G0=s), OPEN=(s), CLOSED=( );2, LOOP: IF OPEN=( ) EXIT (FAIL);3, n=FIRST(OPEN);4, IF G

4、OAL(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 目標在目標在mi中中 THEN EXIT(SUCCESS);9, ADD(mj, OPEN), 并標記并標記mj到到n的指針的指針;10, GO LOOP;2022-6-8人工智能講義102 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 4

5、7 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 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789abcd1 2 3 8 47 6 5目標2022-6-8人工智能講義11深度優(yōu)先搜索的性質(zhì) 一般不能保證找到最優(yōu)解 當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制 最壞情況時，搜索空

6、間等同于窮舉 與回溯法的差別：圖搜索 是一個通用的與問題無關的方法2022-6-8人工智能講義12寬度優(yōu)先搜索 如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索。這種搜索使逐層進行的，在對下一層的任意節(jié)點進行搜索之前，必須搜索完本層的所有節(jié)點。“先產(chǎn)生的節(jié)點先擴展”2022-6-8人工智能講義13寬度優(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, O

7、PEN), ADD(n, CLOSED);6, EXPAND(n) mi, G=ADD(mi, G);7, IF 目標在目標在mi中中 THEN EXIT(SUCCESS);8, ADD(OPEN, mj), 并標記并標記mj到到n的指針的指針;9, GO LOOP;2022-6-8人工智能講義142 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

8、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目標82 3 41 8 7 6 542022-6-8人工智能講義15寬度優(yōu)先搜索的性質(zhì) 當問題有解時，一定能找到解 當問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解 方法與問題無關，具有通用性 效率較低 屬于圖搜索方法2022-6-8人工智能講義16等代價搜索 寬度優(yōu)先搜索可被推廣用來解決尋找從起始節(jié)點到目標節(jié)點具有最小代價路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做等代等代價搜索算法價搜索算法。2022-6-8人工智能講義17等代價搜索算法 算法1,

9、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é)點都合格，那么就要選擇一個目標節(jié)點作為那么就要選擇一個目標節(jié)點作為i(要是有目標節(jié)點的話要是有目標節(jié)點的話)；否則，就從；否則，就從中選一個作為節(jié)點中選一個作為節(jié)點I; REMOVE(i, OPEN), ADD(i, CLOSED);4, IF GOAL(i) EXIT (SUCCESS);5, EXPAND(i) j, G=ADD

10、(j, G);6, 對每個后繼節(jié)點對每個后繼節(jié)點j,計算計算g(j)=g(i)+c(i,j)且且ADD(OPEN, j), 并標記并標記j到到i的的指針指針;7, GO LOOP;2022-6-8人工智能講義18啟發(fā)式圖搜索 利用知識來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。 啟發(fā)信息的強度 強：降低搜索工作量，但可能導致找不到最 優(yōu)解 弱：一般導致工作量加大，極限情況下變?yōu)?盲目搜索，但可能可以找到最優(yōu)解2022-6-8人工智能講義19希望： 引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。2022-6-8人工智能講義20基本思想 定義一個評價函數(shù)f，對當

11、前的搜索狀態(tài)進行評估，找出一個最有希望的節(jié)點來擴展。2022-6-8人工智能講義211，啟發(fā)式搜索算法A（A算法） 評價函數(shù)的格式：f(n) = g(n) + h(n)f(n)：評價函數(shù)h(n)：啟發(fā)函數(shù)2022-6-8人工智能講義22符號的意義 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)的估計值2022-6-8人工智能講義23A算法1, OPEN=(s), f(s)=g(s)+h(s);2, LOOP: IF OPEN

12、=( ) EXIT(FAIL);3, n=FIRST(OPEN);4, IF GOAL(n) EXIT(SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) Mi, 計算f(n, mi)=g(n, mi)+h(mi);2022-6-8人工智能講義24A算法（續(xù)）ADD(mj, OPEN), 標記mj到n的指針；IF f(n, mk)f(mk) f(mk)=f(n, mk), 標記mk到n的指針；IF f(n, ml)f*(s)。2022-6-8人工智能講義32A*算法的性質(zhì)（續(xù)2）引理2.2：A*結束前，OPEN表中必存在f(n)f*

13、(s)。2022-6-8人工智能講義33A*算法的性質(zhì)（續(xù)3）定理2：對無限圖，若從初始節(jié)點s到目標節(jié)點t有路徑存在，則A*一定成功結束。2022-6-8人工智能講義34A*算法的性質(zhì)（續(xù)4）推論2.1：OPEN表上任一具有f(n) h1(n)，則在具有一條從s到t的路徑的隱含圖上，搜索結束時，由A2所擴展的每一個節(jié)點，也必定由A1所擴展，即A1擴展的節(jié)點數(shù)至少和A2一樣多。簡寫：如果h2(n) h1(n), 則A1擴展的節(jié)點數(shù)A2擴展的節(jié)點數(shù)2022-6-8人工智能講義38A*算法的改進 問題的提出：因A算法第6步對ml類節(jié)點可能要重新放回到OPEN表中，因此可能會導致多次重復擴展同一個節(jié)點

14、，導致搜索效率下降。2022-6-8人工智能講義39s(10)A(1)B(5)C(8)G 目標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(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)2022-6-8人工智能講義40出現(xiàn)多次擴展節(jié)點的原因 在前面的擴展中，并沒有

15、找到從初始節(jié)點到當前節(jié)點的最短路徑，如節(jié)點A。2022-6-8人工智能講義41解決的途徑 對h加以限制 能否對h增加適當?shù)南拗?，使得第一次擴展一個節(jié)點時，就找到了從s到該節(jié)點的最短路徑。 對算法加以改進 能否對算法加以改進，避免或減少節(jié)點的多次擴展。2022-6-8人工智能講義42改進的條件 可采納性不變 不多擴展節(jié)點 不增加算法的復雜性2022-6-8人工智能講義43對h加以限制 定義：一個啟發(fā)函數(shù)h，如果對所有節(jié)點ni和nj，其中nj是ni的子節(jié)點，滿足h(ni) - h(nj) c(ni, nj)h(t) = 0則稱h是單調(diào)的。h(ni)ninjh(nj)c(ni,nj)2022-6-8

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

17、點定會被擴展。 A*選作擴展的任一節(jié)點，定有f(n)f*(s)。2022-6-8人工智能講義48改進的出發(fā)點OPEN = ( )f*(s)f值小于f*(s)的節(jié)點f值大于等于f*(s)的節(jié)點fm：到目前為止已擴展節(jié)點的最大f值，用fm代替f*(s)2022-6-8人工智能講義49修正過程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)2022-6-8人工智能講義63n0n1n2n3n4n5n6n7n8n4(1)n1(5)n2(4)

18、n3(4)n6(2)n7(0)n8(0)n0(4)n5(1)n5(1-2)2022-6-8人工智能講義64n0n1n2n3n4n5n6n7n8紅色代價紅色代價：5藍色藍色代價代價：6n0(4)n4(1)n5(1-2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4-5)2022-6-8人工智能講義65n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2022-6-8人工智能講義66目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2

19、)n7(0)n8(0)2022-6-8人工智能講義67目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8初始節(jié)點可解初始節(jié)點可解n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2022-6-8人工智能講義68歸結原理 概述 命題邏輯的歸結法 子句形 Herbrand定理 歸結原理 歸結過程的策略控制2022-6-8人工智能講義69歸結原理 概述 命題邏輯的歸結法 子句形 Herbrand定理 歸結原理 歸結過程的策略控制2022-6-8人工智能講義70概述 歸結原理由J.A.Robinson由1965年提出。 與演繹法完全不同，新的邏輯演算算法。 一

20、階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使用歸結原理，總可以在有限步內(nèi)給以判定。 語義網(wǎng)絡、框架表示、產(chǎn)生式規(guī)則等等都是以推理方法為前提的。即，有了規(guī)則已知條件，順藤摸瓜找到結果。 而歸結方法是自動推理、自動推導證明用的。（“數(shù)學定理機器證明”） 本課程只討論一階謂詞邏輯描述下的歸結推理方法，不涉及高階謂詞邏輯問題。 2022-6-8人工智能講義71歸結原理 概述 命題邏輯的歸結法 子句形 Herbrand定理 歸結原理 歸結過程的策略控制2022-6-8人工智能講義72歸結原理 概述 命題邏輯的歸結法 子句形 Herbrand定理 歸結原理 歸結過程的策略控制

21、2022-6-8人工智能講義73命題邏輯的歸結法 基本單元：簡單命題（陳述句）例： 命題： A1、A2、A3 和 B求證： A1A2A3成立，則B成立，即：A1A2A3 B反證法：證明A1A2A3B 是矛盾式 （永假式） 2022-6-8人工智能講義74命題邏輯的歸結法建立子句集 合取范式：命題、命題和的與， 如：P（ PQ）（ PQ） 子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：P（ PQ）（ PQ） 子句集 S：S = P, PQ, PQ 2022-6-8人工智能講義75命題邏輯的歸結法 歸結式消除互補對，求新子句得到歸結式。如子句：C1= C1L, C2 = C2 歸結式

22、：R(C1, C2) = C1 C2 注意：C1C2 R(C1, C2) ， 反之成立。 L假言推理: 由合適公式W1和W1 W2產(chǎn)生合適公式W2 ,如何用歸結法證明?2022-6-8人工智能講義76命題邏輯的歸結法 歸結過程 對結論作否定,并加入前提中 將命題寫成合取范式 求出子句集 對子句集使用歸結推理規(guī)則 歸結式作為新子句參加歸結 歸結式為空子句 ，S是不可滿足的（矛盾），原命題成立。 （證明完畢） 謂詞的歸結：除了有量詞和函數(shù)以外，其余和命題歸結過程一樣。 2022-6-8人工智能講義77命題邏輯的歸結法命題邏輯的歸結法 例 證明先將化為合取范式 建立子句集 S=對S做歸結 P NIL

23、PQQP)( PQQPPQQPQQP PQQP, , P2022-6-8人工智能講義78歸結原理 概述 命題邏輯的歸結法 子句形 Herbrand定理 歸結原理 歸結過程的策略控制2022-6-8人工智能講義79歸結原理 概述 命題邏輯的歸結法 子句形 Herbrand定理 歸結原理 歸結過程的策略控制2022-6-8人工智能講義80子句形 引用Herbrand定理，以說明歸結原理的意義及一個原理形成的根基與背景 SKOLEM標準形 前束范式：把所有的量詞都提到前面去，然后消掉所有量詞。定義：說公式A是一個前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到

24、公式的末端。 即(Q1x1)(Qnxn)M(x1, , xn),其中Qixi為存在量詞或全稱量詞, M(x1, , xn) 為合取范式(由一些子句的合取組成)。2022-6-8人工智能講義81子句形( Skolem 標準形) 量詞消去原則：消去存在量詞“”，略去全程量詞“”。注意：左邊有全稱量詞的存在量詞，消去時該變量改寫成為全稱量詞的函數(shù)(Skloem函數(shù))；如沒有，改寫成為常量。 例子：見人工智能及其應用P752022-6-8人工智能講義82子句形( Skolem 標準形) 定理：謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。 SKOLEM標準形定義：消去量詞后的謂詞

25、公式。注意：謂詞公式G的SKOLEM標準形同G并不等值。 2022-6-8人工智能講義83子句形( Skolem 標準形) 例:G=(x)(y)(z)(u)P(x,y,z,u)Skolem 標準形為： (y)(z)P(a,y,z,f(y,z)其中，x=a(常量)，u=f(y.z)2022-6-8人工智能講義84子句形 子句與子句集 文字：不含任何連接詞的謂詞公式。 子句：一些文字的析?。ㄖ^詞的和）。 子句集S的求取： G SKOLEM標準形 消去存在變量 以“，”取代“”，并表示為集合形式 。2022-6-8人工智能講義85子句形 G是不可滿足的 S是不可滿足的 G與S不等價，但在不可滿足的意

26、義下是一致的。 定理：若G是給定的公式，而S是相應的子句集，則G是不可滿足的 S是不可滿足的。 注意：G真不一定S真，而S真必有G真。即： S = G2022-6-8人工智能講義86子句形 G = G1 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不可滿足2022-6-8人工智能講義87歸結原理 概述 命題邏輯的歸結法 子句形 Herbrand定理 歸結原理 歸結過程的策略控制2022-6-8

27、人工智能講義88歸結原理 概述 命題邏輯的歸結法 子句形 Herbrand定理 歸結原理 歸結過程的策略控制2022-6-8人工智能講義89Herbrand定理 問題：一階邏輯公式的永真性（永假性）的判定是否能在有限步內(nèi)完成？2022-6-8人工智能講義90Herbrand定理 1936年圖靈(Turing)和邱吉(Church)互相獨立地證明了：n “沒有一般的方法使得在有限步內(nèi)判定一階邏輯的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步內(nèi)判定它是永真（或永假）。對于非永真（或永假）的公式就不一定能在有限步內(nèi)得到結論。判定的過程將可能是不停止的。” 2022-

28、6-8人工智能講義91Herbrand定理 Herbrand的思想 定義：公式G永真：對于G的所有解釋，G都為真。 思想：尋找一個已給的公式是真的解釋。然而，如果所給定的公式的確是永假的，就沒有這樣的解釋存在，并且算法在有限步內(nèi)停止。 2022-6-8人工智能講義92Herbrand定理 H域 H解釋 語義樹 結論：Herbrand定理2022-6-8人工智能講義93Herbrand定理 H域 H解釋 語義樹 結論：Herbrand定理2022-6-8人工智能講義94Herbrand定理（H域） 基本方法： 因為量詞是任意的，所討論的個體變量域D是任意的，所以解釋的個數(shù)是無限、不可數(shù)的 。 簡

29、化討論域。建立一個比較簡單、特殊的域，使得只要在這個論域上，該公式是不可滿足的。 此域稱為H域：H0為G中所出現(xiàn)的常量的集合，若G中沒有常量，就任取常量 ，H0=a。 規(guī)定 為H域 例題請參考教科書P27),.,(11niittfHHDaHH2022-6-8人工智能講義95H域舉例 例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)，2022-6-8人工智能講義96Herbrand定理（H域） 幾個基本概念f（t1, t2, tn）：f為子句集S中的所

30、有函數(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ù)問題。 2022-6-8人工智能講義97原子集舉例 例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), 2022-6-8人工智能講義98Herbrand定理（H域） 沒有變量出現(xiàn)的原子、文字、

31、子句和子句集，分別稱作基原子、基文字、基子句和基子句集。它們在討論子句集S的不可滿足性時占有重要置。2022-6-8人工智能講義99Herbrand定理 H域 H解釋 語義樹 結論：Herbrand定理2022-6-8人工智能講義100Herbrand定理 H域 H解釋 語義樹 結論：Herbrand定理2022-6-8人工智能講義101Herbrand定理（H解釋） 解釋I*：取一個值得到一個結論I映射S中到所有常量符號到它們本身。(即原子集) 令f是n元函數(shù)，I是f下的一個指派，即H中的元素到f的一個映射（函數(shù)值）。簡單地說(P29)，A中的各元素真假組合都是H的解釋。（或真或假只取一個）

32、 問題：對于所有的解釋，全是假才可判定。因為所有解釋代表了所有的情況，如可窮舉，問題便可解決 。2022-6-8人工智能講義102H解釋-舉例 例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我們關心的是：對論域上的任一解釋I，

33、若有 S| I=T,如何求得一個相應的H解釋I*,使得S| I*=T成立。2022-6-8人工智能講義103Herbrand定理（H解釋） 如下三個定理保證了歸結法的正確性： 定理1：設I是S的論域D上的解釋，存在對應于I的H解釋I*，使得若有S|I = T，必有 S|I* = T。 定理2：子句集S是不可滿足的，當且僅當所有的S的H解釋下為假。 定理3：子句集S是不可滿足的，當且僅當對每一個解釋I下，至少有S的某個子句的某個基例為假。 2022-6-8人工智能講義104Herbrand定理（H解釋） 基例S中某子句中所有變元符號均以S的H域中的元素代入時，所得的基子句C稱為C的一個基例。 若

34、一個子句為假，則此解釋為假。 一般來說，D是無窮不可列的，因此，子句集S也是無窮不可列的。但S確定后H是無窮可列的。不過在H上證明S的不可滿足性仍然是不可能的。 解決問題的方法：語義樹2022-6-8人工智能講義105Herbrand定理 H域 H解釋 語義樹 結論：Herbrand定理2022-6-8人工智能講義106Herbrand定理 H域 H解釋 語義樹 結論：Herbrand定理2022-6-8人工智能講義107Herbrand定理（語義樹） 構成方法 原子集中所有元素逐層添加的一棵二叉樹。將元素的是與非分別標記在兩側的分枝上（可不完全畫完） 。(P34) 特點 一般情況H是可數(shù)集，

35、S的語義樹是無限樹。 2022-6-8人工智能講義108Herbrand定理（語義樹） 意義 S H A 語義樹 可以理解語義樹為H域的圖形解釋。 目的：把每個解釋都攤開。語義樹中包含原子集的全部元素，因此，語義樹是完全的。每一個直到葉子節(jié)點的分支對應S的一個解釋?？梢酝ㄟ^對語義樹每一個分支來計算S的真值。如果每個基例都為假，則可認為是不可滿足的。2022-6-8人工智能講義109語義樹-舉例 例1 設子句集S的原子集 A=P,Q,R 語義樹： N0 N11N12N21N22N23N24N31N32N33N34N35N36N37N38P QQR R PI(N)表示從根節(jié)點到節(jié)點N分枝上所標記的

36、所有文字的并集。如 I(N34)=P, Q, R2022-6-8人工智能講義110Herbrand定理（語義樹） 幾個概念 失敗結點失敗結點： 當（由上）延伸到點當（由上）延伸到點N N時，時，I(N)I(N)已表明了已表明了S S的某子句的某基例假。的某子句的某基例假。但但N N以前尚不能判斷這事實。就稱以前尚不能判斷這事實。就稱N N為失敗結點。為失敗結點。完全語義樹完全語義樹： 如果對語義樹的所有葉結點如果對語義樹的所有葉結點NN來說，來說， I(N)I(N)包含了包含了S S的原子集的原子集 A=A1,A2,A=A1,A2, 中的所有元素中的所有元素A Ai i或或 A Ai i，I=

37、1 I=1 nn。 封閉語義樹封閉語義樹：如果如果S S的完全語義樹的每個分枝上都有一個失敗結點，就稱它是的完全語義樹的每個分枝上都有一個失敗結點，就稱它是一棵封閉語義樹。一棵封閉語義樹。2022-6-8人工智能講義111封閉語義樹-舉例例 子句集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(f(a), 語義樹： N0 N11N12N21N22N23N24N31N32N33N34N35N36N37N38P(a)Q(a)P(f(a)N41N42N43N44N45N46N

38、47N48N49N410N411N413N415N412N414N416這是一個無限樹，然而它是否是一個封閉樹？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的父輩不能使子句的基例為假2022-6-8人工智能講義112封閉語義樹-舉例例 子句集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(f(a), 封閉語義樹： N0 N11N12N21N22N23N24N

39、31N32N36N37N38P(a)Q(a)P(f(a)N41N42N49N410N413N414Q(f(a)2022-6-8人工智能講義113Herbrand定理 H域 H解釋 語義樹 結論：Herbrand定理2022-6-8人工智能講義114Herbrand定理 H域 H解釋 語義樹 結論：Herbrand定理2022-6-8人工智能講義115Herbrand定理（結論）Herbrand定理：n 子句集S是不可滿足的，當且僅當對應于S的完全語義數(shù)是棵有限封閉樹。 1. 子句集S是不可滿足的，當且僅當存在不可滿足的S的有限基例集。 2022-6-8人工智能講義116Herbrand定理（結

40、論） 定理的意義 Herbrand定理已將證明問題轉化成了命題邏輯問題。 由此定理保證，可以放心的用機器來實現(xiàn)自動推理了。（歸結原理） 注意 Herbrand定理給出了一階邏輯的半可判定算法，即僅當被證明定理是成立時，使用該算法可以在有限步得證。而當被證定理并不成立時，使用該算法得不出任何結論。但是 2022-6-8人工智能講義117例 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

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

42、有顯著的成績。n n直至1965年Robinson提出了歸結原理。2022-6-8人工智能講義118歸結原理 概述 命題邏輯的歸結法 子句形 Herbrand定理 歸結原理 歸結過程的策略控制2022-6-8人工智能講義119歸結原理 概述 命題邏輯的歸結法 子句形 Herbrand定理 歸結原理 歸結過程的策略控制2022-6-8人工智能講義120歸結原理 歸結原理正確性的根本在于，找到矛盾可以肯定不真。 方法： 和命題邏輯一樣。 但由于有函數(shù)，所以要考慮合一和置換。 (定義與例題參考教科書P41)2022-6-8人工智能講義121歸結原理 置換和合一的注意事項：n謂詞的一致性，P()與Q(

43、)， 不可以n常量的一致性，P(a, )與P(b,.)， 不可以 常量與變量，P(a, .)與P(x, )， 可以n變量與函數(shù)，P(a, x, .)與P(x, f(x), )，不可以；但P(a, x, )與P(x, f(y), )，可以n是不能同時消去兩個互補對，PQ與PQ的空，不可以1.先進行內(nèi)部簡化（置換、合并） 2022-6-8人工智能講義122歸結原理 歸結的過程(P48)寫出謂詞關系公式 用反演法寫出謂詞表達試 SKOLEM標準形 子句集S 對S中可歸結的子句做歸結 歸結式仍放入S中，反復歸結過程 得到空子句 得證2022-6-8人工智能講義123歸結原理 歸結法的實質(zhì)： 歸結法是僅

44、有一條推理規(guī)則的推理方法。 歸結的過程是一個語義樹倒塌的過程。 (P51) 歸結法的問題 子句中有等號或不等號時，完備性不成立。 Herbrand定理的不實用性引出了可實用的歸結法。2022-6-8人工智能講義124歸結原理 概述 命題邏輯的歸結法 子句形 Herbrand定理 歸結原理 歸結過程的策略控制2022-6-8人工智能講義125歸結原理 概述 命題邏輯的歸結法 子句形 Herbrand定理 歸結原理 歸結過程的策略控制2022-6-8人工智能講義126歸結過程的控制策略 要解決的問題： 歸結方法的知識爆炸。 控制策略的目的 歸結點盡量少 控制策略的原則給出控制策略，以使僅對選擇合適

45、的子句間方可做歸結。避免多余的、不必要的歸結式出現(xiàn)?；蛘哒f，少做些歸結仍能導出空子句。2022-6-8人工智能講義127歸結過程的控制策略 盲目歸結 例 S=PQQ, PQ,PQ,PQ, Q, PQ Q是不可滿足。 證明從S0=S開始，依次構造 Si=C1,C2的歸結式|C1S0S1 Si-1,C2 Si-1 ,i=1,2, ,直至得到空子句。具體過程如下：S0 (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)(

46、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)2022-6-8人工智能講義128歸結過程的控制策略(盲目歸結)S S2 2 (13)P (13)P (1)(7)(1)(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)

47、(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)(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

48、) 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)PPQ 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)

49、(39) (5)(12)(5)(12)產(chǎn)生過多不必要的歸結式。一類是重言式（產(chǎn)生過多不必要的歸結式。一類是重言式（7 7）- -（1010）由它們又產(chǎn)）由它們又產(chǎn)生了（生了（1313）- -（1616），（），（2020）- -（2323），），(26)-(29),(33)-(39)(26)-(29),(33)-(39)。另一。另一類是重復的，如類是重復的，如P,Q, P,Q, P, P, Q.Q.2022-6-8人工智能講義129歸結過程的控制策略刪除策略 設有兩個子句設有兩個子句C C和和D D，若有置換，若有置換使得使得 C C D D成立，便說子句成立，便說子句C C把子把子句句D D

50、歸類。歸類。例例 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使用歸結推理過程中，當歸結式Cj是重言式或Cj被S中子句或歸結式Ci(iQR 解釋解釋I= P, Q, R 2022-6-8人工智能講義132歸結過程的控制策略 線性歸結策略 首先從子句集S中選取一個稱為頂子句的子句C0開始做歸結，其次是歸結過程中所得到的歸結式Ci立即同另一個子句Bi進行歸結得歸結式Ci+1。而Bi屬于S或是已出現(xiàn)的歸結式Cj(j完備 采用支撐集 完備 語義歸結完備 線性歸

51、結 完備 單元歸結=完備 輸入歸結 =完備2022-6-8人工智能講義136謂詞邏輯的歸結方法 對于子句C1L1和C2L2，如果L1與L2可合一，且s是其合一者，則(C1C2)s是其歸結式。 例： P(x)Q(y), P(f(z)R(z) = Q(y)R(z)2022-6-8人工智能講義137歸結舉例設公理集：(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)2022-6-8人工智能講義138 (x)(D(x)L(x)= (x)(D(x)L(x)=

52、 D(x)L(x) (2) (x)(D(x)I(x)= D(A)I(A)= D(A) (3) I(A) (4)2022-6-8人工智能講義139 目標求反： ( 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)2022-6-8人工智能講義140例題得歸結樹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

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