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

1、Artificial IntelligenceArtificial IntelligenceArtificial Intelligence第二章第二章 產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng) 1 產(chǎn)生式系統(tǒng)概述 2 問題的表示 3 控制策略分類 4 產(chǎn)生式系統(tǒng)的類型 Artificial IntelligenceArtificial IntelligenceArtificial Intelligence1 產(chǎn)生式系統(tǒng)概述 自然界中各種知識單元間存在著大量的因果關(guān)系 產(chǎn)生式（規(guī)則）：前提和結(jié)論之間的關(guān)系式 表示形式：前提結(jié)論例：1. 如果獲得學(xué)士學(xué)位就有資格考取碩士研究生 2. 如果獲得學(xué)士學(xué)位成績名列前茅德育優(yōu)

2、良就有資格推免上碩士 研究生 事實(shí)：無需前提條件，可用于表示已知的事實(shí) 表示形式：事實(shí)Artificial IntelligenceArtificial IntelligenceArtificial Intelligence1.1 產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu) 三部分：綜合數(shù)據(jù)庫、產(chǎn)生式規(guī)則、控制系統(tǒng)。1 綜合數(shù)據(jù)庫：數(shù)據(jù)結(jié)構(gòu)，問題狀態(tài)或有關(guān)事實(shí)（表示問題的信息）2 一組產(chǎn)生式規(guī)則構(gòu)成了規(guī)則庫（知識） 每一條規(guī)則形如: if 條件 then 行動(dòng) 或 if 前提 then 結(jié)論 3 控制系統(tǒng)：解釋程序或執(zhí)行程序，選擇規(guī)則的原則和規(guī)則使用的方式 (推理方向)，并根據(jù)綜合數(shù)據(jù)庫的信息，控制求解問題的過程（

3、控制策略）（推理引擎） Artificial IntelligenceArtificial IntelligenceArtificial Intelligence各組成成分的特點(diǎn) 綜合數(shù)據(jù)庫：依據(jù)推理情況內(nèi)容動(dòng)態(tài)變化。 規(guī)則：有相對固定的格式。無序性與模塊化，易補(bǔ)充和修改。 控制系統(tǒng)：如何應(yīng)用規(guī)則。與問題無關(guān)，可分匹配、沖突解決和操作三步。 Artificial IntelligenceArtificial IntelligenceArtificial Intelligence 數(shù)據(jù)、知識和控制相互獨(dú)立。 相互影響的間接性：“數(shù)據(jù)驅(qū)動(dòng)”，是通過修改數(shù)據(jù)庫來間接實(shí)現(xiàn)。 關(guān)系: 綜合數(shù)據(jù)庫是基礎(chǔ)，

4、產(chǎn)生式規(guī)則是進(jìn)行推理的依據(jù)， 控制系統(tǒng)是中樞。 重要部分: 控制系統(tǒng)用來控制和協(xié)調(diào)綜合數(shù)據(jù)庫、規(guī)則庫的運(yùn)行，包含了推理方式和控制策略，故是產(chǎn)生式系統(tǒng)的中樞。 Artificial IntelligenceArtificial IntelligenceArtificial Intelligence1.2 產(chǎn)生式系統(tǒng)的基本過程 PRODUCTION 過程 1DATA 初始數(shù)據(jù)庫 (初態(tài)) 2Until DATA 滿足結(jié)束條件之前(目標(biāo)態(tài))，do： （匹配） 3 4在規(guī)則集中，選一條可應(yīng)用于DATA的規(guī)則R （選擇） 5 DATA R 應(yīng)用到 DATA 得到的結(jié)果 （執(zhí)行） 6 上述過程是 “匹配、

5、選擇、執(zhí)行”的循環(huán)過程 Artificial IntelligenceArtificial IntelligenceArtificial Intelligence2 問題的表示 產(chǎn)生式運(yùn)用的方法：把問題的描述轉(zhuǎn)化成系統(tǒng)的三個(gè)部分 基礎(chǔ)：問題的表示（綜合數(shù)據(jù)庫和規(guī)則集） 類型：狀態(tài)空間法和問題歸約法 狀態(tài)空間法：找出所求問題的各種狀態(tài)，通過對可能的狀態(tài)空間的搜索求得一個(gè)解。（PRODUCTION過程） 問題歸約法：在解較復(fù)雜的問題時(shí)，將問題分解為一些較簡單的子問題，通過對各個(gè)子問題解答的搜索求得原問題的解答。 （SPLIT過程） Artificial IntelligenceArtificial

6、 IntelligenceArtificial Intelligence2.1 狀態(tài)空間法 三元組（S，O，G）來描述， S 狀態(tài)集合、起始狀態(tài)S0 、中間狀態(tài)Si 、目標(biāo)狀態(tài)G . O 是操作算子（規(guī)則集）. 狀態(tài)空間：所有可能的狀態(tài)集合；狀態(tài)轉(zhuǎn)換：靠規(guī)則實(shí)現(xiàn). 問題求解：從S0出發(fā)，經(jīng)過一系列操作變換，達(dá)到G，即狀態(tài)空間搜索問題。狀態(tài)空間的一個(gè)解是一個(gè)有限的規(guī)則序列： ，其中， 即為狀態(tài)空間的一個(gè)解，解不一定唯一.GSSSkOOO21021kOO,1Artificial IntelligenceArtificial IntelligenceArtificial Intelligence2.

7、2 問題歸約法 三元組（S0，O，P）來描述，S0是初始問題，即要求解的問題；P是本原問題集； O操作算子集，通過一個(gè)操作算子把一個(gè)問題化成若干個(gè)子問題 思路：由問題出發(fā)，運(yùn)用操作算子產(chǎn)生一些子問題，對子問題再運(yùn)用操作算子產(chǎn)生子問題的子問題，這樣一直進(jìn)行到產(chǎn)生的問題均為本原問題，則問題得解。 特點(diǎn)：最終目的是產(chǎn)生本原問題。 異同：更一般的問題求解方法。 ( 思考: 如果在歸約法中，每運(yùn)用一次操作算子，只產(chǎn)生一個(gè)子問題,那么. )Artificial IntelligenceArtificial IntelligenceArtificial Intelligence2.3 舉例-八數(shù)碼游戲 問題

8、描述：給定一種初始布局和一個(gè)目標(biāo)布局，問如何移動(dòng)將牌（合理的走步序列），實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)變。 綜合數(shù)據(jù)庫：表示將牌布局的一種數(shù)據(jù)結(jié)構(gòu)。選用二維數(shù)組來表示布局較直觀，其數(shù)組元素用 表示，其中 且互不相等，這樣數(shù)組的每個(gè)具體取值矩陣就代表了一個(gè)棋局狀態(tài)。 思考: 該問題有多少 個(gè)狀態(tài)? ijS8 , 1 ,0, 3,1（空）ijSjiArtificial IntelligenceArtificial IntelligenceArtificial Intelligence規(guī)則集：移動(dòng)一塊將牌（即走一步）就使?fàn)顟B(tài)發(fā)生一次轉(zhuǎn)變。四種走法：空格左移、空格上移、空格下移、空格右移。設(shè) 為數(shù)組第i

9、行第j列的數(shù)碼元素， 為空格所在的行、列數(shù)值，即 ,則 規(guī)則1: （向左移一格） 規(guī)則2: （向上移一格） 規(guī)則3: （向右移一格） 規(guī)則4: （向下移一格） ijS00, ji000jiS; 0,2)1()1(0000000jijijiSSSthenjif; 0,2000000) 1() 1(0jijijiSSStheniif; 0,2) 1() 1(0000000jijijiSSSthenjif; 0,2000000)1()1(0jijijiSSStheniifArtificial IntelligenceArtificial IntelligenceArtificial Intellig

10、ence 控制策略：是從規(guī)則集中選擇規(guī)則并作用于狀態(tài)的一種廣義選取方式，如 左、右、上、下 (優(yōu)先級別)。 確定某一策略后，就可編程序完成算法 系統(tǒng)從初始狀態(tài)出發(fā)，通過不斷尋求滿足一定條件的問題狀態(tài)，最后到達(dá)目標(biāo)狀態(tài)Artificial IntelligenceArtificial IntelligenceArtificial Intelligence3 控制策略分類 不同的控制策略能夠產(chǎn)生不同的解，高效率的控制策略能夠走較少的步驟達(dá)到目標(biāo)，但需要問題求解的足夠知識。 核心問題: 如何進(jìn)行規(guī)則的選取? 兩類：不可撤回方式和試探方式。 1）不可撤回方式： 思想: 利用問題給出的局部知識來決定如何

11、選取規(guī)則，不必考慮撤回已用過的規(guī)則 優(yōu)點(diǎn)： 控制簡單Artificial IntelligenceArtificial IntelligenceArtificial Intelligence 例、爬山問題：人們在登山過程中，目標(biāo)是爬上峰頂，如何一步一步地向目標(biāo)前進(jìn)就存在一個(gè)策略問題. 如果利用高度隨位置變化的函數(shù) H（P）來引導(dǎo)爬山，這就是一種不可撤回方式。爬山過程示意圖Artificial IntelligenceArtificial IntelligenceArtificial Intelligence 分析：假設(shè)登山人當(dāng)前所處的位置為P0 (高度為H0)，如果只存在四種走法: 向東（x）

12、、向西（-x ）、 向北（y）、向南（-y）， 這相當(dāng)于4條規(guī)則，那么這時(shí)可以用 H（P）計(jì)算不同方向邁出一步后高度的變化情況。 即相應(yīng)地求出 z1 =H（x）-H0、 z2=H（-x）-H0、z3=H（y）-H0、z4=H（-y）-H0，然后選擇 z 變化最大的那一步攀登，到達(dá)新的位置 P，然后從 P 開始重復(fù)這一過程直到到達(dá)山頂。 Artificial IntelligenceArtificial IntelligenceArtificial Intelligence 爬山算法流程：1. 開始狀態(tài)： 一個(gè)可能狀態(tài)；2. 從該狀態(tài)，試著應(yīng)用可應(yīng)用的規(guī)則集合生成所有新的可能狀態(tài)集；3. 對該狀

13、態(tài)集中每一狀態(tài)，進(jìn)行： 狀態(tài)測試，檢查是否為目標(biāo)，如果是，則停止； 計(jì)算該狀態(tài)的好壞，或者比較各狀態(tài)的好壞；4. 取狀態(tài)集中最好狀態(tài)，作為下一個(gè)可能狀態(tài)。5. 循環(huán)到第 2 步。Artificial IntelligenceArtificial IntelligenceArtificial Intelligence 爬山法的三種狀態(tài) 缺點(diǎn)：容易出現(xiàn)解的停滯，三種情況: 局部極大點(diǎn)（多峰時(shí)處于非主峰）：它比周圍鄰居狀態(tài)都好，但不是目標(biāo)。 平頂：它與全部鄰居狀態(tài)都有同一個(gè)值。 山脊：如果搜索方向與山脊的走向不一致，則有可能會(huì)停留在山脊處。 使用的限定條件：如果測試函數(shù)具有單極值，那么這個(gè)極值對應(yīng)的

14、狀態(tài)就是目標(biāo)。 Artificial IntelligenceArtificial IntelligenceArtificial Intelligence 8 數(shù)碼游戲?qū)嵗?用“不在位”將牌個(gè)數(shù) (當(dāng)前狀態(tài)與目標(biāo)狀態(tài)對應(yīng)位置逐一比較后有差異的將牌總個(gè)數(shù)) 并取其負(fù)值作為狀態(tài)描述的測試函數(shù). - W（n）（n為任一狀態(tài)） 初始狀態(tài)的函數(shù)值為 -4，目標(biāo)狀態(tài) 0。2 8 31 6 47 51 2 3457 6 8Artificial IntelligenceArtificial IntelligenceArtificial Intelligence 爬山法選取規(guī)則的方法： 1）優(yōu)先選取使用規(guī)則后

15、生成的新狀態(tài)的函數(shù)值有最大增長的規(guī)則; 2）其次選取使函數(shù)值不減少的規(guī)則; 3）若這種規(guī)則也沒有，則過程停止。 搜索過程如下圖： 有圓圈的數(shù)字為節(jié)點(diǎn)的擴(kuò)展順序號Artificial IntelligenceArtificial IntelligenceArtificial Intelligence1 2 38 47 6 52 8 31 6 47 51W=-42 8 31 47 6 52W=-3上上2 31 8 47 6 53W=-3上上 2 31 8 47 6 54W=-2左左1 2 3 8 47 6 55W=-1下下1 2 38 47 6 56W=0右右2 8 3 1 47 6 53W=-3

16、左左 8 3 2 1 47 6 54W=-3上上8 3 2 1 47 6 55W=-3右右8 1 3 2 47 6 56W=-3下下8 1 3 2 47 6 57W=-3左左 1 3 8 2 47 6 58W=-2上上1 3 8 2 47 6 59W=-1右右1 2 38 47 6 510W=0下下 八數(shù)碼問題各狀態(tài)的爬山函數(shù)值 Artificial IntelligenceArtificial IntelligenceArtificial Intelligence2）試探方式 種類：回溯方式和圖搜索方式 回溯方式：在選擇一條規(guī)則時(shí)要建立一個(gè)回溯點(diǎn)，當(dāng)計(jì)算遇到困難，不能得到一個(gè)解時(shí)，使?fàn)顟B(tài)返回

17、到原來的回溯點(diǎn)上，從那里改選另外一條可應(yīng)用的規(guī)則。 八數(shù)碼問題: 存在 3 種回溯情況（1）新生成的狀態(tài)已經(jīng)出現(xiàn)過；（2）在給定的搜索深度內(nèi)沒有找到目標(biāo)狀態(tài)；（3）當(dāng)前狀態(tài)再無可應(yīng)用的規(guī)則。 示例: 回溯策略搜索圖 (搜索深度為6層) . Artificial IntelligenceArtificial IntelligenceArtificial Intelligence2 8 31 6 47 51左上右左上右同狀態(tài)同狀態(tài)4 4，回溯到，回溯到5 522 8 31 6 4 7 5上右上右左左2 8 3 6 41 7 53上右下上右下上上 8 32 6 41 7 54右下右下上上8 32 6

18、 41 7 55左右下左右下右右 8 32 6 41 7 56左左同狀態(tài)同狀態(tài)5 5，回溯到，回溯到6 68 32 6 41 7 57左左8 3 42 6 1 7 57下下用了用了6 6條規(guī)則，未找條規(guī)則，未找到解，回溯到到解，回溯到 6 6該狀態(tài)的所有規(guī)則該狀態(tài)的所有規(guī)則用完，回溯到用完，回溯到 5 58 3 2 6 41 7 56左下左下右右8 6 3 2 41 7 57左左1）1）2）3）8 6 32 41 7 56左上右下左上右下下下2）利用回溯策略的部分搜索圖Artificial IntelligenceArtificial IntelligenceArtificial Intell

19、igence 圖搜索方式: 如果把問題求解過程用圖或樹的這種結(jié)構(gòu)來描述，即圖中的每一個(gè)節(jié)點(diǎn)代表問題的狀態(tài)，節(jié)點(diǎn)間的弧代表應(yīng)用的規(guī)則，那么問題的求解空間就可由圖來表示。 圖搜索方式就是用某種策略選擇應(yīng)用規(guī)則，并把狀態(tài)變化過程用圖結(jié)構(gòu)記錄下來，一直到得到解為止，即從圖中搜索出含有解路徑的子圖來。 示例: 對每一個(gè)狀態(tài)可應(yīng)用的所有規(guī)則都要去試，并把結(jié)果記錄下來。（窮舉方式）Artificial IntelligenceArtificial IntelligenceArtificial Intelligence 八數(shù)碼游戲的部分搜索樹 Artificial IntelligenceArtificial

20、 IntelligenceArtificial Intelligence 5個(gè)城市旅行商問題的地圖（全連圖）如圖所示， 求從A出發(fā)經(jīng)B、C、D、E再回到A的最短路徑。產(chǎn)生式系統(tǒng)求解示例：旅行商問題：一個(gè)推銷員要到幾個(gè)城市去辦理業(yè)務(wù)，城市間里程數(shù)已知，問題的提法是：從某個(gè)城市出發(fā)，每個(gè)城市只允許訪問一次，最后又回到最初出發(fā)的城市，求一條最短距離的路徑。 旅行商問題的地圖旅行商問題的地圖 Artificial IntelligenceArtificial IntelligenceArtificial Intelligence問題的產(chǎn)生式描述： 綜合數(shù)據(jù)庫：若每個(gè)城市用一個(gè)字母表示，則問題狀態(tài)可用一

21、個(gè)字母組成的表或字符串來表示，如（A）表示初始狀態(tài)，（A*A）表示目標(biāo)狀態(tài)，（A*）表示訪問兩個(gè)城市后的當(dāng)前狀態(tài)。 規(guī)則集：1）下一步走向城市A；2）下一步走向城市B；， 5）下一步走向城市E； 問題的約束：不重復(fù)走到同一城市，即在沒有轉(zhuǎn)完所有城市時(shí)，不能走向出發(fā)城市。 控制策略：每次走向離的最近的城市 (啟發(fā)信息)Artificial IntelligenceArtificial IntelligenceArtificial Intelligence初態(tài)（初態(tài)（A）B、C、D、E710613（AB）（AC） B、D、E（AD）（AE）5（ACD）B、E6107（ACDE） B（ACDEB）A

22、（ACDEBA） 目標(biāo)目標(biāo)用圖搜索生成的部分搜索樹Artificial IntelligenceArtificial IntelligenceArtificial Intelligence三種控制方式的特點(diǎn)小結(jié)： 不可撤回方式：相當(dāng)于沿著單獨(dú)的一條路向下延伸搜索下去； 回溯方式：不保留完整的搜索樹結(jié)構(gòu)，只記住當(dāng)前工作的一條路徑，回溯就是對這條路徑進(jìn)行修正； 窮舉圖搜索方式：記下完整的搜索樹 啟發(fā)式圖搜索方式: 部分搜索樹Artificial IntelligenceArtificial IntelligenceArtificial Intelligence4 產(chǎn)生式系統(tǒng)的類型 1、正向、逆向、

23、雙向產(chǎn)生式系統(tǒng) 正向：初始狀態(tài)目標(biāo)狀態(tài)，正向使用規(guī)則（Forward 規(guī)則）。 逆向：目標(biāo)狀態(tài)初始狀態(tài)，逆向使用規(guī)則（Backward 規(guī)則），產(chǎn)生子目標(biāo)狀態(tài)，反方向一步一步朝著初始狀態(tài)方向求解。 雙向：正向和逆向同時(shí)進(jìn)行，去求解問題，則稱為雙向產(chǎn)生式系統(tǒng)。F規(guī)則只適用于狀態(tài)描述部分，B規(guī)則則用于目標(biāo)描述部分。Artificial IntelligenceArtificial IntelligenceArtificial Intelligence2、可交換的產(chǎn)生式系統(tǒng) 規(guī)則集合的適用性：可應(yīng)用于D的規(guī)則集合，對用了其中任意一條規(guī)則之后所生成的任何數(shù)據(jù)庫(含新狀態(tài)) ，這個(gè)規(guī)則集合仍然適用； 目

24、標(biāo)條件的滿足性：滿足目標(biāo)條件的某個(gè)數(shù)據(jù)庫D，當(dāng)應(yīng)用任何一個(gè)可應(yīng)用于數(shù)據(jù)庫D的規(guī)則之后所生成的任何數(shù)據(jù)庫 (含新狀態(tài)) ，仍然滿足目標(biāo)條件. 規(guī)則運(yùn)用次序的無關(guān)性：若對D應(yīng)用某一規(guī)則序列之后得到一個(gè)數(shù)據(jù)庫D1 (D D1)，則當(dāng)改變D 的可應(yīng)用規(guī)則集合中的規(guī)則次序后，仍然可求得解，即求得D1與使用滿足D的可應(yīng)用規(guī)則集合中的規(guī)則次序無關(guān). Artificial IntelligenceArtificial IntelligenceArtificial Intelligence例：給定一個(gè)非零的整數(shù)集合Z=a，b，c，可通過把Z中任意一對元素的乘積作為新元素添加到Z中的辦法來擴(kuò)大該整數(shù)集，要求通過若干次操作后能夠生成出所需的整數(shù)集合來。 問題描述：綜合數(shù)據(jù)庫用集合表示，問題的初始狀態(tài)為a，b，c，目標(biāo)狀態(tài)為a，b，c，ab，bc，ca， 初始狀態(tài)可用的規(guī)則集合為： R1：將Z中第一個(gè)元素與第二個(gè)元素相乘，將生成的整數(shù) 添加到集合 R2：將Z中第二個(gè)元素與第三個(gè)元素相乘，將生成的整數(shù)添加到集合 R3：將Z中第三個(gè)元素與第一個(gè)元素相乘，將生成的整數(shù)添加到集合Artificial IntelligenceArtificial IntelligenceArtificial Intelligence整數(shù)集合生成問題的狀態(tài)