第6章問題求解范型.doc

《第6章問題求解范型.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、第6章問題求解范型AI的許多方面涉及問題求解。因此，研究人類的問題求解方法是AI領(lǐng)域的重要課題。在AI的研究和實踐中，總結(jié)出來一整套一般問題求解方法－－問題求解范型。下面的列表給出了AI的主要問題求解范型，但不是一個完全的表：l描述—匹配（第2章）；l目標歸約（第2章）；l約束傳播（第3章）；l搜索（第4章）；l手段－結(jié)局分析（第5章）；l產(chǎn)生－測試（第6章）；l規(guī)則系統(tǒng)（第6章）；l形式邏輯（第7章）；l遺傳算法等本章介紹兩種重要的、常用的問題求解范型：產(chǎn)生—測試和基于規(guī)則系統(tǒng)。產(chǎn)生－測試問題求解范型在很多實際系統(tǒng)中得到應用。本章我

2、們分析兩個系統(tǒng)中使用的該類問題求解范型：lDENTRAL：用于有機化學領(lǐng)域，從質(zhì)譜圖分析有機物的結(jié)構(gòu)；lACRONYM：用于圖象處理，從航空照片中辨別飛機?；谝?guī)則系統(tǒng)，又稱為產(chǎn)生式系統(tǒng)，常見于知識工程中，很多專家系統(tǒng)屬于基于規(guī)則系統(tǒng)問題求解范型。專家系統(tǒng)執(zhí)行的任務的類型可有：l綜合（Synthesis）：如，XCON組配計算機；l分析（Analysis）：如，MYCIN診斷感染疾?。籰解釋（Interpretation）：如，PROSPECTOR解釋油井日志。學習這一章的目的是，通過學習，能根據(jù)問題求解特征，選擇適宜的范型，建立問題

3、求解器。另外，在AI文獻中，經(jīng)常提及“弱方法（weakmethods）”概念。它是指弱方法：不需要對問題領(lǐng)域有深刻理解的問題求解范型。6.1產(chǎn)生和測試產(chǎn)生－測試范型的組成l產(chǎn)生器：枚舉可能的解，即產(chǎn)生假設(shè)。l測試器：評估假設(shè)，判斷是否接受產(chǎn)生的解。產(chǎn)生－測試范型的工作方式l第一種：首先產(chǎn)生所有可能的解，然后對所有的解進行測試；l第二種：產(chǎn)生器和測試器交替工作，產(chǎn)生一個解，就進行測試。終止條件有三種可能：其一，一旦發(fā)現(xiàn)一個可接受的解，系統(tǒng)終止工作；其二，一旦發(fā)現(xiàn)指定數(shù)目的解，系統(tǒng)終止工作；其三，發(fā)現(xiàn)所有的解后，系統(tǒng)終止工作。6.1.1產(chǎn)

4、生－測試系統(tǒng)在識別問題中的應用產(chǎn)生－測試范型經(jīng)常用來解決識別問題。但是，一般限制于問題的可能解答在102量級上的情況。若可能的解答太多，產(chǎn)生－測試的問題求解效率會很低。下面有兩個例子說明怎樣用產(chǎn)生－測試范型解決識別問題。例子1，識別樹。假設(shè)有一未知名的樹，希望通過查閱一本有關(guān)樹的書，來識別它。一般做法是一頁一頁地依次翻書，當發(fā)現(xiàn)書中某張圖片與要識別的樹相同時，停止翻書。一頁一頁地翻書就是產(chǎn)生過程，把圖片與樹匹配就是測試過程。例子2，開保險柜的密碼鎖。假設(shè)保險柜由6位數(shù)字組成，而你忘記了密碼。可能的做法是依次嘗試密碼的所有組合：00－0

5、0－00，00－00－01，00-00-02，…直到打開保險柜的門。生成密碼的各種組合就是產(chǎn)生過程，轉(zhuǎn)動保險柜的手柄就是測試過程。6位數(shù)字密碼的可能組合是106，打開密碼鎖的平均嘗試次數(shù)是500000。因此，用產(chǎn)生－測試方法開密碼鎖是很低效的。6.1.2產(chǎn)生器特性一個好的產(chǎn)生器應該具有下列三個特性：l產(chǎn)生器是完全的。產(chǎn)生器應有能力產(chǎn)生所有可能的解。l產(chǎn)生器是無冗余的。產(chǎn)生器不能多次提出相同的解，以免損害效率。l產(chǎn)生器具有啟發(fā)能力。產(chǎn)生器能使用可能的約束信息，限制解空間。對于一個產(chǎn)生器來說，啟發(fā)能力是非常重要的，因為在一般情況下，可能解

6、的數(shù)目非常大。用上面的例子來說明怎樣使用啟發(fā)式。在識別樹的例子中，若時間是冬季，并發(fā)現(xiàn)要識別的樹是光禿的，則翻書時會跳過常青喬本（針葉樹）部分。在開密碼鎖的例子中，若能確定密碼的組合是素數(shù)，且在00～99之間，則嘗試的可能是253=15625。6.1.3DENTRAL與產(chǎn)生--測試范型DENTRAL是使用產(chǎn)生－測試范型的典型專家系統(tǒng)。DENTRAL代表DENTRiticAlgorithm（所謂樹狀算法），是第一個專家系統(tǒng)。由斯坦福大學Feigenbaum領(lǐng)導的研究小組于1965年開始開發(fā)的，1968年基本開發(fā)成功，主要開發(fā)者是J.Le

7、derbeg。DENTRAL的知識表示產(chǎn)生器用過程語言實現(xiàn)，測試器用InterLisp語言實現(xiàn)，這是一種規(guī)則表示語言。META－DENTRA隨后，開發(fā)了META－DENTRAL，用于獲取DENTRAL所需的知識，它帶學習功能，幫助化學家確定質(zhì)譜片段（fragmentation）與子結(jié)構(gòu)特性之間的關(guān)系，即學習給定分子類的片段規(guī)則。META－DENTRAL也是用InterLisp語言實現(xiàn)的。META－DENTRAL使用示例學習方法，其過程如下：輸入：已知分子的三維結(jié)構(gòu)，及一組質(zhì)譜圖。輸出：關(guān)于分子結(jié)構(gòu)與質(zhì)譜圖的關(guān)系的規(guī)則。1.生成規(guī)則：產(chǎn)

8、生一組關(guān)于特定分子的單一分片過程的、高度特殊化的規(guī)則。2.規(guī)則一般化：用訓練實例將特殊規(guī)則一般化。3.精化規(guī)則：移去冗余或錯誤規(guī)則。有機化學家鑒別分子結(jié)構(gòu)的過程有機化學家在測試試管中生成了一種新物質(zhì)，欲知道這種物質(zhì)的化學