【正文】 圖中節(jié)點(diǎn)旁所標(biāo)數(shù)字為 h(x)的值，箭頭上所標(biāo)為啟用的規(guī)則。在這里 R1與 R2所得到的新狀態(tài)與目標(biāo)狀態(tài)差距最小，且都為 4，而在 R1與 R2中再選擇一條規(guī)則作為啟用規(guī)則，在這里我們使用規(guī)則的排列順序，首先選擇 R1，所以啟用規(guī)則 R1，依次類推。利用啟發(fā)函數(shù)決定哪一條規(guī)則為啟用規(guī)則。 在本題中采用一個(gè)啟發(fā)式函數(shù) f(n)=d(n)+W(n) 其中： d(n)是搜索樹中節(jié)點(diǎn) n的深度； W(n)用來計(jì)算對(duì)應(yīng)于節(jié)點(diǎn) n的數(shù)據(jù)庫(kù)中錯(cuò)放的棋子個(gè)數(shù)。 02 8 3147 6 5S???? ????????? ???? ? ???????????? ??????1 2 3847 6 5gS???? ????????? ???? ? ???????????? ??????3）推理求解 在進(jìn)行推理求解時(shí)，可能會(huì)有多條產(chǎn)生式規(guī)則的條件部分和綜合數(shù)據(jù)庫(kù)中的已有事實(shí)相符，這樣就有可能激活多條規(guī)則。 S(i0+1)j0:=0 end 空格下移 2）建立綜合數(shù)據(jù)庫(kù) 將棋盤的布局表示為狀態(tài)矩陣的形式存入綜合數(shù)據(jù)庫(kù)。 S(i01)j0:=0 end 空格上移 R3: if (j0+1≤3) then begin Si0j0:=Si0(j0+1)。如果在狀態(tài)矩陣中用 0來表示空格的話，則建立如下四條產(chǎn)生式規(guī)則： R1: if (j01≥1) then begin Si0j0:=Si0(j01)。 設(shè) Sij為狀態(tài)矩陣的第 i行和第 j列的數(shù)碼，其中 3≥i, j≥1。 初始狀態(tài) 目標(biāo)狀態(tài) 2 8 31 47 6 51 2 38 47 6 5解： 1）建立棋盤變換的產(chǎn)生式規(guī)則。 其基本形式為 IF 前提 THEN 結(jié)論 ? 控制策略的作用是說明下一步應(yīng)該選用什么規(guī)則。 求：張的老師是誰(shuí)？ 解：令 T(x,y):x是 y的老師； C(x,y)： x是 y的同學(xué) , 則 已知的三個(gè)事實(shí)可解釋為下列公式集 T(Wang,Li) C(Li,Zhang) (?x)(?y)(?z){C(x,y)∧T(z,x)=T(z,y)} 目標(biāo)公式： (?x)T(x,Zhang) 將上述事實(shí)化為子句集： ① T(Wang,Li) ② C(Li,Zhang) ③ ～ C(x,y)∨ ～ T(z,x)∨ T(z,y) 目標(biāo)公式否定的子句形為： ～ T(x,Zhang) 將它與謂詞 ANSWER構(gòu)成析取式： ④ ～ T(w,Zhang)∨ANSWER(w,Zhang) 用下圖的反演樹進(jìn)行消解，并在根部得到子句 ： ～ C(x,y)∨ ～ T(z,x)∨T(z,y) T(Wang,Li) ～ C(Li,y)∨T(Wang,y) C(Li,Zhang) T(Wang,Zhang) ?1={Wang/z,Li/x} ～ T(w,Zhang)∨ANSWER(w,Zhang) ?2={Zhang/y} ANSWER(Wang,Zhang) ?3={Wang/w} 產(chǎn)生式系統(tǒng) 產(chǎn)生式系統(tǒng)的組成 產(chǎn)生式系統(tǒng)由 3個(gè)部分組成，即總數(shù)據(jù)庫(kù) (或全局?jǐn)?shù)據(jù)庫(kù) )、產(chǎn)生式規(guī)則和控制策略， ?總數(shù)據(jù)庫(kù)又稱為綜合數(shù)據(jù)庫(kù)、上下文、黑板等，用于存放求解過程中各種當(dāng)前信息的數(shù)據(jù)結(jié)構(gòu)，如問題是的初始狀態(tài)、事實(shí)或證據(jù)、中間推理結(jié)論和最后結(jié)果等。 求公司錄用誰(shuí)？ 解： 定義： P(x)表示錄用 x。 例 1： 應(yīng)用消解反演求解如下問題： “如果無(wú)論約翰 (John)到哪里去，菲多 (Fido)也就去那里，那么如果約翰在學(xué)校里，菲多在哪里呢 ?” 解：定義謂詞： AT（ x,y）表示 x在 y那里。 (4)對(duì)子句集 S’應(yīng)用 消解 原理進(jìn)行消解。 (2)把 待求解的問題也用謂詞公式表示出來，然后把它的否定與謂詞 ANSWER構(gòu)成析取式。 證： 定義： P(x)表示錄用 x。 例 3 某公司招聘人員， A、 B、 C三人應(yīng)試，經(jīng)面試后，公司有如下想法： (1) 三人中至少錄用一人； (2) 如果錄用 A而不錄用 B，則一定錄用 C； (3) 如果錄用 B，則一定錄用 C。 G1： (?x)(P(x)?(Q(x)∧ R(x))) = (?x)(～ P(x)∨ (Q(x)∧ R(x))) =(?x)((～ P(x)∨ Q(x))∧ (～ P(x)∨ R(x))) 所以 S1={～ P(x1)∨ Q(x1), ～ P(x2)∨ R(x2)} G2: (?x) (P(x)∧ T(x)) 所以 S2= {P(a), T(a)} ～ B:～ (?x)(T(x)∧ R(x)) =(?x)(～ T(x)∨ ～ R(x)) 所以 S～ B={～ T(x)∨ ～ R(x)} 從而求得公式 G的子句集： S=S1∪ S2∪ S～ B= {～ P(x1)∨ Q(x1), ～ P(x2)∨ R(x2), P(a), T(a), ～ T(x3)∨ ～ R(x3)} 第三步：例用消解原理，對(duì)子句集 S進(jìn)行消解 ～ P(x2)∨R(x2) P(a) R(a) ～ T(x3)∨ ～ R(x3) ～ T(a) ?1={a/x2} T(a) ?2={a/x3} NIL 由此得出子句集 S是不可滿足的，因此公式 G也是不可滿足的。 G=(?x)(P(x)?(Q(x)∧ R(x))) ∧ (?x) (P(x)∧ T(x)) ∧ ～ (?x)(T(x)∧ R(x)) 第二步：將公式 G化為子句集。 (2) S={～ P(x)∨Q(f(x),a) ， ～ P(h(y))∨Q(f(h(y)),a)∨ ～ P(z)} 解：因子句集中無(wú)互補(bǔ)對(duì)，故在子句集S中不存在空子句，故 S為 可滿足的。 (2)在子句集中選擇合適的子句對(duì)其進(jìn)行消解，若能推出空子句，就說明子句 S是不可滿足的。 例 判斷下列子句集中哪些是不可滿足的 分析：子句集中各子句間的關(guān)系是合取關(guān)系，因此只要有一個(gè)子句不可滿足，則子句集就是不可滿足的。這種更改變量名稱的過程，有時(shí)稱為變量分離標(biāo)準(zhǔn)化。 2 8 31 47 6 51 2 38 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 58 32 1 47 6 52 8 37 1 46 52 31 8 47 6 528 47 6 51 2 38 47 6 52 38 46 51 2 38 47 6 5Sg 2 8 347 6 5S0 3 4 4 5 5 5 6 4 6 4 4 6 消解原理 重點(diǎn)掌握子句集的求解步驟和消解反演過程，掌握消解推理的規(guī)則。 例：八數(shù)碼難題 解： 采用估價(jià)函數(shù) f(n)=d(n)+W(n) 其中： d(n)是搜索樹中節(jié)點(diǎn) n的深度； W(n)用來計(jì)算對(duì)應(yīng)于節(jié)點(diǎn) n的數(shù)據(jù)庫(kù)中錯(cuò)放的棋子個(gè)數(shù)。 h(n)： 依賴于有關(guān)問題的領(lǐng)域的啟發(fā)信息。 A*算法 ?A*算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。 ?對(duì)于寬度優(yōu)先搜索，我們選擇 f(i)作為節(jié)點(diǎn) i的深度。 f是從起始節(jié)點(diǎn)約束地通過節(jié)點(diǎn) n而到達(dá)目標(biāo)節(jié)點(diǎn)的最小