【正文】 )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é)式。 (P51)? 歸結(jié)法的問題–子句中有等號(hào)或不等號(hào)時(shí)，完備性不成立。元素個(gè)數(shù)已達(dá)（ 10 64） 4=10256Herbrand定理 （結(jié)論）? 仍存在的 問題 ： 基例集序列元素的數(shù)目隨子句基的元素?cái)?shù)目成指數(shù)地增加。但是 ? ? ? ? ? ? ? ? ? ? ? ? ?2/27/2023 116人工智能講義例 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},S0180。– 完全語(yǔ)義樹 ： 如果對(duì)語(yǔ)義樹的所有葉結(jié)點(diǎn) N來(lái)說(shuō)， I(N)包含了 S的原子集 A={A1,A2,… }中的所有元素 Ai或 ～ Ai， I=1 …n 。語(yǔ)義樹中包含原子集的全部元素，因此， 語(yǔ)義樹是完全的。? 一般來(lái)說(shuō)， D是無(wú)窮不可列的，因此，子句集 S也是無(wú)窮不可列的。（或真或假只取一個(gè)） ? 問題：對(duì)于所有的解釋，全是假才可判定。 S中的謂詞是有限的， H是可數(shù)的，因此， A也是可數(shù)的。– 簡(jiǎn)化討論域。2/27/2023 86人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過(guò)程的策略控制2/27/2023 87人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過(guò)程的策略控制2/27/2023 88人工智能講義Herbrand定理?問題：一階邏輯公式的永真性（永假性）的判定是否能在有限步內(nèi)完成 ？2/27/2023 89人工智能講義Herbrand定理? 1936年圖靈 (Turing)和邱吉 (Church)互相獨(dú)立地證明了： “ 沒有一般的方法使得在有限步內(nèi)判定一階邏輯的公式是否是永真（或永假）。–子句：一些文字的析取（謂詞的和）。定義 ：說(shuō)公式 A是一個(gè)前束范式，如果 A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。 而歸結(jié)方法是自動(dòng)推理、自動(dòng)推導(dǎo)證明用的。 3 如果連接于最小代價(jià)連接線上的所有節(jié)點(diǎn)都可解，則標(biāo)注 m可解。對(duì)于 n的父節(jié)點(diǎn)，進(jìn)行同樣的計(jì)算。用三元式表示狀態(tài)： S= (m, c, b)其中， m表示左岸修道士人數(shù)， c表示左岸野人人數(shù)， b表示左岸船的數(shù)目。2/27/2023 47人工智能講義改進(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)2/27/2023 48人工智能講義修正過(guò)程 A1, OPEN=(s), f(s)=g(s)+h(s), fm=0。? 對(duì)算法加以改進(jìn)–能否對(duì)算法加以改進(jìn)，避免或減少節(jié)點(diǎn)的多次擴(kuò)展。2/27/2023 32人工智能講義A*算法的性質(zhì)（續(xù) 3）定理 2：對(duì)無(wú)限圖，若從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t有路徑存在，則 A*一定成功結(jié)束。4, IF GOAL(n) EXIT(SUCCESS)。6, 對(duì)每個(gè)后繼節(jié)點(diǎn) j,計(jì)算 g(j)=g(i)+c(i,j)且 ADD(OPEN, j), 并標(biāo)記 j到 i的指針 。2/27/2023 13人工智能講義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 5125 6 731 2 3 8 47 6 5目標(biāo)82 3 41 8 7 6 542/27/2023 14人工智能講義寬度優(yōu)先搜索的性質(zhì)? 當(dāng)問題有解時(shí)，一定能找到解? 當(dāng)問題為單位耗散值，且問題有解時(shí)，一定能找到最優(yōu)解? 方法與問題無(wú)關(guān)，具有通用性? 效率較低? 屬于圖搜索方法2/27/2023 15人工智能講義等代價(jià)搜索? 寬度優(yōu)先搜索可被推廣用來(lái)解決尋找從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)具有最小代價(jià)路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做 等代價(jià)搜索算法 。2, LOOP: IF OPEN=( ) EXIT (FAIL)。6, IF DEPTH(n)≥Dm GO LOOP。5, IF GOAL(n) EXIT(SUCCESS)。? 路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點(diǎn)間所有耗散值的總和。2, CLOSED=( )。3, n=FIRST(OPEN)。2/27/2023 9人工智能講義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 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 61234 567 89a bcd1 2 3 8 47 6 5目標(biāo)2/27/2023 10人工智能講義深度優(yōu)先搜索的性質(zhì)? 一般不能保證找到最優(yōu)解? 當(dāng)深度限制不合理時(shí)，可能找不到解，可以將算法改為可變深度限制? 最壞情況時(shí)，搜索空間等同于窮舉? 與回溯法的差別：圖搜索? 是一個(gè)通用的與問題無(wú)關(guān)的方法2/27/2023 11人工智能講義寬度優(yōu)先搜索? 如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索。7, IF 目標(biāo)在 {mi}中 THEN EXIT(SUCCESS)。 REMOVE(i, OPEN), ADD(i, CLOSED)。2/27/2023 20人工智能講義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ù)2/27/2023 21人工智能講義符號(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ì)值2/27/2023 22人工智能講義A算法1, OPEN=(s), f(s)=g(s)+h(s)。2/27/2023 28人工智能講義A*條件舉例? 8數(shù)碼問題–h(n) = “不在位 ”的將牌數(shù)–h(n) = 將牌 “不在位 ”的距離和2 8 31 6 47 51 2 3457 6 8將牌 1： 1將牌 2： 1將牌 6： 1將牌 8： 22/27/2023 29人工智能講義A*算法的性質(zhì)定理 1：對(duì)有限圖，如果從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t有路徑存在，則算法 A一定成功結(jié)束。簡(jiǎn)寫：如果 h2(n) h1(n), 則 A1擴(kuò)展的節(jié)點(diǎn)數(shù) ≥A2擴(kuò)展的節(jié)點(diǎn)數(shù)2/27/2023 37人工智能講義A*算法的改進(jìn)? 問題的提出：因 A算法第 6步對(duì) ml類節(jié)點(diǎn)可能要重新放回到 OPEN表中，因此可能會(huì)導(dǎo)致多次重復(fù)擴(kuò)展同一個(gè)節(jié)點(diǎn)，導(dǎo)致搜索效率下降。2/27/2023 45人工智能講義h單調(diào)的例子? 8數(shù)碼問題：–h為 “不在位 ”的將牌數(shù) 1h(ni) h(nj) = 0 (nj為 ni的后繼節(jié)點(diǎn) ) 1 h(t) = 0c(ni, nj) = 1 滿足單調(diào)的條件。該船的負(fù)載能力為兩人。圖生成過(guò)程，就是從初始節(jié)點(diǎn)出發(fā)，按照該指針向下搜索，一直到找到一個(gè)未擴(kuò)展的節(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é)原理，總可以在有限步內(nèi)給以判定。 假言推理 : 由合適公式 W1和 W1 → W2產(chǎn)生合適公式 W2 ,如何用歸結(jié)法證明 ?2/27/2023 75人工智能講義命題邏輯的歸結(jié)法? 歸結(jié)過(guò)程 – 對(duì)結(jié)論作否定 ,并加入前提中– 將命題寫成合取范式– 求出子句集– 對(duì)子句集使用歸結(jié)推理規(guī)則– 歸結(jié)式作為新子句參加歸結(jié)– 歸結(jié)式為空子句 □ ， S是不可滿足的（矛盾），原命題成立。 –SKOLEM標(biāo)準(zhǔn)形定義：消去量詞后的謂詞公式。即： S = G2/27/2023 85人工智能講義子句形? G = G1Λ G 2Λ G 3Λ …Λ G n 的子句形– G的子句集可以分解成幾個(gè)單獨(dú)處理。–思想：尋找一個(gè)已給的公式是真的解釋。通過(guò)它們來(lái)討論永真性。2/27/2023 98人工智能講義Herbrand定理? H域? H解釋? 語(yǔ)義樹? 結(jié)論： Her