【正文】 7, OPEN中的節(jié)點(diǎn)按 f值從小到大排序；8, GO LOOP；2/27/2023 24人工智能講義一個(gè) A算法的例子定義評價(jià)函數(shù)：f(n) = g(n) + h(n)g(n)為從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗散值h(n)為當(dāng)前節(jié)點(diǎn) “不在位 ”的將牌數(shù) 2 8 31 6 47 51 2 38 47 6 52/27/2023 25人工智能講義h計(jì)算舉例h(n) =4 2 8 31 6 47 51 2 3457 6 82/27/2023 26人工智能講義2 8 31 6 47 52 8 31 47 6 52 8 31 6 4 7 52 8 31 6 47 52 31 8 47 6 52 8 3 1 47 6 52 8 31 47 6 52 8 37 1 4 6 5 8 32 1 47 6 5 2 31 8 47 6 52 31 8 47 6 51 2 3 8 47 6 51 2 38 47 6 51 2 37 8 4 6 5s(4)A(6) B(4) C(6)D(5) E(5) F(6)G(6) H(7)I(5) J(7)K(5)L(5) M(7)目標(biāo)123 456定義評價(jià)函數(shù)：f(n) = g(n) + h(n)g(n)為從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的耗散值h(n)為當(dāng)前節(jié)點(diǎn) “不在位 ”的將牌數(shù)2/27/2023 27人工智能講義最佳圖搜索算法 A*（ A*算法）? 在 A算法中，如果滿足條件：h(n)≤h*(n)則 A算法稱為 A*算法。2/27/2023 36人工智能講義A*算法的性質(zhì)（續(xù) 7）定理 4：設(shè)對同一個(gè)問題定義了兩個(gè) A*算法A1和 A2，若 A2比 A1有較多的啟發(fā)信息，即對所有非目標(biāo)節(jié)點(diǎn)有 h2(n) h1(n)，則在具有一條從 s到 t的路徑的隱含圖上，搜索結(jié)束時(shí)，由 A2所擴(kuò)展的每一個(gè)節(jié)點(diǎn)，也必定由 A1所擴(kuò)展，即 A1擴(kuò)展的節(jié)點(diǎn)數(shù)至少和 A2一樣多。2/27/2023 44人工智能講義h單調(diào)的性質(zhì)（續(xù)）? 定理 6：若 h(n)是單調(diào)的，則由 A*所擴(kuò)展的節(jié)點(diǎn)序列其 f值是非遞減的。2/27/2023 49人工智能講義s(10)A(1)B(5)C(8)G 目標(biāo)6311 18前面的例子：OPEN表 CLOSED表 fms(0+10) s(0+10) 10A(6+1) B(3+5) C(1+8) s(0+10) C(1+8) 10A(6+1) B(2+5) s(0+10) C(1+8) B(2+5) 10A(3+1) s(0+10)C(1+8)B(2+5)A(3+1) 10G(11+0) 2/27/2023 50人工智能講義例子： 傳教士與野人問題 設(shè)有 3個(gè)傳教士和 3個(gè)野人來到河邊，打算乘一只船從右岸渡到左岸去。2/27/2023 52人工智能講義(3,2,0) (3,1,0) (2,2,0)(3,3,1) h=4,f=4f(n)=d(n)+m+c2bhh=5,f=6 h=4,f=5 h=4,f=5(3,2,1) h=3,f=5(2,1,0) (3,0,0) h=3,f=6h=3,f=6(2,2,1) (3,1,1) h=2,f=6h=2,f=6h=2,f=7h=2,f=7傳教士和野人問題的 A*搜索圖(0,0,0)(0,3,1)h=1,f=7(0,1,0)h=1,f=8(0,2,1)h=0,f=8(0,2,0) (1,1,0)2/27/2023 53人工智能講義 AO*算法? 搜索 與或圖 的 A*算法? 節(jié)點(diǎn)評價(jià)方法 A*算法中，對節(jié)點(diǎn) n的評價(jià)，實(shí)際上是對 “初始節(jié)點(diǎn) 節(jié)點(diǎn) n目標(biāo)節(jié)點(diǎn) ”這一條路徑的評價(jià) AO*算法中，由于與節(jié)點(diǎn)的存在，解對應(yīng)的不是一條路徑，而是一個(gè)子圖，因此對節(jié)點(diǎn)的評價(jià)，實(shí)際是對局部解圖 的評價(jià) 2/27/2023 54人工智能講義 A (6) B C D(3) (4) (5)f(A) = min {(B)+(C)+2, (D)+1} G H E F(4) (4)(5) (7)(10)(9)(6)(11)與或圖節(jié)點(diǎn)擴(kuò)展與評價(jià)2/27/2023 55人工智能講義算法的兩個(gè)階段第一階段：自上而下的圖生成過程對于每一個(gè)已經(jīng)擴(kuò)展過的節(jié)點(diǎn)， 都對應(yīng)一個(gè)指針，指向該節(jié)點(diǎn)后繼節(jié)點(diǎn)中，代價(jià)值小的那條邊。 2 選擇 G′中的一個(gè)非終節(jié)點(diǎn) n作為當(dāng)前節(jié)點(diǎn)。– 一階邏輯中，至今為止的最有效的半可判定的算法。 注意： C1ΛC 2 → R(C1, C2) ， 反之 不一定不一定成立。 例子：見《人工智能及其應(yīng)用》 P752/27/2023 81人工智能講義子句形 ( Skolem 標(biāo)準(zhǔn)形 )? ? ? ? ? ? ? ? ? ? ? ? ?–定理 ：謂詞邏輯的任意公式都可以化為與之等價(jià)的前束范式，但其前束范式不唯一。 注意 ： G真不一定 S真，而 S真必有 G真。 ” 2/27/2023 90人工智能講義Herbrand定理? Herbrand的思想–定義：公式 G永真：對于 G的所有解釋， G都為真。 t1, t2, …t n為 S的 H域的元素。它們在討論子句集 S的不可滿足性時(shí)占有重要置。–定理 2：子句集 S是不可滿足的，當(dāng)且僅當(dāng)所有的 S的H解釋下為假。將元素的是與非分別標(biāo)記在兩側(cè)的分枝上（可不完全畫完） 。2/27/2023 108人工智能講義語義樹 舉例? 例 1 設(shè)子句集 S的原子集 A={P,Q,R} 語義樹： N0 N11 N12N21 N22 N23 N24N31 N32 N33 N34 N35 N36 N37 N38P～ R ～ R～ PI(N)表示從根節(jié)點(diǎn)到節(jié)點(diǎn) N分枝上所標(biāo)記的所有文字的并集。 2/27/2023 115人工智能講義Herbrand定理 （結(jié)論）? 定理的意義–Herbrand定理已將證明問題轉(zhuǎn)化成了命題邏輯問題。 ， S4180。? 方法：–和命題邏輯一樣。避免多余的、不必要的歸結(jié)式出現(xiàn)。 ? D成立，便說子句 C把子句 D歸類。還引入文字次序，約定歸結(jié)時(shí)其中的一個(gè)子句被歸結(jié)文字只能是該子句中 “最大 ”的文字。2/27/2023 142人工智能講義歸結(jié)反演求解 基于歸結(jié)的問答系統(tǒng)已知： (?x)[AT(John, x) ? AT(Fido, x)] AT(John, School)求證： (?x)AT(Fido, x)子句集：~AT(John, x1) ? AT(Fido, x1)AT(John, School)~AT(Fido, x2)2/27/2023 143人工智能講義~AT(Fido, x2) ~AT(John, x1) ?AT(Fido, x1)子句集： ~AT(John, x1) ? AT(Fido, x1)AT(John, School)~AT(Fido, x2)~AT(John, x2){x2/x1}AT(John, School)nil{School/x2}用重言式代替結(jié)論求反得到的子句2/27/2023 144人工智能講義~AT(Fido, x2) ~AT(John, x1) ?AT(Fido, x1)子句集： ~AT(John, x1) ? AT(Fido, x1)AT(John, School)~AT(Fido, x2)~AT(John, x2){x2/x1}AT(John, School)nil{School/x2}AT(Fido, x2) ??AT(Fido, x2)AT(Fido, School)2/27/2023 145人工智能講義例：猴子摘香蕉問題c2/27/2023 146人工智能講義問題的表示已知：1, ~ON(s0)2, (?x)(?s)(~ON(s) ? AT(box, x, push(x, s)))3, (?s)(ON(climb(s)))4, (?s)((ON(s) ? AT(box, c, s)) ? HB(grasp(s)))5, (?x)(?s)(AT(box, x, s) ? AT(box, x, climb(s)))求解： (?s)HB(s)2/27/2023 147人工智能講義問題的子句集1, ~ON(s0)2, ON(s1) ? AT(box, x1, push(x1, s1))3, ON(climb(s2))4, ~ON(s3) ? ~AT(box, c, s3) ? HB(grasp(s3))5, ~AT(box, x4, s4) ?AT(box, x4, climb(s4))6, ~HB(s5)返回2/27/2023 148人工智能講義~HB(s5) ~ON(s3) ? ~AT(box, c, s3) ? HB(grasp(s3))~ON(s3) ? ~AT(box, c, s3){grasp(s3)/s5}ON(climb(s2)){climb(s2)/s3} ~AT(box, c, climb(s2)) ~ON(s0) ON(s1) ? AT(box, x1, push(x1, s1)){s0/s1}AT(box, x1, push(x1, s0))~AT(box, x4, s4) ?AT(box, x4, climb(s4)){x4/x1,push(x4,s0)/s4}AT(box, x4, climb(push(x4,s0)))NIL{c/x4,push(c,s0)/s2}HB(s5) ?HB(grasp(s3)) ?? HB(grasp(climb(s2)))HB(grasp(climb(push(c,s0))))2/27/2023 149人工智能講義例子 任何兄弟都有同一個(gè)父親， John和Peter是兄弟，且 John的父親是 David,問Peter的父親是誰？2/27/2023 150人工智能講義例子 某人被盜，公安局派出所派出 5個(gè)偵察員卻調(diào)查。2/27/2023 133人工智能講義歸結(jié)過程的控制策略? 輸入歸結(jié)： 在歸結(jié)過程中，對兩個(gè)子句所做的每一次歸結(jié)，其中必須有一個(gè)是 S的子句時(shí)，便稱作輸入歸結(jié)。刪除策略：若對 s使用歸結(jié)推理過程中，當(dāng)歸結(jié)式 Cj是重言式或 Cj被 S中子句或歸結(jié)式Ci(ij)歸類時(shí)，便將 Cj刪除。具體過程如下：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)P∨ ～ P (1)(4) (9)Q ∨ ～ Q (2)(3) (10)P∨ ～ P (2)(3) (11)～ P (2)(4) (12)～ Q (3)(4)2/27/2023 127人工智能講義歸結(jié)過程的控制策略 (盲目歸結(jié) )S2 (13)P (1)(7) (14)P∨Q (1)(8) (15)P∨Q (1)(9) (16)P∨Q (1)(10) (17)Q (1)(11) (18)P (1)(12) (19