人工智能2知識(shí)表示

1、目錄 第一章第一章緒論緒論 第二章第二章知識(shí)表示知識(shí)表示 第三章搜索技術(shù)第三章搜索技術(shù) 第四章推理技術(shù)第四章推理技術(shù) 第五章機(jī)器學(xué)習(xí)第五章機(jī)器學(xué)習(xí) 第六章專家系統(tǒng)第六章專家系統(tǒng) 第七章自動(dòng)規(guī)劃系統(tǒng)第七章自動(dòng)規(guī)劃系統(tǒng) 第八章第八章 自然語(yǔ)言理解自然語(yǔ)言理解 第九章第九章 智能控制智能控制 第十章第十章 人工智能程序設(shè)計(jì)人工智能程序設(shè)計(jì)2.1 知識(shí)及其表示概述1. 知識(shí)及知識(shí)表示知識(shí)及知識(shí)表示 費(fèi)根鮑姆：知識(shí)是經(jīng)過(guò)歸約、塑造、解釋和轉(zhuǎn)換的有用信費(fèi)根鮑姆：知識(shí)是經(jīng)過(guò)歸約、塑造、解釋和轉(zhuǎn)換的有用信息。息。 即知識(shí)是經(jīng)過(guò)加工的信息。即知識(shí)是經(jīng)過(guò)加工的信息。 伯恩斯坦：知識(shí)是由特定領(lǐng)域的描述、關(guān)系和過(guò)程組

2、成的。伯恩斯坦：知識(shí)是由特定領(lǐng)域的描述、關(guān)系和過(guò)程組成的。 海斯海斯-羅思：知識(shí)包括事實(shí)、信念和啟發(fā)式規(guī)則等。羅思：知識(shí)包括事實(shí)、信念和啟發(fā)式規(guī)則等。 知識(shí)庫(kù)的觀點(diǎn)：知識(shí)是某個(gè)論域中所涉及的各有關(guān)方面、狀知識(shí)庫(kù)的觀點(diǎn)：知識(shí)是某個(gè)論域中所涉及的各有關(guān)方面、狀態(tài)的一種符號(hào)表示。態(tài)的一種符號(hào)表示。 知識(shí)可從范圍、目的、有效性知識(shí)可從范圍、目的、有效性3個(gè)方面描述：范圍是由具體個(gè)方面描述：范圍是由具體到到一般一般，目的是由說(shuō)明到，目的是由說(shuō)明到指定指定，有效性是由確定到，有效性是由確定到不確定不確定。2.1 知識(shí)及其表示概述1. 知識(shí)及知識(shí)表示知識(shí)及知識(shí)表示 “為了證明為了證明AB，只需證明，只需證明

3、AB是不可滿足的是不可滿足的” 一般性、指示性、確定性一般性、指示性、確定性 “桌子有四條腿桌子有四條腿” 具體的、說(shuō)明性、不確定性具體的、說(shuō)明性、不確定性 知識(shí)表示是研究用機(jī)器表示知識(shí)的可行性、有效性的一知識(shí)表示是研究用機(jī)器表示知識(shí)的可行性、有效性的一般方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體。既考慮知識(shí)般方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體。既考慮知識(shí)的存儲(chǔ)又考慮知識(shí)的使用。的存儲(chǔ)又考慮知識(shí)的使用。 知識(shí)表示是一組描述事物的約定，以便把人類知識(shí)表示知識(shí)表示是一組描述事物的約定，以便把人類知識(shí)表示成機(jī)器能處理的數(shù)據(jù)結(jié)構(gòu)。成機(jī)器能處理的數(shù)據(jù)結(jié)構(gòu)。2.1 知識(shí)及其表示概述2. 人工智能中知識(shí)表示

4、人工智能中知識(shí)表示 四種知識(shí)四種知識(shí) 事實(shí)知識(shí)：有關(guān)問(wèn)題環(huán)境的一些事物的知識(shí)。如事物的事實(shí)知識(shí)：有關(guān)問(wèn)題環(huán)境的一些事物的知識(shí)。如事物的分類、屬性、事物間的關(guān)系、科學(xué)事實(shí)、客觀事實(shí)等。分類、屬性、事物間的關(guān)系、科學(xué)事實(shí)、客觀事實(shí)等。靜態(tài)靜態(tài) 規(guī)則知識(shí)：有關(guān)問(wèn)題中與事物的行動(dòng)、動(dòng)作相聯(lián)系的因規(guī)則知識(shí)：有關(guān)問(wèn)題中與事物的行動(dòng)、動(dòng)作相聯(lián)系的因果關(guān)系知識(shí)。果關(guān)系知識(shí)。動(dòng)態(tài)動(dòng)態(tài) 控制知識(shí)：有關(guān)問(wèn)題的求解步驟、技巧性知識(shí)。如算法控制知識(shí)：有關(guān)問(wèn)題的求解步驟、技巧性知識(shí)。如算法 元知識(shí)：有關(guān)知識(shí)的知識(shí)，是知識(shí)庫(kù)中的高級(jí)知識(shí)。如元知識(shí)：有關(guān)知識(shí)的知識(shí)，是知識(shí)庫(kù)中的高級(jí)知識(shí)。如怎樣使用規(guī)則、解釋規(guī)則、校驗(yàn)規(guī)則、解

5、釋程序結(jié)構(gòu)等。怎樣使用規(guī)則、解釋規(guī)則、校驗(yàn)規(guī)則、解釋程序結(jié)構(gòu)等。2.1 知識(shí)及其表示概述2. 人工智能中知識(shí)表示人工智能中知識(shí)表示 陳述性知識(shí)表示：是對(duì)知識(shí)和事實(shí)的一種靜止的表達(dá)方陳述性知識(shí)表示：是對(duì)知識(shí)和事實(shí)的一種靜止的表達(dá)方法，如語(yǔ)義網(wǎng)絡(luò)、框架和劇本等。是知識(shí)的一種顯式表達(dá)。法，如語(yǔ)義網(wǎng)絡(luò)、框架和劇本等。是知識(shí)的一種顯式表達(dá)。 過(guò)程式知識(shí)表示：將有關(guān)某一問(wèn)題領(lǐng)域的知識(shí)，連同如過(guò)程式知識(shí)表示：將有關(guān)某一問(wèn)題領(lǐng)域的知識(shí)，連同如何使用這些知識(shí)的方法一起隱式地表達(dá)為一個(gè)求解問(wèn)題的過(guò)何使用這些知識(shí)的方法一起隱式地表達(dá)為一個(gè)求解問(wèn)題的過(guò)程。如程序。程。如程序。2.1 知識(shí)及其表示概述3. 知識(shí)表示應(yīng)該

6、注意的問(wèn)題知識(shí)表示應(yīng)該注意的問(wèn)題 合適性：所采用的知識(shí)表示方法因該恰好適合問(wèn)題的處理和合適性：所采用的知識(shí)表示方法因該恰好適合問(wèn)題的處理和求解。求解。 高效性：求解算法對(duì)所用的知識(shí)表示方法應(yīng)該是高效的高效性：求解算法對(duì)所用的知識(shí)表示方法應(yīng)該是高效的，對(duì)知識(shí)的檢索也應(yīng)該是高效的。，對(duì)知識(shí)的檢索也應(yīng)該是高效的。 可理解性：易于為用戶理解，易于轉(zhuǎn)化為自然語(yǔ)言。可理解性：易于為用戶理解，易于轉(zhuǎn)化為自然語(yǔ)言。 無(wú)二義性：知識(shí)表示的結(jié)果應(yīng)該是唯一的。無(wú)二義性：知識(shí)表示的結(jié)果應(yīng)該是唯一的。問(wèn)問(wèn)題題建建模模機(jī)機(jī)器器處處理理自然語(yǔ)言自然語(yǔ)言自然語(yǔ)言自然語(yǔ)言知識(shí)表示知識(shí)表示知識(shí)表示知識(shí)表示待求解問(wèn)題待求解問(wèn)題問(wèn)題

7、解決方案問(wèn)題解決方案知識(shí)表示的方法知識(shí)表示的方法 狀態(tài)空間法狀態(tài)空間法 問(wèn)題歸約法問(wèn)題歸約法 謂詞邏輯法謂詞邏輯法 產(chǎn)生式表示方法產(chǎn)生式表示方法 語(yǔ)義網(wǎng)絡(luò)法語(yǔ)義網(wǎng)絡(luò)法 框架表示框架表示 面向?qū)ο蟊硎久嫦驅(qū)ο蟊硎?劇本表示劇本表示2.2 狀態(tài)空間法問(wèn)題求解：試探搜索問(wèn)題求解：試探搜索在可能的解空間內(nèi)尋找一個(gè)解在可能的解空間內(nèi)尋找一個(gè)解 1. 問(wèn)題求解技術(shù)：?jiǎn)栴}求解技術(shù)： 問(wèn)題的建模與表示問(wèn)題的建模與表示 知識(shí)表示方法知識(shí)表示方法 求解方法（算法）求解方法（算法） 試探搜索法試探搜索法2. 狀態(tài)空間法：基于解答空間的問(wèn)題表示和求解方法。狀態(tài)空間法：基于解答空間的問(wèn)題表示和求解方法。三要點(diǎn)三要點(diǎn) 狀

8、態(tài)：表示問(wèn)題解法中每一步問(wèn)題狀況的數(shù)據(jù)結(jié)構(gòu)。狀態(tài)：表示問(wèn)題解法中每一步問(wèn)題狀況的數(shù)據(jù)結(jié)構(gòu)。 算符：把問(wèn)題從一種狀態(tài)變換為另一種狀態(tài)的手段。算符：把問(wèn)題從一種狀態(tài)變換為另一種狀態(tài)的手段。 狀態(tài)空間法：以狀態(tài)與算符為基礎(chǔ)來(lái)表示問(wèn)題和求解問(wèn)題。狀態(tài)空間法：以狀態(tài)與算符為基礎(chǔ)來(lái)表示問(wèn)題和求解問(wèn)題。2.2 狀態(tài)空間法2.2.1 問(wèn)題狀態(tài)描述問(wèn)題狀態(tài)描述 1. 定義定義 狀態(tài)狀態(tài)(state):是為描述某類不同事物間的差別而引入的一組最少是為描述某類不同事物間的差別而引入的一組最少變量變量q0，q1，qn的有序集合，其矢量形式如下：的有序集合，其矢量形式如下：Q=q0,q1,qnT (2.1) 式中每個(gè)元

9、素式中每個(gè)元素qi(i=0,1，n)為集合的分量，稱為狀態(tài)變量。為集合的分量，稱為狀態(tài)變量。 算符算符(operator)：使問(wèn)題從一種狀態(tài)變化為另一種狀態(tài)的手段：使問(wèn)題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。操作符可為走步、過(guò)程、規(guī)則、數(shù)學(xué)算子、稱為操作符或算符。操作符可為走步、過(guò)程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號(hào)或邏輯符號(hào)等。運(yùn)算符號(hào)或邏輯符號(hào)等。2.2 狀態(tài)空間法2.2.1 問(wèn)題狀態(tài)描述問(wèn)題狀態(tài)描述 1. 定義定義 問(wèn)題的狀態(tài)空間問(wèn)題的狀態(tài)空間(state space)：是一個(gè)表示該問(wèn)題全部可能狀：是一個(gè)表示該問(wèn)題全部可能狀態(tài)及其關(guān)系的圖，它包含三種說(shuō)明的集合，即所有可能的問(wèn)題初態(tài)及

10、其關(guān)系的圖，它包含三種說(shuō)明的集合，即所有可能的問(wèn)題初始狀態(tài)集合始狀態(tài)集合S、操作符集合、操作符集合F以及目標(biāo)狀態(tài)集合以及目標(biāo)狀態(tài)集合G。因此，可把狀。因此，可把狀態(tài)空間記為三元狀態(tài)態(tài)空間記為三元狀態(tài)(S，F(xiàn)，G)。 2.2 狀態(tài)空間法2.2.1 問(wèn)題狀態(tài)描述問(wèn)題狀態(tài)描述 2. 狀態(tài)空間表示狀態(tài)空間表示 11 9 4 151 3127 5 8 613 2 10 141 2 3 45 6 7 89 10 11 1213 14 15十五數(shù)碼難題十五數(shù)碼難題(a) (a) 初始棋局初始棋局(b) (b) 目標(biāo)棋局目標(biāo)棋局2.2 狀態(tài)空間法2.2.1 問(wèn)題狀態(tài)描述問(wèn)題狀態(tài)描述 2. 狀態(tài)空間表示狀態(tài)空間

11、表示 11 9 4 151 3127 5 8 613 2 10 14十五數(shù)碼難題部分狀態(tài)圖十五數(shù)碼難題部分狀態(tài)圖11 9 4 1513 127 5 8 613 2 10 1411 9151 3 4 127 5 8 613 2 10 1411 9 4 151 3 127 5 8 613 2 10 1411 9 4 151 3 8 127 5613 2 10 14119 151 3 4 127 5 8 613 2 10 1411 9 151 3 4 127 5 8 613 2 10 1411 9 41 3 12 157 5 8 613 2 10 142.2 狀態(tài)空間法2.2.2 狀態(tài)圖示法狀態(tài)圖示

12、法1. 圖的基本概念圖的基本概念節(jié)點(diǎn)節(jié)點(diǎn)(node)：圖形上的匯合點(diǎn)，用來(lái)表示狀態(tài)、事件和時(shí)間：圖形上的匯合點(diǎn)，用來(lái)表示狀態(tài)、事件和時(shí)間 關(guān)系的匯合，也可用來(lái)表示通路的匯合。關(guān)系的匯合，也可用來(lái)表示通路的匯合。 弧線弧線(arc)：節(jié)點(diǎn)間的連接線。：節(jié)點(diǎn)間的連接線。 有向圖有向圖(directed graph)：一對(duì)節(jié)點(diǎn)用弧線連接起來(lái)，從一個(gè)節(jié)：一對(duì)節(jié)點(diǎn)用弧線連接起來(lái)，從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)，這種圖叫做有向圖。點(diǎn)指向另一個(gè)節(jié)點(diǎn)，這種圖叫做有向圖。 后繼節(jié)點(diǎn)后繼節(jié)點(diǎn)(descendant graph)與與父輩節(jié)點(diǎn)父輩節(jié)點(diǎn)(parent node) ：如果：如果某條弧線從節(jié)點(diǎn)某條弧線從節(jié)點(diǎn)ni指

13、向節(jié)點(diǎn)指向節(jié)點(diǎn)nj，那么節(jié)點(diǎn)，那么節(jié)點(diǎn)nj就叫做節(jié)點(diǎn)就叫做節(jié)點(diǎn)ni的后繼節(jié)的后繼節(jié)點(diǎn)，而節(jié)點(diǎn)點(diǎn)，而節(jié)點(diǎn)ni就叫做節(jié)點(diǎn)就叫做節(jié)點(diǎn)nj的父輩節(jié)點(diǎn)。的父輩節(jié)點(diǎn)。2.2 狀態(tài)空間法2.2.2 狀態(tài)圖示法狀態(tài)圖示法1. 圖的基本概念圖的基本概念 路徑路徑(path)：對(duì)于某個(gè)節(jié)點(diǎn)序列：對(duì)于某個(gè)節(jié)點(diǎn)序列(ni1,ni2,nik)，當(dāng)，當(dāng)j=2，3，k時(shí)，如果對(duì)于每一個(gè)時(shí)，如果對(duì)于每一個(gè)ni，j-1都有一個(gè)后繼節(jié)點(diǎn)都有一個(gè)后繼節(jié)點(diǎn)nij存在，那么就把這存在，那么就把這個(gè)節(jié)點(diǎn)序列叫做從節(jié)點(diǎn)個(gè)節(jié)點(diǎn)序列叫做從節(jié)點(diǎn)ni1至節(jié)點(diǎn)至節(jié)點(diǎn)nik的長(zhǎng)度為的長(zhǎng)度為k的路徑。的路徑。代價(jià)代價(jià)(cost) ：是給各弧線指定數(shù)值以

14、表示加在相應(yīng)算符上的：是給各弧線指定數(shù)值以表示加在相應(yīng)算符上的代價(jià)，用代價(jià)，用c(ni,nj)表示節(jié)點(diǎn)表示節(jié)點(diǎn)ni指向節(jié)點(diǎn)指向節(jié)點(diǎn)nj的那段弧線的代價(jià)。的那段弧線的代價(jià)。顯式表示顯式表示：各節(jié)點(diǎn)及其具有代價(jià)的弧線用一張表明確給出。：各節(jié)點(diǎn)及其具有代價(jià)的弧線用一張表明確給出。 隱式表示隱式表示：節(jié)點(diǎn)的無(wú)限集合：節(jié)點(diǎn)的無(wú)限集合si作為起始節(jié)點(diǎn)是已知的。后繼作為起始節(jié)點(diǎn)是已知的。后繼節(jié)點(diǎn)算符也是已知的，它能作用于任意節(jié)點(diǎn)以產(chǎn)生該節(jié)點(diǎn)的全部節(jié)點(diǎn)算符也是已知的，它能作用于任意節(jié)點(diǎn)以產(chǎn)生該節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)和各連接弧線的代價(jià)。后繼節(jié)點(diǎn)和各連接弧線的代價(jià)。NoImage2.2 狀態(tài)空間法2.2.2 狀態(tài)圖示

15、法狀態(tài)圖示法2. 圖的顯式與隱式表示圖的顯式與隱式表示 顯式說(shuō)明對(duì)于大型的圖是不切實(shí)際的，而對(duì)于具有無(wú)限節(jié)點(diǎn)集顯式說(shuō)明對(duì)于大型的圖是不切實(shí)際的，而對(duì)于具有無(wú)限節(jié)點(diǎn)集合的圖則是不可能的。合的圖則是不可能的。2.2 狀態(tài)空間法2.2.3 狀態(tài)空間表示舉例狀態(tài)空間表示舉例1. 產(chǎn)生式系統(tǒng)（產(chǎn)生式系統(tǒng)（production system） 一個(gè)產(chǎn)生式系統(tǒng)由下列一個(gè)產(chǎn)生式系統(tǒng)由下列3部分組成：部分組成：一個(gè)總數(shù)據(jù)庫(kù)一個(gè)總數(shù)據(jù)庫(kù)(global database)，它含有與具體任務(wù)有關(guān)的信，它含有與具體任務(wù)有關(guān)的信息。息。一套規(guī)則一套規(guī)則，它對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算。每條規(guī)則由左右兩部，它對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算。

16、每條規(guī)則由左右兩部分組成，左部鑒別規(guī)則的適用性或先決條件，右部描述規(guī)則應(yīng)用分組成，左部鑒別規(guī)則的適用性或先決條件，右部描述規(guī)則應(yīng)用時(shí)所完成的動(dòng)作。應(yīng)用規(guī)則來(lái)改變數(shù)據(jù)庫(kù)。時(shí)所完成的動(dòng)作。應(yīng)用規(guī)則來(lái)改變數(shù)據(jù)庫(kù)。一個(gè)控制策略一個(gè)控制策略，它確定應(yīng)該采用哪一條適用規(guī)則，而且當(dāng)數(shù)，它確定應(yīng)該采用哪一條適用規(guī)則，而且當(dāng)數(shù)據(jù)庫(kù)的終止條件滿足時(shí)，就停止計(jì)算。據(jù)庫(kù)的終止條件滿足時(shí)，就停止計(jì)算。2.2 狀態(tài)空間法2.2.3 狀態(tài)空間表示舉例狀態(tài)空間表示舉例2、狀態(tài)空間表示舉例、狀態(tài)空間表示舉例a c b箱子猴子與香蕉的問(wèn)題：猴子與香蕉的問(wèn)題：在一個(gè)房間內(nèi)有一在一個(gè)房間內(nèi)有一只猴子、一個(gè)箱子只猴子、一個(gè)箱子和一束香

17、蕉。香蕉和一束香蕉。香蕉掛在天花板下方，掛在天花板下方，但猴子的高度不足但猴子的高度不足以碰到它。那么猴以碰到它。那么猴子怎樣才能摘到香子怎樣才能摘到香蕉呢？蕉呢？a c b2.2 狀態(tài)空間法2.2.3 狀態(tài)空間表示舉例狀態(tài)空間表示舉例2、狀態(tài)空間表示舉例、狀態(tài)空間表示舉例用四元組（用四元組（W，x， Y ，z）表示這個(gè)問(wèn)題狀態(tài)空間，其中：）表示這個(gè)問(wèn)題狀態(tài)空間，其中： W 猴子的水平位置猴子的水平位置(a,b,c)； x 當(dāng)猴子在箱子頂上時(shí)取當(dāng)猴子在箱子頂上時(shí)取x=1；否則??；否則取x=0； Y 箱子的水平位置；箱子的水平位置； z 當(dāng)猴子摘到香蕉時(shí)取當(dāng)猴子摘到香蕉時(shí)取z=1；否則??；否則取

18、z=0。 初始狀態(tài)：初始狀態(tài)：(a,0,b,0) 目標(biāo)狀態(tài)目標(biāo)狀態(tài)：(c,1,c,1)2.2 狀態(tài)空間法2.2.3 狀態(tài)空間表示舉例狀態(tài)空間表示舉例2、狀態(tài)空間表示舉例、狀態(tài)空間表示舉例該問(wèn)題算符：該問(wèn)題算符： (1) goto(U)：猴子走到水平位置：猴子走到水平位置U； （W，0， Y ，z） （U，0， Y ，z） (2) pushbox(V)：猴子把箱子推到水平位置：猴子把箱子推到水平位置V； （W，0， W ，z） （V，0， V ，z） (3) climbbox：猴子爬上箱頂；：猴子爬上箱頂； （W，0， W ，z） （W，1， W ，z） (4) grasp：猴子摘到香蕉。：猴子

19、摘到香蕉。 （c，1， c ，0） （c，1， c ，1） 其中，其中，c是香蕉正下方的地板位置。是香蕉正下方的地板位置。 goto(U)pushbox(V)climbboxgrasp2.2 狀態(tài)空間法2.2.3 狀態(tài)空間表示舉例狀態(tài)空間表示舉例2、狀態(tài)空間表示舉例、狀態(tài)空間表示舉例求解過(guò)程求解過(guò)程 令初始狀態(tài)為令初始狀態(tài)為(a,0,b,0)。這時(shí)，。這時(shí)，goto(U)是唯一適用的操作，是唯一適用的操作，并導(dǎo)致下一狀態(tài)并導(dǎo)致下一狀態(tài)(U，0，b,0)?，F(xiàn)在有。現(xiàn)在有3個(gè)適用的操作，即個(gè)適用的操作，即goto(U)，pushbox(V)和和climbbox(若若U=b)。把所有適用的操作。把所

20、有適用的操作 繼繼續(xù)應(yīng)用于每個(gè)狀態(tài)，我們就能夠得到狀態(tài)空間圖續(xù)應(yīng)用于每個(gè)狀態(tài)，我們就能夠得到狀態(tài)空間圖該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列為：該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列為：goto(b),pushbox(c),climbbox,grasp2.2 狀態(tài)空間法2.2.3 狀態(tài)空間表示舉例狀態(tài)空間表示舉例2、狀態(tài)空間表示舉例、狀態(tài)空間表示舉例該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列為：該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列為：goto(b),pushbox(c),climbbox,grasp(a,0,b,0)(U,0,b,0)(V,0,V,0)(b,1,b,0)(c,1,c,0)(U,0,V,0)(c,

21、1,c,1)U=bU=b, climbboxV=c, climbboxgoto(U)goto(U)goto(U)goto(U)pushbox(V)graspU=V2.2 狀態(tài)空間法習(xí)題：習(xí)題： 設(shè)有設(shè)有3個(gè)傳教士和個(gè)傳教士和3個(gè)野人來(lái)到河邊，打算乘一只船從右岸個(gè)野人來(lái)到河邊，打算乘一只船從右岸渡到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人渡到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過(guò)傳教士人數(shù)，那么野人就會(huì)把傳教士吃掉。他們?cè)鯓尤藬?shù)超過(guò)傳教士人數(shù)，那么野人就會(huì)把傳教士吃掉。他們?cè)鯓硬拍苡眠@條船安全地把所有人都渡過(guò)河去？才能用這條船安全地把所有人都渡過(guò)河去？2.3 問(wèn)題歸

22、約法2.3.1 問(wèn)題歸約描述問(wèn)題歸約描述 已知問(wèn)題的描述，通過(guò)一系列變換把此問(wèn)題最終變?yōu)橐粋€(gè)已知問(wèn)題的描述，通過(guò)一系列變換把此問(wèn)題最終變?yōu)橐粋€(gè)子問(wèn)題集合；這些子問(wèn)題的解可以直接得到，從而解決了初始子問(wèn)題集合；這些子問(wèn)題的解可以直接得到，從而解決了初始問(wèn)題。問(wèn)題。該方法也就是從目標(biāo)該方法也就是從目標(biāo)(要解決的問(wèn)題要解決的問(wèn)題)出發(fā)逆向推理，建立出發(fā)逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題集合。這就是問(wèn)題歸約的實(shí)質(zhì)。平凡的本原問(wèn)題集合。這就是問(wèn)題歸約的實(shí)質(zhì)。 問(wèn)題歸約法的組成部分問(wèn)題歸約法的組成部分（1

23、）一個(gè)初始問(wèn)題描述；）一個(gè)初始問(wèn)題描述；（2）一套把問(wèn)題變換為子問(wèn)題的操作符；）一套把問(wèn)題變換為子問(wèn)題的操作符；（3）一套本原問(wèn)題描述。）一套本原問(wèn)題描述。 2.3 問(wèn)題歸約法2.3.1 問(wèn)題歸約描述問(wèn)題歸約描述梵塔難題梵塔難題問(wèn)題問(wèn)題 有有3個(gè)柱子個(gè)柱子(1，2，3)和和3個(gè)不同尺寸的圓盤(pán)個(gè)不同尺寸的圓盤(pán)(A，B，C)。在每個(gè)圓盤(pán)的中心有個(gè)孔，所以圓盤(pán)可以堆疊在柱子上。最初在每個(gè)圓盤(pán)的中心有個(gè)孔，所以圓盤(pán)可以堆疊在柱子上。最初，全部，全部3個(gè)圓盤(pán)都堆在柱子個(gè)圓盤(pán)都堆在柱子1上：最大的圓盤(pán)上：最大的圓盤(pán)C在底部，最小的在底部，最小的圓盤(pán)圓盤(pán)A在頂部。要求把所有圓盤(pán)都移到柱子在頂部。要求把所有圓

24、盤(pán)都移到柱子3上，每次只許移動(dòng)上，每次只許移動(dòng)一個(gè)，而且只能先搬動(dòng)柱子頂部的圓盤(pán)，還不許把尺寸較大的一個(gè)，而且只能先搬動(dòng)柱子頂部的圓盤(pán)，還不許把尺寸較大的圓盤(pán)堆放在尺寸較小的圓盤(pán)上。圓盤(pán)堆放在尺寸較小的圓盤(pán)上。2.3 問(wèn)題歸約法2.3.1 問(wèn)題歸約描述問(wèn)題歸約描述ABC123ABC123初始配置目標(biāo)配置如何由初始配置變換為目標(biāo)配置？2.3 問(wèn)題歸約法2.3.1 問(wèn)題歸約描述問(wèn)題歸約描述移動(dòng)移動(dòng)A、B - 2 雙圓盤(pán)問(wèn)雙圓盤(pán)問(wèn)題：可進(jìn)一步歸約題：可進(jìn)一步歸約(111)=(113)(113)=(123)(123)=(122)移動(dòng)移動(dòng)A、B - 3 雙圓盤(pán)雙圓盤(pán)問(wèn)題：可進(jìn)一步歸約問(wèn)題：可進(jìn)一步歸約(

25、322)=(321)(321)=(331)(331)=(333)移動(dòng)移動(dòng)C - 3 單圓盤(pán)單圓盤(pán)問(wèn)題：可直接求解問(wèn)題：可直接求解-本本原問(wèn)題原問(wèn)題2.3 問(wèn)題歸約法2.3.1 問(wèn)題歸約描述問(wèn)題歸約描述歸約過(guò)程歸約過(guò)程（1）移動(dòng)圓盤(pán)）移動(dòng)圓盤(pán)A和和B至柱子至柱子2的雙圓盤(pán)難題；的雙圓盤(pán)難題；（2）移動(dòng)圓盤(pán)）移動(dòng)圓盤(pán)C至柱子至柱子3的單圓盤(pán)難題；的單圓盤(pán)難題；（3）移動(dòng)圓盤(pán)）移動(dòng)圓盤(pán)A和和B至柱子至柱子3的雙圓盤(pán)難題。的雙圓盤(pán)難題。由上可以看出簡(jiǎn)化了難題每一個(gè)都比原始難題容易，所以由上可以看出簡(jiǎn)化了難題每一個(gè)都比原始難題容易，所以問(wèn)題都會(huì)變成易解的本原問(wèn)題。問(wèn)題都會(huì)變成易解的本原問(wèn)題。2.3 問(wèn)題

26、歸約法2.3.1 問(wèn)題歸約描述問(wèn)題歸約描述梵塔問(wèn)題歸約圖梵塔問(wèn)題歸約圖 29問(wèn)題歸約描述：?jiǎn)栴}歸約描述： 采用問(wèn)題歸約法采用問(wèn)題歸約法 描述與求解問(wèn)題時(shí)描述與求解問(wèn)題時(shí) 問(wèn)題歸約表示由三部分組成：?jiǎn)栴}歸約表示由三部分組成：（1）一個(gè)一個(gè)初始問(wèn)題描述初始問(wèn)題描述 如：如：（111），（），（333）（2）一套把問(wèn)題變換為子問(wèn)題的操作符一套把問(wèn)題變換為子問(wèn)題的操作符問(wèn)題歸約算符問(wèn)題歸約算符 如：移動(dòng)如：移動(dòng)A、B - 2 等等（3）一套一套本原問(wèn)題描述本原問(wèn)題描述 如：如：（122），（），（322） 本原問(wèn)題：本原問(wèn)題：是可直接求解或具有已知解答的問(wèn)題，出現(xiàn)本原問(wèn)題是可直接求解或具有已知解答的問(wèn)

27、題，出現(xiàn)本原問(wèn)題即可停止搜索。即可停止搜索。問(wèn)題歸約法的實(shí)質(zhì)問(wèn)題歸約法的實(shí)質(zhì)：從目標(biāo)（要解決的問(wèn)題）出發(fā)：從目標(biāo)（要解決的問(wèn)題）出發(fā)逆向推理逆向推理，建，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)本原問(wèn)題集合。本原問(wèn)題集合。問(wèn)題歸約的目的問(wèn)題歸約的目的：最終產(chǎn)生具有明顯解答的本原問(wèn)題。：最終產(chǎn)生具有明顯解答的本原問(wèn)題。 2.3 問(wèn)題歸約法2.3 問(wèn)題歸約法2.3.2 與或圖表示與或圖表示1. 與或圖的概念與或圖的概念用一個(gè)類似圖的結(jié)構(gòu)來(lái)表示把問(wèn)題歸約為后繼問(wèn)題的替換用一個(gè)類似圖的結(jié)構(gòu)來(lái)表示把問(wèn)題歸約為后繼問(wèn)題的替換集合，畫(huà)

28、出歸約問(wèn)題圖。集合，畫(huà)出歸約問(wèn)題圖。例如，設(shè)想問(wèn)題例如，設(shè)想問(wèn)題A需要由求解問(wèn)題需要由求解問(wèn)題B、C和和D來(lái)決定，那么可來(lái)決定，那么可以用一個(gè)與圖來(lái)表示；同樣，一個(gè)問(wèn)題以用一個(gè)與圖來(lái)表示；同樣，一個(gè)問(wèn)題A或者由求解問(wèn)題或者由求解問(wèn)題B、或、或者由求解問(wèn)題者由求解問(wèn)題C來(lái)決定，則可以用一個(gè)或圖來(lái)表示。來(lái)決定，則可以用一個(gè)或圖來(lái)表示。2.3 問(wèn)題歸約法2.3.2 與或圖表示與或圖表示2. 與或圖的有關(guān)術(shù)語(yǔ)與或圖的有關(guān)術(shù)語(yǔ)父節(jié)點(diǎn)父節(jié)點(diǎn): 是一個(gè)初始問(wèn)題或是可分解為子問(wèn)題的問(wèn)題節(jié)點(diǎn)；是一個(gè)初始問(wèn)題或是可分解為子問(wèn)題的問(wèn)題節(jié)點(diǎn)；子節(jié)點(diǎn)子節(jié)點(diǎn): 是一個(gè)初始問(wèn)題或是子問(wèn)題分解的子問(wèn)題節(jié)點(diǎn)；是一個(gè)初始問(wèn)題或是

29、子問(wèn)題分解的子問(wèn)題節(jié)點(diǎn)；或節(jié)點(diǎn)或節(jié)點(diǎn): 只要解決某個(gè)問(wèn)題就可解決其父輩問(wèn)題的節(jié)點(diǎn)集合；只要解決某個(gè)問(wèn)題就可解決其父輩問(wèn)題的節(jié)點(diǎn)集合；與節(jié)點(diǎn)與節(jié)點(diǎn): 只有解決所有子問(wèn)題，才能解決其父輩問(wèn)題的節(jié)點(diǎn)集只有解決所有子問(wèn)題，才能解決其父輩問(wèn)題的節(jié)點(diǎn)集合；合；弧線弧線: 是父輩節(jié)點(diǎn)指向子節(jié)點(diǎn)的圓弧連線；是父輩節(jié)點(diǎn)指向子節(jié)點(diǎn)的圓弧連線；終葉節(jié)點(diǎn)終葉節(jié)點(diǎn): 是對(duì)應(yīng)于原問(wèn)題的本原節(jié)點(diǎn)。是對(duì)應(yīng)于原問(wèn)題的本原節(jié)點(diǎn)。 2.3 問(wèn)題歸約法2.3.2 與或圖表示與或圖表示2. 與或圖的有關(guān)術(shù)語(yǔ)與或圖的有關(guān)術(shù)語(yǔ)ANMHBCDEFG與或圖與或圖 2.3 問(wèn)題歸約法2.3.2 與或圖表示與或圖表示3. 與或圖的有關(guān)定義與或圖的

30、有關(guān)定義可解節(jié)點(diǎn)可解節(jié)點(diǎn) 與或圖中一個(gè)可解節(jié)點(diǎn)的一般定義可以歸納如下：與或圖中一個(gè)可解節(jié)點(diǎn)的一般定義可以歸納如下：(1) 終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)(因?yàn)樗鼈兣c本原問(wèn)題相關(guān)連因?yàn)樗鼈兣c本原問(wèn)題相關(guān)連)。(2) 如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其后繼如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其后繼節(jié)點(diǎn)至少有一個(gè)是可解的時(shí)，此非終葉節(jié)點(diǎn)才是可解的。節(jié)點(diǎn)至少有一個(gè)是可解的時(shí)，此非終葉節(jié)點(diǎn)才是可解的。(3) 如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后繼如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后繼節(jié)點(diǎn)全部為可解時(shí)，此非終葉節(jié)點(diǎn)才是可解的。節(jié)點(diǎn)全部為可解時(shí)，此非終葉節(jié)點(diǎn)

31、才是可解的。2.3 問(wèn)題歸約法2.3.2 與或圖表示與或圖表示3. 與或圖的有關(guān)定義與或圖的有關(guān)定義不可解節(jié)點(diǎn)不可解節(jié)點(diǎn) 不可解節(jié)點(diǎn)的一般定義歸納于下：不可解節(jié)點(diǎn)的一般定義歸納于下：(1) 沒(méi)有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。沒(méi)有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。(2) 如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其全如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其全部后裔為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。部后裔為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。(3) 如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后裔至少有一個(gè)為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解

32、的裔至少有一個(gè)為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。2.3 問(wèn)題歸約法2.3.2 與或圖表示與或圖表示4. 與或圖構(gòu)圖規(guī)則與或圖構(gòu)圖規(guī)則(1) 與或圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一問(wèn)題或問(wèn)題集與或圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一問(wèn)題或問(wèn)題集合。圖中所含起始節(jié)點(diǎn)對(duì)應(yīng)于原始問(wèn)題。合。圖中所含起始節(jié)點(diǎn)對(duì)應(yīng)于原始問(wèn)題。(2) 對(duì)應(yīng)于本原問(wèn)題的節(jié)點(diǎn)，叫做終葉節(jié)點(diǎn)，它沒(méi)有后裔。對(duì)應(yīng)于本原問(wèn)題的節(jié)點(diǎn)，叫做終葉節(jié)點(diǎn)，它沒(méi)有后裔。(3) 對(duì)于把算符應(yīng)用于問(wèn)題對(duì)于把算符應(yīng)用于問(wèn)題A的每種可能情況，都把問(wèn)題變換為的每種可能情況，都把問(wèn)題變換為一個(gè)子問(wèn)題集合；有向弧線自一個(gè)子問(wèn)題集合；有向弧線自A指向后繼節(jié)點(diǎn)，表

33、示所求得指向后繼節(jié)點(diǎn)，表示所求得的子問(wèn)題集合。的子問(wèn)題集合。(4) 一般對(duì)于代表兩個(gè)或兩個(gè)以上子問(wèn)題集合的每個(gè)節(jié)點(diǎn)，有一般對(duì)于代表兩個(gè)或兩個(gè)以上子問(wèn)題集合的每個(gè)節(jié)點(diǎn)，有向弧線從此節(jié)點(diǎn)指向此子問(wèn)題集合中的各個(gè)節(jié)點(diǎn)。向弧線從此節(jié)點(diǎn)指向此子問(wèn)題集合中的各個(gè)節(jié)點(diǎn)。(5) 在特殊情況下，當(dāng)只有一個(gè)算符可應(yīng)用于問(wèn)題在特殊情況下，當(dāng)只有一個(gè)算符可應(yīng)用于問(wèn)題A，而且這個(gè)，而且這個(gè)算符產(chǎn)生具有一個(gè)以上子問(wèn)題的某個(gè)集合時(shí)，由上述規(guī)則算符產(chǎn)生具有一個(gè)以上子問(wèn)題的某個(gè)集合時(shí)，由上述規(guī)則3和規(guī)則和規(guī)則4所產(chǎn)生的圖可以得到簡(jiǎn)化。所產(chǎn)生的圖可以得到簡(jiǎn)化。2.3 問(wèn)題歸約法2.3.2 與或圖表示與或圖表示4. 與或圖構(gòu)圖規(guī)則

34、與或圖構(gòu)圖規(guī)則ADEF與或圖簡(jiǎn)化與或圖簡(jiǎn)化 2.4 謂詞邏輯法2.4.1 謂詞公式謂詞公式 P(x1, x2, , xn) n元元謂詞公式謂詞公式（predicate formulas）其中，其中，P為為n元謂詞，元謂詞，x1, x2, , xn為客體變量或變?cè)?。為客體變量或變?cè)?原子公式只有當(dāng)其對(duì)應(yīng)的語(yǔ)句在定義域內(nèi)為真時(shí)，才具有原子公式只有當(dāng)其對(duì)應(yīng)的語(yǔ)句在定義域內(nèi)為真時(shí)，才具有值值T(真真)；而當(dāng)其對(duì)應(yīng)的語(yǔ)句在定義域內(nèi)為假時(shí)，該原子公式；而當(dāng)其對(duì)應(yīng)的語(yǔ)句在定義域內(nèi)為假時(shí)，該原子公式才具有值才具有值F(假假)。 原子公式原子公式2.4 謂詞邏輯法 2.4 謂詞邏輯法2.4.2 謂詞演算謂詞演

35、算 1. 語(yǔ)法和語(yǔ)義語(yǔ)法和語(yǔ)義謂詞邏輯的基本組成部分是謂詞符號(hào)、變量符號(hào)、函數(shù)符號(hào)謂詞邏輯的基本組成部分是謂詞符號(hào)、變量符號(hào)、函數(shù)符號(hào)和常量符號(hào)，并用圓括弧、方括弧、花括弧和逗號(hào)隔開(kāi)，以和常量符號(hào)，并用圓括弧、方括弧、花括弧和逗號(hào)隔開(kāi)，以表示論域內(nèi)的關(guān)系。表示論域內(nèi)的關(guān)系。 原子公式是由若干謂詞符號(hào)和項(xiàng)組成的謂詞公式，是謂詞演算的基本積原子公式是由若干謂詞符號(hào)和項(xiàng)組成的謂詞公式，是謂詞演算的基本積木塊。木塊。r1r2INROOM(ROBOT, r1)INROOM(ROBOT, r2)通用形式：通用形式：INROOM(X, Y)MARRIED(mather(LI),father(LI)2.4 謂

36、詞邏輯法 2.4 謂詞邏輯法 2.4 謂詞邏輯法 2.4 謂詞邏輯法 2.4 謂詞邏輯法2.4.2 謂詞演算謂詞演算2. 連詞和量詞連詞和量詞 量化一個(gè)合適公式中的某個(gè)變量所得到的表達(dá)式也是合適量化一個(gè)合適公式中的某個(gè)變量所得到的表達(dá)式也是合適公式。如果一個(gè)合適公式中某個(gè)變量是經(jīng)過(guò)量化的，就把這公式。如果一個(gè)合適公式中某個(gè)變量是經(jīng)過(guò)量化的，就把這個(gè)變量叫做約束變量，否則就叫它為自由變量。在合適公式個(gè)變量叫做約束變量，否則就叫它為自由變量。在合適公式中，感興趣的主要是所有變量都是受約束的。這樣的合適公中，感興趣的主要是所有變量都是受約束的。這樣的合適公式叫做句子。式叫做句子。2.4 謂詞邏輯法2

37、.4.2 謂詞演算謂詞演算3. 演算演算 真值表真值表PQP=QPTTFTTFFF2.4 謂詞邏輯法2.4.2 謂詞演算謂詞演算3. 演算演算等價(jià)關(guān)系等價(jià)關(guān)系 (1) 否定之否定否定之否定(P)等價(jià)于等價(jià)于P(2) PQ等價(jià)于等價(jià)于P=Q(3) 摩根定律摩根定律(PQ)等價(jià)于等價(jià)于PQ(PQ)等價(jià)于等價(jià)于PQ2.4 謂詞邏輯法2.4.2 謂詞演算謂詞演算3. 演算演算 (4) 分配律分配律P(QR)等價(jià)于等價(jià)于(PQ)(PR)P(QR)等價(jià)于等價(jià)于(PQ)(PR)(5) 交換律交換律PQ等價(jià)于等價(jià)于QPPQ等價(jià)于等價(jià)于QP(6) 結(jié)合律結(jié)合律(PQ)R等價(jià)于等價(jià)于P(QR)(PQ)R等價(jià)于等價(jià)

38、于P(QR)2.4 謂詞邏輯法 2.4 謂詞邏輯法2.4.3 置換與合一置換與合一1. 置換置換假元推理：假元推理：由合適公式由合適公式W1和和W1=W2產(chǎn)生合適公式產(chǎn)生合適公式W2的運(yùn)的運(yùn)算。算。全稱化推理：全稱化推理：是由合適公式是由合適公式( x)W(x)產(chǎn)生合適公式產(chǎn)生合適公式W(A)，其，其中中A為任意常量符號(hào)。為任意常量符號(hào)。 2.4 謂詞邏輯法2.4.3 置換與合一置換與合一1. 置換置換 例例2.3 表達(dá)式表達(dá)式Px, f(y), B的的4個(gè)置換為個(gè)置換為 s1=z/x, w/y 出現(xiàn)出現(xiàn)x和和y的地方，分別用的地方，分別用z和和w替換替換 s2=A/y s3=q(z)/x,A

39、/y s4=c/x, A/y 用用Es來(lái)表示一個(gè)表達(dá)式來(lái)表示一個(gè)表達(dá)式E用置換用置換s所得的表達(dá)式的置換，則：所得的表達(dá)式的置換，則： Px, f(y), B s1= Pz, f(w), B Px, f(y), B s2= Pz, f(A), B Px, f(y), B s3= Pq(z), f(A), B Px, f(y), B s4= Pc, f(A), B 2.4 謂詞邏輯法2.4.3 置換與合一置換與合一1. 置換置換置換是可結(jié)合的，用置換是可結(jié)合的，用s1s2表示兩個(gè)置換表示兩個(gè)置換s1和和s2的合成。的合成。 (L s1) s2= L (s1s2) (s1 s2) s3= s1 (

40、s2 s3 ) 一般來(lái)說(shuō)，置換是不可交換的，即一般來(lái)說(shuō)，置換是不可交換的，即 s1 s2 s2 s12.4 謂詞邏輯法2.4.3 置換與合一置換與合一2. 合一合一 尋找項(xiàng)對(duì)變量的置換，以使兩表達(dá)式一致，叫做尋找項(xiàng)對(duì)變量的置換，以使兩表達(dá)式一致，叫做合一合一(unification)。 如果一個(gè)置換如果一個(gè)置換s作用于表達(dá)式集作用于表達(dá)式集Ei的每個(gè)元素，則用的每個(gè)元素，則用Eis來(lái)表示置換例的集。稱表達(dá)式集來(lái)表示置換例的集。稱表達(dá)式集Ei是是可合一的可合一的。 如果存在一個(gè)置換如果存在一個(gè)置換s使得：使得：E1s=E2s=E3s=那么稱此那么稱此s為為Ei的的合一者合一者，因?yàn)?，因?yàn)閟的作用

41、是使集合的作用是使集合Ei成為單一形式。稱表達(dá)成為單一形式。稱表達(dá)式集式集Ei是可合一的。是可合一的。 例例2.4 表達(dá)式集表達(dá)式集Px, f(y), B , Px, f(B), B 的合一者為的合一者為 s=A/x, B/y Px, f(y), Bs= Px, f(B), Bs= PA, f(B), B 最簡(jiǎn)單的合一最簡(jiǎn)單的合一 g=B/y Eis= Eigs 稱稱g為最通用（最一般）的合一者，記為最通用（最一般）的合一者，記mgu。2.5 產(chǎn)生式表示法1943年，美國(guó)邏輯學(xué)家年，美國(guó)邏輯學(xué)家Post首先提出首先提出1. 產(chǎn)生式的基本形式產(chǎn)生式的基本形式 產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則 IF P TH

42、EN Q 或或 PQ P稱為條件、前項(xiàng)或產(chǎn)生式的左邊稱為條件、前項(xiàng)或產(chǎn)生式的左邊 Q稱為操作、結(jié)果或產(chǎn)生式的右邊稱為操作、結(jié)果或產(chǎn)生式的右邊與蘊(yùn)涵式與蘊(yùn)涵式 P=Q區(qū)別區(qū)別 蘊(yùn)涵式中蘊(yùn)涵式中 P、Q要求是謂詞公式要求是謂詞公式 產(chǎn)生式中產(chǎn)生式中P、Q可以是謂詞公式，也可以不是可以是謂詞公式，也可以不是2.5 產(chǎn)生式表示法2. 產(chǎn)生式推理產(chǎn)生式推理 產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則 PQ 若觀察到若觀察到P，或者知識(shí)庫(kù)中已有，或者知識(shí)庫(kù)中已有P，則可以得到結(jié)論，則可以得到結(jié)論Q，或執(zhí)行，或執(zhí)行操作操作Q。推理的關(guān)鍵問(wèn)題：推理的關(guān)鍵問(wèn)題：如何有效解決規(guī)則匹配的沖突問(wèn)題如何有效解決規(guī)則匹配的沖突問(wèn)題2.6 語(yǔ)義

43、網(wǎng)絡(luò)法語(yǔ)義網(wǎng)絡(luò)是知識(shí)的一種結(jié)構(gòu)化圖解表示，它由節(jié)點(diǎn)和弧線或語(yǔ)義網(wǎng)絡(luò)是知識(shí)的一種結(jié)構(gòu)化圖解表示，它由節(jié)點(diǎn)和弧線或鏈線組成。節(jié)點(diǎn)用于表示實(shí)體、概念和情況等，弧線用于表示節(jié)鏈線組成。節(jié)點(diǎn)用于表示實(shí)體、概念和情況等，弧線用于表示節(jié)點(diǎn)間的關(guān)系。點(diǎn)間的關(guān)系。 語(yǔ)義網(wǎng)絡(luò)表示由下列語(yǔ)義網(wǎng)絡(luò)表示由下列4個(gè)相關(guān)部分組成：個(gè)相關(guān)部分組成： (1) 詞法部分詞法部分 ：決定表示詞匯表中允許有哪些符號(hào)，它涉及各：決定表示詞匯表中允許有哪些符號(hào)，它涉及各個(gè)節(jié)點(diǎn)和弧線。個(gè)節(jié)點(diǎn)和弧線。 (2) 結(jié)構(gòu)部分結(jié)構(gòu)部分 ：敘述符號(hào)排列的約束條件，指定各弧線連接的：敘述符號(hào)排列的約束條件，指定各弧線連接的節(jié)點(diǎn)對(duì)。節(jié)點(diǎn)對(duì)。 (3) 過(guò)程

44、部分：說(shuō)明訪問(wèn)過(guò)程，這些過(guò)程能用來(lái)建立和修正描過(guò)程部分：說(shuō)明訪問(wèn)過(guò)程，這些過(guò)程能用來(lái)建立和修正描述，以及回答相關(guān)問(wèn)題。述，以及回答相關(guān)問(wèn)題。 (4) 語(yǔ)義部分：確定與描述相關(guān)的語(yǔ)義部分：確定與描述相關(guān)的(聯(lián)想聯(lián)想)意義的方法即確定有意義的方法即確定有關(guān)節(jié)點(diǎn)的排列及其占有物和對(duì)應(yīng)弧線。關(guān)節(jié)點(diǎn)的排列及其占有物和對(duì)應(yīng)弧線。2.6 語(yǔ)義網(wǎng)絡(luò)法語(yǔ)義網(wǎng)絡(luò)具有下列特點(diǎn)：語(yǔ)義網(wǎng)絡(luò)具有下列特點(diǎn)：(1) 能把實(shí)體的結(jié)構(gòu)、屬性與實(shí)體間的因果關(guān)系顯式地和簡(jiǎn)能把實(shí)體的結(jié)構(gòu)、屬性與實(shí)體間的因果關(guān)系顯式地和簡(jiǎn)明地表達(dá)出來(lái)，與實(shí)體相關(guān)的事實(shí)、特征和關(guān)系可以通過(guò)相應(yīng)明地表達(dá)出來(lái)，與實(shí)體相關(guān)的事實(shí)、特征和關(guān)系可以通過(guò)相應(yīng)的節(jié)點(diǎn)弧

45、線推導(dǎo)出來(lái)。的節(jié)點(diǎn)弧線推導(dǎo)出來(lái)。(2) 由于與概念相關(guān)的屬性和聯(lián)系被組織在一個(gè)相應(yīng)的節(jié)點(diǎn)由于與概念相關(guān)的屬性和聯(lián)系被組織在一個(gè)相應(yīng)的節(jié)點(diǎn)中，因而使概念易于受訪和學(xué)習(xí)。中，因而使概念易于受訪和學(xué)習(xí)。(3) 表現(xiàn)問(wèn)題更加直觀，更易于理解，適于知識(shí)工程師與領(lǐng)表現(xiàn)問(wèn)題更加直觀，更易于理解，適于知識(shí)工程師與領(lǐng)域?qū)＜覝贤?。域?qū)＜覝贤ā?4) 語(yǔ)義網(wǎng)絡(luò)結(jié)構(gòu)的語(yǔ)義解釋依賴于該結(jié)構(gòu)的推理過(guò)程而沒(méi)語(yǔ)義網(wǎng)絡(luò)結(jié)構(gòu)的語(yǔ)義解釋依賴于該結(jié)構(gòu)的推理過(guò)程而沒(méi)有結(jié)構(gòu)的約定，因而得到的推理不能保證像謂詞邏輯法那樣有有結(jié)構(gòu)的約定，因而得到的推理不能保證像謂詞邏輯法那樣有效。效。(5) 節(jié)點(diǎn)間的聯(lián)系可能是線狀、樹(shù)狀或網(wǎng)狀的，甚至是遞歸

46、節(jié)點(diǎn)間的聯(lián)系可能是線狀、樹(shù)狀或網(wǎng)狀的，甚至是遞歸狀的結(jié)構(gòu)，使相應(yīng)的知識(shí)存儲(chǔ)和檢索可能需要比較復(fù)雜的過(guò)程狀的結(jié)構(gòu)，使相應(yīng)的知識(shí)存儲(chǔ)和檢索可能需要比較復(fù)雜的過(guò)程。2.6 語(yǔ)義網(wǎng)絡(luò)法2.6.1 二元語(yǔ)義網(wǎng)絡(luò)的表示二元語(yǔ)義網(wǎng)絡(luò)的表示 1. 用語(yǔ)義網(wǎng)絡(luò)表示簡(jiǎn)單事實(shí)用語(yǔ)義網(wǎng)絡(luò)表示簡(jiǎn)單事實(shí)例例2.5 所有的燕子都是鳥(niǎo)所有的燕子都是鳥(niǎo) 。 小燕子是一只燕子。小燕子是一只燕子。 小燕有一個(gè)巢。小燕有一個(gè)巢。 小燕從春天到秋天占有一個(gè)巢。小燕從春天到秋天占有一個(gè)巢。SWALLOWBIRDISAXIAOYANNEST-1NESTISAISAOWNS2.6 語(yǔ)義網(wǎng)絡(luò)法2.6.1 二元語(yǔ)義網(wǎng)絡(luò)的表示二元語(yǔ)義網(wǎng)絡(luò)的表示

47、1. 用語(yǔ)義網(wǎng)絡(luò)表示簡(jiǎn)單事實(shí)用語(yǔ)義網(wǎng)絡(luò)表示簡(jiǎn)單事實(shí)用兩個(gè)節(jié)點(diǎn)和一條弧線可以表示一個(gè)簡(jiǎn)單的事實(shí)，對(duì)于表用兩個(gè)節(jié)點(diǎn)和一條弧線可以表示一個(gè)簡(jiǎn)單的事實(shí)，對(duì)于表示占有關(guān)系的語(yǔ)義網(wǎng)絡(luò)，是通過(guò)允許節(jié)點(diǎn)既可以表示一個(gè)物體示占有關(guān)系的語(yǔ)義網(wǎng)絡(luò)，是通過(guò)允許節(jié)點(diǎn)既可以表示一個(gè)物體或一組物體，也可以表示情況和動(dòng)作。每一情況節(jié)點(diǎn)可以有一或一組物體，也可以表示情況和動(dòng)作。每一情況節(jié)點(diǎn)可以有一組向外的弧組向外的弧(事例弧事例弧)，稱為事例框，用以說(shuō)明與該事例有關(guān)的各，稱為事例框，用以說(shuō)明與該事例有關(guān)的各種變量。種變量。在選擇節(jié)點(diǎn)時(shí)，首先要弄清節(jié)點(diǎn)是用于表示基本的物在選擇節(jié)點(diǎn)時(shí)，首先要弄清節(jié)點(diǎn)是用于表示基本的物體或概念的，或

48、是用于多種目的的。否則，如果語(yǔ)義網(wǎng)絡(luò)只被體或概念的，或是用于多種目的的。否則，如果語(yǔ)義網(wǎng)絡(luò)只被用來(lái)表示一個(gè)特定的物體或概念，那么當(dāng)有更多的實(shí)例時(shí)就需用來(lái)表示一個(gè)特定的物體或概念，那么當(dāng)有更多的實(shí)例時(shí)就需要更多的語(yǔ)義網(wǎng)絡(luò)。要更多的語(yǔ)義網(wǎng)絡(luò)。2.6 語(yǔ)義網(wǎng)絡(luò)法2.6.1 二元語(yǔ)義網(wǎng)絡(luò)的表示二元語(yǔ)義網(wǎng)絡(luò)的表示 2. 用語(yǔ)義網(wǎng)絡(luò)表示復(fù)雜的事實(shí)及其關(guān)系用語(yǔ)義網(wǎng)絡(luò)表示復(fù)雜的事實(shí)及其關(guān)系 選擇語(yǔ)義基元就是試圖用一組基元來(lái)表示知識(shí)。這些選擇語(yǔ)義基元就是試圖用一組基元來(lái)表示知識(shí)。這些基元描述基本知識(shí)，并以圖解表示的形式相互聯(lián)系?；枋龌局R(shí)，并以圖解表示的形式相互聯(lián)系。CHAIRISAFURNITUREMY

49、 CHAIRLEATHERSEATSWALLOWXPERSONISA PARTCOLORISACOVERINGOWNERISA2.6 語(yǔ)義網(wǎng)絡(luò)法2.6.2 多元語(yǔ)義網(wǎng)絡(luò)的表示多元語(yǔ)義網(wǎng)絡(luò)的表示 語(yǔ)義網(wǎng)絡(luò)是一種網(wǎng)絡(luò)結(jié)構(gòu)。節(jié)點(diǎn)之間以鏈相連。從本語(yǔ)義網(wǎng)絡(luò)是一種網(wǎng)絡(luò)結(jié)構(gòu)。節(jié)點(diǎn)之間以鏈相連。從本質(zhì)上講，接點(diǎn)之間的連接是二元關(guān)系。語(yǔ)義網(wǎng)絡(luò)從本質(zhì)上來(lái)說(shuō)質(zhì)上講，接點(diǎn)之間的連接是二元關(guān)系。語(yǔ)義網(wǎng)絡(luò)從本質(zhì)上來(lái)說(shuō)，只能表示二元關(guān)系，如果所要表示的事實(shí)是多元關(guān)系，則把，只能表示二元關(guān)系，如果所要表示的事實(shí)是多元關(guān)系，則把這個(gè)多元關(guān)系轉(zhuǎn)化成一組二元關(guān)系的組合，或二元關(guān)系的合取這個(gè)多元關(guān)系轉(zhuǎn)化成一組二元關(guān)系的組合，或二元

50、關(guān)系的合取。具體來(lái)說(shuō)，多元關(guān)系。具體來(lái)說(shuō)，多元關(guān)系R(X1，X2，Xn)總可以轉(zhuǎn)換成總可以轉(zhuǎn)換成R1 (X11，X12)R2 (X21，X22)Rn (Xn1,Xn2)。要在語(yǔ)義網(wǎng)絡(luò)中進(jìn)行。要在語(yǔ)義網(wǎng)絡(luò)中進(jìn)行這種轉(zhuǎn)換需要引入附加節(jié)點(diǎn)。這種轉(zhuǎn)換需要引入附加節(jié)點(diǎn)。 2.6 語(yǔ)義網(wǎng)絡(luò)法2.6.2 多元語(yǔ)義網(wǎng)絡(luò)的表示多元語(yǔ)義網(wǎng)絡(luò)的表示 北京大學(xué)（北京大學(xué)（BU）和清華大學(xué)（）和清華大學(xué)（TU）兩?；@球隊(duì)在北大）兩校籃球隊(duì)在北大進(jìn)行的一場(chǎng)比賽的比分是進(jìn)行的一場(chǎng)比賽的比分是85比比89。 GAMEG25BU85-89TUISAHOMETEAMVISTINGTEAMSCORE2.6 語(yǔ)義網(wǎng)絡(luò)法2.6.3 基

51、于語(yǔ)義網(wǎng)絡(luò)的知識(shí)推理基于語(yǔ)義網(wǎng)絡(luò)的知識(shí)推理 繼承：把對(duì)事物的描述從概念節(jié)點(diǎn)或類節(jié)點(diǎn)傳遞到實(shí)例節(jié)繼承：把對(duì)事物的描述從概念節(jié)點(diǎn)或類節(jié)點(diǎn)傳遞到實(shí)例節(jié)點(diǎn)。點(diǎn)。 匹配：匹配： 由幾個(gè)部分組成的的事物間的匹配由幾個(gè)部分組成的的事物間的匹配2.7 框架表示2.7.1 框架理論及特點(diǎn)框架理論及特點(diǎn) 1. 框架理論概述框架理論概述 1975年年 ，明斯基，明斯基frame理論理論 當(dāng)遇見(jiàn)一個(gè)新事物時(shí)，人們?cè)谟洃浿羞x擇一個(gè)合適的框架，當(dāng)遇見(jiàn)一個(gè)新事物時(shí)，人們?cè)谟洃浿羞x擇一個(gè)合適的框架，然后根據(jù)事物的具體情況對(duì)框架進(jìn)行填充并進(jìn)行適當(dāng)修改和補(bǔ)充然后根據(jù)事物的具體情況對(duì)框架進(jìn)行填充并進(jìn)行適當(dāng)修改和補(bǔ)充，從而形成當(dāng)前事

52、物的認(rèn)識(shí)。這種數(shù)據(jù)結(jié)構(gòu)就稱為框架。，從而形成當(dāng)前事物的認(rèn)識(shí)。這種數(shù)據(jù)結(jié)構(gòu)就稱為框架?？蚣芸梢远x為是一組語(yǔ)義網(wǎng)絡(luò)的節(jié)點(diǎn)和槽?？蚣芸梢远x為是一組語(yǔ)義網(wǎng)絡(luò)的節(jié)點(diǎn)和槽。2. 框架的特點(diǎn)框架的特點(diǎn) 自然性自然性 結(jié)構(gòu)性：結(jié)構(gòu)化的語(yǔ)義網(wǎng)絡(luò)網(wǎng)絡(luò)結(jié)構(gòu)性：結(jié)構(gòu)化的語(yǔ)義網(wǎng)絡(luò)網(wǎng)絡(luò) 繼承性：繼承性：2.7 框架表示2.7.2 框架的構(gòu)成框架的構(gòu)成 框架通常由描述事物的各個(gè)方面的槽組成，每個(gè)槽可以擁有框架通常由描述事物的各個(gè)方面的槽組成，每個(gè)槽可以擁有若干個(gè)側(cè)面，而每個(gè)側(cè)面又可以擁有若干個(gè)值。一個(gè)框架的一般若干個(gè)側(cè)面，而每個(gè)側(cè)面又可以擁有若干個(gè)值。一個(gè)框架的一般結(jié)構(gòu)如下：結(jié)構(gòu)如下： 框架名框架名槽槽1側(cè)面?zhèn)让?1值

53、值111側(cè)面?zhèn)让?2值值121槽槽2側(cè)面?zhèn)让?1值值211 槽槽n側(cè)面?zhèn)让鎛1值值n11側(cè)面?zhèn)让鎛m值值nm12.7 框架表示2.7.2 框架的構(gòu)成框架的構(gòu)成 較簡(jiǎn)單的情景是用框架來(lái)表示諸如人和房子等事物。例如，較簡(jiǎn)單的情景是用框架來(lái)表示諸如人和房子等事物。例如，一個(gè)人可以用其職業(yè)、身高和體重等項(xiàng)描述，因而可以用這些項(xiàng)一個(gè)人可以用其職業(yè)、身高和體重等項(xiàng)描述，因而可以用這些項(xiàng)目組成框架的槽。當(dāng)描述一個(gè)具體的人時(shí)，再用這些項(xiàng)目的具體目組成框架的槽。當(dāng)描述一個(gè)具體的人時(shí)，再用這些項(xiàng)目的具體值填入到相應(yīng)的槽中。值填入到相應(yīng)的槽中。2.7 框架表示2.7.2 框架的構(gòu)成框架的構(gòu)成 表表2.2給出的是描述

54、給出的是描述John的框架。的框架?？蚣苁且环N通用的知識(shí)表達(dá)形式，對(duì)于如何運(yùn)用框架系統(tǒng)還沒(méi)有框架是一種通用的知識(shí)表達(dá)形式，對(duì)于如何運(yùn)用框架系統(tǒng)還沒(méi)有一種統(tǒng)一的形式一種統(tǒng)一的形式，常常由各種問(wèn)題的不同需要來(lái)決定。，常常由各種問(wèn)題的不同需要來(lái)決定。 JOHNIsa：PERSONProfession：PROGRAMMERHeight：1.8mWeight：79kg2.7 框架表示2.7.3 框架的推理框架的推理 如前所述，框架是一種復(fù)雜結(jié)構(gòu)的語(yǔ)義網(wǎng)絡(luò)。因此語(yǔ)義網(wǎng)絡(luò)如前所述，框架是一種復(fù)雜結(jié)構(gòu)的語(yǔ)義網(wǎng)絡(luò)。因此語(yǔ)義網(wǎng)絡(luò) 推理中的匹配和特性繼承在框架系統(tǒng)中也可以實(shí)行。除此以外，推理中的匹配和特性繼承在框架

55、系統(tǒng)中也可以實(shí)行。除此以外，由于框架用于描述具有固定格式的事物、動(dòng)作和事件，因此可以由于框架用于描述具有固定格式的事物、動(dòng)作和事件，因此可以在新的情況下，推論出未被觀察到的事實(shí)?？蚣苡靡韵聨追N途徑在新的情況下，推論出未被觀察到的事實(shí)?？蚣苡靡韵聨追N途徑來(lái)幫助實(shí)現(xiàn)這一點(diǎn)：來(lái)幫助實(shí)現(xiàn)這一點(diǎn)： (1) 框架包含它所描述的情況或物體的多方面的信息。框架包含它所描述的情況或物體的多方面的信息。 (2) 框架包含物體必須具有的屬性。在填充框架的各個(gè)槽時(shí)，框架包含物體必須具有的屬性。在填充框架的各個(gè)槽時(shí)，要用到這些屬性。要用到這些屬性。 (3) 框架描述它們所代表的概念的典型事例?？蚣苊枋鏊鼈兯淼母拍畹?/p>

56、典型事例。 2.7 框架表示2.7.3 框架的推理框架的推理 用一個(gè)框架來(lái)具體體現(xiàn)一個(gè)特定情況的過(guò)程，經(jīng)常不是很順利用一個(gè)框架來(lái)具體體現(xiàn)一個(gè)特定情況的過(guò)程，經(jīng)常不是很順利的。但當(dāng)這個(gè)過(guò)程碰到障礙時(shí)，經(jīng)常不必放棄原來(lái)的努力去從頭的。但當(dāng)這個(gè)過(guò)程碰到障礙時(shí)，經(jīng)常不必放棄原來(lái)的努力去從頭開(kāi)始，而是有很多辦法可想的：開(kāi)始，而是有很多辦法可想的： (1) 選擇和當(dāng)前情況相對(duì)應(yīng)的當(dāng)前的框架片斷，并把這個(gè)框架選擇和當(dāng)前情況相對(duì)應(yīng)的當(dāng)前的框架片斷，并把這個(gè)框架片斷和候補(bǔ)框架相匹配。選擇最佳匹配。片斷和候補(bǔ)框架相匹配。選擇最佳匹配。 (2) 盡管當(dāng)前的框架和要描述的情況之間有不相匹配的地方，盡管當(dāng)前的框架和要描述的情況之間有不相匹配的地方，但是仍然可以繼續(xù)應(yīng)用這個(gè)框架。但是仍然可以繼續(xù)應(yīng)用這個(gè)框架。 (3) 查詢框架之間專門(mén)保存的鏈，以提出應(yīng)朝哪個(gè)方向進(jìn)行試查詢框架之間專門(mén)保存的鏈，以提出應(yīng)朝哪個(gè)方向進(jìn)行試探的建議。探的建議。 (4) 沿著框架系統(tǒng)排列的層次結(jié)構(gòu)向上移動(dòng)沿著框架系統(tǒng)排列的層次結(jié)構(gòu)向上移動(dòng)(即從狗框架即從狗框架哺乳哺乳動(dòng)物框架動(dòng)物框架