《人工智能及其應(yīng)用知識(shí)》由會(huì)員分享，可在線閱讀，更多相關(guān)《人工智能及其應(yīng)用知識(shí)（114頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),,,*,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),,,*,第二章 知識(shí)表示,,本章主要討論知識(shí)表示問題，介紹7種知識(shí)表示方法：狀態(tài)空間法、問題歸約法、謂詞演算法、語義網(wǎng)絡(luò)法、框架表示、本體技術(shù)、過程表示。　　掌握狀態(tài)空間法、問題歸約法、謂詞演算法、語義網(wǎng)絡(luò)法的要點(diǎn)及其之間的關(guān)系，了解框架表示、本體技術(shù)、過程表示。,,知識(shí)表示的基本概念,,知識(shí)表示,：研究用機(jī)器表示知識(shí)的可行性、有效性的一般方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體，既考慮知識(shí)的存儲(chǔ)又考慮知識(shí)的使用。,,,

2、知識(shí)表示可看成是一組描述事物的約定，以把人類知識(shí)表示成機(jī)器能處理的數(shù)據(jù)結(jié)構(gòu)。,,人工智能系統(tǒng)所關(guān)心的知識(shí),事實(shí),,有關(guān)問題環(huán)境的一些事物的知識(shí)，常以“…是…”的形式出現(xiàn)。如事物的分類、屬性、事物間關(guān)系、科學(xué)事實(shí)、客觀事實(shí)等。如雪是白色的、鳥有翅膀、張三李四是好朋友、這輛車是張三的。,,規(guī)則,有關(guān)問題中與事物的行動(dòng)、動(dòng)作相聯(lián)系的因果關(guān)系知識(shí)，是動(dòng)態(tài)的，常以“如果…那么…”形式出現(xiàn)。,控制,有關(guān)問題的求解步驟、技巧性知識(shí)，告訴怎么做一件事。,元知識(shí),有關(guān)知識(shí)的知識(shí)，是知識(shí)庫中的高層知識(shí)。包括怎樣使用規(guī)則、解釋規(guī)則、校驗(yàn)規(guī)則、解釋程序結(jié)構(gòu)等知識(shí)。,,2.1 狀態(tài)空間法,問題求解,問題求解,(prob

3、lem solving)是個(gè)大課題，它涉及歸約、推斷、決策、規(guī)劃、常識(shí)推理、定理證明和相關(guān)過程的核心概念。,在分析了人工智能研究中運(yùn)用的問題求解方法之后，就會(huì)發(fā)現(xiàn)許多問題求解方法是采用試探搜索方法的。也就是說，這些方法是通過在某個(gè)可能的解空間內(nèi)尋找一個(gè)解來求解問題的。,狀態(tài)空間法,：基于解答空間的問題表示和求解方法，它是以狀態(tài)和算符(operator)為基礎(chǔ)來表示和求解問題的。,,2.1 狀態(tài)空間法,1.問題求解技術(shù)兩個(gè)主要的方面,,(1) 問題的表示：如果描述方法不對(duì)，對(duì)問題求解會(huì)帶來很大的困難；,(2) 求解的方法：采用試探搜索方法。,,2.狀態(tài)空間法三要點(diǎn),,(1)狀態(tài)（state）,(

4、2)算符（operator）,(3)狀態(tài)空間方法,,2.1 狀態(tài)空間法,2.1.1 問題狀態(tài)描述,,1.定義,,狀態(tài),(state)：為描述某類不同事物間的差別而引入的一組最少變量q,0,，q,1,，…，q,n,的有序集合，其矢量形式如下：,Q=[q,0,,q,1,,…,q,n,],T,式中每個(gè)元素q,i,(i=0,1,,n)為集合的分量,稱為狀態(tài)變量,給定每個(gè)分量的一,組值就得到一個(gè)具體的狀態(tài),如,Q,k,=[q,0k,,q,1k,,…,q,nk,],T,式中每個(gè)元素q,i,(i=0,1，…，n)為集合的分量，稱為狀態(tài)變量。,算符,：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。操

5、,作符可為走步、過程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號(hào)或邏輯符號(hào)等。,問題的狀態(tài)空間,(state space)：是一個(gè)表示該問題全部可能狀態(tài)及其關(guān)系,的圖，它包含三種說明的集合，即所有可能的問題初始狀態(tài)集合S、操作符,集合F以及目標(biāo)狀態(tài)集合G?？砂褷顟B(tài)空間記為三元狀態(tài)(S，F(xiàn)，G)。,,2.1 狀態(tài)空間法,2.狀態(tài)空間表示詳釋,,讓我們先用數(shù)碼難題,(puzzle problem),來說明狀態(tài)空間表示的概念。由15個(gè)編有1至15并放在4×4方格棋盤上的可走動(dòng)的棋子組成。棋盤上總有一格是空的，以便可能讓空格周圍的棋子走進(jìn)空格，這也可以理解為移動(dòng)空格。圖中繪出了兩種棋局，即初始棋局和目標(biāo)棋局，它們對(duì)應(yīng)于

6、該下棋問題的初始狀態(tài)和目標(biāo)狀態(tài)。　　如何把初始棋局變換為目標(biāo)棋局呢？問題的解答就是某個(gè)合適的棋子走步序列，如"左移棋子12，下移棋子15，右移棋子4，…"等等。,,,,2.1 狀態(tài)空間法,2.狀態(tài)空間表示詳釋,狀態(tài)空間法：從某個(gè)初始狀態(tài)開始，每次加一個(gè)操作符，遞增的建立起操作符的試驗(yàn)序列，直到達(dá)到目標(biāo)狀態(tài)為止。,尋找狀態(tài)空間的全部過程包括從舊的狀態(tài)描述產(chǎn)生新的狀態(tài)描述，以及此后檢驗(yàn)這些新的狀態(tài)描述，看是否達(dá)到了該目標(biāo)狀態(tài)。對(duì)于最優(yōu)化問題找到任一目標(biāo)狀態(tài)是不夠的，必須按某個(gè)準(zhǔn)則實(shí)現(xiàn)最優(yōu)化路徑。P26,完成目標(biāo)狀態(tài)的三件事：,１狀態(tài)描述方式，特別是初始狀態(tài)描述；,２操作符集合及其對(duì)狀態(tài)描述的作用

7、；,３目標(biāo)狀態(tài)的特性。,,2.1 狀態(tài)空間法,2.1.2 狀態(tài)圖示法,,為,了對(duì)狀態(tài)空間圖有更深入的了解，這里介紹一下圖論中的幾個(gè)術(shù)語和圖的正式表示法。,1.圖論中的幾個(gè)術(shù)語,節(jié)點(diǎn),(node)：,圖形上的匯合點(diǎn)，用來表示狀態(tài)、事件和時(shí)間關(guān)系的匯合，也可用來指示通路的匯合；,弧線,(arc)：,節(jié)點(diǎn)間的連接線；,,有向圖,(directed graph)：,一對(duì)節(jié)點(diǎn)用弧線連接起來，從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)。,后繼節(jié)點(diǎn),(descendant node)與,父輩節(jié)點(diǎn),(parent node)：如果某條弧線從節(jié)點(diǎn)n,i,指向節(jié)點(diǎn)n,j,，那么節(jié)點(diǎn)n,j,就叫做節(jié)點(diǎn)n,i,的后繼節(jié)點(diǎn)或后裔，而節(jié)點(diǎn)

8、n,i,叫做節(jié)點(diǎn)n,j,的父輩節(jié)點(diǎn)或祖先。,,2.1,狀,狀態(tài),空,空間,法,法,狀,狀態(tài),圖,圖示,法,法,1.,圖,圖論,中,中的,幾,幾個(gè),術(shù),術(shù)語,路徑：某,個(gè),個(gè)節(jié),點(diǎn),點(diǎn)序,列,列(n,i1,,n,i2,,…,n,ik,)當(dāng)j=2，3，,…,…，k時(shí),，,，如,果,果對(duì),于,于每,一,一個(gè)n,i,，,j-1,都有,一,一個(gè),后,后繼,節(jié),節(jié)點(diǎn)n,ij,存在,，,，那,么,么就,把,把這,個(gè),個(gè)節(jié),點(diǎn),點(diǎn)序,列,列叫,做,做從,節(jié),節(jié)點(diǎn)n,i1,至節(jié),點(diǎn),點(diǎn)n,ik,的長,度,度為k的,路,路徑,。,。,代價(jià)：用c(n,i,,n,j,)來,表,表示,從,從節(jié),點(diǎn),點(diǎn)n,i,指向,節(jié),

9、節(jié)點(diǎn)n,j,的那,段,段弧,線,線的,代,代價(jià),。,。兩,節(jié),節(jié)點(diǎn),間,間路,徑,徑的,代,代價(jià),等,等于,連,連接,該,該路,徑,徑上,各,各節(jié),點(diǎn),點(diǎn)的,所,所有,弧,弧線,代,代價(jià),之,之和,。,。,顯式,表,表示：各,節(jié),節(jié)點(diǎn),及,及其,具,具有,代,代價(jià),的,的弧,線,線由,一,一張,表,表明,確,確給,出,出。,此,此表,可,可能,列,列出,該,該圖,中,中的,每,每一,節(jié),節(jié)點(diǎn),、,、它,的,的后,繼,繼節(jié),點(diǎn),點(diǎn)以,及,及連,接,接弧,線,線的,代,代價(jià),。,。,隱式,表,表示：節(jié),點(diǎn),點(diǎn)的,無,無限,集,集合{s,i,}作,為,為起,始,始節(jié),點(diǎn),點(diǎn)是,已,已知,的,的。,后

10、,后繼,節(jié),節(jié)點(diǎn),算,算符,Γ,Γ也,是,是已,知,知的,，,，它,能,能作,用,用于,任,任一,節(jié),節(jié)點(diǎn),以,以產(chǎn),生,生該,節(jié),節(jié)點(diǎn),的,的全,部,部后,繼,繼節(jié),點(diǎn),點(diǎn)和,各,各連,接,接弧,線,線的,代,代價(jià),。,。,,2.1,狀,狀態(tài),空,空間,法,法,狀,狀態(tài),圖,圖示,法,法,2.,圖,圖的,顯,顯式,和,和隱,式,式表,示,示,一,一,個(gè),個(gè)圖,可,可由,顯,顯式,說,說明,也,也可,由,由隱,式,式說,明,明。,顯,顯然,，,，顯,式,式說,明,明對(duì),于,于大,型,型的,圖,圖是,不,不切,實(shí),實(shí)際,的,的，,而,而對(duì),于,于具,有,有無,限,限節(jié),點(diǎn),點(diǎn)集,合,合的,圖,圖

11、則,是,是不,可,可能,的,的。,此,此,外,外，,引,引入,后,后繼,節(jié),節(jié)點(diǎn),算,算符,的,的概,念,念是,方,方便,的,的。,后,后繼,節(jié),節(jié)點(diǎn),算,算符,Γ,Γ也,是,是已,知,知的,，,，它,能,能作,用,用于,任,任一,節(jié),節(jié)點(diǎn),以,以產(chǎn),生,生該,節(jié),節(jié)點(diǎn),的,的全,部,部后,繼,繼節(jié),點(diǎn),點(diǎn)和,各,各連,接,接弧,線,線的,代,代價(jià),把,把后,繼,繼算,符,符應(yīng),用,用于{si},的,的成,員,員和,它,它們,的,的后,繼,繼節(jié),點(diǎn),點(diǎn)以,及,及這,些,些后,繼,繼節(jié),點(diǎn),點(diǎn)的,后,后繼,節(jié),節(jié)點(diǎn),，,，如,此,此無,限,限制,地,地進(jìn),行,行下,去,去，,最,最后,使,使得,

12、由,由Γ,和,和{si}所,規(guī),規(guī)定,的,的隱,式,式圖,變,變?yōu)?顯,顯示,圖,圖。,問題,的,的表,示,示對(duì),求,求解,工,工作,量,量有,很,很大,的,的影,響,響。,人,人們,顯,顯然,希,希望,有,有較,小,小的,狀,狀態(tài),空,空間,表,表示,。,。許,多,多似,乎,乎很,難,難的,問,問題,，,，當(dāng),表,表示,適,適當(dāng),時(shí),時(shí)就,可,可能,具,具有,小,小而,簡,簡單,的,的狀,態(tài),態(tài)空,間,間。,,2.1,狀,狀態(tài),空,空間,法,法,狀,狀態(tài),圖,圖示,法,法,,根據(jù),問,問題,狀,狀態(tài),、,、操,作,作符,和,和目,標(biāo),標(biāo)條,件,件選,擇,擇各,種,種表,示,示，,是,是高,效

13、,效率,問,問題,求,求解,必,必須,的,的。,,各種,問,問題,都,都可,以,以用,狀,狀態(tài),空,空間,加,加以,表,表示,，,，并,用,用狀,態(tài),態(tài)空,間,間搜,索,索法,來,來求,解,解。,,2.1,狀,狀態(tài),空,空間,法,法,狀,狀態(tài),圖,圖示,法,法,1.產(chǎn),生,生式系,統(tǒng),統(tǒng),（ProductionSystem,）,）,·一個(gè)總,數(shù),數(shù)據(jù)庫,(global database),：它含,有,有與具,體,體任務(wù),有,有關(guān)的,信,信息；,隨,隨著應(yīng),用,用情況,的,的不同,，,，這些,數(shù),數(shù)據(jù)庫,可,可能小,得,得像數(shù),字,字矩陣,那,那樣簡,單,單，或,許,許大得,如,如檢索,文,文件

14、結(jié),構(gòu),構(gòu)那么,復(fù),復(fù)雜。,·一套規(guī),則,則：它對(duì),數(shù),數(shù)據(jù)庫,進(jìn),進(jìn)行操,作,作運(yùn)算,。,。每條,規(guī),規(guī)則由,左,左右兩,部,部分組,成,成，左,部,部鑒別,規(guī),規(guī)則的,適,適用性,或,或先決,條,條件，,右,右部描,述,述規(guī)則,應(yīng),應(yīng)用時(shí),所,所完成,的,的動(dòng)作,。,。用規(guī),則,則來改,變,變數(shù)據(jù),庫,庫就象,用,用算符,來,來改變,狀,狀態(tài)一,樣,樣。,·一個(gè)控,制,制策略：它確,定,定應(yīng)該,采,采用哪,一,一條適,用,用規(guī)則,，,，而且,當(dāng),當(dāng)數(shù)據(jù),庫,庫的終,止,止條件,滿,滿足時(shí),，,，就停,止,止計(jì)算,。,?？刂?策,策略由,控,控制系,統(tǒng),統(tǒng)選擇,和,和確定,。,。,,推銷員,

15、旅,旅行問,題,題,總數(shù)據(jù),庫,庫：到,目,目前為,止,止所訪,問,問的城,市,市；,規(guī)則對(duì),應(yīng),應(yīng)于決,策,策：即,下,下一步,走,走向城,市,市Ａ，,下,下一步,走,走向城,市,市Ｂ，,…,…，下,一,一步走,向,向城市,Ｅ,Ｅ，一,條,條規(guī)則,必,必須能,把,把某個(gè),數(shù),數(shù)據(jù)庫,變,變?yōu)橐?個(gè),個(gè)合法,數(shù),數(shù)據(jù)庫,，,，否則,不,不適應(yīng),這,這個(gè)數(shù),據(jù),據(jù)庫；,任一以,Ａ,Ａ為起,點(diǎn),點(diǎn)和終,點(diǎn),點(diǎn)，并,出,出現(xiàn)所,有,有其它,城,城市的,總,總數(shù)據(jù),庫,庫，都,滿,滿足終,止,止條件,．,．,,2.1,狀,狀態(tài),空,空間法,狀,狀態(tài)圖,示,示法,2.狀,態(tài),態(tài)空間,表,表示舉,例,例例

16、2,猴,猴子和,香,香蕉問,題,題(monkeyandbanana problem),在,在一,個(gè),個(gè)房間,內(nèi),內(nèi)有一,只,只猴子(可把,這,這只猴,子,子看做,一,一個(gè)機(jī),器,器人),、,、一個(gè),箱,箱子和,一,一束香,蕉,蕉。香,蕉,蕉掛在,天,天花板,下,下方，,但,但猴子,的,的高度,不,不足以,碰,碰到它,。,。那么,這,這只猴,子,子怎樣,才,才能摘,到,到香蕉,呢,呢?圖2.4,表,表示出,猴,猴子、,香,香蕉和,箱,箱子在,房,房間內(nèi),的,的相對(duì),位,位置。,猴子和,香,香蕉...,用一個(gè),四,四元表,列,列(W,X,Y,Z)來表,示,示這個(gè),問,問題,的狀態(tài),，,，,其,其中

17、W－猴,子,子的水,平,平位置X－當(dāng),猴,猴子在,箱,箱子頂,上,上時(shí)取X=1,；,；否則,取,取X=0Y－箱,子,子的水,平,平位置Z－當(dāng),猴,猴子摘,到,到香蕉,時(shí),時(shí)取Z=1；,否,否則取Z=0,,,,,圖 2.4,猴,猴子和,香,香蕉問,題,題,,2.1,狀,狀態(tài),空,空間法,狀,狀態(tài)圖,示,示法,這個(gè)問,題,題中的,操,操作(,算,算符),如,如下：,(1)goto(U),猴子走,到,到水平,位,位置U,，,，或者,用,用產(chǎn)生,式,式規(guī)則,表,表示為,：,：,(W，0，Y,，,，z),?,(U，0，Y,，,，z)(2.3),即應(yīng)用,操,操作,goto(U),，能把,狀,狀態(tài),(W，0

18、，Y,，,，z),變換為,狀,狀態(tài),(U，0，Y,，,，z),。,(2)pushbox(V),猴子把,箱,箱子推,到,到水平,位,位置V,，,，即有,(W，0，W,，,，z),?,(V，0，V,，,，z)(2.4,),應(yīng)當(dāng)注,意,意的是,，,，要應(yīng),用,用算符,pushbox(V)，,就要求,產(chǎn),產(chǎn)生式,規(guī),規(guī)則的,左,左邊，,猴,猴子與,箱,箱子必,須,須在同,一,一位置,上,上，并,且,且，猴,子,子不是,在,在箱子,頂,頂上。,這,這種強(qiáng),加,加于操,作,作的適,用,用性條,件,件，叫,做,做產(chǎn)生,式,式規(guī)則,的,的先決,條,條件。,,2.1,狀,狀態(tài),空,空間法,狀,狀態(tài)圖,示,示法,

19、這個(gè)問,題,題中的,操,操作(,算,算符),如,如下：,(3)climbbox,猴子爬,上,上箱頂,，,，即有,(W，0，W,，,，z),?,(W，1，W,，,，z)(2.5),在應(yīng)用,算,算符climbbox時(shí)也,必,必須注,意,意到，,猴,猴子和,箱,箱子應(yīng),當(dāng),當(dāng)在同,一,一位置,上,上，而,且,且猴子,不,不在箱,頂,頂上,。,。,(4)grasp,猴,猴子摘,到,到香蕉,，,，即有,(c,1,c,0),?,(c,1,c,1)(2.6)其,中,中，c,是,是香蕉,正,正下方,的,的地板,位,位置，,在,在應(yīng)用,算,算符grasp時(shí)，,要,要求猴,子,子和箱,子,子都在,位,位置c,上,

20、上，并,且,且猴子,已,已在箱,子,子頂上,。,,2.1,狀,狀態(tài)空間,法,法,對(duì)于規(guī)則(2)，,只,只有當(dāng)算,符,符pushbox(V),的先決條,件,件，即猴,子,子與箱子,在,在同一位,置上而且,猴,猴子不在,箱,箱頂上這,些,些條件得,到滿足時(shí),，,，算符pushbox(V)才是適,用,用,的。這一,操,操作算符,的,的作用是,猴,猴子把箱,子推到位,置,置V。在,這,這一表示,中,中，目標(biāo),狀態(tài)的集,合,合可由任,何,何最后元,素,素為1的,表列來描,述,述。令初,始,始狀態(tài)為(a,0,b,0),這,這時(shí)，goto(U)是,唯,唯一適用,的,的操作，,并導(dǎo)致下,一,一狀態(tài)(U,0,b

21、,0),。,?，F(xiàn)在有3,個(gè)適用的,操,操作，即goto(U)，,pushbox(V)和climbbox(,若,若U=b)。,猴子和香,蕉,蕉問題的,狀,狀態(tài)空間,圖,圖,,2.2,問,問題歸約,法,法,2.2.1 問題,歸,歸約描述,先把問題,分,分解為子,問,問題和子-子問題,，,，然后解,決,決較小的,問,問題。對(duì),該,該問題的,某,某個(gè)具體,子,子集的解,答,答就意味,著,著對(duì)原始,問,問題的一,個(gè),個(gè)解答。,問,問題歸約,表,表示的組,成,成部分：,一個(gè)初始,問,問題描述,；,；,一套把問,題,題變換為,子,子問題的,操,操作符；,一套本原,問,問題描述,。,。,,問題歸約,的,的實(shí)質(zhì)

22、：,從,從目標(biāo)(,要,要解決的,問,問題)出,發(fā),發(fā)逆向推,理,理，建立,子,子問題以,及,及子問題,的,的子問題,，,，直至最,后,后把初始,問,問題歸約,為,為一個(gè)平,凡,凡的本原,問,問題集合,。,。,,2.2,問,問題歸約,法,法,2.2.1 問題,歸,歸約描述,１梵塔難,題,題,有3個(gè)柱,子,子(1，2和3),和,和3個(gè)不,同,同尺寸的,圓,圓盤（A,，,，B和C,）,）。在每,個(gè),個(gè)圓盤的,中,中心有一,個(gè),個(gè)孔，所,以,以圓盤可,以,以堆疊在,柱,柱子上。,最,最初，3,個(gè),個(gè)圓盤都,堆,堆在柱子1上：最,大,大的圓盤C在底部,，,，最小的,圓,圓盤A在,頂,頂部。要,求,求把所

23、有,圓,圓盤都移,到,到柱子3,上,上，每次,只,只許移動(dòng),一,一個(gè)，而,且,且只能先,搬,搬動(dòng)柱子,頂,頂部的圓,盤,盤，還不,許,許把尺寸,較,較大的圓,盤,盤堆放在,尺,尺寸較小,的,的圓盤上,。,。這個(gè)問,題,題的初始,配,配置和目,標(biāo),標(biāo)配置如,圖,圖2.6,所,所示。,,2.2,問,問題歸約,法,法,解題過程,：,：,將原始問,題,題歸約為,一,一個(gè)較簡,單,單問題集,合,合，要把,所,所有圓盤,都,都移至柱,子,子3，我,們,們必須首,先,先把圓盤C移至柱,子,子3；而,且,且在移動(dòng),圓,圓盤C至,柱,柱子3之,前,前，要求,柱,柱子3必,須,須是空的,。,。只有在,移,移開圓盤

24、A和B之,后,后，才能,移,移動(dòng)圓盤C；而且,圓,圓盤A和B最好不,要,要移至柱,子,子3，否,則,則就不能,把,把圓盤C,移,移至柱子3。因此,，,，首先應(yīng),該,該把圓盤A和B移,到,到柱子2,上,上。然后,才,才能夠進(jìn),行,行關(guān)鍵的,一,一步，把,圓,圓盤C從,柱,柱子1移,至,至柱子3,，,，并繼續(xù),解,解決難題,的,的其余部,分,分。,將原始難,題,題歸約（,簡,簡化）為,下,下列子難,題,題：移動(dòng),圓,圓盤A和B至柱子2的雙圓,盤,盤難題，,如,如圖(a)所示。,,2.2,問,問題歸約,法,法,圖 2.7 梵塔,問,問題解答(a),,圖 2.8 梵塔,問,問題解答(b),圖 2.9

25、梵塔,問,問題解答(c),,2.2,問,問題歸約,法,法,梵塔問題,歸,歸約圖：,子,子問題2,可,可作為本,原,原問題考,慮,慮，因?yàn)?它,它的解只,包,包含一步,移,移動(dòng)。應(yīng),用,用一系列,相,相似的推,理,理，子問,題,題1和子,問,問題3也,可,可被歸約,為,為本原問,題,題，如圖2.10,所,所示。這,種,種圖式結(jié),構(gòu),構(gòu)，叫做,與,與或圖(AND/OR graph)。它,能,能有效地,說,說明如何,由,由問題歸,約,約法求得,問,問題的解,答,答。,梵塔問題,歸,歸約圖,,2.2,問,問題歸約,法,法,2.2.1 問題,歸,歸約描述,２,問題歸約,描,描述,問題歸約,方,方法應(yīng)用

26、,算,算符把問,題,題描述變,換,換為子問,題,題描述，,問,問題描述,可,可以用多,種,種數(shù)據(jù)結(jié),構(gòu),構(gòu)形式，,包,包括表列,、,、樹、字,符,符串、矢,量,量、數(shù)組,等,等。梵塔,問,問題采用,包,包含兩個(gè),數(shù),數(shù)列的表,列,列來描述,[(113),,（,（333)]表示,把,把配置（113）,變,變換為配,置,置（333）。,,用狀態(tài)空,間,間表示的,三,三元組合,（,（S，F(xiàn),，,，G）來,規(guī),規(guī)定與描,述,述問題，,有,有關(guān)子問,題,題可以當(dāng),作,作狀態(tài)空,間,間中的兩,個(gè),個(gè)一定的,“,“腳踏石,”,”之間尋,找,找路徑來,辨,辨別。梵,塔,塔問題中,的,的子問題[（111）=>,

27、（,（122,）,）]，[（122）=>,（,（322,）,）]，[（322）=>,（,（333,）,）]，規(guī),定,定了最后,的,的路徑將,要,要通過“,腳,腳踏石”,狀,狀態(tài)（122）和,（,（322,）,）。,,2.2,問,問題歸約,法,法,2.2.2 與或,圖,圖表示,與圖、或,圖,圖、與或,圖,圖：,一般地，,我,我們用一,個(gè),個(gè)類似圖,的,的結(jié)構(gòu)來,表,表示把問,題,題歸約為,后,后繼問題,的,的替換集,合,合，這種,結(jié),結(jié)構(gòu)圖叫,做,做問題歸,約,約圖，或,叫,叫與或圖,。,。如下圖,所,所示:,（引入附,加,加節(jié)點(diǎn)使,含,含有一個(gè),以,以上后繼,問,問題的每,個(gè),個(gè)集合能,夠,夠

28、聚集在,它,它們各自,的,的父輩節(jié),點(diǎn),點(diǎn)之下。,）,）,子問題替,換,換集合結(jié),構(gòu),構(gòu)圖,與或圖,,2.2,問,問題歸約,法,法,2.2.2 問題,歸,歸約描述,一些關(guān)于,與,與或圖的,術(shù),術(shù)語：,終葉節(jié)點(diǎn),：,對(duì)應(yīng)于原,問,問題的本,原,原節(jié)點(diǎn)。,或節(jié)點(diǎn),：,只要解決,某,某個(gè)問題,就,就可解決,其,其父輩問,題,題的節(jié)點(diǎn),集,集合，如,（,（M，N,，,，H）。,與節(jié)點(diǎn),：,只有解決所,有,有子問題，,才,才能解決其,父,父輩問題的,節(jié),節(jié)點(diǎn)集合，,如,如（B,C)和（D,E,F）各,個(gè),個(gè)結(jié)點(diǎn)之間,用,用一端小圓,弧,弧連接標(biāo)記,。,。,,2.2 問,題,題歸約法,問,問題歸約,描,描

29、述,與或圖,：,由與節(jié)點(diǎn)及,或,或節(jié)點(diǎn)組成,的,的結(jié)構(gòu)圖。,可解節(jié)點(diǎn)的,一,一般定義：,(1),終葉節(jié)點(diǎn)是,可,可解節(jié)點(diǎn)(,因,因?yàn)樗?們與本原問,題,題相關(guān)連),。,。,(2) 如,果,果某個(gè)非終,葉,葉節(jié)點(diǎn)含有,或,或后,繼節(jié)點(diǎn)，那,么,么只要當(dāng)其,后,后繼節(jié)點(diǎn),至少有一個(gè),是,是可解的時(shí),，,，此非終,葉節(jié)點(diǎn)才是,可,可解的。,(3) 如,果,果某個(gè)非終,葉,葉節(jié)點(diǎn)含有,與,與,后繼節(jié)點(diǎn)，,那,那么只有當(dāng),其,其后繼節(jié),點(diǎn)全部為可,解,解時(shí)，此非,終,終葉節(jié)點(diǎn),才是可解的,。,。,圖 2.15 與或圖,例,例子,,2.2 問,題,題歸約法,問,問題歸約描,述,述,不可解節(jié)點(diǎn),的,的一般定

30、義:,(1) 沒,有,有后裔的非,終,終葉節(jié)點(diǎn)為,不,不可解節(jié)點(diǎn),。,。,(2) 如,果,果某個(gè)非終,葉,葉節(jié)點(diǎn)含有,或,或后繼節(jié)點(diǎn),，,，那么只有,當(dāng),當(dāng)其全部后,裔,裔為不可解,時(shí),時(shí)，此非終,葉,葉節(jié)點(diǎn)才是,不,不可解的。,(3) 如,果,果某個(gè)非終,葉,葉節(jié)點(diǎn)含有,與,與后繼節(jié)點(diǎn),，,，那么只要,當(dāng),當(dāng)其后裔至,少,少有一個(gè)為,不,不可解時(shí)，,此,此非終葉節(jié),點(diǎn),點(diǎn)才是不可,解,解的。,,2.2 問,題,題歸約法,問,問題歸約,描,描述,與或圖構(gòu)成,規(guī),規(guī)則(1) 與,或,或圖中的每,個(gè),個(gè)節(jié)點(diǎn)代表,一,一個(gè)要解決,的,的單一問題,或,或問題集合,。,。圖中所含,起,起始節(jié)點(diǎn)對(duì),應(yīng),應(yīng)

31、于原始問,題,題。,(2) 對(duì),應(yīng),應(yīng)于本原問,題,題的節(jié)點(diǎn)，,叫,叫做終葉節(jié),點(diǎn),點(diǎn)，它沒有,后,后裔。,(3) 對(duì),于,于把算符應(yīng),用,用于問題A,的,的每種可能,情,情況，都把,問,問題變換為,一,一個(gè)子問題,集,集合；有向,弧,弧線自A,指,指向后繼節(jié),點(diǎn),點(diǎn)表示所求,得,得的子,問題集合，,如,如下圖所示,，,，把問題A,歸,歸約為3個(gè),不,不同,的子問題集,合,合N，M，H(或節(jié)點(diǎn))。,圖 2.16 與或樹,,2.2 問,題,題歸約法,問,問題歸約,描,描述,與或圖構(gòu)成,規(guī),規(guī)則,(4) 一,般,般對(duì)于代表,兩,兩個(gè)或兩個(gè),以,以上子問題,集,集合的每個(gè),節(jié),節(jié)點(diǎn)，有向,弧,弧線從

32、此節(jié),點(diǎn),點(diǎn)指向此子,問,問題集合中,的,的各個(gè)節(jié)點(diǎn),。,。由于只有,當(dāng),當(dāng)集合中所,有,有的項(xiàng)都有,解,解時(shí)，這個(gè),子,子問題的集,合,合才能獲得,解,解答，所以,這,這些子問題,節(jié),節(jié)點(diǎn)叫做與,節(jié),節(jié)點(diǎn)。,(5) 在,特,特殊情況下,，,，當(dāng)只有一,個(gè),個(gè)算符可應(yīng),用,用于問題A,，,，而且這個(gè),算,算符產(chǎn)生具,有,有一個(gè)以上,子,子問題的某,個(gè),個(gè)集合時(shí)，,由,由上述規(guī)則,3和規(guī)則4,所,所產(chǎn)生的圖,可,可以得到簡,化,化。,因此，代表,子,子問題集合,的,的中間或節(jié),點(diǎn)可以被略,去,去，如右圖,所,所示。,圖 2.16 與或樹,,2.3謂詞邏輯法,謂,謂詞演算,（,（Predicate

33、Calculus）1.,語,語法和語義(Syntax &Semantics),謂詞邏輯的,基,基本組成部,分,分：謂詞符,號(hào),號(hào)、變量符,號(hào),號(hào)、函數(shù)符,號(hào),號(hào)和常量符,號(hào),號(hào)，并用圓,括,括號(hào)、方括,號(hào),號(hào)、花括號(hào),和,和逗號(hào)隔開,，,，表示論域,內(nèi),內(nèi)的關(guān)系。,原子公式(atomic formulas)由若干謂,詞,詞符號(hào)和項(xiàng),組,組成的謂詞,演,演算。原子,公,公式是謂詞,演,演算基本積,木,木塊。,例如，要表,示,示＂機(jī)器人(ROBOT)在１號(hào),房,房間(r1)內(nèi)＂，如,圖,圖2.19,所,所示，可以,應(yīng),應(yīng)用原子公,式,式:,,2.3謂詞邏輯法,謂,謂詞演算,（,（Predicate

34、Calculus）1.語法和,語,語義(Syntax& Semantics)當(dāng)機(jī)器人ROBOT移,到,到房間r2,時(shí),時(shí)，原子公,式,式可以表示,為,為：,INROOM (ROBOT,r2),這兩個(gè)原子,公,公式的通用,形,形式就是,,,,又如,“李,的,的母親和他,的,的父親結(jié)婚,”,”這句話的,原,原子公式表,示,示,如下：,,2.3謂詞邏輯法,謂,謂詞演算,（,（PredicateCalculus）2.連詞,和,和量詞(Connective& Quantifiers),(1) 連,詞,詞　　與,·,·合?。╟onjunction,）,）　合取就,是,是用連詞∧,把,把幾個(gè)公式,連,連接

35、起來而,構(gòu),構(gòu)成的公式,。,。合取項(xiàng)是,合,合取式的每,個(gè),個(gè)組成部分,。,。,例：LIKE(I，MUSIC),∧,∧LIKE(I，PAINTING),(我喜愛音,樂,樂和繪畫。),,,2.3謂詞邏輯法,謂,謂詞演算,（,（PredicateCalculus）2.連詞,和,和量詞(Connective& Quantifiers),或·析?。╠isjunction） 析取,就,就是用連詞,∨,∨把幾個(gè)公,式,式連接起來,而,而構(gòu)成的公,式,式。析取項(xiàng),是,是析取式的,每,每個(gè)組成部,分,分。,例：PLAYS(LILI,，,，BASKETBALL),∨,∨PLAYS(LILI，F(xiàn)OOTBALL),

36、(李,力,力打,籃,籃球,或,或踢,足,足球,。,。),,2.3謂詞,邏,邏輯,法,法,謂,謂詞,演,演算,（,（PredicateCalculus）2.,連,連詞,和,和量,詞,詞(Connective&Quantifiers),(1),連,連詞,蘊(yùn),蘊(yùn),涵,涵"=>",表,表示"如,果,果-,那,那么"的,語,語句,。,。用,連,連詞=>,連,連接,兩,兩個(gè),公,公式,所,所構(gòu),成,成的,公,公式,叫,叫做,蘊(yùn),蘊(yùn)涵,。,。,IF=>THEN,前項(xiàng),后,后項(xiàng),(左,式,式)(右,式,式),例：RUNS(LIUHUA，F(xiàn)ASTEST)=>TWINS(LIUHUA,，,，CHAMPION),(

37、如,果,果劉,華,華跑,得,得最,快,快，,那,那么,他,他取,得,得冠,軍,軍),,非（NOT）,表,表,示,示否,定,定，,～,～、,┑,┑均,可,可表,示,示否,定,定。,例：,～,～I(xiàn)NROOM(ROBOT，r2),(機(jī),器,器人,不,不在2號(hào),房,房間,內(nèi),內(nèi)。),,2.3謂詞,邏,邏輯,法,法,謂,謂詞,演,演算,（,（PredicateCalculus）2.,連,連詞,和,和量,詞,詞(Connective&Quantifiers),(2),量,量詞,全稱,量,量詞(UniversalQuantifier),若,若,一,一個(gè),原,原子,公,公式P(x),，,，對(duì),于,于所,有,有

38、可,能,能變,量,量x,都,都具,有,有T,值,值，,則,則用(x)P(x)表,示,示。,例：(x)[ROBOT(x)=>COLOR(x,GRAY)],(所,有,有的,機(jī),機(jī)器,人,人都,是,是灰,色,色的,）,）,(x)[Student(x)=>Uniform(x,Color)],(所,有,有學(xué),生,生都,穿,穿彩,色,色制,服,服),,2.3謂詞,邏,邏輯,法,法,謂,謂詞,演,演算,（,（PredicateCalculus）2.,連,連詞,和,和量,詞,詞(Connective&Quantifiers),(2),量,量詞,存在,量,量詞(ExistentialQuantifier),若,

39、若,一,一個(gè),原,原子,公,公式P(x),，,，至,少,少有,一,一個(gè),變,變?cè)猉，,可,可使P(X),為,為T,值,值，,則,則用(x)P(x)表,示,示。,例：(x)INROOM(x,r1),(1,號(hào),號(hào)房,間,間內(nèi),有,有個(gè),物,物體),量化,變,變?cè)?QuantifiedVariables),被,被,量,量化,了,了的,變,變?cè)獂-,約,約束,變,變量,。,。,,2.3謂詞,邏,邏輯,法,法,謂,謂詞,公,公式,（,（PredicateFormulas）,1.,謂,謂詞,公,公式,的,的定,義,義原子,謂,謂詞,公,公式：用P(x1,x2,,…,…,xn)表,示,示一,個(gè),個(gè)n,元,元

40、謂,詞,詞公,式,式，,其,其中P為n元,謂,謂詞,，,，x1,x2,…xn,為,為客,體,體變,量,量或,變,變?cè)?。,。通,常,常把P(x1,x2,,…,…,xn)叫,做,做謂,詞,詞演,算,算的,原,原子,公,公式,，,，或,原,原子,謂,謂詞,公,公式,。,。分子謂詞公,式,式：可以用連,詞,詞把原子謂,詞,詞公式組成,復(fù),復(fù)合謂詞公,式,式，并把它,叫,叫做分子謂,詞,詞公式。合適公式(WFF,well-formed formulas)的遞歸定,義,義：(1) 原,子,子謂詞公式,是,是合適公式,。,。　　(2) 若A,為,為合適公式,，,，則～A也,是,是一個(gè)合適,公,公式。(3

41、),若,若A和B都,是,是合適公式,，,，則(A∧B),(A,∨,∨B),(A=>B), (A←,→,→B)也都,是,是合適公式,。,。　　(4) 若A,是,是合適公式,，,，x為A中,的,的自由變?cè)?，,，則(x)A,(x)A,都,都是合適公,式,式。(5) 只,有,有按上述規(guī),則,則(1)至(4)求得,的,的那些公式,，,，才是合適,公,公式。,,2.3謂詞邏輯法,謂,謂詞公式,（,（PredicateFormulas）1.謂詞公,式,式的定義,例題：,"對(duì)于所有,的,的x，如果x是整數(shù)，,則,則x或?yàn)檎?的,的或者為負(fù),的,的。",( x)(I(x)=>(P(x)∨N(x))),I

42、(x)表,示,示"x是整,數(shù),數(shù)"，P(x)表示"x是正數(shù)",，,，N(x),表,表示"x是,負(fù),負(fù)數(shù)"。,,2.3謂詞邏輯法,謂,謂詞公式,（,（PredicateFormulas）2.合適公,式,式的性質(zhì),合適公式的,真,真值：p36,表2-1,真,真值表,,2.3謂詞邏輯法,置,置換與合,一,一（Substitution& Unification）,1.置換,在謂詞邏輯,中,中，有些推,理,理規(guī)則可應(yīng),用,用于一定的,合,合適公式和,合,合適公式集,，,，以產(chǎn)生新,的,的合適公式,。,。一個(gè)重要,的,的推理規(guī)則,是,是假元推理,，,，這就是由,合,合適公式W1和W1=>W2產(chǎn)生,合,合適

43、公式W2的運(yùn)算。,另,另一個(gè)推理,規(guī),規(guī)則叫做全,稱,稱化推理，,它,它是由合適,公,公式(x)W(x)產(chǎn)生合適,公,公式W(A)，其中A,為,為任意常量,符,符號(hào)。,假,假元推理,：,：,,,全稱化推理,：,：,,綜合推理：,,,2.3謂詞邏輯法,置,置換與合,一,一（Substitution& Unification）,1.置換,置,置換：,用,用項(xiàng)(A),替,替換函數(shù)表,達(dá),達(dá)式中的變,量,量(x)，,記,記為ES，,即,即表示一個(gè),表,表達(dá)式E(Expression)用一個(gè)置,換,換S(Substitution)而得到的,表,表達(dá)式的置,換,換。例1,表,表達(dá)式P[x,f(y),B]

44、的4個(gè)置換為,s1={z/x,w/y},s2={A/y},s3={q(z)/x,A/y},s4={c/x,A/y},我們用Es,來,來表示一個(gè),表,表達(dá)式E用,置,置換s所得,到,到的表達(dá)式,的,的置換。于,是,是，我們可,得,得到P[x,f(y),B]的4,個(gè),個(gè)置換的例,，,，如下：,P[x,f(y),B]s1=P[z,f(w),B],P[x,f(y),B]s2=P[x,f(A),B],P[x,f(y),B]s3=P[q(z),f(A),B],P[x,f(y),B]s4=P[c,f(A),B],,2.3謂詞邏輯法,置,置換與合,一,一（Substitution& Unification）2

45、.性質(zhì),可結(jié)合律(LS1)S2=L(S1S2)(L表,示,示一表達(dá)式),(S1S2)S3=S1(S2S3),置換是可結(jié),合,合的。用s1s2表示,兩,兩個(gè)置換s1和s2的,合,合成。L表,示,示一表達(dá)式,，,，則有(Ls1)s2=L(s1s2),以及(s1s2)s3=s1(s2s3),即,即用s1和s2相,繼,繼作用于表,達(dá),達(dá)式L是同,用,用s1s2,作,作用于L一,樣,樣的。一,般,般說來，置,換,換是不可交,換,換的，即,s1s2≠s2s1,,3.合一(unification)P38,合一：尋找,項(xiàng),項(xiàng)對(duì)變量的,置,置換，以使,兩,兩表達(dá)式一,致,致。,可,可合一：如,果,果一個(gè)置換s

46、作用于表,達(dá),達(dá)式集{Ei}的每個(gè),元,元素，則我,們,們用{Ei}s來表示,置,置換例的集,。,。我們稱表,達(dá),達(dá)式集{Ei}是可合,一,一的。,,2.3謂詞邏輯法,置,置換與合,一,一（Substitution& Unification）,例:表達(dá)式,集,集P[x,f(y),B], P[x,f(B),B],的,的合一者為:,s={A/x,B/y},因?yàn)镻[x,f(y),B]s=P[x,f(B),B]=P[A,f(B),B],即s使表達(dá),式,式成為單一,形,形式:,P[A,f(B),B],但最簡,單,單的合一者,為,為:,s’={B/Y},,2.4 語,義,義網(wǎng)絡(luò)法,語義網(wǎng)絡(luò)是1968年Qu

47、ilian在研究,人,人類聯(lián)想記,憶,憶時(shí)提出的,心,心理學(xué)模型,，,，認(rèn)為記憶,是,是由概念間,的,的聯(lián)系來實(shí),現(xiàn),現(xiàn)的。1972年，Simmons首先將語,義,義網(wǎng)絡(luò)表示,法,法用于自然,語,語言理解系,統(tǒng),統(tǒng)。,語,語義網(wǎng)絡(luò)的,結(jié),結(jié)構(gòu)：語義,網(wǎng),網(wǎng)絡(luò)是知識(shí),的,的一種圖解表示，它由節(jié)點(diǎn),和,和弧線或鏈,線,線組成。節(jié),點(diǎn),點(diǎn)用于表示,實(shí),實(shí)體、概念,和,和情況等，,弧,弧線用于表,示,示節(jié)點(diǎn)間的,關(guān),關(guān)系。組成,部,部分:,1 詞法,部,部分：決定,表,表示詞匯表,中,中允許有哪,些,些符號(hào)，它,涉,涉及各個(gè)節(jié),點(diǎn),點(diǎn)和弧線。,2 結(jié)構(gòu),部,部分：敘述,符,符號(hào)排列的,約,約束條件

48、，,指,指定各弧線,連,連接的節(jié)點(diǎn),對(duì),對(duì)。,3 過程,部,部分：說明,訪,訪問過程，,這,這些過程能,用,用來建立和,修,修正描述，,以,以及回答相,關(guān),關(guān)問題。,4 語義,部,部分：確定,與,與描述相關(guān),的,的(聯(lián)想),意,意義的方法,即,即確定有關(guān),節(jié),節(jié)點(diǎn)的排列,及,及其占有物,和,和對(duì)應(yīng)弧線,。,。,,2.4 語,義,義網(wǎng)絡(luò)法,二,二元語義,網(wǎng),網(wǎng)絡(luò)的表示(Representation ofTwo-Element SemanticNetwork)1.表示簡,單,單的事實(shí)例1. 所,有,有的燕子都,是,是鳥,,2.4 語,義,義網(wǎng)絡(luò)法,二,二元語義,網(wǎng),網(wǎng)絡(luò)的表示(Represen

49、tation ofTwo-Element SemanticNetwork),2.表示占,有,有關(guān)系和其,它,它情況P40,例2. 小,燕,燕是一只燕,子,子，燕子是,鳥,鳥；巢-1,是,是小燕的巢,，,，巢-1是,巢,巢中的一個(gè),。,。,3.選擇語,義,義基元,試圖用一組,基,基元來表示,知,知識(shí)，以便,簡,簡化表示，,并,并可用簡單,的,的知識(shí)來表,示,示更復(fù)雜的,知,知識(shí)。,,,2.4 語,義,義網(wǎng)絡(luò)法,例3.我椅,子,子的顏色是,咖,咖啡色的；,椅,椅子包套是,皮,皮革；椅子,是,是一種家具,；,；椅子是座,位,位的一部分,；,；椅子的所,有,有者是X；X是個(gè)人，,如,如下圖所示,：,：

50、,,2.4 語,義,義網(wǎng)絡(luò)法,多,多元語義,網(wǎng),網(wǎng)絡(luò)的表示,語義網(wǎng)絡(luò)是,一,一種網(wǎng)絡(luò)結(jié),構(gòu),構(gòu)。節(jié)點(diǎn)之,間,間以鏈相連,。,。多元語義,網(wǎng),網(wǎng)絡(luò)表示的,實(shí),實(shí)質(zhì)：把多,元,元關(guān)系轉(zhuǎn)化,為,為一組二元,關(guān),關(guān)系的組合,，,，或二元關(guān),系,系的合取。,如,如果所要表,示,示的知識(shí)是,一,一元關(guān)系，,例,例如，要表,示,示李明是一,個(gè),個(gè)人，這在,謂,謂詞邏輯中,可,可表示為MAN(LIMING),。,。用語義網(wǎng),絡(luò),絡(luò)，這就可,以,以表示為:,與這樣的表,示,示法相等效,的,的關(guān)系在謂,詞,詞邏輯中表,示,示為ISA(LIMING，MAN)。這說,明,明語義網(wǎng)絡(luò),可,可以毫無困,難,難地表示一,元

51、,元關(guān)系。,,2.4 語,義,義網(wǎng)絡(luò)法,例如：要表,達(dá),達(dá)北京大學(xué)(BEIJING University,,簡,簡稱BU),和,和清華大學(xué)(TSINGHUA,University,簡稱TU)兩?；@球,隊(duì),隊(duì)在北大進(jìn),行,行的一場(chǎng)比,賽,賽的比分是85比89,。,。,若用謂詞邏,輯,輯可表示為SCORE(BU，TU，(85-89)),。,。這個(gè)表示,式,式中包含3,項(xiàng),項(xiàng)，而語義,網(wǎng),網(wǎng)絡(luò)從本質(zhì),上,上來說，只,能,能表示二元,關(guān),關(guān)系。解決,這,這個(gè)矛盾的,一,一種方法是,把,把這個(gè)多元,關(guān),關(guān)系轉(zhuǎn)化成,一,一組二元關(guān),系,系的組合，,或,或二元關(guān)系,的,的合取。,具體來說，,多,多元關(guān)系R(

52、X1，X2，…，Xn)總可以,轉(zhuǎn),轉(zhuǎn)換成R1(X11，X12)∧R2(X21，X22)∧…∧Rn(Xn1,Xn2),圖 2.20 多元關(guān),系,系的語義網(wǎng),絡(luò),絡(luò)表示,,2.4 語,義,義網(wǎng)絡(luò)法,語,語義網(wǎng)絡(luò)的,推,推理過程,在語義網(wǎng)絡(luò),知,知識(shí)表達(dá)方,法,法中，賦予,網(wǎng),網(wǎng)絡(luò)結(jié)構(gòu)的,含,含義完全決,定,定于管理這,個(gè),個(gè)網(wǎng)絡(luò)的過,程,程的特性。,為了便于以,下,下的敘述，,對(duì),對(duì)所用符號(hào),作,作進(jìn)一步的,規(guī),規(guī)定。區(qū)分,在,在鏈的頭部,和,和在鏈的尾,部,部的節(jié)點(diǎn)，,把,把在鏈的尾,部,部的節(jié)點(diǎn)稱,為,為值節(jié)點(diǎn)。,另,另外，我們,還,還規(guī)定節(jié)點(diǎn),的,的槽相當(dāng)于,鏈,鏈，不過取,不,不同的名字,

53、而,而已。在圖2.28中,磚,磚塊12(BRICK12)有3,個(gè),個(gè)鏈，構(gòu),成兩個(gè)槽。,其,其中一個(gè)槽,只,只有一個(gè),值，另外一,個(gè),個(gè)槽有兩個(gè),值,值。我們,說顏色槽(COLOR)填入紅色(RED),，,，,ISA槽填,入,入了磚塊(BRICK)和玩具,(TOY),。,。,圖 2.28 語義網(wǎng),絡(luò),絡(luò)的槽和數(shù),值,值,,2.4 語,義,義網(wǎng)絡(luò)法,語,語義網(wǎng)絡(luò)的,推,推理過程,語義網(wǎng)絡(luò)中,的,的推理過程,主,主要有兩種:一種是繼,承,承，另一種,是,是匹配。以,下,下我們分別,介,介紹這兩種,過,過程。,1.繼承,在語義網(wǎng)絡(luò),中,中所謂的繼,承,承是把對(duì)事,物,物的描述從,概,概念節(jié)點(diǎn)或,類,

54、類節(jié)點(diǎn)傳遞,到,到實(shí)例節(jié)點(diǎn),。,。例如在圖2.29上,所,所示的語義,網(wǎng),網(wǎng)絡(luò)中BRICK是概,念,念節(jié)點(diǎn)，BRICK12是一個(gè)實(shí),例,例節(jié)點(diǎn)。BRICK節(jié),點(diǎn),點(diǎn)在SHAPE(外形)槽，其中,填,填入了RECTANGULAR(,矩,矩形)，說,明,明磚塊的外,形,形是矩形的,。,。這個(gè)描述,可,可以通過ISA鏈傳遞,給,給實(shí)例節(jié)點(diǎn)BRICK12。因此,，,，雖然BRICK12,節(jié),節(jié)點(diǎn)沒有SHAPE槽,，,，但可以從,這,這個(gè)語義網(wǎng),絡(luò),絡(luò)推理出BRICK12的外形,是,是矩形的。,圖 2.29 語義網(wǎng),絡(luò),絡(luò)的值繼承,,2.4 語,義,義網(wǎng)絡(luò)法,語,語義網(wǎng)絡(luò)的,推,推理過程,1.繼承,這種

55、推理過,程,程，類似于,人,人的思維過,程,程。一旦知,道,道了某種事,物,物的身份以,后,后，可以聯(lián),想,想起很多關(guān),于,于這件事物,的,的一般描述,。,。,例如，我們,通,通常認(rèn)為鯨,魚,魚很大，鳥,比,比較小，城,堡,堡很古老，,運(yùn),運(yùn)動(dòng)員很健,壯,壯。這就像,我,我們用每種,事,事物的典型,情,情況來描述,各,各種事物--鯨魚、鳥,、,、城堡和運(yùn),動(dòng),動(dòng)員--,那,那樣。,一,一共有3,種,種繼承過程,：,：值繼承、"如果需要"繼承和",默,默認(rèn)"繼承,。,。,,2.4 語,義,義網(wǎng)絡(luò)法,語,語義網(wǎng)絡(luò)的,推,推理過程,語義網(wǎng)絡(luò)中,的,的推理過程,主,主要有兩種:一種是繼,承,承，另一種

56、,是,是匹配。以,下,下我們分別,介,介紹這兩種,過,過程。,1.繼承(1) 值,繼,繼承,除了ISA,鏈,鏈以外，另,外,外還有一種AKO(是,某,某種)鏈也,可,可被用于語,義,義網(wǎng)絡(luò)中的,描,描述或特性,的,的繼承。AKO是A-KIND-OF的縮,寫,寫。,總,總之，ISA和AKO,鏈,鏈直接地表,示,示類的成員,關(guān),關(guān)系以及子,類,類和類之間,的,的關(guān)系，提,供,供了一種把,知,知識(shí)從某一,層,層傳遞到另,一,一層的途徑,。,。　　為,了,了能利用語,義,義網(wǎng)絡(luò)的繼,,2.4 語,義,義網(wǎng)絡(luò)法,語,語義網(wǎng)絡(luò)的,推,推理過程,1.繼承(2) “,如,如果需要”,繼,繼承,在某些情況,下

57、,下，當(dāng)我們,不,不知道槽值,時(shí),時(shí)，可以利,用,用已知信息,來,來計(jì)算。例,如,如，我們可,以,以根據(jù)體積,和,和物質(zhì)的密,度,度來計(jì)算積,木,木的重量。,進(jìn),進(jìn)行上述計(jì),算,算的程序稱,為,為if-needed(如果需要)程序。,為了儲(chǔ)存進(jìn),行,行上述計(jì)算,的,的程序，我,們,們需要改進(jìn),節(jié),節(jié)點(diǎn)槽值的,結(jié),結(jié)構(gòu)，允許,槽,槽有幾種類,型,型的值，而,不,不只是一個(gè),類,類型。為此,，,，每個(gè)槽又,可,可以有若干,個(gè),個(gè)側(cè)面，以,儲(chǔ),儲(chǔ)存這些不,同,同類型的值,。,。這樣，以,前,前我們討論,的,的原始意義,上,上的值就放,“,“值側(cè)面”,中,中，if-needed程序，存,放,放在IF-

58、NEEDED側(cè)面中。,例如在,圖,圖2.30(a)中,，,，一個(gè),重,重量確,定,定程序,存,存放在BLOCK節(jié),點(diǎn),點(diǎn)的WEIGHT槽,的,的IF-NEEDED側(cè)面,中,中。,,圖 2.30,語,語義,網(wǎng),網(wǎng)絡(luò)的"如果,需,需要",繼,繼承,,2.4,語,語義,網(wǎng),網(wǎng)絡(luò)法,2.4.3語,義,義網(wǎng)絡(luò),的,的推理,過,過程,1.繼,承,承,(3),“,“缺,省,省”繼,承,承,某些情,況,況下，,當(dāng),當(dāng)我們,對(duì),對(duì)事物,所,所作的,假,假設(shè)不,是,是十分,有,有把握,時(shí),時(shí)，最,好,好對(duì)所,作,作的假,設(shè),設(shè)加上,“,“可能,”,”這樣,的,的字眼,。,。例如,，,，我們,可,可以認(rèn),為,為法官

59、,可,可能是,誠,誠實(shí)的,，,，但不,一,一定是,；,；或認(rèn),為,為寶石,可,可能是,很,很昂貴,的,的，但,不,不一定,是,是。,我們把,這,這種具有相,當(dāng),當(dāng)程度,的,的真,實(shí)性，,但,但又不,能,能十分,肯,肯定的,值,值稱為,“缺省,”,”值。這種,類,類型的,值,值被放,入,入槽,的DEFAULT(,缺,缺省),側(cè),側(cè)面中.,例如，,在,在圖2.31,中,中，網(wǎng),絡(luò),絡(luò)所表,示,示的,含義是,：,：從整,體,體來說,，,，積木,的,的顏色,很可能,是,是藍(lán)色,的,的，但,在,在磚塊,中,中，顏,色可能,是,是紅的,。,。對(duì)BLOCK和BRIC,K節(jié)點(diǎn),來,來說，,在,在COLOR,槽

60、,槽中找,到,到的,側(cè)面都,是,是DEFAULT側(cè),面,面，在,圖,圖中,以括弧,加,加以標(biāo),志,志,圖 2.31,語,語義,網(wǎng),網(wǎng)絡(luò)的"缺省"繼承,,2.4,語,語義,網(wǎng),網(wǎng)絡(luò)法,2.4.3語,義,義網(wǎng)絡(luò),的,的推理,過,過程,2.匹,配,配,至今我,們,們所討,論,論的是,類,類節(jié)點(diǎn),和,和實(shí)例,節(jié),節(jié)點(diǎn)，,例,例如BRICK和BRICK12,之,之間的,繼,繼承值,。,。現(xiàn)在,我,我們轉(zhuǎn),向,向討論,更,更為困,難,難一些,的,的問題,。,。當(dāng)解,決,決涉及,由,由幾部,分,分組成,的,的事物,時(shí),時(shí)，如,圖,圖2.32中,的,的玩具,房,房(TOY-HOUSE),和,和玩具,房,房-7

61、7(TOY-HOUSE77)，,繼,繼承過,程,程將如,何,何進(jìn)行,。,。我們,不,不僅必,須,須制定,如,如何把,值,值從玩,具,具房傳,遞,遞到玩,具,具房-77的,路,路徑，,而,而且必,須,須制定,把,把值從,玩,玩具房,部,部件傳,遞,遞到玩,具,具房-77部,件,件的路,徑,徑。,,,,,,,,例如，,很,很明顯,，,，由于TOY-HOUSE77是TOY-HOUSE,的,的一個(gè),實(shí),實(shí)例，,所,所以它,必,必須有,兩,兩個(gè)部,件,件 ，,一,一個(gè)是,磚,磚塊，,另,另一個(gè),是,是楔塊(wedge)。另,外,外，作,為,為玩具,房,房的一,個(gè),個(gè)部件,的,的磚塊,必,必須支,撐,撐楔

62、塊,。,。在圖2.32中，,玩,玩具房-77,部,部件以,及,及它們,之,之間的,鏈,鏈，都,用,用虛線,畫,畫的節(jié),點(diǎn),點(diǎn)的箭,頭,頭來表,示,示。因,為,為這些,知,知識(shí)是,通,通過繼,承,承而間,接,接知道,的,的，并,不,不是通,過,過實(shí)際,的,的節(jié)點(diǎn),和,和鏈直,接,接知道,的,的。因,此,此，我,們,們說虛,線,線所表,示,示的節(jié),點(diǎn),點(diǎn)和箭,頭,頭表示,的,的鏈?zhǔn)?虛,虛節(jié)點(diǎn),和,和虛鏈,。,。,,圖 2.32,虛,虛節(jié),點(diǎn),點(diǎn)和虛,鏈,鏈,,圖 2.32,虛,虛節(jié),點(diǎn),點(diǎn)和虛,鏈,鏈,沒有必,要,要從TOYHOUSE節(jié),點(diǎn),點(diǎn)把這,些,些節(jié)點(diǎn),和,和鏈復(fù),制,制到TOY-HOU

63、SE77節(jié)點(diǎn),去,去，除,非,非我們,需,需要在,這,這些復(fù),制,制節(jié)點(diǎn),加,加上玩,具,具房-77所,特,特有的,信,信息。,例如,，,，如,果,果我,們,們要,表,表示,玩,玩具,房,房-77,的,的磚,塊,塊的,顏,顏色,是,是紅,的,的，,就,就必,須,須為TOY-HOUSE77建,立,立一,個(gè),個(gè)BRICK,節(jié),節(jié)點(diǎn),，,，并,把,把RED,放,放在,這,這個(gè)BRICK節(jié),點(diǎn),點(diǎn)的COLOR槽,中,中。,假,假設(shè),我,我們,把,把RED,放,放在,作,作為,玩,玩具,房,房部,件,件的BRICK節(jié),點(diǎn),點(diǎn)的COLOR槽,中,中，,這,這將,意,意味,著,著所,有,有玩,具,具房,的,

64、的磚,都,都是,紅,紅色,的,的，,而,而不,是,是只,在,在由,玩,玩具,房,房-77,所,所描,述,述的,特,特定,房,房子,中,中的,磚,磚是,紅,紅色,的,的。,,2.4 語,義,義網(wǎng)絡(luò)法,語,語義網(wǎng)絡(luò)的,推,推理過程,現(xiàn)在我們來,研,研究圖2.33中的結(jié),構(gòu),構(gòu)35(STRUCTURE 35)。已知,這,這個(gè)結(jié)構(gòu)有,兩,兩個(gè)部件，,一,一個(gè)磚塊BRICK12和一個(gè)楔,塊,塊WEDGE18。一,旦,旦在STRUCTURE35和TOY-HOUSE之間,放,放上ISA,鏈,鏈，我們就,知,知道BRICK12必,須,須支撐WEDGE18,。,。在圖2.18上用虛,線,線箭頭表示BRICK12

65、和WEDGE18,之,之間的SUPPORT,虛,虛鏈。因?yàn)?很,很容易做部,件,件匹配，所,以,以虛線箭頭,的,的位置和方,向,向很容易確,定,定。WEDGE18肯,定,定和作為TOY-HOUSE的一,個(gè),個(gè)部件的楔,塊,塊相匹配，,而,而BRICK12肯定,和,和磚塊相匹,配,配。,圖 2.33 部件匹,配,配,,2.5 框,架,架表示法,心理學(xué)的研,究,究結(jié)果表明,，,，在人類日,常,常的思維和,理,理解活動(dòng)中,，,，當(dāng)分析和,解,解釋遇到的,新,新情況時(shí)，,要,要使用到過,去,去經(jīng)驗(yàn)中積,累,累的知識(shí)。,這,這些知識(shí)規(guī),模,模巨大而且,以,以很好的組,織,織形式保留,在,在人們的記,憶,

66、憶中。例如:,當(dāng)我們走進(jìn),一,一家從來沒,來,來過的飯店,時(shí),時(shí)，根據(jù)以,往,往的經(jīng)驗(yàn)，,可,可以預(yù)見在,這,這家飯店我,們,們將會(huì)看到,菜,菜單、桌子,、,、服務(wù)員等,等,等。,當(dāng)我們走進(jìn),教,教室時(shí)，可,以,以預(yù)見在教,室,室里可以看,到,到椅子、黑,板,板等等。,我們?cè)噲D用,以,以往的經(jīng)驗(yàn),來,來分析解釋,當(dāng),當(dāng)前所遇到,的,的情況。,,2.5 框,架,架表示法,當(dāng)然，我們,無,無法把過去,的,的經(jīng)驗(yàn)一一,都,都存在腦子,里,里，而只能,以,以一個(gè)通用,的,的數(shù)據(jù)結(jié)構(gòu),的,的形式存儲(chǔ),以,以往的經(jīng)驗(yàn),。,。這樣的數(shù),據(jù),據(jù)結(jié)構(gòu)稱為,框,框架?？蚣?提,提供了一個(gè),結(jié),結(jié)構(gòu)，一種,組,組織。在這,個(gè),個(gè)結(jié)構(gòu)或組,織,織中，新的,資,資料可以用,從,從過去的經(jīng),驗(yàn),驗(yàn)中得到的,概,概念來分析,和,和解釋。因,此,此，框架是,一,一種結(jié)構(gòu)化,表,表示法。,通?？蚣懿?用,用語義網(wǎng)絡(luò),中,中的節(jié)點(diǎn)-,槽,槽-值表示,結(jié),結(jié)構(gòu)。所以,框,框架也可以,定,定義為是一,組,組語義網(wǎng)絡(luò),的,的節(jié)點(diǎn)和槽,，,，這組節(jié)點(diǎn),和,和槽可以描,述,述格式固定,的,的事物、行,動(dòng),動(dòng)和事件。,語,語義網(wǎng)絡(luò)可