第三章搜索推理技術(shù)人工智能課程北京大學(xué)

1、第三章 搜索推理技術(shù)教學(xué)內(nèi)容：本章在上一章知識(shí)表示的基礎(chǔ)上研究問題求解的方法，是人工智能研究的又一核心問題。內(nèi)容包括早期搜索推理技術(shù)，如圖搜索策略和消解原理；以及高級搜索推理技術(shù)，如規(guī)則演繹系統(tǒng)、產(chǎn)生式系統(tǒng)、系統(tǒng)組織技術(shù)、不確定性推理和非單調(diào)推理。教學(xué)重點(diǎn)：圖搜索策略、消解原理、規(guī)則演繹系統(tǒng)、產(chǎn)生式系統(tǒng)。教學(xué)難點(diǎn)：啟發(fā)式搜索、規(guī)則雙向演繹系統(tǒng)等。教學(xué)方法：課堂教學(xué)為主，輔以恰當(dāng)?shù)膶?shí)驗(yàn)。注意結(jié)合前面所學(xué)知識(shí)表示的基礎(chǔ)內(nèi)容，將其與問題求解方法融為一體。及時(shí)提問、收集學(xué)生學(xué)習(xí)情況。盡量使用實(shí)例和網(wǎng)絡(luò)課程中的多媒體素材進(jìn)行講解。教學(xué)要求：重點(diǎn)掌握一般圖搜索策略和消解原理，掌握各種搜索方法和產(chǎn)生式系統(tǒng)原

2、理，了解規(guī)則演繹系統(tǒng)的基本原理，對系統(tǒng)組織技術(shù)、不確定性推理和非單調(diào)推理等高級推理技術(shù)作一般性了解。3.1 圖搜索策略教學(xué)內(nèi)容：本節(jié)介紹圖搜索的一般策略，作為各種圖搜索技術(shù)的基礎(chǔ)。教學(xué)重點(diǎn)：圖搜索的一般過程、OPEN表和CLOSE表的概念。教學(xué)難點(diǎn)：OPEN表和CLOSE表的物理意義。教學(xué)方法：課堂教學(xué)為主，通過提問徹底弄清圖搜索的基本概念。教學(xué)要求：重點(diǎn)掌握圖搜索一般策略，掌握OPEN表和CLOSE表的構(gòu)成及作用。1、圖搜索策略的定義圖搜索策略可看作一種在圖中尋找路徑的方法。初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別代表初始數(shù)據(jù)庫和滿足終止條件的數(shù)據(jù)庫。求得把一個(gè)數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價(jià)于求得

3、圖中的一條路徑問題。研究圖搜索的一般策略，能夠給出圖搜索過程的一般步驟。2、圖搜索算法中的幾個(gè)重要名詞術(shù)語（1）OPEN表與CLOSE表（2）搜索圖與搜索樹3、圖搜索(GRAPHSEARCH)的一般過程(1) 建立一個(gè)只含有起始節(jié)點(diǎn)S的搜索圖G，把S放到一個(gè)叫做OPEN的未擴(kuò)展節(jié)點(diǎn)表中。(2) 建立一個(gè)叫做CLOSED的已擴(kuò)展節(jié)點(diǎn)表，其初始為空表。(3) LOOP：若OPEN表是空表，則失敗退出。(4) 選擇OPEN表上的第一個(gè)節(jié)點(diǎn)，把它從OPEN表移出并放進(jìn)CLOSED表中。稱此節(jié)點(diǎn)為節(jié)點(diǎn)n。(5) 若n為一目標(biāo)節(jié)點(diǎn)，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針將

4、在第7步中設(shè)置)。(6) 擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成不是n的祖先的那些后繼節(jié)點(diǎn)的集合M。把M的這些成員作為n的后繼節(jié)點(diǎn)添入圖G中。(7) 對那些未曾在G中出現(xiàn)過的(既未曾在OPEN表上或CLOSED表上出現(xiàn)過的)M成員設(shè)置一個(gè)通向n的指針。把M的這些成員加進(jìn)OPEN表。對已經(jīng)在OPEN或CLOSED表上的每一個(gè)M成員，確定是否需要更改通到n的指針方向。對已在CLOSED表上的每個(gè)M成員，確定是否需要更改圖G中通向它的每個(gè)后裔節(jié)點(diǎn)的指針方向。(8) 按某一任意方式或按某個(gè)探試值，重排OPEN表。(9) GO LOOP。提問：圖搜索是針對什么知識(shí)表示方法的問題求解方法？4、圖搜索方法分析：圖搜索過程的第

5、8步對OPEN表上的節(jié)點(diǎn)進(jìn)行排序，以便能夠從中選出一個(gè)“最好”的節(jié)點(diǎn)作為第4步擴(kuò)展用。這種排序可以是任意的即盲目的(屬于盲目搜索)，也可以用以后要討論的各種啟發(fā)思想或其它準(zhǔn)則為依據(jù)(屬于啟發(fā)式搜索)。每當(dāng)被選作擴(kuò)展的節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)時(shí)，這一過程就宣告成功結(jié)束。這時(shí)，能夠重現(xiàn)從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的這條成功路徑，其辦法是從目標(biāo)節(jié)點(diǎn)按指針向S返回追溯。當(dāng)搜索樹不再剩有未被擴(kuò)展的端節(jié)點(diǎn)時(shí)，過程就以失敗告終(某些節(jié)點(diǎn)最終可能沒有后繼節(jié)點(diǎn)，所以O(shè)PEN表可能最后變成空表)。在失敗終止的情況下，從起始節(jié)點(diǎn)出發(fā)，一定達(dá)不到目標(biāo)節(jié)點(diǎn)。提問：什么是圖搜索? 其中，重排OPEN表意味著什么，重排的原則是什么?3.2盲

6、目搜索教學(xué)內(nèi)容：介紹三種盲目搜索方法，即寬度優(yōu)先搜索、深度優(yōu)先搜索和等代價(jià)搜索。教學(xué)重點(diǎn)：盲目搜索的特點(diǎn)，寬度優(yōu)先搜索。教學(xué)難點(diǎn)：等代價(jià)搜索中代價(jià)的概念。教學(xué)方法：以實(shí)例強(qiáng)化內(nèi)容的學(xué)習(xí)，通過提問引導(dǎo)學(xué)生對三種方法的特點(diǎn)進(jìn)行比較。教學(xué)要求：掌握盲目搜索的特點(diǎn)，比較三種盲目搜索方法的優(yōu)缺點(diǎn)。3.2.1寬度優(yōu)先搜索1、定義如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索(breadth-first search)。2、特點(diǎn)這種搜索是逐層進(jìn)行的；在對下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。3、寬度優(yōu)先搜索算法(1) 把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)

7、為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答)。(2) 如果OPEN是個(gè)空表，則沒有解，失敗退出；否則繼續(xù)。(3) 把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。(4) 擴(kuò)展節(jié)點(diǎn)n。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第(2)步。(5) 把n的所有后繼節(jié)點(diǎn)放到OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到n的指針。(6) 如果n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出；否則轉(zhuǎn)向第(2)步。4、寬度優(yōu)先搜索方法分析：寬度優(yōu)先搜索是圖搜索一般過程的特殊情況，將圖搜索一般過程中的第8步具體化為本算法中的第6步，這實(shí)際是將OPEN表作為“先進(jìn)先出”的隊(duì)列進(jìn)行操作。寬度優(yōu)先搜索方法能夠

8、保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的最短途徑；這棵搜索樹提供了所有存在的路徑(如果沒有路徑存在，那么對有限圖來說，我們就說該法失敗退出；對于無限圖來說，則永遠(yuǎn)不會(huì)終止)。5、例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹，這個(gè)問題就是要把初始棋局變?yōu)槿缦履繕?biāo)棋局的問題：1 2 38 47 6 5提問：寬度優(yōu)先搜索方法中OPEN表需要按什么方式進(jìn)行操作？A先進(jìn)后出 B先進(jìn)先出3.2.2深度優(yōu)先搜索1、定義在此搜索中，首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)。深度相等的節(jié)點(diǎn)可以任意排列。這種盲目(無信息)搜索叫做深度優(yōu)先搜索(depth-first search)。2、特點(diǎn)首先，擴(kuò)展最深的節(jié)點(diǎn)的結(jié)果

9、使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點(diǎn)向下進(jìn)行下去；只有當(dāng)搜索到達(dá)一個(gè)沒有后裔的狀態(tài)時(shí)，它才考慮另一條替代的路徑。3、深度界限為了避免考慮太長的路徑(防止搜索過程沿著無益的路徑擴(kuò)展下去)，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度棗深度界限。任何節(jié)點(diǎn)如果達(dá)到了深度界限，那么都將把它們作為沒有后繼節(jié)點(diǎn)處理。4、含有深度界限的深度優(yōu)先搜索算法請同學(xué)們課后自學(xué)，并回答課后思考題。思考題：有界深度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的最短途徑嗎？3.2.3等代價(jià)搜索1、定義寬度優(yōu)先搜索可被推廣用來解決尋找從起始狀態(tài)至目標(biāo)狀態(tài)的具有最小代價(jià)的路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價(jià)搜索算

10、法。2、等代價(jià)搜索中的幾個(gè)記號(hào)起始節(jié)點(diǎn)記為S；從節(jié)點(diǎn)i到它的后繼節(jié)點(diǎn)j的連接弧線代價(jià)記為c(i，j)；從起始節(jié)點(diǎn)S到任一節(jié)點(diǎn)i的路徑代價(jià)記為g(i)。3、等代價(jià)搜索算法（請同學(xué)們課后認(rèn)真閱讀本算法，指出與寬度優(yōu)先、深度優(yōu)先算法有何特別之處。）4、等代價(jià)搜索方法分析如果所有的連接弧線具有相等的代價(jià)，那么等代價(jià)算法就簡化為寬度優(yōu)先搜索算法。思考：試比較各種盲目搜索搜索方法的效率，找出影響算法效率的原因。3.3 啟發(fā)式搜索教學(xué)內(nèi)容：啟發(fā)式搜索策略概述和有序搜索。啟發(fā)式搜索彌補(bǔ)盲目搜索的不足，提高搜索效率。教學(xué)重點(diǎn)：啟發(fā)式搜索策略、啟發(fā)信息和有序搜索。教學(xué)難點(diǎn)：估價(jià)函數(shù)的設(shè)計(jì)、A*算法原理。教學(xué)方法：

11、通過實(shí)例加深對原理的理解，鼓勵(lì)同學(xué)擴(kuò)大閱讀范圍。教學(xué)要求：掌握啟發(fā)式搜索策略和估價(jià)函數(shù)的設(shè)計(jì)方法，了解A*算法原理。3.3.1啟發(fā)式搜索策略和估價(jià)函數(shù)1、為什么需要啟發(fā)式搜索盲目搜索效率低，耗費(fèi)過多的計(jì)算空間與時(shí)間，這是組合爆炸的一種表現(xiàn)形式。2、定義進(jìn)行搜索技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域的特性的信息，把此種信息叫做啟發(fā)信息。利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索方法。3、啟發(fā)式搜索策略有關(guān)具體問題領(lǐng)域的信息常?？梢杂脕砗喕阉鳌Ｒ粋€(gè)比較靈活(但代價(jià)也較大)的利用啟發(fā)信息的方法是應(yīng)用某些準(zhǔn)則來重新排列每一步OPEN表中所有節(jié)點(diǎn)的順序。然后，搜索就可能沿著某個(gè)被認(rèn)為是最有希望的邊緣區(qū)段向外擴(kuò)展。

12、應(yīng)用這種排序過程，需要某些估算節(jié)點(diǎn)“希望”的量度，這種量度叫做估價(jià)函數(shù)(evalution function)。4、估價(jià)函數(shù)為獲得某些節(jié)點(diǎn)“希望”的啟發(fā)信息，提供一個(gè)評定侯選擴(kuò)展節(jié)點(diǎn)的方法，以便確定哪個(gè)節(jié)點(diǎn)最有可能在通向目標(biāo)的最佳路徑上 。f(n)表示節(jié)點(diǎn)n的估價(jià)函數(shù)值建立估價(jià)函數(shù)的一般方法：試圖確定一個(gè)處在最佳路徑上的節(jié)點(diǎn)的概率；提出任意節(jié)點(diǎn)與目標(biāo)集之間的距離量度或差別量度；或者在棋盤式的博弈和難題中根據(jù)棋局的某些特點(diǎn)來決定棋局的得分?jǐn)?shù)。這些特點(diǎn)被認(rèn)為與向目標(biāo)節(jié)點(diǎn)前進(jìn)一步的希望程度有關(guān)。3.3.2 有序搜索1、定義用估價(jià)函數(shù)f來排列GRAPHSEARCH第8步中OPEN表上的節(jié)點(diǎn)。應(yīng)用某個(gè)算

13、法(例如等代價(jià)算法)選擇OPEN表上具有最小f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。這種搜索方法叫做有序搜索(ordered search)或最佳優(yōu)先搜索(best-first search)，而其算法就叫做有序搜索算法或最佳優(yōu)先算法。尼爾遜(Nilsson)曾提出一個(gè)有序搜索的基本算法。估價(jià)函數(shù)f是這樣確定的：一個(gè)節(jié)點(diǎn)的希望程序越大，其f值就越小。被選為擴(kuò)展的節(jié)點(diǎn)，是估價(jià)函數(shù)最小的節(jié)點(diǎn)。2、實(shí)質(zhì)選擇OPEN表上具有最小f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)，即總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。3、有序狀態(tài)空間搜索算法(1) 把起始節(jié)點(diǎn)S放到OPEN表中，計(jì)算f(S)并把其值與節(jié)點(diǎn)S聯(lián)系起來。

14、(2) 如果OPEN是個(gè)空表，則失敗退出，無解。(3) 從OPEN表中選擇一個(gè)f值最小的節(jié)點(diǎn)i。結(jié)果有幾個(gè)節(jié)點(diǎn)合格，當(dāng)其中有一個(gè)為目標(biāo)節(jié)點(diǎn)時(shí)，則選擇此目標(biāo)節(jié)點(diǎn)，否則就選擇其中任一個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)i。(4) 把節(jié)點(diǎn)i從OPEN表中移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。(5) 如果i是個(gè)目標(biāo)節(jié)點(diǎn)，則成功退出，求得一個(gè)解。(6) 擴(kuò)展節(jié)點(diǎn)i，生成其全部后繼節(jié)點(diǎn)。對于i的每一個(gè)后繼節(jié)點(diǎn)j：(a)計(jì)算f(j)。(b)如果j既不在OPEN表中，又不在CLOSED表中，則用估價(jià)函數(shù)f把它添入OPEN表。從j加一指向其父輩節(jié)點(diǎn)i的指針，以便一旦找到目標(biāo)節(jié)點(diǎn)時(shí)記住一個(gè)解答路徑。(c)如果j已在OPEN表上或

15、CLOSED表上，則比較剛剛對j計(jì)算過的f值和前面計(jì)算過的該節(jié)點(diǎn)在表中的f值。如果新的f值較小，則(i) 以此新值取代舊值。(ii) 從j指向i，而不是指向它的父輩節(jié)點(diǎn)。(iii) 如果節(jié)點(diǎn)j在CLOSED表中，則把它移回OPEN表。(7) 轉(zhuǎn)向(2)，即GO TO(2)。4、有序搜索方法分析寬度優(yōu)先搜索、等代價(jià)搜索和深度優(yōu)先搜索統(tǒng)統(tǒng)是有序搜索技術(shù)的特例。對于寬度優(yōu)先搜索，選擇f(i)作為節(jié)點(diǎn)i的深度。對于等代價(jià)搜索，f(i)是從起始節(jié)點(diǎn)至節(jié)點(diǎn)i這段路徑的代價(jià)。有序搜索的有效性直接取決于f的選擇，如果選擇的f不合適，有序搜索就可能失去一個(gè)最好的解甚至全部的解。如果沒有適用的準(zhǔn)確的希望量度，那么

16、f的選擇將涉及兩個(gè)方面的內(nèi)容：一方面是一個(gè)時(shí)間和空間之間的折衷方案；另一方面是保證有一個(gè)最優(yōu)的解或任意解。5、例：八數(shù)碼難題采用了簡單的估價(jià)函數(shù)f(n)=d(n)+W(n)其中：d(n)是搜索樹中節(jié)點(diǎn)n的深度；W(n)用來計(jì)算對應(yīng)于節(jié)點(diǎn)n的數(shù)據(jù)庫中錯(cuò)放的棋子個(gè)數(shù)。因此，起始節(jié)點(diǎn)棋局2 8 31 47 6 5的f值等于0+4=4。3.3.3 A*算法A*算法是一種有序搜索算法，其特點(diǎn)在于對估價(jià)函數(shù)的定義上。1、幾個(gè)記號(hào)令k(ni，nj)表示任意兩個(gè)節(jié)點(diǎn)ni和nj之間最小代價(jià)路徑的實(shí)際代價(jià)(對于兩節(jié)點(diǎn)間沒有通路的節(jié)點(diǎn)，函數(shù)k沒有定義)。于是，從節(jié)點(diǎn)n到某個(gè)具體的目標(biāo)節(jié)點(diǎn)ti，某一條最小代價(jià)路徑的代

17、價(jià)可由k(n,ti)給出。令h*(n)表示整個(gè)目標(biāo)節(jié)點(diǎn)集合ti上所有k(n,ti)中最小的一個(gè)，因此，h*(n)就是從n到目標(biāo)節(jié)點(diǎn)最小代價(jià)路徑的代價(jià)，而且從n到目標(biāo)節(jié)點(diǎn)能夠獲得h*(n)的任一路徑就是一條從n到某個(gè)目標(biāo)節(jié)點(diǎn)的最佳路徑(對于任何不能到達(dá)目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)n，函數(shù)h*沒有定義)。2、估價(jià)函數(shù)的定義定義g*為g*(n)=k(S,n)定義函數(shù)f*，使得在任一節(jié)點(diǎn)n上其函數(shù)值f*(n)就是從節(jié)點(diǎn)S到節(jié)點(diǎn)n的一條最佳路徑的實(shí)際代價(jià)加上從節(jié)點(diǎn)n到某目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)之和，即f*(n)=g*(n)+h*(n)希望估價(jià)函數(shù)f是f*的一個(gè)估計(jì)，此估計(jì)可由下式給出：f(n)=g(n)+h(n)

18、其中：g是g*的估計(jì)；h是h*的估計(jì)。對于g(n)來說，一個(gè)明顯的選擇就是搜索樹中從S到n這段路徑的代價(jià)，這一代價(jià)可以由從n到S尋找指針時(shí)，把所遇到的各段弧線的代價(jià)加起來給出(這條路徑就是到目前為止用搜索算法找到的從S到n的最小代價(jià)路徑)。這個(gè)定義包含了g(n)g*(n)。h*(n)的估計(jì)h(n)依賴于有關(guān)問題的領(lǐng)域的啟發(fā)信息。這種信息可能與八數(shù)碼難題中的函數(shù)W(n)所用的那種信息相似。把h叫做啟發(fā)函數(shù)。3、A*算法定義定義1 在GRAPHSEARCH過程中，如果第8步的重排OPEN表是依據(jù)f(x)=g(x)+h(x)進(jìn)行的，則稱該過程為A算法。定義2 在A算法中，如果對所有的x存在h(x)h

19、*(x),則稱h(x)為h*(x)的下界，它表示某種偏于保守的估計(jì)。定義3 采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當(dāng)h=0時(shí)，A*算法就變?yōu)橛行蛩阉魉惴ā?、A*算法A*算法描述參考教材。提問：由g*(n)和g(n)的定義知g*(n)g(n)A對 B錯(cuò)思考：試比較寬度優(yōu)先搜索、有界深度優(yōu)先搜索及有序搜索的搜索效率，并以實(shí)例數(shù)據(jù)加以說明3.4 消解原理教學(xué)內(nèi)容：消解原理是針對謂詞邏輯知識(shí)表示的問題求解方法。本節(jié)內(nèi)容主要包括子句集的求取、消解推理的規(guī)則和消解反演問題求解方法。教學(xué)重點(diǎn)：子句集的求取、消解推理的規(guī)則和消解反演問題求解方法。教學(xué)難點(diǎn)：消解反演的思想。教學(xué)方法：實(shí)

20、例講解，注重課堂練習(xí)。教學(xué)要求：重點(diǎn)掌握子句集的求解步驟和消解反演過程，掌握消解推理的規(guī)則。消解原理的基礎(chǔ)知識(shí)：（1）謂詞公式、某些推理規(guī)則以及置換合一等概念。（2）子句：由文字的析取組成的公式(一個(gè)原子公式和原子公式的否定都叫做文字)。（3）消解：當(dāng)消解可使用時(shí)，消解過程被應(yīng)用于母體子句對，以便產(chǎn)生一個(gè)導(dǎo)出子句。例如，如果存在某個(gè)公理E1E2和另一公理E2E3，那么E1E3在邏輯上成立。這就是消解，而稱E1E3為E1E2和E2E3的消解式(resolvent)。3.4.1子句集的求取1、步驟(1) 消去蘊(yùn)涵符號(hào)只應(yīng)用和符號(hào)，以AB替換AB。提問：現(xiàn)有公式(AB) B C，在消去蘊(yùn)涵符號(hào)后得到

21、公式：A(AB) B C B(AB) B CC(AB) B C D (AB) B C(2) 減少否定符號(hào)的轄域每個(gè)否定符號(hào)最多只用到一個(gè)謂詞符號(hào)上，并反復(fù)應(yīng)用狄·摩根定律。例如：以AB代替(AB)以AB代替(AB)以A代替(A)以(x)A代替(x)A以(x)A代替(x)A提問：設(shè)有公式(x)(y)(y)P(x,y)(x)Q(x,y)，在經(jīng)過對變量標(biāo)準(zhǔn)化后得到公式為：A(x)(y)(y)P(x,y)(y)Q(y,y)B(x)(y)(x)P(x,x)(x)Q(x,y)C(x)(y)(z)P(x,z)(q)Q(q,y)D(x)(y)(z)P(x,z)(q)Q(q,z)E(x)(y)(z)P

22、(q,z)(q)Q(q,z)(3) 對變量標(biāo)準(zhǔn)化在任一量詞轄域內(nèi)，受該量詞約束的變量為一啞元(虛構(gòu)變量)，它可以在該轄域內(nèi)處處統(tǒng)一地被另一個(gè)沒有出現(xiàn)過的任意變量所代替，而不改變公式的真值。合適公式中變量的標(biāo)準(zhǔn)化意味著對啞元改名以保證每個(gè)量詞有其自己唯一的啞元。(4) 消去存在量詞用Skolem函數(shù)代替存在的x,就可以消去全部存在量詞，并寫成：(y)Pg(y),y從一個(gè)公式消去一個(gè)存在量詞的一般規(guī)則是以一個(gè)Skolem函數(shù)代替每個(gè)出現(xiàn)的存在量詞的量化變量，而這個(gè)Skolem函數(shù)的變量就是由那些全稱量詞所約束的全稱量詞量化變量，這些全稱量詞的轄域包括要被消去的存在量詞的轄域在內(nèi)。Skolem函數(shù)所

23、使用的函數(shù)符號(hào)必須是新的，即不允許是公式中已經(jīng)出現(xiàn)過的函數(shù)符號(hào)。例如：(y)(x)P(x,y)被(y)P(g(y),y)代替，其中g(shù)(y)為一Skolem函數(shù)。如果要消去的存在量詞不在任何一個(gè)全稱量詞的轄域內(nèi)，則用不含變量的Skolem函數(shù)即常量。例如，(x)P(x)化為P(A)，其中常量符號(hào)A用來表示人們知道的存在實(shí)體。A必須是個(gè)新的常量符號(hào)，它未曾在公式中其它地方使用過。(5) 化為前束形把所有全稱量詞移到公式的左邊，并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。所得公式稱為前束形。(6) 把母式化為合取范式任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。

24、這種母式叫做合取范式。(7) 消去全稱量詞消去明顯出現(xiàn)的全稱量詞。提問：對于公式(z)(y)(x)P(x,y,z)(q)(w)(e)Q(q,w,e,z)，在經(jīng)過消去存在量詞后，正確的公式為：A(y)P(B,y,A)(w)Q(C,w,D,A)B(y)P(B,y,A)(w)Q(C,w,g(w),A) , g(w)為一Skolem函數(shù)C(y)P(g1(y),y,A)(w)Q(g(y),w,g(w),A)式中，(g1(y)，g(y)和g(w)為Skolem函數(shù)D(y)P(g1(y),y,A)(w)Q(g(y),w,g(y,w),A)式中，(g1(y)，g(y)和g(y,w)為Skolem函數(shù)(8) 消

25、去連詞符號(hào)用A，B代替(AB)，以消去明顯的符號(hào)。反復(fù)代替的結(jié)果，最后得到一個(gè)有限集，其中每個(gè)公式是文字的析取。任一個(gè)只由文字的析取構(gòu)成的合適公式叫做一個(gè)子句。(9) 更換變量名稱可以更換變量符號(hào)的名稱，使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中。2、例將下列謂詞演算公式化為一個(gè)子句集(x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y)3、說明并不是所有問題的謂詞公式化為子句集都需要上述9個(gè)步驟。對于某些問題，可能不需要其中的一些步驟。3.4.2 消解推理規(guī)則1、消解式令L1為任一原子公式，L2為另一原子公式；L1和L2具有相同的謂詞符號(hào)，但一般具有不同的變量。已知兩子句L1和L

26、2,如果L1和L2具有最一般合一者，那么通過消解可以從這兩個(gè)父輩子句推導(dǎo)出一個(gè)新子句()。這個(gè)新子句叫做消解式。它是由取這兩個(gè)子句的析取，然后消去互補(bǔ)對而得到的。2、消解式求法(1) 假言推理父輩子句 P PQ(即PQ)          /        /消解式Q(2) 合并 (3) 重言式(4) 空子句(矛盾)P       P    

27、60;   /      /NIL(5) 鏈?zhǔn)?三段論)即取各子句的析取，然后消去互補(bǔ)對。說明：對合并、重言式、鏈?zhǔn)?三段論)請同學(xué)們自行閱讀。3.4.3 含有變量的消解式1、消解式求法為了對含有變量的子句使用消解規(guī)則，必須找到一個(gè)置換，作用于父輩子句使其含有互補(bǔ)文字。2、例子 P(x)Q(x)Qf(y) 置換=f(y)/xPf(y)3.4.4 消解反演求解過程1、基本思想把要解決的問題作為一個(gè)要證明的命題，其目標(biāo)公式被否定并化成子句形，然后添加到命題公式集中去，把消解反演系統(tǒng)應(yīng)用于聯(lián)合集，并推導(dǎo)出一個(gè)空子句(NIL)，產(chǎn)生

28、一個(gè)矛盾，這說明目標(biāo)公式的否定式不成立，即有目標(biāo)公式成立，定理得證，問題得到解決，與數(shù)學(xué)中反證法的思想十分相似。2、消解反演反演求解的步驟給出一個(gè)公式集S和目標(biāo)公式L，通過反證或反演來求證目標(biāo)公式L，其證明步驟如下：(1)否定L，得L；(2)把L添加到S中去；(3)把新產(chǎn)生的集合L，S化成子句集；(4)應(yīng)用消解原理，力圖推導(dǎo)出一個(gè)表示矛盾的空子句NIL。反演求解的正確性設(shè)公式L在邏輯上遵循公式集S，那么按照定義滿足S的每個(gè)解釋也滿足L。決不會(huì)有滿足S的解釋能夠滿足L的，所以不存在能夠滿足并集SL的解釋。如果一個(gè)公式集不能被任一解釋所滿足，那么這個(gè)公式是不可滿足的。因此，如果L在邏輯上遵循S，那

29、么SL是不可滿足的?？梢宰C明，如果消解反演反復(fù)應(yīng)用到不可滿足的子句集，那么最終將要產(chǎn)生空子句NIL。因此，如果L在邏輯上遵循S，那么由并集SL消解得到的子句，最后將產(chǎn)生空子句；反之，可以證明，如果從SL的子句消解得到空子句，那么L在邏輯上遵循S。3、反演求解過程步驟：(1)把由目標(biāo)公式的否定產(chǎn)生的每個(gè)子句添加到目標(biāo)公式否定之否定的子句中去。(2)按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個(gè)子句止。(3)用根部的子句作為一個(gè)回答語句。分析：答案求取涉及到把一棵根部有NIL的反演樹變換為在根部帶有可用作答案的某個(gè)語句的一顆證明樹。由于變換關(guān)系涉及到把由目標(biāo)公式的否定產(chǎn)生的每個(gè)子句變換為一個(gè)

30、重言式，所以被變換的證明樹就是一棵消解的證明樹，其在根部的語句在邏輯上遵循公理加上重言式，因而也單獨(dú)地遵循公理。因此被變換的證明樹本身就證明了求取辦法是正確的。例：儲(chǔ)蓄問題前提：每個(gè)儲(chǔ)蓄錢的人都獲得利息。結(jié)論：如果沒有利息，那么就沒有人去儲(chǔ)蓄錢思考：應(yīng)用消解反演求解如下問題：“如果無論約翰(John)到哪里去，菲多(Fido)也就去那里，那么如果約翰在學(xué)校里，菲多在哪里呢?” 3.5 規(guī)則演繹系統(tǒng)教學(xué)內(nèi)容：規(guī)則演繹系統(tǒng)屬于高級搜索推理技術(shù)，用于解決比較復(fù)雜的系統(tǒng)和問題。本節(jié)介紹規(guī)則演繹系統(tǒng)的定義及其三種推理方法：規(guī)則正向演繹系統(tǒng)、規(guī)則逆向演繹系統(tǒng)和規(guī)則雙向演繹系統(tǒng)。教學(xué)重點(diǎn)：規(guī)則演繹

31、系統(tǒng)的定義、正向推理和逆向推理過程。教學(xué)難點(diǎn)：雙向演繹的匹配問題等。教學(xué)方法：課堂教學(xué)為主。通過比較揭示正向推理、逆向推理和雙向推理的特點(diǎn)。教學(xué)要求：掌握規(guī)則演繹系統(tǒng)的定義和正向推理、逆向推理的過程，了解規(guī)則雙向演繹系統(tǒng)。規(guī)則演繹系統(tǒng)的定義：基于規(guī)則的問題求解系統(tǒng)運(yùn)用下述規(guī)則來建立：IfThen其中，If部分可能由幾個(gè)if組成，而Then部分可能由一個(gè)或一個(gè)以上的then組成。在所有基于規(guī)則系統(tǒng)中，每個(gè)if可能與某斷言(assertion)集中的一個(gè)或多個(gè)斷言匹配。有時(shí)把該斷言集稱為工作內(nèi)存。在許多基于規(guī)則系統(tǒng)中，then部分用于規(guī)定放入工作內(nèi)存的新斷言。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng)(r

32、ule based deduction system)。在這種系統(tǒng)中，通常稱每個(gè)if部分為前項(xiàng)(antecedent)，稱每個(gè)then部分為后項(xiàng)(consequent)。3.5.1規(guī)則正向演繹系統(tǒng)1、定義正向規(guī)則演繹系統(tǒng)是從事實(shí)到目標(biāo)進(jìn)行操作的，即從狀況條件到動(dòng)作進(jìn)行推理的，也就是從if到then的方向進(jìn)行推理的。2、正向推理過程（1）事實(shí)表達(dá)式的與或形變換把事實(shí)表示為非蘊(yùn)涵形式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫。具體變換步驟與前述化為子句形類似。注意：我們不想把這些事實(shí)化為子句形，而是把它們表示為謂詞演算公式，并把這些公式變換為叫做與或形的非蘊(yùn)涵形式。例：有事實(shí)表達(dá)式(u)(v)Q(v，u)(R(

33、v)P(v)S(u，v)把它化為Q(v,A)R(v)P(v)S(A,v)對變量更名標(biāo)準(zhǔn)化，使得同一變量不出現(xiàn)在事實(shí)表達(dá)式的不同主要合取式中，得：Q(w,A)R(v)P(v)S(A,v)（2）事實(shí)表達(dá)式的與或圖表示將上例與或形的事實(shí)表達(dá)式用與或圖來表示，見圖3.1。圖 3.1 一個(gè)事實(shí)表達(dá)式的與或樹表示一般把事實(shí)表達(dá)式的與或圖表示倒過來畫，即把根節(jié)點(diǎn)畫在最下面，而把其后繼節(jié)點(diǎn)往上畫。上節(jié)的與或圖表示，就是按通常方式畫出的，即目標(biāo)在上面。（3）與或圖的F規(guī)則變換這些規(guī)則是建立在某個(gè)問題轄域中普通陳述性知識(shí)的蘊(yùn)涵公式基礎(chǔ)上的。把允許用作規(guī)則的公式類型限制為下列形式：LW式中：L是單文字；W為與或形的

34、唯一公式。將這類規(guī)則應(yīng)用于與或圖進(jìn)行推演。假設(shè)有一條規(guī)則L=>W，根據(jù)此規(guī)則及事實(shí)表達(dá)式F(L)，可以推出表達(dá)式F(W)。F(W)是用W代替F中的所有L而得到的。當(dāng)用規(guī)則L=>W來變換以上述方式描述的F(L)的與或圖表示時(shí)，就產(chǎn)生一個(gè)含有F(W)表示的新圖；也就是說，它的以葉節(jié)點(diǎn)終止的解圖集以F(W)子句形式代表該子句集。這個(gè)子句集包括在F(L)的子句形和L=>W的子句形間對L進(jìn)行所有可能的消解而得到的整集。該過程以極其有效的方式達(dá)到了用其它方法要進(jìn)行多次消解才能達(dá)到的目的。（4）作為終止條件的目標(biāo)公式應(yīng)用F規(guī)則的目的在于從某個(gè)事實(shí)公式和某個(gè)規(guī)則集出發(fā)來證明某個(gè)目標(biāo)公式。在正

35、向推理系統(tǒng)中，這種目標(biāo)表達(dá)式只限于可證明的表達(dá)式，尤其是可證明的文字析取形的目標(biāo)公式表達(dá)式。用文字集表示此目標(biāo)公式，并設(shè)該集各元都為析取關(guān)系。結(jié)論：當(dāng)正向演繹系統(tǒng)產(chǎn)生一個(gè)含有以目標(biāo)節(jié)點(diǎn)作為終止的解圖時(shí)，此系統(tǒng)就成功地終止。3.5.2 規(guī)則逆向演繹系統(tǒng)1、定義基于規(guī)則的逆向演繹系統(tǒng)，其操作過程與正向演繹系統(tǒng)相反，即為從目標(biāo)到事實(shí)的操作過程，從then到if的推理過程。2、逆向推理過程（1）目標(biāo)表達(dá)式的與或形式逆向演繹系統(tǒng)能夠處理任意形式的目標(biāo)表達(dá)式。首先，采用與變換事實(shí)表達(dá)式同樣的過程，把目標(biāo)公式化成與或形。（2）與或圖的B規(guī)則變換B規(guī)則是建立在確定的蘊(yùn)涵式基礎(chǔ)上的，正如正向系統(tǒng)的F規(guī)則一樣。不

36、過，我們現(xiàn)在把這些B規(guī)則限制為WL (3.4)形式的表達(dá)式。其中，W為任一與或形公式，L為文字，而且蘊(yùn)涵式中任何變量的量詞轄域?yàn)檎麄€(gè)蘊(yùn)涵式。（3）作為終止條件的事實(shí)節(jié)點(diǎn)的一致解圖逆向系統(tǒng)成功的終止條件是與或圖包含有某個(gè)終止在事實(shí)節(jié)點(diǎn)上的一致解圖。提問：逆向推理與正向推理的區(qū)別有哪些？3.5.3 規(guī)則雙向演繹系統(tǒng)1.基于規(guī)則的正向演繹系統(tǒng)和逆向演繹系統(tǒng)的特點(diǎn)和局限性 正向演繹系統(tǒng)能夠處理任意形式的if表達(dá)式，但被限制在then表達(dá)式為由文字析取組成的一些表達(dá)式。逆向演繹系統(tǒng)能夠處理任意形式的then表達(dá)式，但被限制在if表達(dá)式為文字合取組成的一些表達(dá)式。雙向(正向和逆向)組合演繹系統(tǒng)具有正向和逆

37、向兩系統(tǒng)的優(yōu)點(diǎn)，克服各自的缺點(diǎn)。2.雙向(正向和逆向)組合演繹系統(tǒng)的構(gòu)成 正向和逆向組合系統(tǒng)是建立在兩個(gè)系統(tǒng)相結(jié)合的基礎(chǔ)上的。此組合系統(tǒng)的總數(shù)據(jù)庫由表示目標(biāo)和表示事實(shí)的兩個(gè)與或圖結(jié)構(gòu)組成，并分別用F規(guī)則和B規(guī)則來修正。3.終止條件 組合演繹系統(tǒng)的主要復(fù)雜之處在于其終止條件，終止涉及兩個(gè)圖結(jié)構(gòu)之間的適當(dāng)交接處。當(dāng)用F規(guī)則和B規(guī)則對圖進(jìn)行擴(kuò)展之后，匹配就可以出現(xiàn)在任何文字節(jié)點(diǎn)上。在完成兩個(gè)圖間的所有可能匹配之后，目標(biāo)圖中根節(jié)點(diǎn)上的表達(dá)式是否已經(jīng)根據(jù)事實(shí)圖中根節(jié)點(diǎn)上的表達(dá)式和規(guī)則得到證明的問題仍然需要判定。只有當(dāng)求得這樣的一個(gè)證明時(shí)，證明過程才算成功地終止。若能夠斷定在給定方法限度內(nèi)找不到證明時(shí)過程

38、則以失敗告終。 3.6 產(chǎn)生式系統(tǒng)教學(xué)內(nèi)容：本節(jié)介紹產(chǎn)生式系統(tǒng)的定義、組成和推理技術(shù)。教學(xué)重點(diǎn)：產(chǎn)生式系統(tǒng)與規(guī)則演繹系統(tǒng)的差別和產(chǎn)生式系統(tǒng)的組成。教學(xué)難點(diǎn)：產(chǎn)生式系統(tǒng)的控制策略等。教學(xué)方法：課堂教學(xué)和實(shí)驗(yàn)相結(jié)合。重點(diǎn)講解原理，通過實(shí)驗(yàn)進(jìn)一步領(lǐng)會(huì)系統(tǒng)的精髓。充分利用網(wǎng)絡(luò)課程中的多媒體素材來表示抽象概念。教學(xué)要求：掌握產(chǎn)生式系統(tǒng)的組成結(jié)構(gòu)，通過實(shí)踐掌握產(chǎn)生式系統(tǒng)的設(shè)計(jì)和工作過程。定義：在基于規(guī)則系統(tǒng)中，每個(gè)if可能與某斷言(assertion)集中的一個(gè)或多個(gè)斷言匹配，then部分用于規(guī)定放入工作內(nèi)存的新斷言。當(dāng)then部分用于規(guī)定動(dòng)作時(shí)，稱這種基于規(guī)則的系統(tǒng)為反應(yīng)式系統(tǒng)(reactio

39、n system)或產(chǎn)生式系統(tǒng)(production system)。提問：產(chǎn)生式系統(tǒng)與規(guī)則演繹系統(tǒng)有什么區(qū)別？3.6.1 產(chǎn)生式系統(tǒng)的組成1.產(chǎn)生式系統(tǒng)的組成 產(chǎn)生式系統(tǒng)由3個(gè)部分組成，即總數(shù)據(jù)庫(或全局?jǐn)?shù)據(jù)庫)、產(chǎn)生式規(guī)則和控制策略，如圖3.2所示。 圖3.2 產(chǎn)生式系統(tǒng)的主要組成總數(shù)據(jù)庫有時(shí)也被稱作上下文，當(dāng)前數(shù)據(jù)庫或暫時(shí)存儲(chǔ)器?？倲?shù)據(jù)庫是產(chǎn)生式規(guī)則的注意中心。產(chǎn)生式規(guī)則的左邊表示在啟用這一規(guī)則之前總數(shù)據(jù)庫內(nèi)必須準(zhǔn)備好的條件。例如在上述例子中，在得出該動(dòng)物是食肉動(dòng)物的結(jié)論之前，必須在總數(shù)據(jù)庫中存有“該動(dòng)物是哺乳動(dòng)物”和“該動(dòng)物吃肉”這兩個(gè)事實(shí)。執(zhí)行產(chǎn)生式規(guī)則的操作會(huì)引起總數(shù)據(jù)庫的變化，這

40、就使其他產(chǎn)生式規(guī)則的條件可能被滿足。 產(chǎn)生式規(guī)則是一個(gè)規(guī)則庫，用于存放與求解問題有關(guān)的某個(gè)領(lǐng)域知識(shí)的規(guī)則之集合及其交換規(guī)則。規(guī)則庫知識(shí)的完整性、一致性、準(zhǔn)確性、靈活性和知識(shí)組織的合理性，將對產(chǎn)生式系統(tǒng)的運(yùn)行效率和工作性能產(chǎn)生重要影響?？刂撇呗詾橐煌评頇C(jī)構(gòu)，由一組程序組成，用來控制產(chǎn)生式系統(tǒng)的運(yùn)行，決定問題求解過程的推理線路，實(shí)現(xiàn)對問題的求解。產(chǎn)生式系統(tǒng)的控制策略隨搜索方式的不同可分為可撤回策略、回溯策略、圖搜索策略等。2.產(chǎn)生式系統(tǒng)的控制策略 控制策略的作用是說明下一步應(yīng)該選用什么規(guī)則，也就是如何應(yīng)用規(guī)則。通常從選擇規(guī)則到執(zhí)行操作分3步：匹配、沖突解決和操作。（1）匹配在這一步，把當(dāng)前數(shù)據(jù)庫與

41、規(guī)則的條件部分相匹配。如果兩者完全匹配，則把這條規(guī)則稱為觸發(fā)規(guī)則。當(dāng)按規(guī)則的操作部分去執(zhí)行時(shí)，稱這條規(guī)則為啟用規(guī)則。被觸發(fā)的規(guī)則不一定總是啟用規(guī)則，因?yàn)榭赡芡瑫r(shí)有幾條規(guī)則的條件部分被滿足，這就要在解決沖突步驟中來解決這個(gè)問題。在復(fù)雜的情況下，在數(shù)據(jù)庫和規(guī)則的條件部分之間可能要進(jìn)行近似匹配。（2）沖突解決當(dāng)有一條以上規(guī)則的條件部分和當(dāng)前數(shù)據(jù)庫相匹配時(shí)，就需要決定首先使用哪一條規(guī)則，這稱為沖突解決。（3）操作操作就是執(zhí)行規(guī)則的操作部分，經(jīng)過操作以后，當(dāng)前數(shù)據(jù)庫將被修改。然后，其他的規(guī)則有可能被使用。3.6.2 產(chǎn)生式系統(tǒng)的推理1.正向推理 從一組表示事實(shí)的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則，用以證

42、明該謂詞公式或命題是否成立。一般策略：先提供一批事實(shí)（數(shù)據(jù)）到總數(shù)據(jù)庫中。系統(tǒng)利用這些事實(shí)與規(guī)則的前提相匹配，觸發(fā)匹配成功的規(guī)則，把其結(jié)論作為新的事實(shí)添加到總數(shù)據(jù)庫中。繼續(xù)上述過程，用更新過的總數(shù)據(jù)庫的所有事實(shí)再與規(guī)則庫中另一條規(guī)則匹配，用其結(jié)論再次修改總數(shù)據(jù)庫的內(nèi)容，直到?jīng)]有可匹配的新規(guī)則，不再有新的事實(shí)加到總數(shù)據(jù)庫中。2.逆向推理 從表示目標(biāo)的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則證明事實(shí)謂詞或命題成立，即首先提出一批假設(shè)目標(biāo)，然后逐一驗(yàn)證這些假設(shè)。 一般策略：首先假設(shè)一個(gè)可能的目標(biāo)，然后由產(chǎn)生式系統(tǒng)試圖證明此假設(shè)目標(biāo)是否在總數(shù)據(jù)庫中。若在總數(shù)據(jù)庫中，則該假設(shè)目標(biāo)成立；否則，若該假設(shè)為終葉（證

43、據(jù)）節(jié)點(diǎn)，則詢問用戶。若不是，則再假定另一個(gè)目標(biāo)，即尋找結(jié)論部分包含該假設(shè)的那些規(guī)則，把它們的前提作為新的假設(shè)，并力圖證明其成立。這樣反復(fù)進(jìn)行推理，直到所有目標(biāo)均獲證明或者所有路徑都得到測試為止。3.雙向推理 雙向推理的推理策略是同時(shí)從目標(biāo)向事實(shí)推理和從事實(shí)向目標(biāo)推理，并在推理過程中的某個(gè)步驟，實(shí)現(xiàn)事實(shí)與目標(biāo)的匹配。3.6.3產(chǎn)生式系統(tǒng)舉例說明：請同學(xué)們課后認(rèn)真閱讀本部分內(nèi)容，并以此為參考進(jìn)行實(shí)驗(yàn)準(zhǔn)備！思考：規(guī)則演繹系統(tǒng)和產(chǎn)生式系統(tǒng)有哪幾種推理方式?各自的特點(diǎn)為何?3.7 系統(tǒng)組織技術(shù)教學(xué)內(nèi)容：系統(tǒng)組織技術(shù)屬于高級搜索推理技術(shù)，能夠用于求解比較復(fù)雜的系統(tǒng)。本節(jié)簡要介紹三種系統(tǒng)組織技術(shù)：議程表法

44、、黑板法和極小搜索法。教學(xué)重點(diǎn)：系統(tǒng)組織技術(shù)如何實(shí)現(xiàn)模塊之間的合作。教學(xué)難點(diǎn)：無要求。教學(xué)方法：課堂教學(xué)。教學(xué)要求：了解系統(tǒng)組織技術(shù)的基本原理。3.7.1議程表1.定義 議程表(agenda)是一個(gè)系統(tǒng)能夠執(zhí)行的任務(wù)表列。與每個(gè)任務(wù)有關(guān)的有兩件事，即提出該任務(wù)的理由和表示對該任務(wù)是有用的證據(jù)總權(quán)的評價(jià)。2.模塊間的合作 從組織大系統(tǒng)的觀點(diǎn)看，議程表方法的意義在于它允許幾個(gè)獨(dú)立模塊進(jìn)行通訊。其通訊方法是每個(gè)模塊可將支持(或反對)某個(gè)具體任務(wù)的證據(jù)，加到一個(gè)證明選擇該任務(wù)是正確的表中。這樣就使系統(tǒng)能夠選出從各方面都有充分證據(jù)的任務(wù)。雖然各模塊共同使用關(guān)于為什么要執(zhí)行各項(xiàng)任務(wù)的證據(jù)，但一個(gè)模塊并不需

45、要了解其它模塊如何工作，以及它們所包含的知識(shí)。這樣，議程表方法便具有大系統(tǒng)中模塊化的一切優(yōu)點(diǎn)，而無相互隔離的缺點(diǎn)。3.7.2黑板法1.定義 黑板法(the Blackboard Approach)首先是在HEARSAY-語音理解系統(tǒng)中發(fā)展起來的。它的思想比較簡單。整個(gè)系統(tǒng)由一組稱為知識(shí)資源(KS)的獨(dú)立模塊和一塊黑板組成。這里，知識(shí)資源含有系統(tǒng)中專門領(lǐng)域的知識(shí)，而黑板則是一切KS可以訪問的公用數(shù)據(jù)結(jié)構(gòu)。2.模塊間的合作 當(dāng)一個(gè)KS被激發(fā)時(shí)，它檢查當(dāng)時(shí)黑板上的內(nèi)容，并應(yīng)用其知識(shí)產(chǎn)生一個(gè)新的假設(shè)寫到黑板上，直到完成任務(wù)為止。當(dāng)時(shí)間表沒有發(fā)現(xiàn)未解決的活動(dòng)記錄時(shí)，系統(tǒng)便停止執(zhí)行。3.7.3 -極小搜索

46、法1、定義值表示一假設(shè)的級別與參加競爭的最佳假設(shè)的級別之差，提供了一種選擇最有希望假設(shè)的技術(shù)。2、工作過程 一次接受一串輸入，順序地處理，使其形成一個(gè)關(guān)于輸入的統(tǒng)一而相容的解釋。-極小法是這樣來解決這類問題的：在適當(dāng)?shù)臅r(shí)刻，觸發(fā)某KS，然后為它生成所有它認(rèn)為是可能的假設(shè)，并賦給某個(gè)假設(shè)一種級別。由這些級別計(jì)算出的值，表示一假設(shè)的級別與參加競爭的最佳假設(shè)的級別之差。而在該假設(shè)最后導(dǎo)致不相容時(shí)，再考慮參加競爭的另一假設(shè)。 3.8 不確定性推理教學(xué)內(nèi)容：本節(jié)介紹兩種不確定性(uncertainty)，即關(guān)于證據(jù)的不確定性和關(guān)于結(jié)論的不確定性。教學(xué)要點(diǎn)：不確定性如何表示和推理。教學(xué)難點(diǎn)：不確定性的推理。教學(xué)方法：課堂教學(xué)為主。教學(xué)要求：了解不確定性的表示和推理方法。3.8.1關(guān)于證據(jù)的不確定性1.不確定性的表示 一般通過對事實(shí)賦于一個(gè)介于0和1之間的系數(shù)來表示事實(shí)的不確定性。1代表完全確定，0代表完全不確定。這個(gè)系數(shù)被稱為可信度(也有一些專家系統(tǒng)，如MYCIN和EXPERT等，取可信度的范圍為-1到+1)。2.不確定性的處理 當(dāng)規(guī)則具有一個(gè)以上的條件時(shí)，就需要根據(jù)各條件的可信度來求得總條件部分的可信度。已有的方法有兩類：（1）以模糊集理論為基礎(chǔ)的方法按這種方法，把所有條件中最小的可信度作為總條件的可信度。這種方法類似于當(dāng)把幾根繩子連接起來使用時(shí)，總的繩子強(qiáng)度與強(qiáng)度最差的繩子的相