第3章 產(chǎn)生式系統(tǒng)

1、1第3章 產(chǎn)生式系統(tǒng)2內(nèi)容提要 產(chǎn)生式系統(tǒng)的描述 推理 控制策略 兩類特殊的產(chǎn)生式系統(tǒng) 基于規(guī)則的演繹系統(tǒng)產(chǎn)生式系統(tǒng)的描述推理控制策略兩類特殊的產(chǎn)生式系統(tǒng)基于規(guī)則的演繹系統(tǒng)3產(chǎn)生式系統(tǒng)的描述 產(chǎn)生式產(chǎn)生式一種知識表示方法，常用來表示有因果關(guān)系的知識。前提 結(jié)論條件 行動 下雨地面濕燙手縮手形式:if (conditions) then (actions)4產(chǎn)生式系統(tǒng)的描述 產(chǎn)生式產(chǎn)生式1212,mna aab bb左邊表示條件右邊表示結(jié)論例如：下雨甲未打傘甲被淋濕5產(chǎn)生式系統(tǒng)的描述 產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng) 把一組產(chǎn)生式放在一起，讓它們互相配合，協(xié)同作用，一個產(chǎn)生式的結(jié)論可以供另一個產(chǎn)生式作為前提

2、使用，以這種方式求解問題的系統(tǒng)稱為產(chǎn)生式系統(tǒng)。ab, bc, cd ad？6產(chǎn)生式系統(tǒng)的描述 歷史 1943年，美國數(shù)學(xué)家post設(shè)計(jì)的產(chǎn)生式系統(tǒng)，稱為post系統(tǒng)。 目的是構(gòu)造一種形式化的計(jì)算工具。 證明它和圖靈機(jī)具有相同的計(jì)算能力。7產(chǎn)生式系統(tǒng)的描述 產(chǎn)生式系統(tǒng)的構(gòu)成 一組產(chǎn)生式規(guī)則(set of rules) 綜合數(shù)據(jù)庫(global database) 控制機(jī)制(control system)產(chǎn)生式產(chǎn)生式系統(tǒng)系統(tǒng)規(guī)則規(guī)則控制控制機(jī)制機(jī)制數(shù)據(jù)數(shù)據(jù)庫庫8產(chǎn)生式系統(tǒng)的描述 產(chǎn)生式規(guī)則 例子下雨地面濕下雨甲未打傘甲被淋濕 所有人會死甲是人甲會死產(chǎn)生式產(chǎn)生式系統(tǒng)系統(tǒng)規(guī)則規(guī)則控制控制機(jī)制機(jī)制數(shù)據(jù)數(shù)

3、據(jù)庫庫9產(chǎn)生式系統(tǒng)的描述 綜合數(shù)據(jù)庫 存放已知的事實(shí)和推導(dǎo)出的事實(shí); 數(shù)據(jù)基(global database); 和database（數(shù)據(jù)庫）不同: database: 強(qiáng)調(diào)數(shù)據(jù)的管理（存取、增、刪、改等） 產(chǎn)生式系統(tǒng): 抽象的概念 只是說明數(shù)據(jù)在此存放，和物理實(shí)現(xiàn)沒關(guān)系。 具體實(shí)現(xiàn)時，用dbms和文件等都可以。 數(shù)據(jù)是廣義的，可以是常量、變量、謂詞、圖像等。 數(shù)據(jù)結(jié)構(gòu): 符號串、向量、集合、數(shù)組、樹、表格、文件等;產(chǎn)生式產(chǎn)生式系統(tǒng)系統(tǒng)規(guī)則規(guī)則控制控制機(jī)制機(jī)制數(shù)據(jù)數(shù)據(jù)庫庫10產(chǎn)生式系統(tǒng)的描述 控制機(jī)制 控制機(jī)制完成的工作有：匹配規(guī)則條件部分；多于一條規(guī)則匹配成功時，選擇哪條規(guī)則執(zhí)行(點(diǎn)燃)；如

4、何將匹配規(guī)則的結(jié)論部分放入綜合數(shù)據(jù)庫（是直接添加到數(shù)據(jù)庫中，還是替換其中的某些東西）；決定系統(tǒng)何時終止；產(chǎn)生式產(chǎn)生式系統(tǒng)系統(tǒng)規(guī)則規(guī)則控制控制機(jī)制機(jī)制數(shù)據(jù)數(shù)據(jù)庫庫11產(chǎn)生式系統(tǒng)的描述 產(chǎn)生式系統(tǒng)的運(yùn)行過程產(chǎn)生式系統(tǒng)的運(yùn)行過程建立產(chǎn)生式規(guī)則；考察每一條產(chǎn)生式規(guī)則，如果條件部分和綜合數(shù)據(jù)庫中的數(shù)據(jù)匹配，則規(guī)則的結(jié)論放入綜合數(shù)據(jù)庫；將已知的事實(shí)放入綜合數(shù)據(jù)庫；12產(chǎn)生式系統(tǒng)的算法初始化綜合數(shù)據(jù)庫是否滿足終止條件是否有可以應(yīng)用的規(guī)則選擇一條規(guī)則作用于綜合數(shù)據(jù)庫noyesendyesno13產(chǎn)生式系統(tǒng)的描述 算法綜合數(shù)據(jù)庫產(chǎn)生式規(guī)則控制機(jī)制14產(chǎn)生式系統(tǒng)的描述 例1-八數(shù)碼游戲(eight puzzle)

5、15產(chǎn)生式系統(tǒng)的描述 游戲說明： 一個棋盤有9個方格，放了8個數(shù)（1-8）； 初始時，8個數(shù)隨機(jī)放置； 數(shù)字移動規(guī)則：空格周圍的數(shù)字可移動到空格中； 如果通過移動數(shù)字，達(dá)到一個目標(biāo)狀態(tài)，則游戲成功結(jié)束； 求一個走步序列;問題：怎樣用一個產(chǎn)生式系統(tǒng)描述并解決上述問題？16產(chǎn)生式系統(tǒng)的描述綜合數(shù)據(jù)庫：存放棋盤的狀態(tài)。 棋盤的狀態(tài)：8個數(shù)字在棋盤上的位置分布。 每走一步，狀態(tài)就會發(fā)生變化； 存放棋盤的當(dāng)前狀態(tài)；規(guī)則：規(guī)則是數(shù)字移動的方法。 空格的移動: 如果空格左邊有數(shù)字，則將左邊的數(shù)字移到空格上； 如果空格右邊有數(shù)字，則將右邊的數(shù)字移到空格上； 如果空格上邊有數(shù)字，則將上邊的數(shù)字移到空格上； 如果

6、空格下邊有數(shù)字，則將下邊的數(shù)字移到空格上； 控制機(jī)制： 用當(dāng)前數(shù)據(jù)庫與規(guī)則左半部分進(jìn)行匹配，確定可執(zhí)行的規(guī)則集； 從中選擇一條規(guī)則執(zhí)行，用規(guī)則的右半部分代替數(shù)據(jù)庫中的狀態(tài)； 如果當(dāng)前數(shù)據(jù)庫中的狀態(tài)與目標(biāo)狀態(tài)相同，則終止;17產(chǎn)生式系統(tǒng)的描述 例2 ： 問題：設(shè)字符轉(zhuǎn)換規(guī)則abcacdbcgbefde已知：a，b求：f綜合數(shù)據(jù)庫綜合數(shù)據(jù)庫x，其中x為字符規(guī)則集規(guī)則集1，if ab then c2，if ac then d3，if bc then g4，if be then f5，if d then e18產(chǎn)生式系統(tǒng)的描述v控制策略: 順序排隊(duì)初始條件a，b結(jié)束條件fx規(guī)則：1，if ab the

7、n c2，if ac then d3，if bc then g4，if be then f5，if d then e數(shù)據(jù)庫數(shù)據(jù)庫可觸發(fā)規(guī)則可觸發(fā)規(guī)則被觸發(fā)規(guī)則被觸發(fā)規(guī)則a，b(1)(1)a，b，c(2) (3)(2) a，b，c，d(3) (5)(3) a，b，c，d，g(5)(5)a，b，c，d，g，e，f(4)(4)a，b，c，d，g，e求解過程求解過程19產(chǎn)生式系統(tǒng)的描述 例3: 猴子摘香蕉問題綜合數(shù)據(jù)庫綜合數(shù)據(jù)庫（m, b, box, on, h） m：猴子的位置 b：香蕉的位置 box：箱子的位置 on=0：猴子在地板上 on=1：猴子在箱子上 h=0：猴子沒有抓到香蕉 h=1：猴子

8、抓到了香蕉初始綜合數(shù)據(jù)庫初始綜合數(shù)據(jù)庫（a, b, c, 0, 0）結(jié)束綜合數(shù)據(jù)庫結(jié)束綜合數(shù)據(jù)庫（x1, x2, x3, x4, 1）其中x1x4為變量。20產(chǎn)生式系統(tǒng)的描述 例3: 猴子摘香蕉問題 （m, b, box, on, h） 規(guī)則集r1: if (x, y, z, 0, 0) then (w, y, z, 0, 0)r2: if (x, y, x, 0, 0) then (z, y, z, 0, 0)r3: if (x, y, x, 0, 0) then (x, y, x, 1, 0)r4: if (x, x, x, 1, 0) then (x, x, x, 1, 1) 其中x,

9、y, z, w為變量21產(chǎn)生式系統(tǒng)的描述 產(chǎn)生式系統(tǒng)的特點(diǎn) 規(guī)則的表示形式固定： 規(guī)則分為左半部分和右半部分； 左半部分是條件，右半部分是結(jié)論； 知識模塊化： 知識元：通俗的說，知識元是產(chǎn)生式規(guī)則的條件中的獨(dú)立部分，ai；所有的規(guī)則或數(shù)據(jù)庫中的數(shù)據(jù)都是由知識元構(gòu)成； 1212,mna aab bb22產(chǎn)生式系統(tǒng)的描述 產(chǎn)生式系統(tǒng)的特點(diǎn)(續(xù)) 產(chǎn)生式之間的相互影響是間接的 產(chǎn)生式之間的作用通過綜合數(shù)據(jù)庫的變化完成，因此是數(shù)據(jù)驅(qū)動的； 易擴(kuò)展: 規(guī)則的添加和刪除較為自由，因?yàn)闆]有相互作用； 添加規(guī)則不能造成矛盾；ab，ab。 系統(tǒng)自動完成? 謂詞情況困難； 可解釋性23產(chǎn)生式系統(tǒng)的描述 適用領(lǐng)域

10、對某些領(lǐng)域適用，而對某些領(lǐng)域不適用; 按照知識的性質(zhì)，可將系統(tǒng)劃分為兩種 知識由許多獨(dú)立的知識元組成，彼此之間的關(guān)系不很密切；(西醫(yī)) 有一個很小的核心，其它部分由此核心推導(dǎo)出來，或彼此糾纏，形成一個整體，難以分割。(數(shù)學(xué)) 產(chǎn)生式系統(tǒng)適合于前者，不適合后者。 知識是否可以模塊化。24推理 推理(reasoning) 從某些已知事實(shí)依照推理規(guī)則推出另外一些結(jié)論的過程。 系統(tǒng)狀態(tài)的轉(zhuǎn)換; 向前推理(正向推理)： 向后推理(反向推理)： 25推理 正向推理 基本思想： 從用戶提供的初始己知事實(shí)出發(fā)，在規(guī)則集中找出當(dāng)前可適用的規(guī)則, 然后進(jìn)行推理，并將推出的新事實(shí)加入到綜合數(shù)據(jù)庫中作為下一步推理的已

11、知事實(shí), 在此之后再在知識庫中選取可適用的規(guī)則進(jìn)行推理，如此重復(fù)進(jìn)行這一過程，直到求得了所要求的解或者沒有知識可用 用綜合數(shù)據(jù)庫與規(guī)則的條件部分匹配，并用規(guī)則的結(jié)論部分修改綜合數(shù)據(jù)庫;26推理 正向推理s1s2sn規(guī)則1算法2728推理 積木世界acbacb初始狀態(tài) 目標(biāo)狀態(tài) 29推理 知識元： handempty，holding(x), ontable(x), clear(x), on(x, y) 規(guī)則: r1: pickup(x): 機(jī)械手從桌子上拿起積木x。 handempty ontable(x) clear(x) holding(x) r2: putdown(x): 機(jī)械手把拿著的積

12、木放在桌子上。 holding(x) handempty , ontable(x), clear(x) r3: unstack (x, y): 積木x在積木y上, 機(jī)械手拿起x。 handempty on(x, y) clear(x) holding(x), clear(y) r4: stack (x, y): 機(jī)械手把拿著的積木x放在積木y上。 holding(x) clear(y) handempty, on(x, y), clear(x)acb30推理 綜合數(shù)據(jù)庫 初始狀態(tài)： (handempty，ontable(a)，ontable(b), on(c, a), clear(c), cl

13、ear(b) 目標(biāo)狀態(tài)： (ontable(a)，on (b, a), on(c, b), clear(c)acbacb初始狀態(tài) 目標(biāo)狀態(tài) 31推理(handempty，ontable(a)，ontable(b), on(c, a), clear(c), clear(b) r3: unstack(c, a) handempty on(x, y) clear(x) holding(x), clear(y)(holding(c)，ontable(a)，ontable(b), clear(b), clear(a)acbacb32推理(holding(c)，ontable(a)，ontable(b),

14、 clear(b), clear(a) r2: putdown(c) holding(x) handempty , ontable(x), clear(x)(handempty，ontable(a)，ontable(b), ontable(c), clear(a), clear(b), clear(c) acbacb33推理(handempty，ontable(a)，ontable(b), ontable(c), clear(a), clear(b), clear(c) r1: pickup(b) handempty ontable(x) clear(x) holding(x) (holdin

15、g(b), ontable(a)，ontable(c), clear(a), clear(c) acbacb34推理(holding(b), ontable(a)，ontable(c), clear(a), clear(c) r4: stack(b, a) holding(x) clear(y) handempty, on(x, y), clear(x)(handempty, ontable(a)，ontable(c), on(b, a), clear(b), clear(c)acbacb35推理(handempty, ontable(a)，ontable(c), on(b, a), clea

16、r(b), clear(c)r1: pickup(c) handempty ontable(x) clear(x) holding(x) (holding(b), ontable(a)，ontable(c), on(b, a), clear(b)acbabc36推理(holding(c), ontable(a)，on(b, a), clear(b) r4: stack(c, b) holding(x) clear(y) handempty, on(x, y), clear(x) (handempty, ontable(a)，on(b, a), on(c, b), clear(c)acbabc3

17、7推理 例：動物世界 規(guī)則: r1：動物有毛 哺乳類 r2：動物產(chǎn)奶 哺乳類 r3：哺乳類 吃肉 食肉類 r4：哺乳類 吃草 有蹄類 r5：食肉類 黃褐色 有斑點(diǎn) 獵狗 r6：食肉類 黃褐色 黑條紋 虎 r7：有蹄類 長脖 長頸鹿 r8：有蹄類 黑條紋 斑馬 38推理 例：動物世界 規(guī)則集的樹表示andandor斑馬虎獵狗食肉類有蹄類哺乳類有毛產(chǎn)奶吃草吃肉黃褐色有斑點(diǎn)黑條紋長脖黑條紋長頸鹿規(guī)則規(guī)則:r1：動物有毛 哺乳類 r2：動物產(chǎn)奶 哺乳類 r3：哺乳類 吃肉 食肉類 r4：哺乳類 吃草 有蹄類 r5：食肉類 黃褐色 有斑點(diǎn) 獵狗 r6：食肉類 黃褐色 黑條紋 虎 r7：有蹄類 長脖 長頸

18、鹿 r8：有蹄類 黑條紋 斑馬 39推理 例：動物世界 問題： 觀察到一種動物是有毛，吃草，黑條紋，問是不是斑馬？ 推理過程： 尋找結(jié)論是斑馬的規(guī)則，看它的條件部分是否可以被當(dāng)前綜合數(shù)據(jù)庫滿足。如果是，則結(jié)束；否則，看哪些條規(guī)則能推出這些條件（規(guī)則的結(jié)論與這些條件匹配）。重復(fù)這個過程。 40推理 例：動物世界 問題： 觀察到一種動物是有毛，吃草，黑條紋，問是不是斑馬？ 具體推理過程 有毛，吃草，黑條紋 r1：動物有毛 哺乳類 r2：動物產(chǎn)奶 哺乳類 r3：哺乳類 吃肉 食肉類 r4：哺乳類 吃草 有蹄類 r5：食肉類 黃褐色 有斑點(diǎn) 獵狗 r6：食肉類 黃褐色 黑條紋 虎 r7：有蹄類 長脖

19、長頸鹿 r8：有蹄類 黑條紋 斑馬41推理 例：動物世界 問題： 觀察到一種動物是有毛，吃草，黑條紋，問是不是斑馬？ 具體推理過程 有毛，吃草，黑條紋 r1：動物有毛 哺乳類 r2：動物產(chǎn)奶 哺乳類 r3：哺乳類 吃肉 食肉類 r4：哺乳類 吃草 有蹄類 r5：食肉類 黃褐色 有斑點(diǎn) 獵狗 r6：食肉類 黃褐色 黑條紋 虎 r7：有蹄類 長脖 長頸鹿 r8：有蹄類 黑條紋 斑馬42推理 例：動物世界 問題： 觀察到一種動物是有毛，吃草，黑條紋，問是不是斑馬？ 具體推理過程 有毛，吃草，黑條紋 r1：動物有毛 哺乳類 r2：動物產(chǎn)奶 哺乳類 r3：哺乳類 吃肉 食肉類 r4：哺乳類 吃草 有蹄類

20、 r5：食肉類 黃褐色 有斑點(diǎn) 獵狗 r6：食肉類 黃褐色 黑條紋 虎 r7：有蹄類 長脖 長頸鹿 r8：有蹄類 黑條紋 斑馬43推理 反向推理反向推理 基本思想： 首先選定個假設(shè)目標(biāo)，然后尋找支持該假設(shè)的證據(jù)， 若所需的證據(jù)都能找到，則說明原假設(shè)是成立的； 若無論如何都找不到所需要的證據(jù)，說明原假設(shè)不成立，此時需要另作新的假設(shè)。44推理 反向推理s1s2sn規(guī)則145推理 反向推理46推理 反向推理的特點(diǎn) 優(yōu)點(diǎn): 不必使用與目標(biāo)無關(guān)的知識，目的性強(qiáng)， 有利于向用戶提供解釋。 缺點(diǎn): 初始目標(biāo)的選擇有盲目性，若不符合實(shí)際，就要多次提出假設(shè)，影響到系統(tǒng)的效率。47推理 反向推理的特點(diǎn) 注意 向前

21、推理是從事實(shí)到目標(biāo)的推理，稱為數(shù)據(jù)驅(qū)動的推理; 向后推理是從假設(shè)目標(biāo)為真，再用事實(shí)證明這個目標(biāo)為真，稱為目標(biāo)驅(qū)動的推理; 向前推理還是向后推理，由問題決定: 向前推理: 機(jī)器人規(guī)劃，程序自動設(shè)計(jì)； 向后推理: 診斷問題。 一起使用;48推理 混合推理 正向推理 具有盲目、效率低等缺點(diǎn)，可能推出許多與問題求解無關(guān)的子目標(biāo); 逆向推理 若提出的假設(shè)目標(biāo)不合適，也會降低系統(tǒng)的效率。 正向推理 +逆向推理? 混合推理1. robin (x)bird (x)2. robin (x)small (x)3. robin (x)red breast (x)4. bird (x) animal (x)5. bi

22、rd (x)has wings (x)6. redbreast (x)colourful (x)7. redbreast (x) attractive (x)8. small (x) not large (x)9. small (x) not medium(x) robin (tweety） ? attractive (tweety)推理50控制策略 選取規(guī)則的原則稱為控制策略; 不可撤回的控制策略： 在任意時刻，如果從被激勵的規(guī)則集中選擇點(diǎn)燃的規(guī)則都是合適的，即，使用這條規(guī)則所求的解，一定在全局解的路徑上。 特點(diǎn)：局部解與全局解是一致的。51控制策略 試探性控制策略 使用某條規(guī)則時, 必須為

23、以后應(yīng)用另一條規(guī)則做好準(zhǔn)備; 回溯型: 特點(diǎn)：每個被放棄的狀態(tài)，可以保證不在解路上。 n1n0n2 n3 n4 n5 x=1y=1 x+y=352控制策略 圖搜索 任一個暫時放棄的狀態(tài)，將來都可能被重新使用;n1n0n2 n3 n4 53控制策略 注意： 效率最高: 不可撤回的控制策略 效率最低: 圖搜索54控制策略 沖突刪除策略 規(guī)則的狀態(tài): 激勵：如果某規(guī)則的全部條件與綜合數(shù)據(jù)庫匹配，此規(guī)則處于激勵狀態(tài)。 點(diǎn)燃：根據(jù)策略從激勵的規(guī)則中選取一個執(zhí)行，稱此規(guī)則被點(diǎn)燃。 55控制策略 當(dāng)激勵的規(guī)則多于一條時，選擇哪條點(diǎn)燃，策略有兩種： 領(lǐng)域相關(guān): 啟發(fā)式知識 領(lǐng)域無關(guān): 沖突刪除策略(并不是嚴(yán)格

24、領(lǐng)域無關(guān))56控制策略 重要性排序 新舊排序 匹配程度排序 數(shù)據(jù)排序 特殊排序 57控制策略 重要性排序 產(chǎn)生式規(guī)則事先按照重要性排序; 當(dāng)多條規(guī)則被激勵時，選擇最重要的規(guī)則點(diǎn)燃。 58控制策略 新舊排序 如果規(guī)則的獲取時間不同，新得到的知識比舊知識更先點(diǎn)燃。 匹配程度排序 非確定性匹配中，如果有加權(quán)的情況，按照規(guī)則的權(quán)值大小排序。 數(shù)據(jù)排序 重要性排序： 對知識元事先按重要性排序。 被激勵的規(guī)則的條件部分第一個文字在綜合數(shù)據(jù)庫中的重要性，決定點(diǎn)燃的規(guī)則。 例：a，b，c，d，e r1：ade r2：bc 先執(zhí)行r1. 新舊排序：新進(jìn)入綜合數(shù)據(jù)庫的數(shù)據(jù)優(yōu)先級高。 59控制策略 特殊排序 更特殊

25、的規(guī)則先執(zhí)行。 尺寸排序：條件多的先執(zhí)行。 r1：abc r2：de 先執(zhí)行r1. 包含排序: 兩個規(guī)則的條件部分，一個是另一個的子集，執(zhí)行全集的那條(尺寸排序的特例) r1：abc r2：ab 先執(zhí)行r1.60控制策略 有時是矛盾的; 例如尺寸排序和數(shù)據(jù)排序; 論域知識很重要;61兩類特殊的產(chǎn)生式系統(tǒng) 可交換產(chǎn)生式系統(tǒng) 可分解產(chǎn)生式系統(tǒng)62兩類特殊的產(chǎn)生式系統(tǒng) 可交換產(chǎn)生式系統(tǒng) 使用規(guī)則的次序不影響產(chǎn)生的結(jié)果; 例子： r1r2r3 r1r3r2 r2r1r3 r2r3r1 r3r1r2 r3r2r163兩類特殊的產(chǎn)生式系統(tǒng) 可交換產(chǎn)生式系統(tǒng) r1s0s11s12s13s3s2s1sgr2r

26、3r2r3r1r3r1r2r2r3r1r1r2r3r1r2r1r3r2r3r1r3r264兩類特殊的產(chǎn)生式系統(tǒng) 可交換產(chǎn)生式系統(tǒng) 如果一個產(chǎn)生式系統(tǒng)對任意數(shù)據(jù)庫都滿足如下條件，則稱這個產(chǎn)生式系統(tǒng)是可交換的: 令r是可作用于數(shù)據(jù)庫d的規(guī)則集，ri r，作用于d產(chǎn)生d，則r中的任一條規(guī)則均可作用于d。 如果d滿足目標(biāo)條件，那么可作用于d上的任一條規(guī)則，作用于d后產(chǎn)生d，也滿足目標(biāo)條件。 令r是可作用于數(shù)據(jù)庫d的規(guī)則集，對數(shù)據(jù)庫d來說，使用規(guī)則ri r的順序不影響從d 到d。65兩類特殊的產(chǎn)生式系統(tǒng) 可交換產(chǎn)生式系統(tǒng) 特點(diǎn) 可交換產(chǎn)生式系統(tǒng)可以采用不可撤回的搜索策略; 但相反不成立。 效率高; 純粹

27、的可交換產(chǎn)生式系統(tǒng)一般不存在，但一個系統(tǒng)的局部可能滿足這個條件; 66兩類特殊的產(chǎn)生式系統(tǒng) 可分解產(chǎn)生式系統(tǒng) 如果一個系統(tǒng)可將其數(shù)據(jù)庫分為幾個子數(shù)據(jù)庫，并通過規(guī)則作用于子數(shù)據(jù)庫，而達(dá)到目標(biāo)，這個系統(tǒng)稱為可分解產(chǎn)生式系統(tǒng)。全局?jǐn)?shù)據(jù)庫全局?jǐn)?shù)據(jù)庫子數(shù)據(jù)庫子數(shù)據(jù)庫1子數(shù)據(jù)庫子數(shù)據(jù)庫2子數(shù)據(jù)庫子數(shù)據(jù)庫3規(guī)則集合規(guī)則集合67兩類特殊的產(chǎn)生式系統(tǒng) 可分解產(chǎn)生式系統(tǒng) 例子: 初始數(shù)據(jù)庫：（c, b, z） 目標(biāo)數(shù)據(jù)庫：（m, m,m） 規(guī)則： r1: c (d, l) r2: c (b, m) r3: b (m, m) r4: z (b, b, m)c( b , m)bmr2(m, m)br3(m, m)r3

28、z(b,b,m)bmr4(m, m)r3(m, m)r3b(c, b, z)68兩類特殊的產(chǎn)生式系統(tǒng) 可分解產(chǎn)生式系統(tǒng) split算法： 1data初始數(shù)據(jù)庫； 2didata的分解表示。每個di為一個子數(shù)據(jù)庫； 3直到所有di滿足結(jié)束條件。 3.1 從di中選擇不滿足結(jié)束條件的數(shù)據(jù)庫d*; 3.2 從di中刪除d*; 3.3 選擇一條可作用于d*的規(guī)則r; 3.4 dr作用于d*所產(chǎn)生的結(jié)果; 3.5 did的分解表示; 3.6 將di加入di中;69兩類特殊的產(chǎn)生式系統(tǒng) 可分解產(chǎn)生式系統(tǒng) split算法：規(guī)則： r1: c (d, l)r2: c (b, m)r3: b (m, m)r4:

29、 z (b, b, m)70兩類特殊的產(chǎn)生式系統(tǒng) 可分解產(chǎn)生式系統(tǒng) 注意： 關(guān)鍵在于如何用控制策略選擇規(guī)則; 如果一個問題使用這個算法，可以終止，則這個問題是可分解的，否則是不可分解的； 具體來說，數(shù)據(jù)庫如何分解，是領(lǐng)域相關(guān)的。 分解的一個好處是可用分布式系統(tǒng)求解。71兩類特殊的產(chǎn)生式系統(tǒng) 應(yīng)用 slagle, 1963, 符號積分程序saint 產(chǎn)生式求解系統(tǒng) 輸入: 不定積分題目 輸出: 積分結(jié)果 例子: xsin3xdx 1/9(sin3x) 1/3(xcos3x) 軟件： mathematica, maple, matlabjames robert slagle 72兩類特殊的產(chǎn)生式系

30、統(tǒng) 應(yīng)用 產(chǎn)生式規(guī)則集: 分部積分規(guī)則: udv udv - vdu 和式分解規(guī)則: (f(x)+g(x)dx f(x)dx + g(x)dx 因子規(guī)則: kf(x)dx kf(x)dx 相除化簡變換: z4/(z2+1)dz (z2-1+ 1/(z2+1)dz73兩類特殊的產(chǎn)生式系統(tǒng) 應(yīng)用 由于任意一個含有積分和式的表達(dá)式均可分解為若干個單獨(dú)的積分式，每一個積分式又可單獨(dú)進(jìn)行求解，因此可以看成是一個可分解產(chǎn)生式系統(tǒng). 74兩類特殊的產(chǎn)生式系統(tǒng) 應(yīng)用75兩類特殊的產(chǎn)生式系統(tǒng) 產(chǎn)生式系統(tǒng)的應(yīng)用產(chǎn)生式系統(tǒng)的應(yīng)用 專家系統(tǒng) 分類：診病，故障診斷 規(guī)劃：機(jī)器人規(guī)劃，自動程序設(shè)計(jì)、自動電路設(shè)計(jì)等76兩類

31、特殊的產(chǎn)生式系統(tǒng) 固定的產(chǎn)生式系統(tǒng)(fixed production system) 只能解決某些特定的問題，沒有學(xué)習(xí)的功能. 自適應(yīng)的產(chǎn)生式系統(tǒng)(adaptive production system) 是一種計(jì)算機(jī)程序，能夠在問題解決的過程中建構(gòu)新的產(chǎn)生式規(guī)則，并把這些規(guī)則加到它的“記憶”中去，從而能更加有效地解決問題。 例子: 一個學(xué)生由于遲到而沒有聽到老師的講課；但在課堂上，他看了其他的學(xué)生的解題作業(yè)；在課后的測試中，這個遲到的學(xué)生正確地完成了所有的測試題。77基于規(guī)則的演繹系統(tǒng) 歸結(jié)方法的缺點(diǎn)： 不便于閱讀與理解。 “鳥能飛”：(x)(bird(x)fly(x) 子句：bird(x)

32、fly(x) 不夠直觀，自然pqpq 78基于規(guī)則的演繹系統(tǒng) 歸結(jié)方法的缺點(diǎn)： 有可能丟失一些重要的控制信息。 (ab)c (ac)b (bc)a a(bc) b(ac) c(ab) 子句: a b c79基于規(guī)則的演繹系統(tǒng) 基于規(guī)則的演繹系統(tǒng)(與/或形演繹推理) 分類 正向演繹 反向演繹 雙向演繹80基于規(guī)則的演繹系統(tǒng) 基本定義 在謂詞邏輯中，把原子公式和原子公式的否定統(tǒng)稱為文字。 任何文字的析取式稱為子句。81基于規(guī)則的演繹系統(tǒng) 正向演繹 已知事實(shí)用不含蘊(yùn)含符號“”的與或形表示。 與或形 無量詞約束 否定符只作用于單個文字 只有“與”()、“或”() 例子: (u)(v)(q(v, u)(

33、r(v)p(v)s(u, v)=(u)(v) (q(v, u)(r(v) p(v) s(u, v)=q(v, a)(r(v) p(v) s(a, v) skolem化= q(w, a)(r(v) p(v) s(a, v)主合取元變量換名82基于規(guī)則的演繹系統(tǒng) 事實(shí)的與或樹表示例： q(w, a)(r(v) p(v) s(a, v)q(w, a)(r(v) p(v) s(a, v)q(w, a)(r(v) p(v) s(a, v)r(v) p(v) s(a, v)r(v)p(v)解圖集：q(w, a), r(v)s(a, v), p(v)s(a, v) 83基于規(guī)則的演繹系統(tǒng) 規(guī)則表示 規(guī)則的形

34、式(f規(guī)則)：l w其中，l是單文字，w是與或形，變量受全稱量詞約束 例： (x)(y)(z)p(x, y, z) (u)q(x, u) = (x)(y)(z)p(x, y, z) (u)q(x, u) （消去蘊(yùn)含符）= (x)(y)(z)p(x, y, z) (u)q(x, u) （否定符移植謂詞前）= (x)(y)(z) (u)(p(x, y, z) q(x, u) （化為前束形）= p(x, y, f(x, y) q(x, u) (略去全稱量詞）= p(x, y, f(x, y) q(x, u) 例： (l1 l2) w = l1 w 和 l2 w 84基于規(guī)則的演繹系統(tǒng) 命題邏輯 例：

35、事實(shí)：(p q) r) (s (t u)規(guī)則：s (x y) z 85基于規(guī)則的演繹系統(tǒng)(p q) r) (s (t u)(p q) r s (t u)p q r st upqtusx yzx yp q sp q t us rr t up q x zp q y zp q t ur x zr y zr t u規(guī)則的子句： s (x y) z= s（(x y) z）= s x z s y z結(jié)論：加入規(guī)則后得到的解圖，是事實(shí)與規(guī)則對應(yīng)子句的歸結(jié)式86基于規(guī)則的演繹系統(tǒng) 目標(biāo)表示和結(jié)束條件 目標(biāo)表示 化為析取式 結(jié)束條件 找到一個終止在目標(biāo)節(jié)點(diǎn)上的解圖;87基于規(guī)則的演繹系統(tǒng) 目標(biāo)表示和結(jié)束條件 例

36、： 事實(shí)：a b 規(guī)則集： a c d b e g 目標(biāo)公式： c ga babacdbegcg目標(biāo)88基于規(guī)則的演繹系統(tǒng) 謂詞邏輯的情況 事實(shí)表達(dá)式化成與或形 規(guī)則化成l w的形式，其中l(wèi)為單文字 目標(biāo)用skolem 化的對偶形式，即 消去全稱量詞，用skolem函數(shù)代替 保留存在量詞 對析取元作變量換名 例：(y)(x)(p(x, y) q(x, y) = (y)(p(f(y), y) q(f(y), y) = p(f(y1), y1) q(f(y2), y2) 換名89基于規(guī)則的演繹系統(tǒng) 謂詞邏輯的情況 例：事實(shí)：p(x, y) (q(x, a) r(b, y) 規(guī)則集： p(a, b)

37、 (s(a) x(b) q(b, a) u(a) r(b, b) v(b) 目標(biāo)：s(a) x(b) u(a) v(b)90基于規(guī)則的演繹系統(tǒng)p(x, y) (q(x, a) r(b, y)p(x, y)q(x, a) r(b, y)q(x, a) r(b, y)p(a, b)a/x,b/ys(a)x(b)q(b, a) b/xu(a) r(b, b)b/yv(b) 規(guī)則集：規(guī)則集： p(a, b) (s(a) x(b) q(b, a) u(a) r(b, b) v(b) 目標(biāo)：目標(biāo)：s(a) x(b) u(a) v(b)91基于規(guī)則的演繹系統(tǒng) 一個問題:置換是否相容?事實(shí): p(x) q(x)規(guī)則: p(a) r(a) q(b) r(b)目