人工智能系統(tǒng)的基本結(jié)構(gòu)演示文稿現(xiàn)在是1頁\一共有30頁\編輯于星期四第二章人工智能系統(tǒng)結(jié)構(gòu)

2.1產(chǎn)生式系統(tǒng)概述

2.2問題的表示

2.3控制策略分類

2.4產(chǎn)生式系統(tǒng)的類型

現(xiàn)在是2頁\一共有30頁\編輯于星期四2.1產(chǎn)生式系統(tǒng)概述產(chǎn)生式，也稱作規(guī)則，或產(chǎn)生式規(guī)則，用于描述各種知識(shí)單元間廣泛存在的因果關(guān)系，即前提和結(jié)論之間的關(guān)系。在產(chǎn)生式系統(tǒng)中，待描述系統(tǒng)的知識(shí)被分為兩部分：事實(shí)：表示已知事實(shí)，如事物、事件及其之間關(guān)系，也可以看作是無前提條件的產(chǎn)生式。產(chǎn)生式規(guī)則：前提和結(jié)論之間的關(guān)系式，表示推理過程和行為?，F(xiàn)在是3頁\一共有30頁\編輯于星期四2.1.1產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu)三個(gè)基本部分：綜合數(shù)據(jù)庫（事實(shí)庫）、規(guī)則庫（規(guī)則集）、控制器（規(guī)則解釋）。1、綜合數(shù)據(jù)庫是產(chǎn)生式系統(tǒng)使用的主要數(shù)據(jù)結(jié)構(gòu)，存儲(chǔ)有關(guān)問題狀態(tài)、性質(zhì)等事實(shí)（敘述型知識(shí)），包括推理過程中形成的中間結(jié)論，對(duì)應(yīng)問題的表示信息。2、規(guī)則庫是產(chǎn)生式規(guī)則的集合，存儲(chǔ)有關(guān)問題的狀態(tài)轉(zhuǎn)移、性質(zhì)變化等規(guī)則（過程型知識(shí)），規(guī)則形式:if條件then行動(dòng)if前提t(yī)hen結(jié)論如果某規(guī)則的前件能夠被事實(shí)庫中的事實(shí)滿足，則該規(guī)則被激活?，F(xiàn)在是4頁\一共有30頁\編輯于星期四3、控制器是規(guī)則的解釋程序或執(zhí)行程序，它規(guī)定選擇一條可用規(guī)則的原則和規(guī)則使用的方式(推理方向)，并根據(jù)綜合數(shù)據(jù)庫的信息，控制求解問題的過程（控制策略,推理引擎）。通常從選擇規(guī)則到執(zhí)行操作分三步：匹配。判斷規(guī)則的前件是否成立?可能有多條規(guī)則的前件能夠與綜合數(shù)據(jù)庫中的事實(shí)匹配!沖突解決，選擇可調(diào)用的規(guī)則。從匹配滿足的規(guī)則集中選擇一條規(guī)則。執(zhí)行規(guī)則，并在滿足結(jié)束條件時(shí)終止產(chǎn)生式系統(tǒng)的運(yùn)行。如果規(guī)則的后件是結(jié)論，把該結(jié)論加入綜合數(shù)據(jù)庫；如果規(guī)則的后件是動(dòng)作，執(zhí)行該動(dòng)作；現(xiàn)在是5頁\一共有30頁\編輯于星期四4、產(chǎn)生式系統(tǒng)的特點(diǎn)：數(shù)據(jù)、知識(shí)和控制相互獨(dú)立。知識(shí)具有相對(duì)固定的格式：均由左、右兩部分組成。知識(shí)無序性與模塊化：知識(shí)的補(bǔ)充和修改非常容易?？刂葡到y(tǒng)與問題無關(guān)。現(xiàn)在是6頁\一共有30頁\編輯于星期四2.1.2產(chǎn)生式系統(tǒng)的基本過程

基本算法如下：過程PRODUCTION1．DATA初始數(shù)據(jù)庫

2．UntilDATA滿足結(jié)束條件(匹配）之前,do:

{3．從規(guī)則集中選一條可應(yīng)用于DATA的規(guī)則R（選擇）

4．綜合數(shù)據(jù)庫

R應(yīng)用到DATA得到結(jié)果（執(zhí)行）

}上述過程是“匹配、選擇、執(zhí)行”的循環(huán)過程?，F(xiàn)在是7頁\一共有30頁\編輯于星期四2.2問題的表示用產(chǎn)生式系統(tǒng)求解問題，就是把一個(gè)問題的描述轉(zhuǎn)化成產(chǎn)生式系統(tǒng)的三個(gè)部分。其中問題的表示（即綜合數(shù)據(jù)庫和規(guī)則集的描述）對(duì)問題的求解有很大的影響。狀態(tài)空間法。所求問題的已知事實(shí)及中間結(jié)論，稱為狀態(tài)。狀態(tài)的集合及狀態(tài)間的轉(zhuǎn)移規(guī)則構(gòu)成問題的表示?；谶@種表示的問題求解稱為狀態(tài)空間法。求解過程是，通過對(duì)可能的狀態(tài)空間的搜索求得一個(gè)解。（PRODUCTION過程）問題歸約法。待求問題分解為一些較為簡單的子問題，且子問題也可以分解，所以可得到若干子問題。包含問題、子問題的集合與問題分解的規(guī)則一起構(gòu)成問題的表示。基于這種表示的問題求解稱為問題歸約法。求解過程是，通過對(duì)各個(gè)子問題解答的搜索求得原問題的解答。（SPLIT過程）現(xiàn)在是8頁\一共有30頁\編輯于星期四2.2.1狀態(tài)空間法狀態(tài)空間可用三元組（S，O，G）來描述S是狀態(tài)集合。狀態(tài)是表示某種事實(shí)的符號(hào)或數(shù)據(jù)。問題的狀態(tài)可以用任何類型的數(shù)據(jù)結(jié)構(gòu)描述。起始狀態(tài)S0是S的一個(gè)非空子集，描述問題的初始狀態(tài)。G是目標(biāo)狀態(tài)。G是S的一個(gè)非空子集，它可以是一個(gè)或多個(gè)要達(dá)到的狀態(tài)，也可以是對(duì)某些狀態(tài)性質(zhì)的描述。O是規(guī)則集合。集合中的每個(gè)元素稱作操作算子，將一個(gè)狀態(tài)轉(zhuǎn)化為另一個(gè)狀態(tài)。問題求解：從S0出發(fā)，經(jīng)過一系列操作變換達(dá)到G，即狀態(tài)空間搜索問題。狀態(tài)空間的一個(gè)解是一個(gè)有限的規(guī)則序列，即為狀態(tài)空間的一個(gè)解，解不一定唯一?，F(xiàn)在是9頁\一共有30頁\編輯于星期四2.2.2問題歸約法問題歸約法也可用一個(gè)三元組（S0，O，P）來描述S0是初始問題，即要求解的問題；P是本原問題集，其中的每一個(gè)問題是自然成立的，不需證明的；O是操作算子集，一個(gè)操作算子可把一個(gè)問題化成若干個(gè)子問題。該方法由問題出發(fā)，運(yùn)用操作算子產(chǎn)生一些子問題，對(duì)子問題再運(yùn)用操作算子產(chǎn)生子問題的子問題，一直進(jìn)行到產(chǎn)生的問題均為本原問題，則問題得解。問題歸約的最終目的是產(chǎn)生本原問題。問題歸約法是比狀態(tài)空間法更一般的問題求解方法，如果在歸約法中，每運(yùn)用一次操作算子，只產(chǎn)生一個(gè)子問題，則就是狀態(tài)空間法?，F(xiàn)在是10頁\一共有30頁\編輯于星期四2.2.3產(chǎn)生式系統(tǒng)舉例圖2-1八數(shù)碼游戲問題描述：給定一種初始布局（初始狀態(tài)）和一個(gè)目標(biāo)的布局（目標(biāo)狀態(tài)），問如何移動(dòng)將牌，實(shí)現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)變。一個(gè)合理的走步序列是問題的一個(gè)解?，F(xiàn)在是11頁\一共有30頁\編輯于星期四1．綜合數(shù)據(jù)庫：選擇一種數(shù)據(jù)結(jié)構(gòu)表示將牌布局。本例選用二維數(shù)組來表示布局較直觀，其數(shù)組元素用表示，其中且互不相等。

這樣每個(gè)具體取值矩陣就代表了一個(gè)棋局狀態(tài)。顯然，該問題有個(gè)狀態(tài)?，F(xiàn)在是12頁\一共有30頁\編輯于星期四2.規(guī)則集：移動(dòng)一塊將牌（即走一步）就使?fàn)顟B(tài)發(fā)生一次轉(zhuǎn)變。有四種走法：空格左移、空格上移、空格右移、空格下移。 記數(shù)組第i行第j列的元素為 空格所在的行、列分別記為，則 則空格左移一格、空格上移一格、空格右移一格、空格下移一格可用如下4條規(guī)則來描述：現(xiàn)在是13頁\一共有30頁\編輯于星期四規(guī)則1:（空格左移一格）

規(guī)則2:（空格上移一格）規(guī)則3:（空格右移一格）規(guī)則4:（空格下移一格）現(xiàn)在是14頁\一共有30頁\編輯于星期四3.控制策略：從規(guī)則集中選擇規(guī)則并作用于狀態(tài)的一種廣義選取函數(shù)。 確定某一策略后，可以用算法的形式給出程序。使用該策略從初始狀態(tài)出發(fā)，通過不斷尋求滿足一定條件的問題狀態(tài)，最后到達(dá)目標(biāo)狀態(tài)?，F(xiàn)在是15頁\一共有30頁\編輯于星期四2.3控制策略分類對(duì)當(dāng)前的狀態(tài)，只要某一條規(guī)則作用之后能生成合法的新狀態(tài)，那么，這條規(guī)則就是可用規(guī)則。產(chǎn)生式系統(tǒng)的運(yùn)行表現(xiàn)出一種搜索過程，在每一個(gè)循環(huán)中選一條規(guī)則試用，直到找到某一個(gè)序列能產(chǎn)生滿足結(jié)束條件的狀態(tài)為止。不同的控制策略產(chǎn)生不同的解，高效率的控制策略能夠走較少的步驟達(dá)到目標(biāo)，但需要問題求解的足夠知識(shí)?？刂撇呗苑譃閮深悾翰豢沙坊胤绞剑↖rrevocable）和試探方式（Tentative）?，F(xiàn)在是16頁\一共有30頁\編輯于星期四1）不可撤回方式：思想:利用問題給出的局部知識(shí)決定如何選取規(guī)則，已用過的規(guī)則不能撤回。優(yōu)點(diǎn)是控制簡單。例：爬山問題。登山過程中，登山人的目標(biāo)是爬上峰頂，如何一步一步地向目標(biāo)前進(jìn)就是一個(gè)策略問題。通常，人們利用高度隨位置變化的函數(shù)H(P)來引導(dǎo)爬山，這是一種不可撤回方式。現(xiàn)在是17頁\一共有30頁\編輯于星期四利用H(P)可以計(jì)算朝不同方向邁出一步后高度的變化情況。即向東：△z1=H（P0+△x）-H(P0)向西：△z2=H（P0

-△x）-H(P0)向北：△z3=H（P0+△y）-H(P0)向南：△z4=H（P0

-△y）-H(P0)

選擇△z變化最大的那一步攀登，到達(dá)新的位置P；從P開始重復(fù)這一過程，直到到達(dá)山頂。圖2-2爬山過程示意圖假設(shè)登山人當(dāng)前所處的位置為P0，如果只有四個(gè)方向可供選擇：[向東（△x）、向西（-△x）、向北（△y）、向南（-△y）]，分別記為規(guī)則1、2、3、4?，F(xiàn)在是18頁\一共有30頁\編輯于星期四

爬山算法1.開始狀態(tài)作為一個(gè)可能狀態(tài)。2.從一個(gè)可能狀態(tài)，應(yīng)用可用規(guī)則集生成所有新的可能狀態(tài)集。3.對(duì)該狀態(tài)集中每一狀態(tài)：（1）進(jìn)行狀態(tài)測(cè)試，檢查其是否為目標(biāo)：（2）如果是目標(biāo)則程序停止。（3）如果不是目標(biāo)，計(jì)算該狀態(tài)的好壞或者比較各狀態(tài)的好壞。4.取狀態(tài)集中最好狀態(tài)，作為下一個(gè)可能狀態(tài)。5.回到第2步?，F(xiàn)在是19頁\一共有30頁\編輯于星期四爬山算法缺點(diǎn)：有時(shí)到達(dá)某一狀態(tài)后，盡管它不是目標(biāo)狀態(tài)，但在測(cè)試過中又找不到比該狀態(tài)更好的狀態(tài)，如圖2-3。⑴局部極大點(diǎn)（多峰時(shí)處于非主峰）：它比周圍鄰居狀態(tài)都好，但不是目標(biāo)。⑵平頂：它與全部鄰居狀態(tài)都有同一個(gè)值。⑶山脊：如果搜索方向與山脊的走向不一致，則有可能會(huì)停留在山脊處。

所以，用不可撤回方式來求解登山問題，需要對(duì)狀態(tài)測(cè)試函數(shù)進(jìn)行選擇：這個(gè)函數(shù)應(yīng)具有單極值，且這個(gè)極值對(duì)應(yīng)目標(biāo)狀態(tài)值。圖2-3爬山法的三種可能狀態(tài)

現(xiàn)在是20頁\一共有30頁\編輯于星期四測(cè)試函數(shù)例：以8數(shù)碼為例，統(tǒng)計(jì)“不在位”將牌個(gè)數(shù)（逐一比較當(dāng)前狀態(tài)與目標(biāo)狀態(tài)對(duì)應(yīng)位置,有差異的將牌總個(gè)數(shù)），并取其負(fù)值作為狀態(tài)描述的函數(shù).-W(n)（n為測(cè)試狀態(tài)）基于該定義，下圖所示狀態(tài)的函數(shù)值為-4。顯然，目標(biāo)狀態(tài)的函數(shù)值為0。283164751234576

8現(xiàn)在是21頁\一共有30頁\編輯于星期四12384765283164751W=-4283147652W=-3上231847653W=-3上231847654W=-2左123847655W=-1下123847656W=0右283147653W=-3左832147654W=-3上832147655W=-3右813247656W=-3下813247657W=-3左138247658W=-2上138247659W=-1右1238476510W=0下圖2-4八數(shù)碼問題各狀態(tài)的爬山函數(shù)值現(xiàn)在是22頁\一共有30頁\編輯于星期四爬山法的策略執(zhí)行使新狀態(tài)的測(cè)試函數(shù)值有最大增長的規(guī)則；所有規(guī)則都不能使新狀態(tài)的測(cè)試函數(shù)值增長時(shí)，執(zhí)行使測(cè)試函數(shù)值不減少的規(guī)則；如果以上兩種規(guī)則都不存在，則過程停止?，F(xiàn)在是23頁\一共有30頁\編輯于星期四2）試探方式試探方式分為兩種：回溯方式和圖搜索方式?；厮莘绞剑簯?yīng)用規(guī)則后遇到規(guī)定的情況時(shí)，返回到最近的回溯點(diǎn)（無特殊規(guī)定時(shí)，最近的上一狀態(tài)即是回溯點(diǎn)），從那里改選另外一條可應(yīng)用規(guī)則。現(xiàn)在是24頁\一共有30頁\編輯于星期四2）試探方式對(duì)八數(shù)碼問題而言，在3種情況下應(yīng)考慮回溯：新生成的狀態(tài)在通向目標(biāo)的路徑上已經(jīng)出現(xiàn)過；從初始狀態(tài)開始，在應(yīng)用了指定數(shù)目的規(guī)則后，仍沒有找到目標(biāo)狀態(tài)；對(duì)當(dāng)前狀態(tài)，再?zèng)]有可應(yīng)用規(guī)則。假如規(guī)定的搜索深度為6層（表現(xiàn)為：應(yīng)用了第6條規(guī)則之后得到的狀態(tài)仍然不是目標(biāo)狀態(tài)），回溯策略應(yīng)用于八數(shù)碼游戲時(shí)的一部分搜索圖如圖2-5所示現(xiàn)在是25頁\一共有30頁\編輯于星期四283164751左、上、右同狀態(tài)4，回溯到上一步，到狀態(tài)5228316475上、右左283641753上、右、下上832641754右、下上832641755左、右、下右832641756左同狀態(tài)5，回溯到上一步，到狀態(tài)6832641757左834261757下用了6條規(guī)則，未找到解，回溯到上一步，到狀態(tài)6狀態(tài)6的所有規(guī)則用完，回溯到上一步，到狀態(tài)5832641756左、下右863241757左（1）（1）（2）（3）863241756左、上、右、下下（2）圖2-5利用回溯策略的部分搜索圖現(xiàn)在是26頁\一共有30頁\編輯于星期四圖搜索方式:對(duì)任一狀態(tài)，應(yīng)用其所有可應(yīng)用規(guī)則，并把狀態(tài)變化過程用圖結(jié)構(gòu)記錄下來，一直到得到解為止。圖搜索策略求解問題是一種窮舉方式。圖搜索方式下，求得一條解路徑需要搜索問題的整個(gè)求解空間。對(duì)于狀態(tài)空間較大的問題，需要利用與問題有關(guān)的知識(shí)引導(dǎo)規(guī)則的選擇，以便在較窄的空間內(nèi)找到問題的解。搜索過程中利用應(yīng)用問題相關(guān)知識(shí)對(duì)規(guī)則進(jìn)行選擇的搜索，稱為啟發(fā)式圖搜索。圖2-6八數(shù)碼游戲的部分搜索樹現(xiàn)在是27頁\一共有30頁\編輯于星期四圖2-7是5個(gè)城市旅行商問題的地圖，求從A出發(fā)經(jīng)B、C、D、E再回到A的最短路徑。問題的表示：