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

1、人工智能一般搜索算法原理1532022/7/15人工智能一般搜索算法原理153盲目搜索圖搜索策略深度優(yōu)先搜索寬度優(yōu)先搜索等代價(jià)搜索2022/7/152人工智能一般搜索算法原理153一些基本概念節(jié)點(diǎn)深度：根節(jié)點(diǎn)深度=0其它節(jié)點(diǎn)深度=父節(jié)點(diǎn)深度+101232022/7/153人工智能一般搜索算法原理153一些基本概念（續(xù)1）路徑設(shè)一節(jié)點(diǎn)序列為(n0, n1,nk)，對(duì)于i=1,k，若節(jié)點(diǎn)ni-1具有一個(gè)后繼節(jié)點(diǎn)ni，則該序列稱為從n0到nk的路徑。路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。用C(ni, nj)表示從ni到nj的路徑的耗散值。2022/7/154人工智能一

2、般搜索算法原理153一些基本概念（續(xù)1）擴(kuò)展一個(gè)節(jié)點(diǎn)生成出該節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)，并給出它們之間的耗散值。這一過(guò)程稱為“擴(kuò)展一個(gè)節(jié)點(diǎn)”。2022/7/155人工智能一般搜索算法原理153一般的圖搜索算法（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/7/156

3、人工智能一般搜索算法原理153一般的圖搜索算法（續(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, GO LOOP；2022/7/157人工智能一般搜索算法原理153深度優(yōu)先搜索在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的(最深的)節(jié)點(diǎn)，深度 相等的節(jié)點(diǎn)可以任意排列。“最晚產(chǎn)生的節(jié)點(diǎn)最先擴(kuò)展”2022/7/158人工智能一般搜索算法原理153深度優(yōu)先搜索算法1, G=G0(G0=s), OPEN=(s), CLOSED=( );2, LOOP: IF O

4、PEN=( ) 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)在mi中 THEN EXIT(SUCCESS);9, ADD(mj, OPEN), 并標(biāo)記mj到n的指針;10, GO LOOP;2022/7/159人工智能一般搜索算法原理1532 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8

5、 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 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)2022/7/1510人工智能一般搜索算法原理153深度優(yōu)先搜索的性質(zhì)一

6、般不能保證找到最優(yōu)解當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制最壞情況時(shí)，搜索空間等同于窮舉與回溯法的差別：圖搜索是一個(gè)通用的與問(wèn)題無(wú)關(guān)的方法2022/7/1511人工智能一般搜索算法原理153寬度優(yōu)先搜索如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索。這種搜索使逐層進(jìn)行的，在對(duì)下一層的任意節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。“先產(chǎn)生的節(jié)點(diǎn)先擴(kuò)展”2022/7/1512人工智能一般搜索算法原理153寬度優(yōu)先搜索算法1, G=G0(G0=s), OPEN=(s), CLOSED=( );2, LOOP: IF OPEN=( ) EXIT (

7、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)在mi中 THEN EXIT(SUCCESS);8, ADD(OPEN, mj), 并標(biāo)記mj到n的指針;9, GO LOOP;2022/7/1513人工智能一般搜索算法原理1532 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

8、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 542022/7/1514人工智能一般搜索算法原理153寬度優(yōu)先搜索的性質(zhì)當(dāng)問(wèn)題有解時(shí)，一定能找到解當(dāng)問(wèn)題為單位耗散值，且問(wèn)題有解時(shí)，一定能找到最優(yōu)解方法與問(wèn)題無(wú)關(guān)，具有通用性效率較低屬于圖搜索方法2022/7/1515人工智能一般搜索算法原理153等代價(jià)搜索寬度優(yōu)先搜索可被推廣用來(lái)解決尋找從

9、起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)具有最小代價(jià)路徑問(wèn)題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價(jià)搜索算法。2022/7/1516人工智能一般搜索算法原理153等代價(jià)搜索算法算法1,G=G0(G0=s), OPEN=(s), CLOSED=( ),g(s)=0;2, LOOP: IF OPEN=( ) 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, IF GOAL(i) EXIT (SUCCESS);5,

10、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, GO LOOP;2022/7/1517人工智能一般搜索算法原理153啟發(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)解2022/7/1518人工智能一般搜索算法原理153希望：引入啟發(fā)知識(shí)，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。2022/7/1519人工智能一般

11、搜索算法原理153基本思想定義一個(gè)評(píng)價(jià)函數(shù)f，對(duì)當(dāng)前的搜索狀態(tài)進(jìn)行評(píng)估，找出一個(gè)最有希望的節(jié)點(diǎn)來(lái)擴(kuò)展。2022/7/1520人工智能一般搜索算法原理1531，啟發(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ù)2022/7/1521人工智能一般搜索算法原理153符號(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ì)值2022/7/1522人工智能一般搜索算法原理

12、153A算法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);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) Mi, 計(jì)算f(n, mi)=g(n, mi)+h(mi);2022/7/1523人工智能一般搜索算法原理153A算法（續(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)

13、f*(s)。2022/7/1531人工智能一般搜索算法原理153A*算法的性質(zhì)（續(xù)2）引理2.2：A*結(jié)束前，OPEN表中必存在f(n)f*(s)。2022/7/1532人工智能一般搜索算法原理153A*算法的性質(zhì)（續(xù)3）定理2：對(duì)無(wú)限圖，若從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則A*一定成功結(jié)束。2022/7/1533人工智能一般搜索算法原理153A*算法的性質(zhì)（續(xù)4）推論2.1：OPEN表上任一具有f(n) h1(n)，則在具有一條從s到t的路徑的隱含圖上，搜索結(jié)束時(shí)，由A2所擴(kuò)展的每一個(gè)節(jié)點(diǎn)，也必定由A1所擴(kuò)展，即A1擴(kuò)展的節(jié)點(diǎn)數(shù)至少和A2一樣多。簡(jiǎn)寫：如果h2(n) h1(n), 則A1

14、擴(kuò)展的節(jié)點(diǎn)數(shù)A2擴(kuò)展的節(jié)點(diǎn)數(shù)2022/7/1537人工智能一般搜索算法原理153A*算法的改進(jìn)問(wèn)題的提出：因A算法第6步對(duì)ml類節(jié)點(diǎn)可能要重新放回到OPEN表中，因此可能會(huì)導(dǎo)致多次重復(fù)擴(kuò)展同一個(gè)節(jié)點(diǎn)，導(dǎo)致搜索效率下降。2022/7/1538人工智能一般搜索算法原理153s(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

15、) 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/7/1539人工智能一般搜索算法原理153出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因在前面的擴(kuò)展中，并沒有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑，如節(jié)點(diǎn)A。2022/7/1540人工智能一般搜索算法原理153解決的途徑對(duì)h加以限制能否對(duì)h增加適當(dāng)?shù)南拗疲沟玫谝淮螖U(kuò)展一個(gè)節(jié)點(diǎn)時(shí)，就找到了從s到該節(jié)點(diǎn)的最短路徑。對(duì)算法加以改進(jìn)能否對(duì)算法加以改進(jìn)，避免或減少節(jié)點(diǎn)的多次擴(kuò)展。2022/7/1541人工智能一般搜索算法原理153改進(jìn)的條件可采納性不變不多擴(kuò)展節(jié)點(diǎn)不增加算法的復(fù)雜性2022

16、/7/1542人工智能一般搜索算法原理153對(duì)h加以限制定義：一個(gè)啟發(fā)函數(shù)h，如果對(duì)所有節(jié)點(diǎn)ni和nj，其中nj是ni的子節(jié)點(diǎn)，滿足h(ni) - h(nj) c(ni, nj)h(t) = 0則稱h是單調(diào)的。h(ni)ninjh(nj)c(ni,nj)2022/7/1543人工智能一般搜索算法原理153h單調(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)。2022/7/1544人工智能一般搜索算法原理153h單調(diào)的性質(zhì)（續(xù)）定理6：若h(n)是單調(diào)的，則由A*所擴(kuò)展的節(jié)點(diǎn)序列其f值是非遞減的。2022/

17、7/1545人工智能一般搜索算法原理153h單調(diào)的例子8數(shù)碼問(wèn)題：h為“不在位”的將牌數(shù) 1h(ni) - h(nj) = 0(nj為ni的后繼節(jié)點(diǎn)) -1 h(t) = 0c(ni, nj) = 1 滿足單調(diào)的條件。2022/7/1546人工智能一般搜索算法原理153對(duì)算法加以改進(jìn)一些結(jié)論：OPEN表上任一具有f(n) f*(s)的節(jié)點(diǎn)定會(huì)被擴(kuò)展。A*選作擴(kuò)展的任一節(jié)點(diǎn)，定有f(n)f*(s)。2022/7/1547人工智能一般搜索算法原理153改進(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*(

18、s)2022/7/1548人工智能一般搜索算法原理153修正過(guò)程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/7/1562人工智能一般搜索算法原理153n0n1n2n3n4n5n6n7n8n4(1)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4)n5(1)n5(1-2)2022/7/1563人工智能一般搜索算法原理153n0n1n2n3n4n5n6n7n8紅色代價(jià)：5藍(lán)色代價(jià)：6n0(4)n4(1

19、)n5(1-2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4-5)2022/7/1564人工智能一般搜索算法原理153n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2022/7/1565人工智能一般搜索算法原理153目標(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)2022/7/1566人工智能一般搜索算法原理153目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8初始節(jié)點(diǎn)可解n0(5)n4(1)n

20、5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2022/7/1567人工智能一般搜索算法原理153歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制2022/7/1568人工智能一般搜索算法原理153歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制2022/7/1569人工智能一般搜索算法原理153概述歸結(jié)原理由J.A.Robinson由1965年提出。與演繹法完全不同，新的邏輯演算算法。一階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在有限步內(nèi)給以判定。 語(yǔ)義網(wǎng)絡(luò)

21、、框架表示、產(chǎn)生式規(guī)則等等都是以推理方法為前提的。即，有了規(guī)則已知條件，順藤摸瓜找到結(jié)果。 而歸結(jié)方法是自動(dòng)推理、自動(dòng)推導(dǎo)證明用的。（“數(shù)學(xué)定理機(jī)器證明”）本課程只討論一階謂詞邏輯描述下的歸結(jié)推理方法，不涉及高階謂詞邏輯問(wèn)題。 2022/7/1570人工智能一般搜索算法原理153歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制2022/7/1571人工智能一般搜索算法原理153歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制2022/7/1572人工智能一般搜索算法原理153命題邏輯的歸結(jié)法基本單元：簡(jiǎn)單命題（陳述句）例： 命題：

22、 A1、A2、A3 和 B求證： A1A2A3成立，則B成立，即：A1A2A3 B反證法：證明A1A2A3B 是矛盾式 （永假式） 2022/7/1573人工智能一般搜索算法原理153命題邏輯的歸結(jié)法建立子句集合取范式：命題、命題和的與， 如：P（ PQ）（ PQ）子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：P（ PQ）（ PQ） 子句集 S：S = P, PQ, PQ 2022/7/1574人工智能一般搜索算法原理153命題邏輯的歸結(jié)法歸結(jié)式消除互補(bǔ)對(duì)，求新子句得到歸結(jié)式。如子句：C1= C1L, C2 = C2 歸結(jié)式：R(C1, C2) = C1 C2注意：C1C2 R(

23、C1, C2) ， 反之不一定成立。 假言推理: 由合適公式W1和W1 W2產(chǎn)生合適公式W2 ,如何用歸結(jié)法證明?2022/7/1575人工智能一般搜索算法原理153命題邏輯的歸結(jié)法歸結(jié)過(guò)程 對(duì)結(jié)論作否定,并加入前提中將命題寫成合取范式求出子句集對(duì)子句集使用歸結(jié)推理規(guī)則歸結(jié)式作為新子句參加歸結(jié)歸結(jié)式為空子句 ，S是不可滿足的（矛盾），原命題成立。 （證明完畢）謂詞的歸結(jié)：除了有量詞和函數(shù)以外，其余和命題歸結(jié)過(guò)程一樣。 2022/7/1576人工智能一般搜索算法原理153命題邏輯的歸結(jié)法例 證明先將化為合取范式 建立子句集 S=對(duì)S做歸結(jié) P NIL2022/7/1577人工智能一般搜索算法原理

24、153歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制2022/7/1578人工智能一般搜索算法原理153歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制2022/7/1579人工智能一般搜索算法原理153子句形 引用Herbrand定理，以說(shuō)明歸結(jié)原理的意義及一個(gè)原理形成的根基與背景SKOLEM標(biāo)準(zhǔn)形前束范式：把所有的量詞都提到前面去，然后消掉所有量詞。定義：說(shuō)公式A是一個(gè)前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。 即(Q1x1)(Qnxn)M(x1, , xn),其中Q

25、ixi為存在量詞或全稱量詞, M(x1, , xn) 為合取范式(由一些子句的合取組成)。2022/7/1580人工智能一般搜索算法原理153子句形( Skolem 標(biāo)準(zhǔn)形) 量詞消去原則：消去存在量詞“”，略去全程量詞“”。注意：左邊有全稱量詞的存在量詞，消去時(shí)該變量改寫成為全稱量詞的函數(shù)(Skloem函數(shù))；如沒有，改寫成為常量。 例子：見人工智能及其應(yīng)用P752022/7/1581人工智能一般搜索算法原理153子句形( Skolem 標(biāo)準(zhǔn)形) 定理：謂詞邏輯的任意公式都可以化為與之等價(jià)的前束范式，但其前束范式不唯一。 SKOLEM標(biāo)準(zhǔn)形定義：消去量詞后的謂詞公式。注意：謂詞公式G的SKO

26、LEM標(biāo)準(zhǔn)形同G并不等值。 2022/7/1582人工智能一般搜索算法原理153子句形( 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)2022/7/1583人工智能一般搜索算法原理153子句形子句與子句集文字：不含任何連接詞的謂詞公式。子句：一些文字的析?。ㄖ^詞的和）。子句集S的求?。?G SKOLEM標(biāo)準(zhǔn)形 消去存在變量 以“，”取代“”，并表示為集合形式 。2022/7/1584人工智能一般搜索算法原理153子句形 G是不可滿足的 S是不可滿足的G與S不等

27、價(jià)，但在不可滿足的意義下是一致的。 定理：若G是給定的公式，而S是相應(yīng)的子句集，則G是不可滿足的 S是不可滿足的。 注意：G真不一定S真，而S真必有G真。即： S = G2022/7/1585人工智能一般搜索算法原理153子句形G = G1 G2 G3 Gn 的子句形G的子句集可以分解成幾個(gè)單獨(dú)處理。 有 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/7/1586人工智能一般搜索算法原理153歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand

28、定理歸結(jié)原理歸結(jié)過(guò)程的策略控制2022/7/1587人工智能一般搜索算法原理153歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制2022/7/1588人工智能一般搜索算法原理153Herbrand定理問(wèn)題：一階邏輯公式的永真性（永假性）的判定是否能在有限步內(nèi)完成？2022/7/1589人工智能一般搜索算法原理153Herbrand定理1936年圖靈(Turing)和邱吉(Church)互相獨(dú)立地證明了： “沒有一般的方法使得在有限步內(nèi)判定一階邏輯的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步內(nèi)判定它是永真（或永假）。對(duì)于非永真

29、（或永假）的公式就不一定能在有限步內(nèi)得到結(jié)論。判定的過(guò)程將可能是不停止的?！?2022/7/1590人工智能一般搜索算法原理153Herbrand定理Herbrand的思想定義：公式G永真：對(duì)于G的所有解釋，G都為真。思想：尋找一個(gè)已給的公式是真的解釋。然而，如果所給定的公式的確是永假的，就沒有這樣的解釋存在，并且算法在有限步內(nèi)停止。 2022/7/1591人工智能一般搜索算法原理153Herbrand定理H域H解釋語(yǔ)義樹結(jié)論：Herbrand定理2022/7/1592人工智能一般搜索算法原理153Herbrand定理H域H解釋語(yǔ)義樹結(jié)論：Herbrand定理2022/7/1593人工智能一般

30、搜索算法原理153Herbrand定理（H域）基本方法：因?yàn)榱吭~是任意的，所討論的個(gè)體變量域D是任意的，所以解釋的個(gè)數(shù)是無(wú)限、不可數(shù)的 。簡(jiǎn)化討論域。建立一個(gè)比較簡(jiǎn)單、特殊的域，使得只要在這個(gè)論域上，該公式是不可滿足的。此域稱為H域：H0為G中所出現(xiàn)的常量的集合，若G中沒有常量，就任取常量 ，H0=a。 規(guī)定 為H域 例題請(qǐng)參考教科書P272022/7/1594人工智能一般搜索算法原理153H域舉例例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)，2

31、022/7/1595人工智能一般搜索算法原理153Herbrand定理（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)題。 2022/7/1596人工智能一般搜索算法原理153原子集舉例例1 S=P(a), P(x)P(f(x) H= a,f(a),f(f(a)，

32、 S的原子集為 A=P(a),P(f(a),P(f(f(a), 2022/7/1597人工智能一般搜索算法原理153Herbrand定理（H域）沒有變量出現(xiàn)的原子、文字、子句和子句集，分別稱作基原子、基文字、基子句和基子句集。它們?cè)谟懻撟泳浼疭的不可滿足性時(shí)占有重要置。2022/7/1598人工智能一般搜索算法原理153Herbrand定理H域H解釋語(yǔ)義樹結(jié)論：Herbrand定理2022/7/1599人工智能一般搜索算法原理153Herbrand定理H域H解釋語(yǔ)義樹結(jié)論：Herbrand定理2022/7/15100人工智能一般搜索算法原理153Herbrand定理（H解釋）解釋I*：取一個(gè)值

33、得到一個(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ì)于所有的解釋，全是假才可判定。因?yàn)樗薪忉尨砹怂械那闆r，如可窮舉，問(wèn)題便可解決 。2022/7/15101人工智能一般搜索算法原理153H解釋-舉例例1 S=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解釋：I1*= P(a),P(f(a),P(f(f(a), S| I1*

34、=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)心的是：對(duì)論域上的任一解釋I，若有 S| I=T,如何求得一個(gè)相應(yīng)的H解釋I*,使得S| I*=T成立。2022/7/15102人工智能一般搜索算法原理153Herbrand定理（H解釋）如下三個(gè)定理保證了歸結(jié)法的正確性：定理1：設(shè)I是S的論域D上的解釋，存在對(duì)應(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)對(duì)每一個(gè)解釋I

35、下，至少有S的某個(gè)子句的某個(gè)基例為假。 2022/7/15103人工智能一般搜索算法原理153Herbrand定理（H解釋）基例S中某子句中所有變?cè)?hào)均以S的H域中的元素代入時(shí)，所得的基子句C稱為C的一個(gè)基例。若一個(gè)子句為假，則此解釋為假。一般來(lái)說(shuō)，D是無(wú)窮不可列的，因此，子句集S也是無(wú)窮不可列的。但S確定后H是無(wú)窮可列的。不過(guò)在H上證明S的不可滿足性仍然是不可能的。解決問(wèn)題的方法：語(yǔ)義樹2022/7/15104人工智能一般搜索算法原理153Herbrand定理H域H解釋語(yǔ)義樹結(jié)論：Herbrand定理2022/7/15105人工智能一般搜索算法原理153Herbrand定理H域H解釋語(yǔ)義樹

36、結(jié)論：Herbrand定理2022/7/15106人工智能一般搜索算法原理153Herbrand定理（語(yǔ)義樹）構(gòu)成方法原子集中所有元素逐層添加的一棵二叉樹。將元素的是與非分別標(biāo)記在兩側(cè)的分枝上（可不完全畫完） 。(P34)特點(diǎn)一般情況H是可數(shù)集，S的語(yǔ)義樹是無(wú)限樹。 2022/7/15107人工智能一般搜索算法原理153Herbrand定理（語(yǔ)義樹）意義S H A 語(yǔ)義樹可以理解語(yǔ)義樹為H域的圖形解釋。 目的：把每個(gè)解釋都攤開。語(yǔ)義樹中包含原子集的全部元素，因此，語(yǔ)義樹是完全的。每一個(gè)直到葉子節(jié)點(diǎn)的分支對(duì)應(yīng)S的一個(gè)解釋?？梢酝ㄟ^(guò)對(duì)語(yǔ)義樹每一個(gè)分支來(lái)計(jì)算S的真值。如果每個(gè)基例都為假，則可認(rèn)為是不

37、可滿足的。2022/7/15108人工智能一般搜索算法原理153語(yǔ)義樹-舉例例1 設(shè)子句集S的原子集 A=P,Q,R 語(yǔ)義樹： N0 N11N12N21N22N23N24N31N32N33N34N35N36N37N38P QQR R PI(N)表示從根節(jié)點(diǎn)到節(jié)點(diǎn)N分枝上所標(biāo)記的所有文字的并集。如 I(N34)=P, Q, R2022/7/15109人工智能一般搜索算法原理153Herbrand定理（語(yǔ)義樹）幾個(gè)概念失敗結(jié)點(diǎn)： 當(dāng)（由上）延伸到點(diǎn)N時(shí)，I(N)已表明了S的某子句的某基例假。但N以前尚不能判斷這事實(shí)。就稱N為失敗結(jié)點(diǎn)。完全語(yǔ)義樹： 如果對(duì)語(yǔ)義樹的所有葉結(jié)點(diǎn)N來(lái)說(shuō)， I(N)包含了S

38、的原子集 A=A1,A2,中的所有元素Ai或 Ai，I=1 n。封閉語(yǔ)義樹：如果S的完全語(yǔ)義樹的每個(gè)分枝上都有一個(gè)失敗結(jié)點(diǎn)，就稱它是一棵封閉語(yǔ)義樹。2022/7/15110人工智能一般搜索算法原理153封閉語(yǔ)義樹-舉例例 子句集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ǔ)義樹： N0 N11N12N21N22N23N24N31N32N33N34N35N36N37N38P(a)Q(a)P(f(a)N41N42N43N44N45N46N47N48N49N410N411N413N415N412N414N

39、416這是一個(gè)無(wú)限樹，然而它是否是一個(gè)封閉樹？Q(f(a)I(N41)=P(a),Q(a),P(f(a),Q(f(a),它使S的子句Q(f(y)的基例Q(f(a)為假，而N41的父輩不能使子句的基例為假2022/7/15111人工智能一般搜索算法原理153封閉語(yǔ)義樹-舉例例 子句集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ǔ)義樹： N0 N11N12N21N22N23N24N31N32N36N37N38P(a)Q(a)P(f(a)N41N42N49N410N413N414Q(f(a)2022/

40、7/15112人工智能一般搜索算法原理153Herbrand定理H域H解釋語(yǔ)義樹結(jié)論：Herbrand定理2022/7/15113人工智能一般搜索算法原理153Herbrand定理H域H解釋語(yǔ)義樹結(jié)論：Herbrand定理2022/7/15114人工智能一般搜索算法原理153Herbrand定理（結(jié)論）Herbrand定理：子句集S是不可滿足的，當(dāng)且僅當(dāng)對(duì)應(yīng)于S的完全語(yǔ)義數(shù)是棵有限封閉樹。 子句集S是不可滿足的，當(dāng)且僅當(dāng)存在不可滿足的S的有限基例集。 2022/7/15115人工智能一般搜索算法原理153Herbrand定理（結(jié)論）定理的意義Herbrand定理已將證明問(wèn)題轉(zhuǎn)化成了命題邏輯問(wèn)題

41、。由此定理保證，可以放心的用機(jī)器來(lái)實(shí)現(xiàn)自動(dòng)推理了。（歸結(jié)原理）注意Herbrand定理給出了一階邏輯的半可判定算法，即僅當(dāng)被證明定理是成立時(shí)，使用該算法可以在有限步得證。而當(dāng)被證定理并不成立時(shí)，使用該算法得不出任何結(jié)論。但是 2022/7/15116人工智能一般搜索算法原理153例 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è)

42、元素 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才是不可滿足。然而 S5元素個(gè)數(shù)已達(dá)（ 10 64）4=10256Herbrand定理（結(jié)論）仍存在的問(wèn)題：基例集序列元素的數(shù)目隨子句基的元素?cái)?shù)目成指數(shù)地增加。因此，Herbrand定理是30年代提出的，始終沒有顯著的成績(jī)。 直至1965年Robinson提出了歸結(jié)原理。2022/7/15117人工智能一般搜索算法原理153歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Her

43、brand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制2022/7/15118人工智能一般搜索算法原理153歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制2022/7/15119人工智能一般搜索算法原理153歸結(jié)原理歸結(jié)原理正確性的根本在于，找到矛盾可以肯定不真。方法：和命題邏輯一樣。但由于有函數(shù)，所以要考慮合一和置換。 (定義與例題參考教科書P41)2022/7/15120人工智能一般搜索算法原理153歸結(jié)原理置換和合一的注意事項(xiàng)：謂詞的一致性，P()與Q()， 不可以常量的一致性，P(a, )與P(b,.)， 不可以 常量與變量，P(a, .)與P(x, )， 可以變量

44、與函數(shù)，P(a, x, .)與P(x, f(x), )，不可以；但P(a, x, )與P(x, f(y), )，可以是不能同時(shí)消去兩個(gè)互補(bǔ)對(duì)，PQ與PQ的空，不可以先進(jìn)行內(nèi)部簡(jiǎn)化（置換、合并） 2022/7/15121人工智能一般搜索算法原理153歸結(jié)原理歸結(jié)的過(guò)程(P48)寫出謂詞關(guān)系公式 用反演法寫出謂詞表達(dá)試 SKOLEM標(biāo)準(zhǔn)形 子句集S 對(duì)S中可歸結(jié)的子句做歸結(jié) 歸結(jié)式仍放入S中，反復(fù)歸結(jié)過(guò)程 得到空子句 得證2022/7/15122人工智能一般搜索算法原理153歸結(jié)原理歸結(jié)法的實(shí)質(zhì)：歸結(jié)法是僅有一條推理規(guī)則的推理方法。 歸結(jié)的過(guò)程是一個(gè)語(yǔ)義樹倒塌的過(guò)程。 (P51)歸結(jié)法的問(wèn)題子句中

45、有等號(hào)或不等號(hào)時(shí)，完備性不成立。 Herbrand定理的不實(shí)用性引出了可實(shí)用的歸結(jié)法。2022/7/15123人工智能一般搜索算法原理153歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制2022/7/15124人工智能一般搜索算法原理153歸結(jié)原理概述命題邏輯的歸結(jié)法子句形Herbrand定理歸結(jié)原理歸結(jié)過(guò)程的策略控制2022/7/15125人工智能一般搜索算法原理153歸結(jié)過(guò)程的控制策略要解決的問(wèn)題：歸結(jié)方法的知識(shí)爆炸?？刂撇呗缘哪康臍w結(jié)點(diǎn)盡量少控制策略的原則給出控制策略，以使僅對(duì)選擇合適的子句間方可做歸結(jié)。避免多余的、不必要的歸結(jié)式出現(xiàn)。或者說(shuō)，少做些歸結(jié)

46、仍能導(dǎo)出空子句。2022/7/15126人工智能一般搜索算法原理153歸結(jié)過(guò)程的控制策略盲目歸結(jié) 例 S=PQ, PQ,PQ, PQ是不可滿足。 證明從S0=S開始，依次構(gòu)造 Si=C1,C2的歸結(jié)式|C1S0S1 Si-1,C2 Si-1 ,i=1,2, ,直至得到空子句。具體過(guò)程如下：S0 (1) PQ (2) PQ (3)PQ (4) PQS1 (5)Q (1)(2) (6)P (1)(3) (7)QQ (1)(4) (8)PP (1)(4) (9)Q Q (2)(3) (10)PP (2)(3) (11)P (2)(4) (12)Q (3)(4)2022/7/15127人工智能一般搜索

47、算法原理153歸結(jié)過(guò)程的控制策略(盲目歸結(jié))S2 (13)P (1)(7) (14)PQ (1)(8) (15)PQ (1)(9) (16)PQ (1)(10) (17)Q (1)(11) (18)P (1)(12) (19)Q (2)(6) (20)PQ (3)(4) (21)PQ (2)(8) (22)PQ (2)(9) (23)PQ (2)(10) (24)P (2)(12) (25) P (3)(5) (26)PQ (3)(7) (27) PQ (3)(8) (28) PQ (3)(9) (29) PQ (3)(10) (30)Q (3)(11) (31)P (4)(5) (32)Q

48、(4)(6) (33)PQ (4)(7) (34)PQ (4)(8) (35)PQ (4)(9) (36)PQ (4)(10) (37)Q (5)(7) (38)Q (5)(9) (39) (5)(12)產(chǎn)生過(guò)多不必要的歸結(jié)式。一類是重言式（7）-（10）由它們又產(chǎn)生了（13）-（16），（20）-（23），(26)-(29),(33)-(39)。另一類是重復(fù)的，如P,Q, P, Q.2022/7/15128人工智能一般搜索算法原理153歸結(jié)過(guò)程的控制策略刪除策略 設(shè)有兩個(gè)子句C和D，若有置換使得 C D成立，便說(shuō)子句C把子句D歸類。例 C=P(X) D=P(a)Q(a) 取=a/x,便有C

49、=P(a) P(a),Q(a)。刪除策略：若對(duì)s使用歸結(jié)推理過(guò)程中，當(dāng)歸結(jié)式Cj是重言式或Cj被S中子句或歸結(jié)式Ci(iQR 解釋I=P, Q, R 2022/7/15131人工智能一般搜索算法原理153歸結(jié)過(guò)程的控制策略線性歸結(jié)策略 首先從子句集S中選取一個(gè)稱為頂子句的子句C0開始做歸結(jié)，其次是歸結(jié)過(guò)程中所得到的歸結(jié)式Ci立即同另一個(gè)子句Bi進(jìn)行歸結(jié)得歸結(jié)式Ci+1。而Bi屬于S或是已出現(xiàn)的歸結(jié)式Cj(j完備采用支撐集完備語(yǔ)義歸結(jié)完備線性歸結(jié) 完備單元?dú)w結(jié)=完備輸入歸結(jié) =完備2022/7/15135人工智能一般搜索算法原理153謂詞邏輯的歸結(jié)方法對(duì)于子句C1L1和C2L2，如果L1與L2可

50、合一，且s是其合一者，則(C1C2)s是其歸結(jié)式。例： P(x)Q(y), P(f(z)R(z) = Q(y)R(z)2022/7/15136人工智能一般搜索算法原理153歸結(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)2022/7/15137人工智能一般搜索算法原理153 (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)

51、 (4)2022/7/15138人工智能一般搜索算法原理153目標(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)2022/7/15139人工智能一般搜索算法原理153例題得歸結(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) A/x2 D(A) nil2022/7/15140

52、人工智能一般搜索算法原理153歸結(jié)反演求解-提取回答的過(guò)程先進(jìn)行歸結(jié)，證明結(jié)論的正確性；用重言式代替結(jié)論求反得到的子句；按照證明過(guò)程，進(jìn)行歸結(jié)；最后，在原來(lái)為空的地方，得到的就是提取的回答。修改后的證明樹稱為修改證明樹2022/7/15141人工智能一般搜索算法原理153歸結(jié)反演求解-舉例“如果無(wú)論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) 在邏輯上遵循前提公式集，然后尋求一個(gè)存在x的例，那么就能解決“Fido在哪里”的問(wèn)題。2022/7/15142人工智能一般搜索算法原理153歸結(jié)反演求解-基于歸結(jié)的