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

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

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

3、一般方法 用一個四元表列(W,x,Y,z)表示該問題的狀態(tài)，其中，W 表示猴子的位置x 表示猴子在箱子頂上時取x=1；否則x=0Y 表示箱子的水平位置z 表示猴子摘到香蕉時取z=1;否則z=0 定義該問題中的算符如下： (1) goto(U) 猴子走到水平位置U (2) pushbox(V) 猴子把箱子推到水平位置V (3) Climbbox 猴子爬到箱子頂上 (4) Grasp 猴子摘到香蕉第一節(jié) 知識表示的一般方法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) 把該問題從初始狀態(tài)變換為目標狀態(tài)的操作系列為： Goto(b),pushbox(c),climbbox,grasp第一節(jié) 知識表示的一般方法首先必須定義狀態(tài)的描述形式，通過使用這種描述形式把問題的一切狀態(tài)全部表示出來。其次，定義一組算子，通過算子可以把問題從一種狀態(tài)變換為另一種狀態(tài)。問題求解的過程是一個不斷把算子作用于狀態(tài)的過程。如果在使用某個算子后，得到的狀態(tài)是目標狀態(tài)，則得到了問題的解。 使用算子最少的解是最優(yōu)解。對任何一個狀態(tài)，可使用的算子可能不止一個，因此，可產(chǎn)生的后續(xù)狀態(tài)就可能有多個。用狀態(tài)空間法解決問題時的幾點說明第一節(jié) 知識表示的一般方法二

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

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

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

8、域：個體變元的取值范圍。 例如，用I(x)表示“x是整數(shù)”，則個體域是所有整數(shù)，且是無限的。謂詞公式： 連接詞 : 否定 : 析取 : 合取 : 蘊含 : 雙條件。第一節(jié) 知識表示的一般方法 量詞 : 全稱量詞 : 存在量詞 謂詞公式 定義：按下列規(guī)則得到的謂詞演算稱為合式公式： 單個謂詞公式是合式公式，稱為原子謂詞公式； 若A是合式公式，則A也是合式公式； 若A、B都是合式公式，則A B、A B、AB、A B也都是合式公式。 若A是合式公式，x是任一個個體變元，則(x) A、(x)A也都是合式公式。第一節(jié) 知識表示的一般方法 謂詞公式的解釋 在命題邏輯中，對命題公式中各個變元的一次真值指派，

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

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

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

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

13、人從c處出發(fā)把盒子從a處拿到b處，然后再回到c處。用一階謂詞描述機器人的行動過程。abc機器人行動規(guī)劃第一節(jié) 知識表示的一般方法定義謂詞： Table(x)：x是桌子 Empty(y)：y手中是空的 At(y,z)：y在z的附近Holds(y,w)：y拿著w On(w,x)：w在x的上面則，個體域， xa,b, yrobot, za,b,c, wbox第一節(jié) 知識表示的一般方法問題的初始狀態(tài)： At(robot,c), Empty(robot), On(box,a) Table(a), Table(b)問題的目標狀態(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處放下盒子通過搜索狀態(tài)空間即可得到機器人的行動過程。第一節(jié) 知識表示的一般方法(2)一階謂詞表示法的特點 自然性 精確性 嚴密性 容易實現(xiàn)(3)一階謂詞表示法的局限性 不能表示不確定性知識 組合爆炸 效率低第一節(jié) 知識表示的一般方法四、產(chǎn)生式表示法(產(chǎn)生式規(guī)則) 產(chǎn)生式的基本形式 IF P Then Q 或 P Q例如， IF 動物會飛 and 會下蛋 Then 該動物是鳥注意：蘊含式和產(chǎn)生式的區(qū)別(1) 產(chǎn)生式可以表示不確定知識；(2)

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

16、側(cè)面值。 框架名、槽名、側(cè)面名。第一節(jié) 知識表示的一般方法槽名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é) 知識表示的一般方法例1、一個描述教師的通用框架 框架名： 姓名：單位(姓、名) 年齡：單位(歲) 性別：范圍(男、女) 缺?。耗?職稱：范圍(教授、副教授、講師、助教) 缺省：講師 部門：單位（系、教研室） 住址： 工資：第一節(jié) 知識表示的一般方法一個具體教師的框架： 框架名： 姓名：張三 年齡：36 性別：

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

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

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

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

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

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

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

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

25、東方大學1990時間ISARecipientISAAgentISABeginISAMajorISA第一節(jié) 知識表示的一般方法問題：趙云主修的課程？根據(jù)該問題構(gòu)造語義網(wǎng)絡(luò)片段：趙云教育？RecipientISAMajor教育1 根據(jù)該語義網(wǎng)絡(luò)片段與知識庫的匹配可知，主修的課程是計算機。第一節(jié) 知識表示的一般方法七、Petri網(wǎng)表示法 構(gòu)成Petri網(wǎng)的基本要素：位置、轉(zhuǎn)換、標記。yjyktipkPj 如果用 Pj和Pk分別表示產(chǎn)生式的前提和結(jié)論，ti表示規(guī)則強度，則可用Petri網(wǎng)表示規(guī)則。第一節(jié) 知識表示的一般方法例如、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é) 知識表示的一般方法d1d6d9d2d3d4d8d7d50.90.930.80.80.90.90.90.85第一節(jié) 知識表示的一般方法八、過程表示法 將知識溶入控制中，推理與知識不分離。例如，一個規(guī)則

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

28、。（1）求任一解路徑的搜索策略（2）求最佳解路徑的搜索策略（3）求與或圖的搜索策略搜索策略第二節(jié) 搜索策略 問題求解搜索問題組合爆炸。回溯法爬山法寬度優(yōu)先法深度優(yōu)先法限定范圍搜索法好的優(yōu)先法大英博物館法分枝界限法動態(tài)規(guī)劃法最佳圖搜索一般與或圖搜索法極小極大法-剪枝法啟發(fā)式剪枝法一、回溯策略例子，n = 3 的 0-1背包問題。設(shè)： 背包容量：C = 30 貨物重量：W=16,15,15 貨物價值：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背包問題的解空間背包剩余容量=14貨物重量=15是不可解節(jié)點一、回溯策略基本思想： 在包含問題的所有解的解空間中，按照深度優(yōu)先的策略，從根節(jié)點出發(fā)搜索解空間樹，當搜索到任一個節(jié)點時，總是先判斷該節(jié)點是否包含問題的解，如果不包含，則跳過對該節(jié)點子樹的搜索，逐層向其祖先節(jié)點回溯；否則，繼續(xù)按深度優(yōu)先的策略搜索其子樹。 算法體現(xiàn)出了遞歸特性。 回溯法有“通用的解題法”之稱，是一個既帶有系統(tǒng)性又帶有跳躍性的搜索算法，用它可以系統(tǒng)地搜索一個問題的所有解或任一解。一、回溯策略回溯的遞歸過程 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);找到目標,則返回空表是死節(jié)點,則返回FAIL.必須回溯!計算DATA的可應(yīng)用規(guī)則集,并按某種策略排序規(guī)則用完,返回FAIL.必須回溯!取第一條規(guī)則刪去頭條規(guī)則,減少規(guī)則長度規(guī)則應(yīng)用于當前狀態(tài)產(chǎn)生新狀態(tài)對新狀態(tài)遞歸調(diào)用本過程一、回溯策略 IF PAT

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

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

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

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

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

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

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

38、等于跳過的將牌數(shù)加1。要求：把所有黑色將牌移動到白色將牌的右邊。四、啟發(fā)式圖搜索過程評估函數(shù)的設(shè)計： 由于白色左邊的黑色越少，則越接近目標，因此，可以用白色左邊的黑色將牌個數(shù)作為h(x)。即： h(x)=3(每個白色將牌左邊的黑色將牌個數(shù)的總和)四、啟發(fā)式圖搜索過程1、啟發(fā)式搜索算法A 利用評價函數(shù)f(x) = g(x)+h(x)來排序Open表中的節(jié)點順序的圖搜索算法稱為算法A。算法過程： 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ā)式圖搜索過程 Expand(n)mi, 計算f(n,mi) = g(n,mi)+h(mi)。 g(n,mi)是從s通過n到mi的耗散值； f(n,mi)是從s通過n、mi到目標節(jié)點耗散值的估計。 Add(mi,Open)，標記mi到n的指針。 IF f(n,mk)f(mk) Then f(mk) := f(n,mk)，標記mk到n的指針；比較f(n,mk)和f(mk)，f(mk)是擴展n之前計算的耗散值。 IF f(n,mi)f(mi) Then f(mi) := f(n,mi) ，標記mi到n的指針，Add(m

40、i,Open)；把mi重放回OPEN中，不比考慮修改到其子節(jié)點的指針。 Open表中的節(jié)點按f值排序 Go Loop四、啟發(fā)式圖搜索過程例子、八數(shù)碼問題28316475評價函數(shù)：f(x) = d(x) + w(x)其中，d(x)代表節(jié)點的深度，取g(x)=d(x)； 取 h(x) = w(x)，表示“不在位”將牌個數(shù)。初始狀態(tài)12384765目標狀態(tài)初始化S(4)Open表Closed表28316475S(4)第一次循環(huán)結(jié)束B(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ù)目標節(jié)點L返回到S的指針，可得到解路徑： S(4),B(4),E(5),I(5),K(5),L(5)四、啟發(fā)式圖搜索過程2、爬山法算法過程： n :=s; Lo

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

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

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