【正文】 Spring 問題求解中的搜索策略 R1 (7) R2 (10) 3 1 R2 R3 (5) R1 R4 (20) 6 9 4 2 R3 R4 R2 R3 R4 8 7 13 10 5 R4 R4 R4 11 14 12 圖 啟發(fā)式搜索 (3)啟發(fā)式搜索 假設(shè)各規(guī)則給定權(quán)重如下 :R1 :7。 R3 :5。 Technology, Nanjing University Artificial Intelligence Spring 產(chǎn)生式系統(tǒng)的基本過程 ? (1) 初始化綜合數(shù)據(jù)庫，即把欲解決問題的已知事實(shí)送入綜合數(shù)據(jù)庫中； ? (2) 檢查規(guī)則庫中是否有未使用過的規(guī)則，若無轉(zhuǎn) (7)； ? (3) 檢查規(guī)則庫的未使用規(guī)則中是否有其前提可與綜合數(shù)據(jù)庫中已知事實(shí)相匹配的規(guī)則，若有，形成當(dāng)前可用規(guī)則集；否則轉(zhuǎn) (6)； ? (4) 按照沖突消解策略，從當(dāng)前可用規(guī)則集中選擇一個規(guī)則執(zhí)行，并對該規(guī)則作上標(biāo)記。 ? 說明：從第 (3)步到第 (5)步的循環(huán)過程實(shí)際上就是一個搜索過程 48 Department of Computer Science amp。 不理想規(guī)則的應(yīng)用會降低效率，但不影響可解性。即在問題求解過程中，允許先試一試某條規(guī)則，如果以后發(fā)現(xiàn)這條規(guī)則不合適，則允許退回去，再另選一條規(guī)則來試。 圖搜索方式： 圖搜索方式是一種用圖或樹把全部求解過程記錄下來的方式。 主要區(qū)別 回溯方式抹去了所有引起失敗的試探路徑，而圖搜索方式則記住了已試過的所有路徑。 Technology, Nanjing University Artificial Intelligence Spring ? 正向推理產(chǎn)生式系統(tǒng)： 也稱數(shù)據(jù)驅(qū)動方式 ， 它是從初始狀態(tài)出發(fā) ， 朝著目標(biāo)狀態(tài)前進(jìn) ， 正向使用規(guī)則的一種推理方法 。 優(yōu)點(diǎn)：簡單明了 ， 且能求出所有解 缺點(diǎn)：執(zhí)行效率較低 ， 原因是使用規(guī)則具有一定的盲目性 。 所謂逆向使用規(guī)則 ， 是指以問題的目標(biāo)狀態(tài)作為初始綜合數(shù)據(jù)庫 ， 僅當(dāng)綜合數(shù)據(jù)庫中的事實(shí)滿足某條規(guī)則的后件時 ， 該規(guī)則才被使用 。 因此 ， 對那些目標(biāo)明確的問題 ， 使用反向推理方式是一種最佳選擇 。 Technology, Nanjing University Artificial Intelligence Spring 問題求解的方法 ? procedure generate。 while S is nonempty do begin select a rule R from S。 if the problem is solved by the application of R then indicate SUCCESS else call′generate′recursively remove R from S and undo the effect of applying R end end。 Technology, Nanjing University Artificial Intelligence Spring 假設(shè)有包含以下四條規(guī)則的產(chǎn)生式系統(tǒng) : R1 :如果 X能被 12整除則 X能被 6整除 。 R3 :如果 X能被 6整除則 X能被 2整除 。 初始數(shù)據(jù)庫 : N能被 12整除 , N能被 20整除 目標(biāo)是判斷 N是否能被 5整除。 Technology, Nanjing University Artificial Intelligence Spring 問題求解的方法 R1 R2 R2 R3 R1 R4 S6 R3 R4 R2 R3 R4 R4 S2 R4 R4 S5 S1 S3 S4 圖 數(shù)據(jù)驅(qū)動方法的搜索樹 執(zhí)行 generate過程 : R1 :如果 X能被 12整除則 X能被 6整除 。 R3 :如果 X能被 6整除則 X能被 2整除 。 N能被 12整除 , N能被 20整除 (1)S =｛ R1 ,R2 ｝ (2)S ′= ｛ R2 ,R3 ｝ (3)S′′= ｛ R3 ,R4 ｝ (4)S′′′= ｛ R4 ｝ 跟蹤求解過程得到使用規(guī)則的第一路徑是 :R1 ,R2 ,R3 ,R4 53 Department of Computer Science amp。 R2 :如果 X能被 20整除則 X能被 10整除 。 R4 :如果 X能被 10整除則 X能被 5整除 。 Technology, Nanjing University Artificial Intelligence Spring 問題求解的方法 ? function validate(X:expression): boolean。 scan the rule base to identify the set of applicable rules S which have X on the righthand side。 While (result = false) and (S is nonempty) do begin select and remove a rule R from S。 if C is true in the database then result:=true else if C is false in the database then do nothing else if validate (C) is true then result:=true end。 55 Department of Computer Science amp。 R2 :如果 X能被 20整除則 X能被 10整除 。 R4 :如果 X能被 10整除則 X能被 5整除 。 Technology, Nanjing University Artificial Intelligence Spring 問題求解的方法 在很多應(yīng)用中，條件部分是復(fù)合表達(dá)式，如：如果C1且 C2且 C3， 則 Validate必須修改以適應(yīng)這種規(guī)則，修改的方法如下： ?（ 1）將 “ if C is false in the database” 改為： “ if (C1 is false) or (C2 is false) or (C3 is false)” ?（ 2）將 “ if Validate(C) is true” 改為： “ if (Validate(C1) is true)and (Validate(C2) is true) or (Validate(C3) is true)” 57 Department of Computer Science amp。 begin repeat let user enter data into the database。 call′selecthypothesis′to select a goal statement E。 until the problem is solved end。 Technology, Nanjing University Artificial Intelligence Spring ? 設(shè)綜合數(shù)據(jù)庫的初始狀態(tài)為 {C， B， Z}，目標(biāo)狀態(tài)為 { M， M， …… ， M }，規(guī)則庫中有如下規(guī)則： r1： C→{D ， L} r2： C→{B ， M} r3： B→{M ， M} r4： Z→{B ， B， M} 解決該問題時，可先把初始綜合數(shù)據(jù)庫分為三個子庫，然后對這三個子庫分別應(yīng)用規(guī)則庫中的相應(yīng)規(guī)則進(jìn)行求解。 Technology, Nanjing University Artificial Intelligence Spring {C,B,Z} {C} {B} {Z} {D,L} {B,M} {M,M} {B,B,M} {D} {L} {B} {M} {M} {M} {B} {M} {B} {M,M} {M} {M} {M,M} {M,M} {M} {M} {M} {M} r1 r2 r3 r4 r3 r3 r3 60 Department of Computer Science amp。 它既可以向綜合數(shù)據(jù)庫中添加新的內(nèi)容，又可以從綜合數(shù)據(jù)庫中刪除或修改老的內(nèi)容。 61 Department of Computer Science amp。 模塊性：規(guī)則是規(guī)則庫中最基本的知識單元，各規(guī)則之間只能通過綜合數(shù)據(jù)庫發(fā)生聯(lián)系，而不能相互調(diào)用，從而增加了規(guī)則的模塊性。 一致性：規(guī)則庫中的所有規(guī)則都具有相同的格式，并且綜合數(shù)據(jù)庫可被所有規(guī)則訪問，因此規(guī)則庫中的規(guī)則可以統(tǒng)一處理。 Technology, Nanjing University Artificial Intelligence Spring 主要缺點(diǎn)： 效率較低：各規(guī)則之間的聯(lián)系必須以綜合數(shù)據(jù)庫為媒介。這樣的執(zhí)行方式將導(dǎo)致執(zhí)行的低效率。 產(chǎn)生式系統(tǒng)的特點(diǎn) 63 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 語義網(wǎng)絡(luò)表示法 ? 語義網(wǎng)絡(luò)的基本概念 ? 事務(wù)和概念的語義網(wǎng)絡(luò)表示 ? 情況和動作的語義網(wǎng)絡(luò)表示 ? 邏輯關(guān)系的語義網(wǎng)絡(luò)表示 ? 語義網(wǎng)絡(luò)的求解過程 ? 語義網(wǎng)絡(luò)表示法的特征 語義網(wǎng)絡(luò)是奎廉 () 1968年在研究人類聯(lián)想記憶時提出的一種心理學(xué)模型，認(rèn)為記憶是由概念間的聯(lián)系實(shí)現(xiàn)的。 1972年，西蒙在他的自然語言理解系統(tǒng)中也采用了語義網(wǎng)絡(luò)表示法。 65 Department of Computer Science amp。 ?語義網(wǎng)絡(luò)是一個有向圖，其中結(jié)點(diǎn)表示個體，而弧表示二個體間的二元關(guān)系，弧上標(biāo)記關(guān)系模型名稱，單一個體就由一結(jié)點(diǎn)表示。 Technology, Nanjing University Artificial Intelligence Spring 什么是語義網(wǎng)絡(luò) 結(jié)點(diǎn)： 實(shí)體，表示各種事物、概念、情況、屬性、狀態(tài)、事件、動作等； 弧：語義關(guān)系，表示它所連結(jié)的兩個實(shí)體之間的語義聯(lián)系，它必須帶有標(biāo)識。 Technology, Nanjing University Artificial Intelligence Spring 例如：若有語義基元（ A, R, B），其中， A、 B分別表示兩個結(jié)點(diǎn)， R表示 A與 B之間的某種語義聯(lián)系，則它所對應(yīng)的基本網(wǎng)元如下圖所示： A B R 語義網(wǎng)絡(luò)的基本概念 68 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 實(shí)例關(guān)系： ISA 體現(xiàn)的是“具體與抽象”的概念，含義為“是一個”，表示一個事物是另一個事物的一個實(shí)例。例 成員關(guān)系： AMemberof 體現(xiàn)的是“個體與集體”的關(guān)系，含義為“是一員”，表示一個事物是另一個事物的一個成員。 Technology, Nanjing University Artificial Intelligence Spring 屬性關(guān)系： 指事物和其屬性之間的關(guān)系。 Technology, Nanjing University Artificial Intelligence Spring ? Partof ：含義為“是一部分”，表示一個事物是另一個事物的一部分。 Technology, Nanjing University Artificial Intelligence Spring ? 時間關(guān)系 指不同事件在其發(fā)生時間方面的先后