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