【正文】 程，了解規(guī)則雙向演繹系統(tǒng)。 教學(xué)方法：課堂教學(xué)為主。 教學(xué)重點(diǎn)：規(guī)則演繹系統(tǒng)的定義、正向推理和逆向推理過(guò)程。 結(jié)論：如果沒(méi)有利息，那么就沒(méi)有人去儲(chǔ)蓄錢 思考： 應(yīng)用消解反演求解如下問(wèn)題： “如果無(wú)論約翰 (John)到哪里去，菲多(Fido)也就去那里，那么如果約翰在學(xué)校里，菲多在哪里呢 ?” 65 規(guī)則演繹系統(tǒng) 教學(xué)內(nèi)容：規(guī)則演繹系統(tǒng)屬于高級(jí)搜索推理技術(shù)，用于解決比較復(fù)雜的系統(tǒng)和問(wèn)題。因此被變換的證明樹本身就證明了求取辦法是正確的。 63 ? 分析： 答案求取涉及到把一棵根部有 NIL的反演樹變換為在根部帶有可用作答案的某個(gè)語(yǔ)句的一顆證明樹。 (2)按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個(gè)子句止。因此，如果 L在邏輯上遵循 S，那么由并集 S∪ ｛～ L｝消解得到的子句，最后將產(chǎn)生空子句；反之，可以證明，如果從 S∪ ｛～ L｝的子句消解得到空子句，那么 L在邏輯上遵循 S。因此，如果 L在邏輯上遵循 S，那么 S∪ ｛～ L｝是不可滿足的。決不會(huì)有滿足 S的解釋能夠滿足～ L的，所以不存在能夠滿足并集 S∪ ｛～ L｝的解釋。 60 消解反演 反演求解的步驟 給出一個(gè)公式集 S和目標(biāo)公式 L，通過(guò)反證或反演來(lái)求證目標(biāo)公式 L，其證明步驟如下： (1)否定 L，得～ L； (2)把～ L添加到 S中去； (3)把新產(chǎn)生的集合｛～ L， S｝化成子句集； (4)應(yīng)用消解原理，力圖推導(dǎo)出一個(gè)表示矛盾的空子句 NIL。 57 含有變量的消解式 消解式求法 為了對(duì)含有變量的子句使用消解規(guī)則，必須找到一個(gè)置換，作用于父輩子句使其含有互補(bǔ)文字。 55 消解式求法 (1) 假言推理 父輩子句 P ～ P∨Q( 即 P→Q) \ / \ / 消解式 Q 56 (2) 合并 (3) 重言式 (4) 空子句 (矛盾 ) ～ P P \ / \ / NIL (5) 鏈?zhǔn)?(三段論 ) 即取各子句的析取，然后消去互補(bǔ)對(duì)。這個(gè)新子句叫做消解式。 54 消解推理規(guī)則 消解式 令 L1為任一原子公式， L2為另一原子公式； L1和 L2具有相同的謂詞符號(hào)，但一般具有不同的變量。 52 例 將下列謂詞演算公式化為一個(gè)子句集 (? x)｛ P(x)→ ｛ (? y)［ P(y)→P(f(x,y)) ］ ∧ ～ (? y)［ Q(x,y)→P(y) ］｝｝ 53 說(shuō)明 并不是所有問(wèn)題的謂詞公式化為子句集都需要上述 9個(gè)步驟。任一個(gè)只由文字的析取構(gòu)成的合適公式叫做一個(gè)子句。 50 提問(wèn)：對(duì)于公式 (? z)(? y){(? x)P(x,y,z)∨( ? q)(?)(? e)Q(q,w,e,z)，在經(jīng)過(guò)消去存在量詞后，正確的公式為： A． (? y){P(B,y,A)∨( ? w)Q(C,w,D,A) B． (? y){P(B,y,A)∨( ? ? w)Q(C,w,g(w),A) , g(w)為一 Skolem函數(shù) C． (? y){P(g1(y),y,A)∨( ? w)Q(g２ (y),w,g３(w),A) 式中， (g1(y)， g２ (y)和 g３ (w)為 Skolem函數(shù) D． (? y){P(g1(y),y,A)∨( ? w)Q(g２ (y),w,g３(y,w),A) 式中， (g1(y)， g２ (y)和 g３ (y,w)為 Skolem函數(shù) 51 (8) 消去連詞符號(hào) ∧ 用｛ A， B｝代替 (A∧B) ，以消去明顯的符號(hào) ∧ 。這種母式叫做合取范式。所得公式稱為前束形。A必須是個(gè)新的常量符號(hào)，它未曾在公式中其它地方使用過(guò)。 48 如果要消去的存在量詞不在任何一個(gè)全稱量詞的轄域內(nèi)，則用不含變量的 Skolem函數(shù)即常量。 Skolem函數(shù)所使用的函數(shù)符號(hào)必須是新的，即不允許是公式中已經(jīng)出現(xiàn)過(guò)的函數(shù)符號(hào)。合適公式中變量的標(biāo)準(zhǔn)化意味著對(duì)啞元改名以保證每個(gè)量詞有其自己唯一的啞元。 摩根定律。 43 步驟 (1) 消去蘊(yùn)涵符號(hào) 只應(yīng)用 ∨ 和～符號(hào)，以～ A∨B 替換 A→B 。例如，如果存在某個(gè)公理 E1∨E 2和另一公理～E2∨E 3，那么 E1∨E 3在邏輯上成立。 （ 2）子句：由文字的析取組成的公式 (一個(gè)原子公式和原子公式的否定都叫做文字 )。 教學(xué)要求：重點(diǎn)掌握子句集的求解步驟和消解反演過(guò)程，掌握消解推理的規(guī)則。 教學(xué)難點(diǎn)：消解反演的思想。本節(jié)內(nèi)容主要包括子句集的求取、消解推理的規(guī)則和消解反演問(wèn)題求解方法。 40 A*算法 A*算法描述參考教材。 定義 3 采用 h*(x)的下界 h(x)為啟發(fā)函數(shù)的A算法，稱為 A*算法。 39 A*算法定義 定義 1 在 GRAPHSEARCH過(guò)程中，如果第 8步的重排 OPEN表是依據(jù) f(x)=g(x)+h(x)則稱該過(guò)程為 A算法。這種信息可能與八數(shù)碼難題中的函數(shù) W(n)所用的那種信息相似。這個(gè)定義包含了g(n)≥g*(n) 。 37 估價(jià)函數(shù)的定義 定義 g*為 : g*(n)=k(S,n) 定義函數(shù) f*，使得在任一節(jié)點(diǎn) n上其函數(shù)值f*(n)就是從節(jié)點(diǎn) S到節(jié)點(diǎn) n的一條最佳路徑的實(shí)際代價(jià)加上從節(jié)點(diǎn) n到某目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)之和，即 f*(n)=g*(n)+h*(n) 38 希望估價(jià)函數(shù) f是 f*的一個(gè)估計(jì)，此估計(jì)可由下式給出： f(n)=g(n)+h(n) 其中： g是 g*的估計(jì)； h是 h*的估計(jì)。于是，從節(jié)點(diǎn) n到某個(gè)具體的目標(biāo)節(jié)點(diǎn) ti，某一條最小代價(jià)路徑的代價(jià)可由 k(n,ti)給出。 36 A*算法 A*算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。 35 例：八數(shù)碼難題 采用了簡(jiǎn)單的估價(jià)函數(shù) f(n)=d(n)+W(n) 其中： d(n)是搜索樹中節(jié)點(diǎn) n的深度； W(n)用來(lái)計(jì)算對(duì)應(yīng)于節(jié)點(diǎn) n的數(shù)據(jù)庫(kù)中錯(cuò)放的棋子個(gè)數(shù)。 有序搜索的有效性直接取決于 f的選擇，如果選擇的 f不合適，有序搜索就可能失去一個(gè)最好的解甚至全部的解。對(duì)于寬度優(yōu)先搜索，選擇 f(i)作為節(jié)點(diǎn) i的深度。 (7) 轉(zhuǎn)向 (2)，即 GO TO(2)。 (ii) 從 j指向 i，而不是指向它的父輩節(jié)點(diǎn)。 (c)如果 j已在 OPEN表上或 CLOSED表上，則比較剛剛對(duì) j計(jì)算過(guò)的 f值和前面計(jì)算過(guò)的該節(jié)點(diǎn)在表中的 f值。 (b)如果 j既不在 OPEN表中，又不在 CLOSED表中，則用估價(jià)函數(shù) f把它添入 OPEN表。 33 (6) 擴(kuò)展節(jié)點(diǎn) i，生成其全部后繼節(jié)點(diǎn)。 (4) 把節(jié)點(diǎn) i從 OPEN表中移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 (3) 從 OPEN表中選擇一個(gè) f值最小的節(jié)點(diǎn) i。 32 有序狀態(tài)空間搜索算法 (1) 把起始節(jié)點(diǎn) S放到 OPEN表中，計(jì)算 f(S)并把其值與節(jié)點(diǎn) S聯(lián)系起來(lái)。被選為擴(kuò)展的節(jié)點(diǎn)，是估價(jià)函數(shù)最小的節(jié)點(diǎn)。 尼爾遜 (Nilsson)曾提出一個(gè)有序搜索的基本算法。應(yīng)用某個(gè)算法 (例如等代價(jià)算法 )選擇 OPEN表上具有最小 f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。這些特點(diǎn)被認(rèn)為與向目標(biāo)節(jié)點(diǎn)前進(jìn)一步的希望程度有關(guān)。 29 估價(jià)函數(shù) 為獲得某些節(jié)點(diǎn)“希望”的啟發(fā)信息，提供一個(gè)評(píng)定侯選擴(kuò)展節(jié)點(diǎn)的方法，以便確定哪個(gè)節(jié)點(diǎn)最有可能在通向目標(biāo)的最佳路徑上 。然后，搜索就可能沿著某個(gè)被認(rèn)為是最有希望的邊緣區(qū)段向外擴(kuò)展。 28 啟發(fā)式搜索策略 有關(guān)具體問(wèn)題領(lǐng)域的信息常常可以用來(lái)簡(jiǎn)化搜索。 27 定義 進(jìn)行搜索技術(shù)一般需要某些有關(guān)具體問(wèn)題領(lǐng)域的特性的信息，把此種信息叫做啟發(fā)信息。 教學(xué)要求：掌握啟發(fā)式搜索策略和估價(jià)函數(shù)的設(shè)計(jì)方法，了解 A*算法原理。 教學(xué)難點(diǎn)：估價(jià)函數(shù)的設(shè)計(jì)、 A*算法原理。啟發(fā)式搜索彌補(bǔ)盲目