【正文】 】 方格棋盤分割問題 原始問題 :2n 2n方格盤 ， 去掉對(duì)頂角上兩方格 ， 問能否將它分割為若干1 2長(zhǎng)方塊 ？ 直接求解 :考察 (2**(2n))**2種可能分割方案 ， 且隨著 n增大 ， 會(huì) “ 組合爆炸 ” 同構(gòu)問題 :方格相間著色 ,無論 n為何值 ， 對(duì)頂角上兩方格同色 ， 去掉后白格與黑格的數(shù)目間差值為 2——最后剩的必是同色兩方格 ——因 同構(gòu)問題無解 ， 果 等價(jià)的原始問題無解 。 初始狀態(tài)： 2n2,2n22， 目標(biāo)狀態(tài)： 0,0。 經(jīng)過 2n22次操作后 ， 狀態(tài)變?yōu)?2,0， 不可能達(dá)到 0,0——因同態(tài)問題無解 ， 蘊(yùn)含著其原始問題也無解 2022/2/9 9 第二章 知識(shí)表達(dá)技術(shù) 2． 3 狀態(tài)空間表達(dá) 狀態(tài) 用來表示系統(tǒng)狀態(tài) ,事實(shí)等敘述型知識(shí)的一組變量或數(shù)組 Q=[q1,q2,… qn]t 操作 是用來表示引起狀態(tài)變化的過程型知識(shí)的一組關(guān)系或函數(shù) F:{f1,f2,… fm} 狀態(tài)空間 (State Space)是利用狀態(tài)變量和操作符號(hào) ， 表示系統(tǒng)或問題的有關(guān)知識(shí)的符號(hào)體系 ， 狀態(tài)空間是一個(gè) 四元組 （ S， O， S0， G） ： S—狀態(tài)集合 。S0—初始狀態(tài) ,S0?S。 狀態(tài)空間一解 是一有限操作算子序列 ， 它使初始狀態(tài)轉(zhuǎn)換為目標(biāo)狀態(tài)： O1 O2 O3 Ok S0???? S1???? S2???? …… ???? G 其中 O1， … ， Ok即為狀態(tài)空間的一個(gè)解 (解往往不是唯一的 ) 2022/2/9 10 第二章 知識(shí)表達(dá)技術(shù) 2． 3 狀態(tài)空間表達(dá) 【 例 2． 2】 八數(shù)碼問題的狀態(tài)空間 在一 3 3方格盤 ， 放 1到 8八個(gè)數(shù)碼 ， 另一格為空 。 一布局： 2 3 1 5 8 4 6 7 八數(shù)碼任何一種擺法就是一個(gè) 狀態(tài) ， 所有的擺法為狀態(tài)集 S， 構(gòu)成了一個(gè) 狀態(tài)空間 ， 其大小為 9！ 相應(yīng) 操作算 子是數(shù)碼移動(dòng) ， 其操作算子共有 4（ 方向 ） 8（ 數(shù)碼 ） =32個(gè) 。 在 b處有可移動(dòng)的臺(tái)子 ， 若猴子站在臺(tái)子上 ， 就可以拿到香蕉 。 香蕉 a猴子 c b臺(tái)子 2022/2/9 13 第二章 知識(shí)表達(dá)技術(shù) 2． 4 與 /或圖表達(dá)法 【 例 2． 3】 猴子和香蕉問題 狀態(tài)空間法 :四元數(shù)組描述： S=(w,x,y,z) 其中： w：猴子所處水平位置 x：臺(tái)子所在水平位置 y：猴子是否在臺(tái)子上 （ y=1:在 。z=0:沒拿到 ） 可能出現(xiàn)的 狀態(tài) 如下： S0=(a,b,0,0) S1=(b,b,0,0) S2=(c,c,0,0) S3=(c,c,1,0) S4=(c,c,1,1) 其中 S0為 初始狀態(tài) ， S4為 目標(biāo)狀態(tài) 2022/2/9 14 第二章 知識(shí)表達(dá)技術(shù) 2． 4 與 /或圖表達(dá)法 【 例 2． 3】 猴子和香蕉問題 允許的操作集為： F={f1,f2,f3,f4} 其中： f1(u)為猴子走到 u處 (w,x,0,z)?(u,x,0,z) f2(v)為猴子推臺(tái)子到 v處 (x,x,0,0)?(v,v,0,0) f3為猴子爬上臺(tái)子 (x,x,0,z)?(x,x,1,z) f4為猴子拿到香蕉 (c,c,1,0)?(c,c,1,1) 比較 目標(biāo)狀態(tài) （ S4） 與初始狀態(tài) （ S0） 的 差異 ， 來 選擇主操作 。 因此 ， 可將原問題變換為四個(gè)新問題 ， 而新問題又可分為幾個(gè)子問題及子子問題 。 這個(gè)基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對(duì)的概念 論域知識(shí)分為兩部分： 1. 事實(shí)表示靜態(tài)知識(shí) ， 如事物 、 事件和它們之間的關(guān)系 2. 產(chǎn)生式規(guī)則表示推理過程和行為 ， 如動(dòng)作 ， 算子 ， 變換等 這類系統(tǒng)的知識(shí)庫主要用于存儲(chǔ)規(guī)則 ， 因此又把此類系統(tǒng)稱為 基于規(guī)則的系統(tǒng) (rulebased system) 2022/2/9 17 第二章 知識(shí)表達(dá)技術(shù) 2． 5 產(chǎn)生式系統(tǒng) 產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu) 一個(gè)產(chǎn)生式系統(tǒng)包含事實(shí)庫 、 規(guī)則集和規(guī)則解釋 （ 控制器 ） 三部分 控制器匹配排序 沖突裁決規(guī)則集激發(fā)樹 元規(guī)則事實(shí)庫知識(shí)匹配 相關(guān)檢索匹配檢索2022/2/9 18 第二章 知識(shí)表達(dá)技術(shù) 2． 5 產(chǎn)生式系統(tǒng) 事實(shí)庫 —— 當(dāng)前已知的知識(shí)信息數(shù)據(jù) ， 包括推理過程中形成的 中間結(jié)論 知識(shí) ， 換句話說 ， 它用于存儲(chǔ)有關(guān)問題的狀態(tài) 、 性質(zhì)等事實(shí)的 敘述型知識(shí) ， 也稱為綜合數(shù)據(jù)庫或工作存儲(chǔ)器 。 規(guī)則集庫 —— 存儲(chǔ)有關(guān)問題的狀態(tài)轉(zhuǎn)移 、 性質(zhì)變化等規(guī)則的 過程型知識(shí) ，或稱 “ 規(guī)則庫 ” 產(chǎn)生式規(guī)則的一般 形式 可以表述為： P1,P2,… ,Pm?C1,C2,… ,Cn 每條產(chǎn)生式規(guī)則分為 左部 和 右部 兩個(gè)部分 ， 左部表示激活該產(chǎn)生式規(guī)則的 前提條件 /規(guī)則前件 ， 右部表示調(diào)用該產(chǎn)生式規(guī)則后所做的 行為部分 /規(guī)則后件 /結(jié)論 。 對(duì)事實(shí)庫的修改在產(chǎn)生式系統(tǒng)中扮演著 推理 的角色 ， 正是由于事實(shí)庫內(nèi)容的不斷改變 ， 才構(gòu)成了由原始數(shù)據(jù)到結(jié)論的變換過程 2022/2/9 19 第二章 知識(shí)表達(dá)技術(shù) 2． 5 產(chǎn)生式系統(tǒng) 產(chǎn)生式規(guī)則的形式 與傳統(tǒng)程序設(shè)計(jì)語言中 條件語句 非常相似 ， 但實(shí)際上兩者之間存在根本的 區(qū)別： 產(chǎn)生式規(guī)則左部表達(dá)的是一組 復(fù)雜模式 ， 而不僅僅是一個(gè) 布爾表達(dá)式 規(guī)則之間控制流不象傳統(tǒng)語言中從一條語句向其下一條語句 傳遞 ， 而且 滿足條件的規(guī)則被激活但不一定立即執(zhí)行 ， 這將取決于產(chǎn)生式系統(tǒng)的 沖突消解策略 ， 這也是區(qū)分傳統(tǒng)程序與產(chǎn)生式系統(tǒng)行為特征的 關(guān)鍵 邏輯程序中的語句可以視作產(chǎn)生式規(guī)則的一種 特殊形式 在產(chǎn)生式系統(tǒng)中 ， 一條規(guī)則僅描述前提條件與行為之間的靜態(tài)關(guān)系 ， 因此 ， 規(guī)則的正確性應(yīng)當(dāng)獨(dú)立地得到保證 。 2022/2/9 20 第二章 知識(shí)表達(dá)技術(shù) 2． 5 產(chǎn)生式系統(tǒng) 規(guī)則解釋 （ 控制器 ） —— 根據(jù)有關(guān)問題的控制型知識(shí) ， 選擇控制策略 ， 將規(guī)則與事實(shí)進(jìn)行匹配 ， 控制并利用知識(shí)進(jìn)行推理并求解問題 通常從選擇規(guī)則到執(zhí)行操作分 3步： 匹配 、 沖突消解 和 操作 —— 由匹配器負(fù)責(zé)判斷規(guī)則 條件是否成立 ， 沖突消解器負(fù)責(zé) 選擇可調(diào)用的規(guī)則 ， 解釋器負(fù)責(zé) 執(zhí)行規(guī)則的動(dòng)作 ， 并在滿足結(jié)束條件時(shí) 終止 產(chǎn)生式系統(tǒng)的運(yùn)行 。 如果兩者完全匹配 ，則把這條規(guī)則稱為 觸發(fā)規(guī)則 。 被觸發(fā)的規(guī)則不一定總是啟用規(guī)則 ， 因?yàn)榭赡芡瑫r(shí)有幾條規(guī)則的條件部分被滿足 ， 需解決沖突步驟中來解決 。然后 ， 其它的規(guī)則有可能被使用 ， 即進(jìn)入下一循環(huán) 2022/2/9 21 第二章 知識(shí)表達(dá)技術(shù) 2． 5 產(chǎn)生式系統(tǒng) 如：設(shè)有以下兩條美式足球的規(guī)則： 規(guī)則 R1 規(guī)則 R2 IF fourth dawn IF fourth dawn short yardage short yardage THEN punt within 30 yards(from the goal line) THEN field goal R1規(guī)則 ：如進(jìn)攻方在前三次進(jìn)攻中前進(jìn)的距離少于 10碼 (short yardage)，那么在第四次進(jìn)攻時(shí) (fourth dawn)， 可以踢懸空球 (punt) R2規(guī)則 ：如進(jìn)攻方在前三次進(jìn)攻中前進(jìn)的距離少于 10碼 ， 而進(jìn)攻的位置又在離對(duì)方球門線 30碼距離之內(nèi) ， 那么就可以射門 (field goal) 如果當(dāng)前事實(shí)庫包含事實(shí) “ fourth dawn”和 “ short yardage”以及 “ within 30 yards”？？？ 2022/2/9 22 第二章 知識(shí)表達(dá)技術(shù) 2． 5 產(chǎn)生式系統(tǒng) 專一性排序 —— 如某一規(guī)則條件部分規(guī)定的情況 ， 比另一規(guī)則條件部分規(guī)定的情況更有針對(duì)性 ， 則這條規(guī)則有較高的優(yōu)先級(jí) 規(guī)則排序 —— 如規(guī)則編排的順序就表示了啟用的優(yōu)先級(jí) ， 則稱之為規(guī)則排序 數(shù)據(jù)排序 —— 把規(guī)則條件部分的所有條件按優(yōu)先級(jí)次序編排起來 ， 運(yùn)行時(shí)首先使用在條件部分包含較高優(yōu)先級(jí)數(shù)據(jù)的規(guī)則 。 這和人類的行為有相似之處 上下文限制 —— 把產(chǎn)生式規(guī)則按它們所描述的上下文分組 ， 也就是說按上下文對(duì)規(guī)則分組 。 I11是有蹄動(dòng)物的 ， 而 I13是鳥的分類 ， 無混淆 ） 規(guī)則 I14 如果 該動(dòng)物是鳥類 ， 它不能飛行 ， 它能游水 ， 它的顏色是黑色和白色 ， 那么 它是企鵝 規(guī)則 I15 如果 該動(dòng)物是鳥類 ， 它善于飛行 ， 那么 它是海燕 2022/2/9 26 第二章 知識(shí)表達(dá)技術(shù) 2． 5 產(chǎn)生式系統(tǒng) 【 例 2． 4】 動(dòng)物識(shí)別系統(tǒng) ——識(shí)別長(zhǎng)頸鹿的過程