人工智能課件 －－02.知識(shí)的表示與推理-1

1、第2章 知識(shí)的表示與推理(1) 以符號(hào)和邏輯為基礎(chǔ)的傳統(tǒng)人工智能問(wèn)題求解是通過(guò)知識(shí)表示和知識(shí)推理來(lái)實(shí)現(xiàn)的。 每種以知識(shí)和符號(hào)操作為基礎(chǔ)的智能系統(tǒng)，其問(wèn)題求解方法都需要對(duì)某種解答空間的搜索。 知識(shí)表示空間搜索。第一節(jié) 知識(shí)表示的一般方法 狀態(tài)空間法 問(wèn)題歸約法 謂詞邏輯法 產(chǎn)生式表示法 語(yǔ)義網(wǎng)絡(luò)法 框架表示法 腳本表示法 過(guò)程表示法 Petri表示法 面向?qū)ο蟊硎痉ㄖR(shí)表示的常用方法：?jiǎn)栴}狀態(tài)的描述第一節(jié) 知識(shí)表示的一般方法一、狀態(tài)空間法狀態(tài)算符狀態(tài)空間 是為描述某類(lèi)問(wèn)題不同事物間的差別而引入的一組最少變量的有序集合。 其矢量形式為： Q = q0,q1,qn T 其中，每個(gè)元素qi為集合的分量

2、，稱(chēng)為狀態(tài)變量。 每個(gè)分量的一組值就得到一個(gè)具體狀態(tài)。 使問(wèn)題從一種狀態(tài)變化為另一種狀態(tài)的手段稱(chēng)為算符、操作符或運(yùn)算符。 由問(wèn)題的全部可能狀態(tài)及其關(guān)系所構(gòu)成的集合。 狀態(tài)空間一般表示為：(S,F,G)其中，S是初始狀態(tài)； F是算符；G是目標(biāo)狀態(tài)。 狀態(tài)空間的圖示形式稱(chēng)為狀態(tài)空間圖。第一節(jié) 知識(shí)表示的一般方法BACDE 路程或費(fèi)用 A B C D EA 7 6 10 13B 7 10 10C 5 9 D 6例1：推銷(xiāo)員問(wèn)題第一節(jié) 知識(shí)表示的一般方法起始節(jié)點(diǎn)AABACADAEACBACDACE問(wèn)題：如何進(jìn)行有效搜索？第一節(jié) 知識(shí)表示的一般方法例2：猴子和香蕉問(wèn)題香蕉箱子猴子acb第一節(jié) 知識(shí)表示的

3、一般方法 用一個(gè)四元表列(W,x,Y,z)表示該問(wèn)題的狀態(tài)，其中，W 表示猴子的位置x 表示猴子在箱子頂上時(shí)取x=1；否則x=0Y 表示箱子的水平位置z 表示猴子摘到香蕉時(shí)取z=1;否則z=0 定義該問(wèn)題中的算符如下： (1) goto(U) 猴子走到水平位置U (2) pushbox(V) 猴子把箱子推到水平位置V (3) Climbbox 猴子爬到箱子頂上 (4) Grasp 猴子摘到香蕉第一節(jié) 知識(shí)表示的一般方法V=c,pushbox(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,1,c,1)goto(U)U=bU=b,c

4、limbboxgraspgoto(U) 把該問(wèn)題從初始狀態(tài)變換為目標(biāo)狀態(tài)的操作系列為： Goto(b),pushbox(c),climbbox,grasp第一節(jié) 知識(shí)表示的一般方法首先必須定義狀態(tài)的描述形式，通過(guò)使用這種描述形式把問(wèn)題的一切狀態(tài)全部表示出來(lái)。其次，定義一組算子，通過(guò)算子可以把問(wèn)題從一種狀態(tài)變換為另一種狀態(tài)。問(wèn)題求解的過(guò)程是一個(gè)不斷把算子作用于狀態(tài)的過(guò)程。如果在使用某個(gè)算子后，得到的狀態(tài)是目標(biāo)狀態(tài)，則得到了問(wèn)題的解。 使用算子最少的解是最優(yōu)解。對(duì)任何一個(gè)狀態(tài)，可使用的算子可能不止一個(gè)，因此，可產(chǎn)生的后續(xù)狀態(tài)就可能有多個(gè)。用狀態(tài)空間法解決問(wèn)題時(shí)的幾點(diǎn)說(shuō)明第一節(jié) 知識(shí)表示的一般方法二

5、、問(wèn)題歸約法 問(wèn)題歸約是另一種問(wèn)題描述與求解方法。它由目標(biāo)出發(fā)，逆向推理，通過(guò)一系列變換把初始問(wèn)題變換為子問(wèn)題集合和子子問(wèn)題集合，直到最后規(guī)約為一個(gè)平凡的本原問(wèn)題。 變換的一般過(guò)程分解 等價(jià)變換 把一個(gè)復(fù)雜問(wèn)題分解為若干個(gè)較為簡(jiǎn)單的子問(wèn)題，每個(gè)子問(wèn)題繼續(xù)分解，直到不需要分解為止。 分解得到的是與樹(shù)。 利用同構(gòu)或同態(tài)的等價(jià)變換，把問(wèn)題變換為若干個(gè)較易解決的問(wèn)題。 等價(jià)變換得到的是或樹(shù)。第一節(jié) 知識(shí)表示的一般方法PP1P2P3PP1P2P3第一節(jié) 知識(shí)表示的一般方法本原問(wèn)題 不能再分解或變換，而且是直接可解的子問(wèn)題。端節(jié)點(diǎn)與終止節(jié)點(diǎn) 在與或樹(shù)中，沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)稱(chēng)為端節(jié)點(diǎn)；本原問(wèn)題對(duì)應(yīng)的節(jié)點(diǎn)稱(chēng)為終

6、止節(jié)點(diǎn)?？山夤?jié)點(diǎn)、不可解節(jié)點(diǎn)、解樹(shù)一些概念第一節(jié) 知識(shí)表示的一般方法例、三階梵塔問(wèn)題123ABC初始情況123ABC目標(biāo)情況用三元組(CBA)表示三個(gè)圓盤(pán)所在的柱子。解決的問(wèn)題：(111)=(333)第一節(jié) 知識(shí)表示的一般方法123ABC123(111)(122)123(122)123(322)123(322)123(333)移動(dòng)A和B到2移動(dòng)C到3移動(dòng)A和B到3第一節(jié) 知識(shí)表示的一般方法(111)=(333)(111)=(122)(122)=(322)(322)=(333)(111)=(113)(113)=(123)(123)=(122)(322)=(321)(321)=(331)(331)

7、=(333)第一節(jié) 知識(shí)表示的一般方法三、謂詞表示法1、復(fù)習(xí)(命題邏輯與謂詞邏輯)(1) 命題 定義：命題是具有真假意義的語(yǔ)句。 命題代表人們進(jìn)行思維的一種判斷，或者為肯定，或者為否定。 在命題邏輯中，通常用大寫(xiě)的英文字母表示。例如，可用英文字母P表示“西安是個(gè)古老的城市”這個(gè)命題。第一節(jié) 知識(shí)表示的一般方法(2)謂詞 在謂詞邏輯中，命題用謂詞來(lái)表示。 謂詞的一般形式：P(x1,x2,xn)其中P是謂詞名，xi是個(gè)體。個(gè)體可以是變量、常量或函數(shù)。 在P(x1,x2,xn)中，如果xi是變量、常量或函數(shù),則稱(chēng)為一階謂詞；如果xi本身又是一個(gè)一階謂詞，則稱(chēng)為二階謂詞。第一節(jié) 知識(shí)表示的一般方法個(gè)體

8、域：個(gè)體變?cè)娜≈捣秶?例如，用I(x)表示“x是整數(shù)”，則個(gè)體域是所有整數(shù)，且是無(wú)限的。謂詞公式： 連接詞 : 否定 : 析取 : 合取 : 蘊(yùn)含 : 雙條件。第一節(jié) 知識(shí)表示的一般方法 量詞 : 全稱(chēng)量詞 : 存在量詞 謂詞公式 定義：按下列規(guī)則得到的謂詞演算稱(chēng)為合式公式： 單個(gè)謂詞公式是合式公式，稱(chēng)為原子謂詞公式； 若A是合式公式，則A也是合式公式； 若A、B都是合式公式，則A B、A B、AB、A B也都是合式公式。 若A是合式公式，x是任一個(gè)個(gè)體變?cè)?，則(x) A、(x)A也都是合式公式。第一節(jié) 知識(shí)表示的一般方法 謂詞公式的解釋 在命題邏輯中，對(duì)命題公式中各個(gè)變?cè)囊淮握嬷抵概桑?/p>

9、稱(chēng)為命題公式的一個(gè)解釋。 謂詞公式的永真性、可滿足性、不可滿足性 如果謂詞公式P對(duì)個(gè)體域D上的任何一個(gè)解釋都取真值T，則稱(chēng)P在D上永真的。 對(duì)于謂詞公式P，如果至少存在一個(gè)解釋使得公式P為真值T,則稱(chēng)公式P是可滿足的。 如果謂詞公式P對(duì)于個(gè)體域D上的任何一個(gè)解釋都取真值 F，則稱(chēng)P在D上是不可滿足的，或永假的。第一節(jié) 知識(shí)表示的一般方法 謂詞公式的等價(jià)性和永真蘊(yùn)含 各類(lèi)等價(jià)公式 對(duì)于謂詞公式P和Q，如果PQ永真，則稱(chēng)P永真蘊(yùn)含Q，且稱(chēng) Q為P的邏輯結(jié)論，稱(chēng)P為Q的前提，即，P=Q 常用的永真蘊(yùn)含公式： 化簡(jiǎn)式 P Q =P, P Q =Q 附加式 P=P Q 析取三段論 P, P Q =Q第一

10、節(jié) 知識(shí)表示的一般方法 假言推理 P, P Q =Q 拒取式 Q, PQ= P 假言三段論 PQ, QR = PR 二難推論 P Q, P R, Q R = R 全稱(chēng)固化 (x) P(x) = p(y) 其中,y是個(gè)體域中的任一個(gè)體。第一節(jié) 知識(shí)表示的一般方法 存在固化 (x) P(x) = p(y) 其中,y是個(gè)體域中某個(gè)可使p(y)為真的個(gè)體。重要的推理規(guī)則： P規(guī)則：在推理的任何步驟上都可引入前提。 T規(guī)則：推理時(shí)，如果前面的步驟中有一個(gè)或多個(gè)公式永真蘊(yùn)含公式S，則可把S加入推理過(guò)程中。 CP規(guī)則：如果能從R和前提規(guī)則集合中推出S，則可從前提集合中推出 RS。第一節(jié) 知識(shí)表示的一般方法

11、反證法：P=Q，當(dāng)且僅當(dāng)P Q F。即，Q是P的邏輯結(jié)論，當(dāng)且僅當(dāng)P Q是不可滿足的。 重要定理： Q為P1,P2,Pn的邏輯結(jié)論，當(dāng)且僅當(dāng) （P1 P2 Pn） Q是不可滿足的。第一節(jié) 知識(shí)表示的一般方法2、一階謂詞表示法(1) 表示知識(shí)的方法 謂詞邏輯適合于表示事物的狀態(tài)、屬性、概念等事實(shí)性知識(shí)，也可以表示事物之間的因果關(guān)系，即，規(guī)則。 事實(shí)通常用謂詞公式的與/或形表示，規(guī)則用蘊(yùn)含式表示。 用謂詞表示知識(shí)前，要首先定義謂詞，指出每個(gè)謂詞的確切含義，然后再用連接詞把相關(guān)的謂詞連接起來(lái)，形成一個(gè)有完整意義的謂詞公式。第一節(jié) 知識(shí)表示的一般方法例1，設(shè)有如下知識(shí)： 劉歡比他父親出名。 高揚(yáng)是計(jì)算

12、機(jī)系的一名學(xué)生，但他不喜歡編程。 人人愛(ài)勞動(dòng)。定義謂詞： Bigger(x,y): x比y 出名； Computer(x):x是計(jì)算機(jī)系的學(xué)生; Like(x,y): x喜歡y; Love(x,y):x愛(ài)y; Man(x): x是人。第一節(jié) 知識(shí)表示的一般方法則上述知識(shí)可表示為： Bigger(liuhuan, father(liuhuan) ) Computer(Gaoyang) Like(Gaoyang,programming) (x) ( Man(x) Love(x,Labour) )第一節(jié) 知識(shí)表示的一般方法例2，設(shè)在房?jī)?nèi)c處有一個(gè)機(jī)器人，在a,b處各有一張桌子，a上有一個(gè)盒子。讓機(jī)器

13、人從c處出發(fā)把盒子從a處拿到b處，然后再回到c處。用一階謂詞描述機(jī)器人的行動(dòng)過(guò)程。abc機(jī)器人行動(dòng)規(guī)劃第一節(jié) 知識(shí)表示的一般方法定義謂詞： Table(x)：x是桌子 Empty(y)：y手中是空的 At(y,z)：y在z的附近Holds(y,w)：y拿著w On(w,x)：w在x的上面則，個(gè)體域， xa,b, yrobot, za,b,c, wbox第一節(jié) 知識(shí)表示的一般方法問(wèn)題的初始狀態(tài)： At(robot,c), Empty(robot), On(box,a) Table(a), Table(b)問(wèn)題的目標(biāo)狀態(tài)： At(robot,c), Empty(robot), On(box,b)

14、Table(a), Table(b)定義操作算子： Goto(x,y): 從x處走到y(tǒng)處 Pick-up(x): 在x處拿起盒子 Set-Down(x):在x處放下盒子通過(guò)搜索狀態(tài)空間即可得到機(jī)器人的行動(dòng)過(guò)程。第一節(jié) 知識(shí)表示的一般方法(2)一階謂詞表示法的特點(diǎn) 自然性 精確性 嚴(yán)密性 容易實(shí)現(xiàn)(3)一階謂詞表示法的局限性 不能表示不確定性知識(shí) 組合爆炸 效率低第一節(jié) 知識(shí)表示的一般方法四、產(chǎn)生式表示法(產(chǎn)生式規(guī)則) 產(chǎn)生式的基本形式 IF P Then Q 或 P Q例如， IF 動(dòng)物會(huì)飛 and 會(huì)下蛋 Then 該動(dòng)物是鳥(niǎo)注意：蘊(yùn)含式和產(chǎn)生式的區(qū)別(1) 產(chǎn)生式可以表示不確定知識(shí)；(2)

15、 產(chǎn)生式的條件匹配可以是不精確的。第一節(jié) 知識(shí)表示的一般方法五、框架表示法 1975年明斯基提出了框架理論，該理論認(rèn)為，人們對(duì)現(xiàn)實(shí)世界的認(rèn)識(shí)都是以一種類(lèi)似于框架的結(jié)構(gòu)存儲(chǔ)在記憶中的，當(dāng)面臨一個(gè)新問(wèn)題時(shí)，就從記憶中找出一個(gè)合適的框架，并根據(jù)實(shí)際情況對(duì)其細(xì)節(jié)進(jìn)行修改、補(bǔ)充，從而形成對(duì)當(dāng)前事物的認(rèn)識(shí)。第一節(jié) 知識(shí)表示的一般方法1、框架 框架是描述所論對(duì)象屬性的數(shù)據(jù)結(jié)構(gòu)。在框架理論中，將框架視其為表示知識(shí)的基本單位。 一個(gè)框架由若干個(gè)“槽”組成，每一個(gè)槽根據(jù)實(shí)際情況又由若干個(gè)“側(cè)面”組成。 一個(gè)“槽”描述所論對(duì)象某一方面的屬性，一個(gè)“側(cè)面”用于描述相應(yīng)屬性的一個(gè)方面。 槽和側(cè)面所具有的值分別稱(chēng)為槽值和

16、側(cè)面值。 框架名、槽名、側(cè)面名。第一節(jié) 知識(shí)表示的一般方法槽名1: 側(cè)面名1: 值1,值2,值p1 側(cè)面名2: 值1,值2,值p2 . 側(cè)面名m1: 值1,值2,值pm.槽名n: 側(cè)面名1: 值1,值2,值p1 . 側(cè)面名m1: 值1,值2,值pm約束： 約束條件1 . 約束條件n第一節(jié) 知識(shí)表示的一般方法例1、一個(gè)描述教師的通用框架 框架名： 姓名：?jiǎn)挝?姓、名) 年齡：?jiǎn)挝?歲) 性別：范圍(男、女) 缺?。耗?職稱(chēng)：范圍(教授、副教授、講師、助教) 缺?。褐v師 部門(mén)：?jiǎn)挝唬ㄏ?、教研室?住址： 工資：第一節(jié) 知識(shí)表示的一般方法一個(gè)具體教師的框架： 框架名： 姓名：張三 年齡：36 性別：

17、女 職稱(chēng)：教授 部門(mén)：計(jì)算機(jī)軟件教研室 住址： 工資：第一節(jié) 知識(shí)表示的一般方法例2、一個(gè)描述假冒偽劣商品的通用框架 框架名： 商品名稱(chēng)： 生成廠家： 銷(xiāo)售商店： 處 罰：處理方式： 處罰依據(jù)： 處罰時(shí)間： 經(jīng)辦部門(mén)：第一節(jié) 知識(shí)表示的一般方法2、框架網(wǎng)絡(luò) 由于框架中的槽值和側(cè)面值都可以是另一個(gè)框架的名字，因此就在框架之間建立了聯(lián)系，通過(guò)一個(gè)框架可以找到另一個(gè)框架。 例如、張三框架中的住址、工資。(橫向聯(lián)系) 框架間除橫向聯(lián)系外，還可以建立縱向聯(lián)系。第一節(jié) 知識(shí)表示的一般方法師生員工框架教職工框架學(xué)生框架教師框架工人框架教師-1教師-N電子系學(xué)生框架機(jī)械系學(xué)生框架框架的一個(gè)重要特性：繼承性第一

18、節(jié) 知識(shí)表示的一般方法3、框架中槽的設(shè)置(1) 充分表達(dá)事物各有關(guān)方面的屬性(2) 充分表達(dá)相關(guān)事物間的各種聯(lián)系(3) 系統(tǒng)預(yù)定義的一些槽名 ISA AKO Subclass Instace Part-of infer Passible-Reason第一節(jié) 知識(shí)表示的一般方法(4) 系統(tǒng)預(yù)定義的附加過(guò)程 .if_needed過(guò)程：當(dāng)需要槽值，但值不存在，且缺省值也沒(méi)有設(shè)定時(shí)，執(zhí)行該過(guò)程。 .if_added過(guò)程：當(dāng)需要在槽中增加槽值時(shí)，執(zhí)行該過(guò)程。 .if_removal過(guò)程：當(dāng)要從槽中刪除槽值時(shí)，執(zhí)行該過(guò)程。第一節(jié) 知識(shí)表示的一般方法4、框架系統(tǒng)中求解問(wèn)題的基本過(guò)程 (1)把問(wèn)題用一個(gè)框架表

19、示出來(lái)； (2)通過(guò)與知識(shí)庫(kù)中已有的框架進(jìn)行匹配，找出一個(gè)或幾個(gè)可匹配的預(yù)選框架作為初步假設(shè)，并在此假設(shè)的引導(dǎo)下收集進(jìn)一步的信息； (3)用某種評(píng)價(jià)方法對(duì)預(yù)選框架進(jìn)行評(píng)價(jià)，決定是否接受。第一節(jié) 知識(shí)表示的一般方法例、今天一次強(qiáng)度為里氏級(jí)的強(qiáng)烈地震襲擊了下斯洛文尼亞地區(qū)，造成25人死亡和5億美元的財(cái)產(chǎn)損失。如需了解詳細(xì)情況，可查詢網(wǎng)站：。 用框架表示該新聞。第一節(jié) 知識(shí)表示的一般方法框架名： 新聞?lì)愋停鹤匀粸?zāi)害 新聞內(nèi)容：框架名： 發(fā)生地區(qū)：下斯洛文尼亞 發(fā)生日期：今天 地震強(qiáng)度： 死亡人數(shù)：25 財(cái)產(chǎn)損失：5 詳細(xì)情況：if_needed: Procedure Search_ 第一節(jié) 知識(shí)表示

20、的一般方法六、語(yǔ)義網(wǎng)絡(luò)1、語(yǔ)義網(wǎng)絡(luò)的概念 語(yǔ)義網(wǎng)絡(luò)是通過(guò)概念及其語(yǔ)義關(guān)系來(lái)表達(dá)知識(shí)的一種網(wǎng)絡(luò)圖。 從圖論的觀點(diǎn)看，即是一個(gè)“帶標(biāo)識(shí)的有向圖”。其中，節(jié)點(diǎn)表示各種事物、概念、屬性、動(dòng)作、狀態(tài)、情況；弧表示各種語(yǔ)義聯(lián)系。例如：獵狗狗是一種第一節(jié) 知識(shí)表示的一般方法2、知識(shí)的語(yǔ)義網(wǎng)絡(luò)表示 任何一種知識(shí)表示方法都應(yīng)具備兩種功能： 表示事實(shí)；表示事實(shí)間的有關(guān)聯(lián)系。(1)用語(yǔ)義網(wǎng)絡(luò)表示事實(shí)獵狗狗動(dòng)物是一種是一種吃肉能狩獵身上有毛有尾巴有生命能運(yùn)動(dòng)會(huì)吃第一節(jié) 知識(shí)表示的一般方法一本書(shū)張三給李四主體客體-1客體-2用動(dòng)作作為節(jié)點(diǎn)的語(yǔ)義網(wǎng)絡(luò)第一節(jié) 知識(shí)表示的一般方法人與會(huì)者ABC與或或男女年老年輕 在一些較復(fù)雜

21、的事實(shí)和知識(shí)表示中，可以使用“并且”及“或者”等連接詞。 例如、“與會(huì)者有男、有女、有老、有少”。第一節(jié) 知識(shí)表示的一般方法例子、“小信使”這只鴿子從春天到秋天占有一個(gè)窩。小信使鴿子鳥(niǎo)占有窩鳥(niǎo)窩春天秋天時(shí)間是一只是一種是一種是是占有物開(kāi)始于結(jié)束于占有者第一節(jié) 知識(shí)表示的一般方法(2)用語(yǔ)義網(wǎng)絡(luò)表示事物之間的關(guān)系 分類(lèi)關(guān)系 分類(lèi)關(guān)系指事物間的類(lèi)屬關(guān)系，下層節(jié)點(diǎn)除可以繼承、細(xì)化、補(bǔ)充上層節(jié)點(diǎn)的屬性外，還可能出現(xiàn)變異情況。第一節(jié) 知識(shí)表示的一般方法動(dòng)物鳥(niǎo)魚(yú)鸚鵡鴕鳥(niǎo)鯊魚(yú)草魚(yú)是一種是一種是一種是一種是一種是一種有羽毛會(huì)飛生活在水中會(huì)游泳不會(huì)飛善奔走會(huì)學(xué)人語(yǔ)善鳴吃肉吃草分類(lèi)關(guān)系第一節(jié) 知識(shí)表示的一般方法

22、聚集關(guān)系 下層節(jié)點(diǎn)是上層節(jié)點(diǎn)的一部分或一個(gè)方面。教學(xué)學(xué)生教師課程部分部分部分聚集關(guān)系第一節(jié) 知識(shí)表示的一般方法饑餓需進(jìn)食推出推論關(guān)系 推論關(guān)系 由一個(gè)概念可以推出另一個(gè)概念。第一節(jié) 知識(shí)表示的一般方法 時(shí)間、位置等關(guān)系例如、 胡途是思源公司的經(jīng)理。 該公司位于朱雀大街上。 胡途今年35歲。朱雀大街思源公司胡途經(jīng)理35歲位于工作在是年齡第一節(jié) 知識(shí)表示的一般方法該公司有兩個(gè)胡途。胡途胡1胡235思源公司20被聘者經(jīng)理朱雀大街姓名姓名是受聘者是年齡年齡工作在位于第一節(jié) 知識(shí)表示的一般方法 多元關(guān)系 鄭州位于北京和西安之間。位置關(guān)系鄭州西安北京邊界1邊界2居中第一節(jié) 知識(shí)表示的一般方法(3)具有量詞

23、的語(yǔ)義網(wǎng)絡(luò).對(duì)存在量詞的處理方法 直接用“是一個(gè)”、“是一種”等語(yǔ)義聯(lián)系表示。.對(duì)全稱(chēng)量詞的處理方法 采用網(wǎng)絡(luò)分區(qū)技術(shù)。 基本思想：把一個(gè)表示復(fù)雜知識(shí)的命題劃分為若干個(gè)子命題，每一個(gè)子命題用一個(gè)較簡(jiǎn)單的語(yǔ)義網(wǎng)絡(luò)表示-子空間，多個(gè)子空間構(gòu)成一個(gè)大空間。每個(gè)子空間可以看作是大空間中的一個(gè)節(jié)點(diǎn)-超節(jié)點(diǎn)，子空間之間用弧互相連接。第一節(jié) 知識(shí)表示的一般方法例1：每個(gè)學(xué)生都背誦了一首唐詩(shī)。GSg學(xué)生背誦唐詩(shī)srp是主體客體是是整個(gè)空間代表子空間全稱(chēng)量詞表示任一個(gè)學(xué)生變量，表示某一次背誦變量，表示某一首唐詩(shī)第一節(jié) 知識(shí)表示的一般方法例2：每個(gè)學(xué)生都背誦了“靜夜思”這首唐詩(shī)。GSg學(xué)生背誦唐詩(shī)sr靜夜思是主體

24、客體是是第一節(jié) 知識(shí)表示的一般方法3 常用的語(yǔ)義聯(lián)系 A-Member-of Gomposed-of Have Before,After,At Located-on Similar-to第一節(jié) 知識(shí)表示的一般方法4 語(yǔ)義網(wǎng)絡(luò)系統(tǒng)中求解問(wèn)題的基本過(guò)程(1)根據(jù)待解決的問(wèn)題構(gòu)造一個(gè)網(wǎng)絡(luò)片段，其中某些節(jié)點(diǎn)或弧的標(biāo)識(shí)是空的；(2)根據(jù)此網(wǎng)絡(luò)片段在知識(shí)庫(kù)中尋找可匹配的網(wǎng)絡(luò)，以找出所需的信息；(3)當(dāng)匹配時(shí)，則與詢問(wèn)處匹配的事實(shí)即是問(wèn)題的解。第一節(jié) 知識(shí)表示的一般方法例、設(shè)有如下事實(shí)： 趙云是一個(gè)學(xué)生 他在東方大學(xué)主修計(jì)算機(jī)課程 他入校的時(shí)間是1990年則語(yǔ)義網(wǎng)絡(luò)知識(shí)庫(kù)為：學(xué)生趙云教育教育1計(jì)算機(jī)科學(xué)大學(xué)

25、東方大學(xué)1990時(shí)間ISARecipientISAAgentISABeginISAMajorISA第一節(jié) 知識(shí)表示的一般方法問(wèn)題：趙云主修的課程？根據(jù)該問(wèn)題構(gòu)造語(yǔ)義網(wǎng)絡(luò)片段：趙云教育？RecipientISAMajor教育1 根據(jù)該語(yǔ)義網(wǎng)絡(luò)片段與知識(shí)庫(kù)的匹配可知，主修的課程是計(jì)算機(jī)。第一節(jié) 知識(shí)表示的一般方法七、Petri網(wǎng)表示法 構(gòu)成Petri網(wǎng)的基本要素：位置、轉(zhuǎn)換、標(biāo)記。yjyktipkPj 如果用 Pj和Pk分別表示產(chǎn)生式的前提和結(jié)論，ti表示規(guī)則強(qiáng)度，則可用Petri網(wǎng)表示規(guī)則。第一節(jié) 知識(shí)表示的一般方法例如、R1: IF d1 then d2 ( CF=0.85 )R2: IF d

26、2 then d3 ( CF=0.8 )R3: IF d2 then d4 ( CF=0.8 )R4: IF d4 then d5 ( CF=0.9 )R5: IF d1 then d6 ( CF=0.9 )R6: IF d6 then d9 ( CF=0.93 )R7: IF d1 and d8 then d7 ( CF=0.85 )R8: IF d7 then d4 ( CF=0.9 )第一節(jié) 知識(shí)表示的一般方法d1d6d9d2d3d4d8d7d50.90.930.80.80.90.90.90.85第一節(jié) 知識(shí)表示的一般方法八、過(guò)程表示法 將知識(shí)溶入控制中，推理與知識(shí)不分離。例如，一個(gè)規(guī)則

27、為IF Brother(x,y) and Father(x,z) then Uncle(y,z)用過(guò)程表示時(shí)為： BR( Uncle ?y ?z ) Goal(Brother ?x y ) Goal(Father x z )第一節(jié) 知識(shí)表示的一般方法九、腳本表示法 依賴?yán)碚摗?類(lèi)似于電影劇本。十、面向?qū)ο蟊硎痉?用類(lèi)表示。第二節(jié) 搜索策略一、基本概念什么是搜索？ AI所要解決的問(wèn)題大部分是不良結(jié)構(gòu)或非結(jié)構(gòu)化的問(wèn)題，對(duì)這樣的問(wèn)題一般不存在成熟的求解算法，只能利用已有的知識(shí)一步步地摸索前進(jìn)。 根據(jù)問(wèn)題的實(shí)際情況不斷尋找可利用的知識(shí)，從而構(gòu)造出一條代價(jià)較少的推理路線，使問(wèn)題得到圓滿解決的過(guò)程稱(chēng)為搜索

28、。（1）求任一解路徑的搜索策略（2）求最佳解路徑的搜索策略（3）求與或圖的搜索策略搜索策略第二節(jié) 搜索策略 問(wèn)題求解搜索問(wèn)題組合爆炸?；厮莘ㄅ郎椒▽挾葍?yōu)先法深度優(yōu)先法限定范圍搜索法好的優(yōu)先法大英博物館法分枝界限法動(dòng)態(tài)規(guī)劃法最佳圖搜索一般與或圖搜索法極小極大法-剪枝法啟發(fā)式剪枝法一、回溯策略例子，n = 3 的 0-1背包問(wèn)題。設(shè)： 背包容量：C = 30 貨物重量：W=16,15,15 貨物價(jià)值：P =45,25,25 解空間： (0,0,0),(0,1,0),(0,0,1),(1,0,0), (0,1,1),(1,0,1),(1,1,0),(1,1,1) 一、回溯策略ABCDEFGHIJKL

29、MNO10000000111110-1背包問(wèn)題的解空間背包剩余容量=14貨物重量=15是不可解節(jié)點(diǎn)一、回溯策略基本思想： 在包含問(wèn)題的所有解的解空間中，按照深度優(yōu)先的策略，從根節(jié)點(diǎn)出發(fā)搜索解空間樹(shù)，當(dāng)搜索到任一個(gè)節(jié)點(diǎn)時(shí)，總是先判斷該節(jié)點(diǎn)是否包含問(wèn)題的解，如果不包含，則跳過(guò)對(duì)該節(jié)點(diǎn)子樹(shù)的搜索，逐層向其祖先節(jié)點(diǎn)回溯；否則，繼續(xù)按深度優(yōu)先的策略搜索其子樹(shù)。 算法體現(xiàn)出了遞歸特性。 回溯法有“通用的解題法”之稱(chēng)，是一個(gè)既帶有系統(tǒng)性又帶有跳躍性的搜索算法，用它可以系統(tǒng)地搜索一個(gè)問(wèn)題的所有解或任一解。一、回溯策略回溯的遞歸過(guò)程 BACKTRACK(DATA) IF TERM(DATA), RETURN N

30、IL; IF DEADEND(DATA), RETURN FAIL; RULES :=APPRULES(DATA); LOOP: IF NULL(RULES),RETURN FAIL; R:=FIRST(RULES); RULES :=TAIL(RULES); RDATA :=GEN(R,DATA); PATH :=BACKTRACK(RDATA);找到目標(biāo),則返回空表是死節(jié)點(diǎn),則返回FAIL.必須回溯!計(jì)算DATA的可應(yīng)用規(guī)則集,并按某種策略排序規(guī)則用完,返回FAIL.必須回溯!取第一條規(guī)則刪去頭條規(guī)則,減少規(guī)則長(zhǎng)度規(guī)則應(yīng)用于當(dāng)前狀態(tài)產(chǎn)生新?tīng)顟B(tài)對(duì)新?tīng)顟B(tài)遞歸調(diào)用本過(guò)程一、回溯策略 IF PAT

31、H=FAIL,GO LOOP; RETURN CONS(R,PATH);遞歸調(diào)用失敗,則轉(zhuǎn)移調(diào)用另一個(gè)規(guī)則過(guò)程返回解路徑規(guī)則表一、回溯策略例子，四皇后問(wèn)題QQQQ一、回溯策略描述: 綜合數(shù)據(jù)庫(kù):DATA = L(表), L的元素ij,1i,j4;DATA非空時(shí),其表元素表示棋子所在的行和列。因只有四個(gè)棋子，所以表元素的個(gè)數(shù)最多為4。QQQQL=12,24,31,43一、回溯策略規(guī)則集： if 1i4 and Length DATA = i 1 then Append (DATA (ij) ); ( 1j4 )共16條規(guī)則，每條規(guī)則表示滿足條件下，在ij處放一個(gè)棋子。一、回溯策略（0）（11）（

32、12）（13）（14）（21）（22）（23）（24）（21）（22）（23）（24）（31）（32）（33）（34）一、回溯策略說(shuō)明： 運(yùn)行時(shí)可能出現(xiàn)重復(fù)狀態(tài)，使過(guò)程陷入死循環(huán)。 一種解決方法：設(shè)置深度范圍，當(dāng)達(dá)到設(shè)置的深度時(shí)，進(jìn)行回溯。二、圖搜索策略概念節(jié)點(diǎn)深度路徑路徑耗散值擴(kuò)展一個(gè)節(jié)點(diǎn)根節(jié)點(diǎn)的深度為0，其他節(jié)點(diǎn)的深度規(guī)定為父節(jié)點(diǎn)的深度加1，即dn+1=dn+1。設(shè)一節(jié)點(diǎn)序列為(n0,n1,nk)，對(duì)i=1,2,k，若節(jié)點(diǎn)ni-1都具有一個(gè)后繼節(jié)點(diǎn)ni,則該節(jié)點(diǎn)序列稱(chēng)為從節(jié)點(diǎn)n0到節(jié)點(diǎn)nk的長(zhǎng)度為k的一條路徑。設(shè)C(ni,nj)是節(jié)點(diǎn)ni到nj的耗散值，一條路徑上的耗散值等于連接這條路徑各

33、節(jié)點(diǎn)間耗散值的總和。后繼節(jié)點(diǎn)操作符作用到節(jié)點(diǎn)上，生成其所有后繼節(jié)點(diǎn)，并給出連接弧線的耗散值，這個(gè)過(guò)程稱(chēng)為擴(kuò)展一個(gè)節(jié)點(diǎn)。二、圖搜索策略搜索過(guò)程中用到的兩個(gè)數(shù)據(jù)結(jié)構(gòu)：狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)Open表Close表 Open表用于存放剛生成的節(jié)點(diǎn)，對(duì)于不同搜索策略，節(jié)點(diǎn)在Open表中的排列順序是不同的。 Close表用于存放將要擴(kuò)展或已擴(kuò)展的節(jié)點(diǎn)。一般搜索過(guò)程二、圖搜索策略(1)把起始節(jié)點(diǎn)S0放入Open表，并建立只包含S0的圖G。(2)檢查Open表是否為空，若為空，問(wèn)題無(wú)解，退出。(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Close表，并記該節(jié)點(diǎn)為n。(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，是，則求

34、得解，退出。(5)擴(kuò)展節(jié)點(diǎn)n，生成一組節(jié)點(diǎn)。把其中不是節(jié)點(diǎn)n先輩的那些子節(jié)點(diǎn)記做集合M,并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)加入圖G。二、圖搜索策略(6)針對(duì)M中子節(jié)點(diǎn)的不同情況，分別進(jìn)行處理： 對(duì)那些未曾在G中出現(xiàn)過(guò)的M成員設(shè)置一個(gè)指向父節(jié)點(diǎn)的指針，并放入Open表。 對(duì)那些先前已在G中出現(xiàn)過(guò)的M成員，確定是否需要修改它指向父節(jié)點(diǎn)的指針。 對(duì)那些先前已在G中出現(xiàn)并且已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。(7)按某種策略對(duì)Open表的節(jié)點(diǎn)進(jìn)行排序。(8)轉(zhuǎn)第(2)步。二、圖搜索策略說(shuō)明：（1）上述過(guò)程具有具有通用性，其他的一些搜索策略都是它的一個(gè)特例。各種搜索策略的主要區(qū)

35、別是對(duì)Open表中節(jié)點(diǎn)排序的準(zhǔn)則不同。（2）一個(gè)節(jié)點(diǎn)經(jīng)過(guò)一個(gè)算符操作后一般只生成一個(gè)節(jié)點(diǎn)，但適用于一個(gè)節(jié)點(diǎn)的算符可能是多個(gè)，此時(shí)會(huì)生成多個(gè)子節(jié)點(diǎn)，這些子節(jié)點(diǎn)中可能有些是當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)或祖先節(jié)點(diǎn)，此時(shí)不能把這些先輩節(jié)點(diǎn)作為當(dāng)前的擴(kuò)展節(jié)點(diǎn)，余下的子節(jié)點(diǎn)記作集合M，并加入圖中。二、圖搜索策略（3）一個(gè)新生成的節(jié)點(diǎn)，它可能是第一次被生成的節(jié)點(diǎn)，也可能是先前已作為其他節(jié)點(diǎn)的后繼節(jié)點(diǎn)生成過(guò)，當(dāng)前又作為另一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)被再次生成。 此時(shí)，它究竟應(yīng)作為哪個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)？一般的做法是，由開(kāi)始節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑耗散值來(lái)決定，哪條路徑的耗散值小，相應(yīng)的節(jié)點(diǎn)就作為它的父節(jié)點(diǎn)。（4）通過(guò)搜索得到的圖稱(chēng)為搜索圖，

36、由搜索圖中的所有節(jié)點(diǎn)及反向指針?biāo)鶚?gòu)成的集合是一棵樹(shù)，稱(chēng)為搜索樹(shù)。二、圖搜索策略（5）在搜索過(guò)程中，一旦某個(gè)被考察的節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)就得到了一個(gè)解。（6）如果在搜索中一直找不到目標(biāo)節(jié)點(diǎn)，而且Open表中不在有可供擴(kuò)展的節(jié)點(diǎn)，則搜索失敗。三、無(wú)信息圖搜索過(guò)程盲目搜索廣度優(yōu)先搜索深度優(yōu)先搜索三、無(wú)信息圖搜索過(guò)程1、廣度優(yōu)先搜索 基本思想:從初始節(jié)點(diǎn)開(kāi)始，逐層進(jìn)行搜索。 廣度優(yōu)先搜索是完備的。 做法:Open表中的節(jié)點(diǎn)按進(jìn)入的先后順序排列，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面。三、無(wú)信息圖搜索過(guò)程2、深度優(yōu)先搜索 基本思想:從初始節(jié)點(diǎn)開(kāi)始，在其子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察，若不是目標(biāo)節(jié)點(diǎn)，則再在該子節(jié)

37、點(diǎn)的子節(jié)點(diǎn)中進(jìn)行考察，并如此向下搜索。 深度優(yōu)先搜索不是完備的。 做法:把新擴(kuò)展的子節(jié)點(diǎn)放在Open表中的首部。四、啟發(fā)式圖搜索過(guò)程 啟發(fā)式搜索是利用問(wèn)題擁有的啟發(fā)信息來(lái)引導(dǎo)搜索，達(dá)到減少搜索范圍、降低問(wèn)題復(fù)雜度的目的。 這類(lèi)和具體問(wèn)題相關(guān)的信息稱(chēng)為啟發(fā)信息。四、啟發(fā)式圖搜索過(guò)程一般形式為： f(x) = g(x)+h(x) 其中，g(x)是從初始節(jié)點(diǎn)到節(jié)點(diǎn)x的實(shí)際代價(jià)；h(x)是x到目標(biāo)節(jié)點(diǎn)的代價(jià)估計(jì)。啟發(fā)式信息的評(píng)價(jià)（評(píng)價(jià)函數(shù)）四、啟發(fā)式圖搜索過(guò)程例、設(shè)有如下結(jié)構(gòu)的移動(dòng)將牌游戲：黑黑黑白白白空游戲規(guī)則：.當(dāng)將牌移入相鄰空位置時(shí)，費(fèi)用為1個(gè)單位；.一個(gè)將牌最多可跳過(guò)兩個(gè)將牌進(jìn)入空位置，其費(fèi)用

38、等于跳過(guò)的將牌數(shù)加1。要求：把所有黑色將牌移動(dòng)到白色將牌的右邊。四、啟發(fā)式圖搜索過(guò)程評(píng)估函數(shù)的設(shè)計(jì)： 由于白色左邊的黑色越少，則越接近目標(biāo)，因此，可以用白色左邊的黑色將牌個(gè)數(shù)作為h(x)。即： h(x)=3(每個(gè)白色將牌左邊的黑色將牌個(gè)數(shù)的總和)四、啟發(fā)式圖搜索過(guò)程1、啟發(fā)式搜索算法A 利用評(píng)價(jià)函數(shù)f(x) = g(x)+h(x)來(lái)排序Open表中的節(jié)點(diǎn)順序的圖搜索算法稱(chēng)為算法A。算法過(guò)程： Open :=(s), f(s) = g(s)+h(s) Loop: IF Open=() Then Exit(FAIL) n: = First(Open); IF Goal(n) Then Exit(S

39、uccess) Remove(n,Open), Add(n,Closed)四、啟發(fā)式圖搜索過(guò)程 Expand(n)mi, 計(jì)算f(n,mi) = g(n,mi)+h(mi)。 g(n,mi)是從s通過(guò)n到mi的耗散值； f(n,mi)是從s通過(guò)n、mi到目標(biāo)節(jié)點(diǎn)耗散值的估計(jì)。 Add(mi,Open)，標(biāo)記mi到n的指針。 IF f(n,mk)f(mk) Then f(mk) := f(n,mk)，標(biāo)記mk到n的指針；比較f(n,mk)和f(mk)，f(mk)是擴(kuò)展n之前計(jì)算的耗散值。 IF f(n,mi)f(mi) Then f(mi) := f(n,mi) ，標(biāo)記mi到n的指針，Add(m

40、i,Open)；把mi重放回OPEN中，不比考慮修改到其子節(jié)點(diǎn)的指針。 Open表中的節(jié)點(diǎn)按f值排序 Go Loop四、啟發(fā)式圖搜索過(guò)程例子、八數(shù)碼問(wèn)題28316475評(píng)價(jià)函數(shù)：f(x) = d(x) + w(x)其中，d(x)代表節(jié)點(diǎn)的深度，取g(x)=d(x)； 取 h(x) = w(x)，表示“不在位”將牌個(gè)數(shù)。初始狀態(tài)12384765目標(biāo)狀態(tài)初始化S(4)Open表Closed表28316475S(4)第一次循環(huán)結(jié)束B(niǎo)(4),A(6),C(6)Open表S(4)Closed表2831647528316475S(4)28314765A(6)B(4)C(6)28316475第二次循環(huán)結(jié)束D

41、(5),E(5),A(6)C(6),F(6)Open表S(4),B(4)Closed表2831476528314765B(4)23184765D(5)E(5)F(6)28314765第三次循環(huán)結(jié)束E(5),A(6),C(6)F(6),G(6),H(7)Open表S(4),B(4),D(5)Closed表283147658321476528371465D(5)G(6)H(7)第四次循環(huán)結(jié)束I(5),A(6),C(6)F(6),G(6),H(7)J(7)Open表S(4),B(4),D(5)E(5)Closed表2318476523184765E(5)23184765I(5)J(7)第五次循環(huán)結(jié)束

42、K(5),A(6),C(6)F(6),G(6),H(7)J(7)Open表S(4),B(4),D(5)E(5),I(5)Closed表23184765I(5)K(5)12384765第六次循環(huán)結(jié)束L(5),A(6),C(6)F(6),G(6),H(7)J(7),M(7)Open表S(4),B(4),D(5)E(5),I(5),K(5)Closed表1238476512378465K(5)12384765第七次循環(huán) 第4步成功退出。 根據(jù)目標(biāo)節(jié)點(diǎn)L返回到S的指針，可得到解路徑： S(4),B(4),E(5),I(5),K(5),L(5)四、啟發(fā)式圖搜索過(guò)程2、爬山法算法過(guò)程： n :=s; Lo

43、op: IF Goal(n) Then Exit(Success); Expand (n)mi,計(jì)算h(mi), Nextn := m(min h(mi)的節(jié)點(diǎn)); IF h(n)0; . h(x)是h*(x)的下界，即有，h(x)h*(x)則稱(chēng)為A*算法。 其中，g*(x)是從節(jié)點(diǎn)S0到節(jié)點(diǎn)x的最小代價(jià)；h*(x)是從節(jié)點(diǎn)x到目標(biāo)的路徑代價(jià)，恒有g(shù)(x)g*(x)，而且在算法執(zhí)行過(guò)程中隨著更多信息的獲得，g(x)的值呈下降趨勢(shì)。h(x)的確定依賴于具體問(wèn)題領(lǐng)域的啟發(fā)性信息，其中,h(x)h*(x)限制十分重要，它可保證A*算法能找到最優(yōu)解。四、啟發(fā)式圖搜索過(guò)程 可納性含義：對(duì)于可解狀態(tài)空間圖

44、，如果一個(gè)搜索算法能在有限步內(nèi)終止，并且能找到最優(yōu)解，則稱(chēng)該搜索算法是可納的。A*算法的可納性四、啟發(fā)式圖搜索過(guò)程 定理1：對(duì)有限圖，如果從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t有路徑存在，則算法A一定成功結(jié)束。 證明： . 因?yàn)閳D有解，則令 n0=s,n1,nk=t，表示某一解路徑。 . 從 nk 開(kāi)始逆向逐個(gè)檢測(cè)該序列的節(jié)點(diǎn),找到出現(xiàn)在Open表中的節(jié)點(diǎn)ni,即niOpen， ni+1Open，（特別的，在開(kāi)始時(shí)，n0=s）。四、啟發(fā)式圖搜索過(guò)程 . 由于ni在Open表中，則必定在第6步被擴(kuò)展，且ni+1被加到Open表中，因此，在Open表空之前， ni+1被處理過(guò)。 . 若ni+1是目標(biāo)節(jié)點(diǎn)，則搜索

45、成功，否則它被加入到Open表中，這兩種情況都與搜索失敗的假設(shè)矛盾。 由于A*是A的特例，因此它具有A的所有性質(zhì)。四、啟發(fā)式圖搜索過(guò)程 引理1：對(duì)無(wú)限圖，若有從初始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的一條路徑，則A*不結(jié)束時(shí)，在Open中即使最小的一個(gè)f值也將增到任意大，或有f(n)f*(s) 證明： . 設(shè) e 是A*生成的搜索圖中各條邊的最小耗散值，d*(xn)是從開(kāi)始節(jié)點(diǎn)s到節(jié)點(diǎn)xn的最短路徑長(zhǎng)度，則有： g*(xn) d*(xn)e四、啟發(fā)式圖搜索過(guò)程 . 因?yàn)椋琯(xn) g*(xn) 所以，g(xn) d*(xn)e 又因?yàn)?，h(xn) 0，f(xn) g(xn) 故得到：f(xn) d*(xn)e 由于A*算法不終止，隨著搜索的進(jìn)行d*(xn)會(huì)無(wú)限增大，從而f(xn)也無(wú)限增大。 設(shè) M = f*(s)/e，M是一個(gè)定數(shù)，所以搜索到