【正文】 而 Bi屬于 S或是已出現(xiàn)的歸結(jié)式 Cj(ji)。2/27/2023 126人工智能講義歸結(jié)過程的控制策略? 盲目歸結(jié) 例 S={P∨Q , ～ P∨Q,P∨ ～ Q, ～ P∨ ～ Q}是不可滿足。才是不可滿足。但 N以前尚不能判斷這事實。 2/27/2023 103人工智能講義Herbrand定理 （ H解釋）? 基例S中某子句中所有變元符號均以 S的 H域中的元素代入時，所得的基子句 C’ 稱為 C的一個基例。 –原子集 A：謂詞套上 H域的元素組成的集合。 –有 SG = S1 U S2 U S3 U …U S n則 SG 與 S1 U S2 U S3 U …U Sn在不可滿足的意義上是一致的。? （證明完畢）? 謂詞的歸結(jié)：除了有量詞和函數(shù)以外，其余和命題歸結(jié)過程一樣。將所有子節(jié)點添加到 G中。在任何時候，如果野人人數(shù)超過傳教士人數(shù)，那么野人就會把傳教士吃掉。2/27/2023 38人工智能講義s(10)A(1)B(5)C(8)G 目標(biāo)6311 18一個例子：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)2/27/2023 39人工智能講義出現(xiàn)多次擴展節(jié)點的原因? 在前面的擴展中，并沒有找到從初始節(jié)點到當(dāng)前節(jié)點的最短路徑，如節(jié)點 A。2, LOOP: IF OPEN=( ) EXIT(FAIL)。8, ADD(OPEN, mj), 并標(biāo)記 mj到 n的指針 。4, IF GOAL(n) EXIT (SUCCESS)。第三章 一般搜索原理? 盲目搜索? 啟發(fā)式搜索? 歸結(jié)原理2/27/2023 1人工智能講義盲目搜索? 圖搜索策略? 深度優(yōu)先搜索? 寬度優(yōu)先搜索? 等代價搜索2/27/2023 2人工智能講義一些基本概念? 節(jié)點深度：根節(jié)點深度 =0其它節(jié)點深度 =父節(jié)點深度 +101232/27/2023 3人工智能講義一些基本概念（續(xù) 1）? 路徑設(shè)一節(jié)點序列為 (n0, n1,…,n k)，對于i=1,…,k ，若節(jié)點 ni1具有一個后繼節(jié)點 ni，則該序列稱為從 n0到 nk的路徑。5, REMOVE(n, OPEN), ADD(n, CLOSED)。9, GO LOOP。3, n=FIRST(OPEN)。2/27/2023 40人工智能講義解決的途徑? 對 h加以限制–能否對 h增加適當(dāng)?shù)南拗?，使得第一次擴展一個節(jié)點時，就找到了從 s到該節(jié)點的最短路徑。他們怎樣才能用這條船安全地把所有人都渡河過去？ 2/27/2023 51人工智能講義問題表示 ：需要考慮兩岸的修道士人數(shù)和野人人數(shù)，船的位置。 4 建立含 n的單一節(jié)點集合 S ， S:＝ {n}2/27/2023 58人工智能講義 修改節(jié)點的可解性與代價值 重復(fù)以下步驟，直到 S為空：1 從 S中挑選一個子孫節(jié)點都不在 S中的節(jié)點 m 2 計算始于 m的每條連接線的代價，取其中最小值為m對應(yīng)的代價，并在對應(yīng)于最小代價的連接線上加指針。 2/27/2023 76人工智能講義命題邏輯的歸結(jié)法? 例 證明先將化為合取范式 建立子句集 S=對 S做歸結(jié) P NIL2/27/2023 77人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 78人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 79人工智能講義子句形 引用 Herbrand定理，以說明歸結(jié)原理的意義及一個原理形成的根基與背景? SKOLEM標(biāo)準形–前束范式 ：把所有的量詞都提到前面去，然后消掉所有量詞。即 SG 不可滿足 = S1 U S2 U S3 U …U Sn不可滿足如A = {所有形如 P(t1, t2, …t n)的元素 }即把 H中的東西填到 S的謂詞里去。? 若一個子句為假，則此解釋為假。就稱 N為失敗結(jié)點。然而 S5180。 證明從 S0=S開始，依次構(gòu)造 Si={C1,C2的歸結(jié)式 |C1∈ S0∪ S1 ∪ … ∪ Si1,C2 ∈ Si1} ,i=1,2, …, 直至得到空子句。2/27/2023 132人工智能講義歸結(jié)過程的控制策略? 單元歸結(jié)： 在歸結(jié)過程中，每次歸結(jié)都有一個子句是單元（只含一個文字）子句或單元因子時的歸結(jié)過程。例 S={～P∨～ Q∨ R, P∨ R, Q∨ R ,～R } 文字次序： PQR 解釋 I={～P, ～Q, ～R} 2/27/2023 131人工智能講義歸結(jié)過程的控制策略? 線性歸結(jié)策略 首先從子句集 S中選取一個稱為頂子句的子句 C0開始做歸結(jié)，其次是歸結(jié)過程中所得到的歸結(jié)式 Ci立即同另一個子句 Bi進行歸結(jié)得歸結(jié)式 Ci+1?；蛘哒f，少做些歸結(jié)仍能導(dǎo)出空子句。 ， 直到 S5180。如 I(N34)={P, ～ Q, ～ R}2/27/2023 109人工智能講義Herbrand定理 （語義樹）? 幾個概念– 失敗結(jié)點 ： 當(dāng)（由上）延伸到點 N時， I(N)已表明了 S的某子句的某基例假。 –定理 3：子句集 S是不可滿足的，當(dāng)且僅當(dāng)對每一個解釋 I下，至少有 S的某個子句的某個 基例 為假。通過它們來討論永真性。即： S = G2/27/2023 85人工智能講義子句形? G = G1Λ G 2Λ G 3Λ …Λ G n 的子句形– G的子句集可以分解成幾個單獨處理。 假言推理 : 由合適公式 W1和 W1 → W2產(chǎn)生合適公式 W2 ,如何用歸結(jié)法證明 ?2/27/2023 75人工智能講義命題邏輯的歸結(jié)法? 歸結(jié)過程 – 對結(jié)論作否定 ,并加入前提中– 將命題寫成合取范式– 求出子句集– 對子句集使用歸結(jié)推理規(guī)則– 歸結(jié)式作為新子句參加歸結(jié)– 歸結(jié)式為空子句 □ ， S是不可滿足的（矛盾），原命題成立。 3 擴展節(jié)點 n，如不能擴展，則標(biāo)記為不可解，否則生成子節(jié)點集，如子節(jié)點為非終節(jié)點，計算其代價值，若為終節(jié)點，標(biāo)注其可解。該船的負載能力為兩人。簡寫：如果 h2(n) h1(n), 則 A1擴展的節(jié)點數(shù) ≥A2擴展的節(jié)點數(shù)2/27/2023 37人工智能講義A*算法的改進? 問題的提出：因 A算法第 6步對 ml類節(jié)點可能要重新放回到 OPEN表中，因此可能會導(dǎo)致多次重復(fù)擴展同一個節(jié)點，導(dǎo)致搜索效率下降。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)。7, IF 目標(biāo)在 {mi}中 THEN EXIT(SUCCESS)。3, n=FIRST(OPEN)。? 路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。6, IF DEPTH(n)≥Dm GO LOOP。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)問題有解時，一定能找到解? 當(dāng)問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解? 方法與問題無關(guān)，具有通用性? 效率較低? 屬于圖搜索方法2/27/2023 15人工智能講義等代價搜索? 寬度優(yōu)先搜索可被推廣用來解決尋找從起始節(jié)點到目標(biāo)節(jié)點具有最小代價路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做 等代價搜索算法 。4, IF GOAL(n) EXIT(SUCCESS)。? 對算法加以改進–能否對算法加以改進，避免或減少節(jié)點的多次擴展。用三元式表示狀態(tài)： S= (m, c, b)其中， m表示左岸修道士人數(shù)， c表示左岸野人人數(shù)， b表示左岸船的數(shù)目。 3 如果連接于最小代價連接線上的所有節(jié)點都可解，則標(biāo)注 m可解。定義 ：說公式 A是一個前束范式，如果 A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。2/27/2023 86人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 87人工智能講義歸結(jié)原理? 概述? 命題邏輯的歸結(jié)法? 子句形? Herbrand定理? 歸結(jié)原理? 歸結(jié)過程的策略控制2/27/2023 88人工智能講義Herbrand定理?問題：一階邏輯公式的永真性（永假性）的判定是否能在有限步內(nèi)完成 ？2/27/2023 89人工智能講義Herbrand定理? 1936年圖靈 (Turing)和邱吉 (Church)互相獨立地證明了： “ 沒有一般的方法使得在有限步內(nèi)判定一階邏輯的公式是否是永真（或永假）。 S中的謂詞是有限的， H是可數(shù)的，因此， A也是可數(shù)的。? 一般來說， D是無窮不可列的，因此，子句集 S也是無窮不可列的。– 完全語義樹 ： 如果對語義樹的所有葉結(jié)點 N來說， I(N)包含了 S的原子集 A={A1,A2,… }中的所有元素 Ai或 ～ Ai， I=1 …n 。元素個數(shù)已達（ 10 64） 4=10256Herbrand定理 （結(jié)論）? 仍存在的 問題 ： 基例集序列元素的數(shù)目隨子句基的元素數(shù)目成指數(shù)地增加。具體過程如下：S0 (1) P∨Q (2) ～ P∨Q (3)P∨ ～ Q (4)～ P∨ ～ QS1 (5)Q (1)(2) (6)P (1)(3) (7)Q∨ ～ Q (1)(4) (8