人工智能第二章上

1、人工智能第二章上第1頁，共50頁，2022年，5月20日，10點59分，星期日2.1搜索問題問題提出人工智能要解決的問題是非結構化問題； 難以獲得求解所需的全部信息；更沒有現成的算法可供求解使用。應用第2頁，共50頁，2022年，5月20日，10點59分，星期日搜索需要解決的問題知識表示（狀態(tài)空間表示）搜索策略（如何搜索，知識的使用）最優(yōu)搜索(如何找到最優(yōu)路徑）第3頁，共50頁，2022年，5月20日，10點59分，星期日2.2狀態(tài)空間表示法表示方法 (1)狀態(tài)(State): Sk=Sk1,Sk2,Skn (2)操作(Operator): 操作描述了狀態(tài)之間的關系 表示：F:f1,f2,fn

2、(3)狀態(tài)空間(State Space) 三元組表示S,F,G 其中：S初始狀態(tài)集 G：目標狀態(tài)集合 F： 操作的集合。第4頁，共50頁，2022年，5月20日，10點59分，星期日狀態(tài)空間圖可有相應的賦值有向圖節(jié)點表示狀態(tài)，有向邊表示操作 問題求解過程轉化為在圖中尋找從初始狀態(tài)S出發(fā)到達目標狀態(tài)G的路徑問題，也就是尋找操作序列的問題第5頁，共50頁，2022年，5月20日，10點59分，星期日舉例（用狀態(tài)空間方法）2階“梵塔”問題(Tower of Hanoi Problem):有三個柱子(1，2和3)和兩個不同尺寸的圓盤(A，B)。在每個圓盤的中心有個孔，所以圓盤可以堆疊在柱子上,最初,全

3、部兩個圓盤都堆在柱子1上(最大的在底部,最小的在頂部)。要求把所有 圓盤都移到另一個柱子上，搬動規(guī)則為： (1)一次只能搬一個圓盤 (2)不能將大圓盤放在小圓盤上 (3)可以利用空柱子。(example,hono)第6頁，共50頁，2022年，5月20日，10點59分，星期日用狀態(tài)空間方法來描述問題：狀態(tài)的表示柱的編號用i,j來代表 (i,j)表示問題的狀態(tài)其中: i代表A(小）所在的柱子, j 代表B（大）所在的柱子狀態(tài)集合 （可能的）s0=(1,1), s1=(1,2), s2=(1,3)s3=(2,1), s4=(2,2), s5=(2,3)s6=(3,1), s7=(3,2), s8=

4、(3,3)第7頁，共50頁，2022年，5月20日，10點59分，星期日初始狀態(tài)S=s0，目標狀態(tài)G=s4,s8S0=(1,1)A132BS4=(2,2)123ABS8=(3,3)123AB第8頁，共50頁，2022年，5月20日，10點59分，星期日操作（算符）定義操作A(i,j), B(i,j)操作集合(12種操作）：A(1,2),A(1,3),A(2,1),A(2,3),A(3,1),A(3,2) B(1,2),B(1,3),B(2,1),B(2,3),B(3,1),B(3,2)約束：不能將大圓盤（B）放在小圓盤（A）上第9頁，共50頁，2022年，5月20日，10點59分，星期日狀態(tài)空

5、間圖S0(1,1)S3(2,1)S6(3,1)S5(2,3)S7(3,2)S8(3,3)S2(1,3)S1(1,2) S4(2,2)A(1,3)B(1,2)A(3,2)目標目標初始A(1,2)B(1,3)A(2,3)第10頁，共50頁，2022年，5月20日，10點59分，星期日搜索要解決的問題搜索策略：如何找到解的路徑即如何生成進一步的狀態(tài)約定：不可走回頭路搜索圖：問題求解過程中經過的所有路徑最優(yōu)解：使用操作（算符）最少的解例第11頁，共50頁，2022年，5月20日，10點59分，星期日搜索策略1：寬度優(yōu)先S0(1,1)S 3(2,1)S6(3,1)S5(2,3)S7(3,2)012S8(

6、3,3)S6(3,1)S3(2,1)3465S2(1,3)S7(3,2)S5(2,3)78910S1(1,2)S4(2,2)1112S1(1,2)13第12頁，共50頁，2022年，5月20日，10點59分，星期日搜索策略2：深度優(yōu)先S0(1,1)S 3(2,1)S6(3,1)S5(2,3)012S8(3,3)S6(3,1)34S2(1,3)56第13頁，共50頁，2022年，5月20日，10點59分，星期日狀態(tài)空間法求解問題的基本過程首先為問題選擇適當的“狀態(tài)”及“操作”的形式化描述方法；然后從某個初始狀態(tài)出發(fā)，每次使用一個“操作”，遞增地建立起操作序列，直到達到目標狀態(tài)為止；此時，由初始狀

7、態(tài)到目標狀態(tài)所使用的算符序列就是該問題的一個解。 第14頁，共50頁，2022年，5月20日，10點59分，星期日狀態(tài)空間求解問題的關鍵選擇合適的狀態(tài)描述形式定義一組算符（操作）搜索策略：決定算符生成進一步狀態(tài)的順序第15頁，共50頁，2022年，5月20日，10點59分，星期日狀態(tài)空間表示方法的應用語法分析a: The dogs kick the ball.b: The small dogs kick the ball.c:The small black dogs kick the ball.d: The small black dogs kick the red ball.第16頁，共50

8、頁，2022年，5月20日，10點59分，星期日搜索策略分類無信息搜索過程寬度優(yōu)先深度優(yōu)先啟發(fā)式搜索過程代價樹的廣度優(yōu)先搜索動態(tài)規(guī)劃法（改進的代價樹廣度優(yōu)先搜索)代價樹的深度優(yōu)先搜索(局部優(yōu)先搜索)代價樹有界深度優(yōu)先搜索局部擇優(yōu)A算法A算法(全局優(yōu)先搜索)第17頁，共50頁，2022年，5月20日，10點59分，星期日2.3 無信息搜索基本術語廣（寬）度優(yōu)先搜索深度優(yōu)先搜索有界深度優(yōu)先搜索第18頁，共50頁，2022年，5月20日，10點59分，星期日基本術語圖搜索：實現從一個隱含圖中,生成出一部分確實含有一個目標節(jié)點的顯式表示子圖的搜索過程.例： 2階“梵塔”問題第19頁，共50頁，2022

9、年，5月20日，10點59分，星期日狀態(tài)空間圖S0(1,1)S3(2,1)S6(3,1)S5(2,3)S7(3,2)S8(3,3)S2(1,3)S1(1,2) S4(2,2)A(1,3)B(1,2)A(3,2)目標目標初始A(1,2)B(1,3)A(2,3)第20頁，共50頁，2022年，5月20日，10點59分，星期日搜索樹：由初始狀態(tài)出發(fā)進行試探，以期找到一條通往目標狀態(tài)的路徑. 記錄這搜索過程的狀態(tài)的樹初始節(jié)點，目標節(jié)點，子節(jié)點節(jié)點深度路徑例： 2階“梵塔”問題第21頁，共50頁，2022年，5月20日，10點59分，星期日基本術語S0(1,1)S 3(2,1)S6(3,1)S5(2,3

10、)S7(3,2)012S8(3,3)S6(3,1)S3(2,1)3465S2(1,3)S7(3,2)S5(2,3)78910S1(1,2)S4(2,2)1112S1(1,2)13初始節(jié)點終止節(jié)點路徑第22頁，共50頁，2022年，5月20日，10點59分，星期日數據結構記錄搜索過程：OPEN表，CLOSED表OPEN表:存放剛生成的節(jié)點OPEN表形式： 狀態(tài)節(jié)點，父節(jié)點CLOSED表:存放將要擴展或已擴展的節(jié)點CLOSED表形式：編號，狀態(tài)節(jié)點，父節(jié)點例： 2階“梵塔”問題第23頁，共50頁，2022年，5月20日，10點59分，星期日搜索樹：寬度優(yōu)先S0(1,1)S 3(2,1)S6(3,1

11、)S5(2,3)S7(3,2)012S8(3,3)S6(3,1)S3(2,1)3465S2(1,3)S7(3,2)S5(2,3)78910S1(1,2)S4(2,2)1112S1(1,2)13第24頁，共50頁，2022年，5月20日，10點59分，星期日初始Open表 CLOSE表狀態(tài)節(jié)點 父節(jié)點 S0(1,1)編號狀態(tài)節(jié)點父節(jié)點第25頁，共50頁，2022年，5月20日，10點59分，星期日第一次擴展Open表 CLOSE表狀態(tài)節(jié)點 父節(jié)點 S3(2,1)S0(1,1)S6(3,1)S0(1,1)編號狀態(tài)結點父結點1S0(1,1)第26頁，共50頁，2022年，5月20日，10點59分，星

12、期日第二次擴展OPEN表 CLOSED表編號狀態(tài)結點父結點1S0(1,1)2S3(2,1)S0(1,1)第27頁，共50頁，2022年，5月20日，10點59分，星期日廣（寬）度優(yōu)先搜索基本思想搜索過程實例算法討論第28頁，共50頁，2022年，5月20日，10點59分，星期日寬度優(yōu)先搜索基本思想從初始節(jié)點S0開始，逐層地對節(jié)點進行擴展并考察它是否為目標節(jié)點，在第n層節(jié)點沒有全部擴展并考察前，不對第n+1層的節(jié)點進行擴展。節(jié)點按進入open表的先后順序排列第29頁，共50頁，2022年，5月20日，10點59分，星期日廣（寬）度優(yōu)先搜索過程(1)把初始節(jié)點S0放入Open表中；(2)如果Ope

13、n表為空，則問題無解，失敗退出；(3)把Open表的第一個節(jié)點取出放入Closed表，并記該節(jié)點為n；(4)考察節(jié)點n是否為目標節(jié)點。若是，則得到問題的解，成功退出；(5)若節(jié)點n不可擴展，則轉第(2)步；(6)擴展節(jié)點n，將其子節(jié)點放入Open表的尾部，并為每一個子節(jié)點設置指向父節(jié)點的指針，然后轉第(2)步。 第30頁，共50頁，2022年，5月20日，10點59分，星期日例1 寬度優(yōu)先（2級梵塔）S0(1,1)S 3(2,1)S6(3,1)S5(2,3)S7(3,2)012S8(3,3)S6(3,1)S3(2,1)3465S2(1,3)S7(3,2)S5(2,3)78910S1(1,2)S

14、4(2,2)1112S1(1,2)13第31頁，共50頁，2022年，5月20日，10點59分，星期日例2：重排九宮問題例：重排九宮問題。在33的方格棋盤上放置八張牌，初始狀態(tài)和目標狀態(tài)如右圖算符有： R1: 如果滿足條件 則 空格左移R2: 如果滿足條件 則 空格上移R3: 如果滿足條件 則 空格右移R4: 如果滿足條件 則 空格下移注：條件指有位置并且不重復沖突解決方法：算符序號2 8 31 47 6 5 1 2 3 8 47 6 5第32頁，共50頁，2022年，5月20日，10點59分，星期日寬度優(yōu)先搜索演示演示.ppt（九宮圖）2 8 31 47 6 51 2 3 47 6 5初始狀

15、態(tài)目標狀態(tài)第33頁，共50頁，2022年，5月20日，10點59分，星期日算法討論存在問題嗎？如何改進？算法特點第34頁，共50頁，2022年，5月20日，10點59分，星期日2 8 31 47 6 52 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 4 6 5 2 31 8 47 6 52 31 8 47 6 52 8 1 4 37 6 52 8 31 4 57 6 8 32 1 47 6 52 8 37 1 46 51 2 3 8 47 6 52 3 41 87 6 52 8 1 4 37

16、 6 52 8 31 4 57 62 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 58 1 32 47 6 52 8 37 46 1 52 8 37 1 46 51 2 38 47 6 513452 8 31 6 4 7 52 8 31 6 47 567891011121314151617181920212223242526寬度優(yōu)先搜索圖(改進)2解的路徑：1381626第35頁，共50頁，2022年，5月20日，10點59分，星期日Open表的變化(改進的寬度優(yōu)先搜索法）初始 (1) 1 (2,3,4,5) 2 (3,4,5,6,7) 3 (4,5,6,7,8,

17、9) 4 (5,6,7,8,9,10,11) 5 (6,7,8,9,10,11,12,13) 6 (7,8,9,10,11,12,13,14) 7 (8,9,10,11,12,13,14,15,) 8 (9,10,11,12,13,14,15,16) 9 (10,11,12,13,14,15,16,17) 10 (11,12,13,14,15,16,17,18) 11 (12,13,14,15,16,17,18,19) 12 (13,14,15,16,17,18,19,20) 13 (14,15,16,17,18,19,20,21) 14 (15,16,17,18,19,20,21,22,23

18、) 15 (16,17,18,19,20,21,22,23,24,25) 16 (17,18,19,20,21,22,23,24,25,) 26第36頁，共50頁，2022年，5月20日，10點59分，星期日 深度優(yōu)先搜索基本思想搜索過程實例算法討論第37頁，共50頁，2022年，5月20日，10點59分，星期日深度優(yōu)先搜索基本思想從初始節(jié)點S0開始，在其子節(jié)點中選擇一個節(jié)點進行擴展并考察它是否為目標節(jié)點，若不是目標節(jié)點，則在該子節(jié)點的子節(jié)點中選擇一個節(jié)點進行考察，一直如此向下搜索。當到達某個子節(jié)點，且該子節(jié)點即不是目標節(jié)點又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進行擴展。節(jié)點按后進入open表的順

19、序排列，即后進入的節(jié)點排在表的最前面第38頁，共50頁，2022年，5月20日，10點59分，星期日深度優(yōu)先搜索過程(1) 把初始節(jié)點S0放入Open表中；(2) 如果Open表為空，則問題無解 ，失敗退出；(3) 把Open表的第一個節(jié)點取出放入Closed表，并記該節(jié)點為n；(4) 考察節(jié)點n是否為目標節(jié)點。若是，則得到問題的解，成功退出；(5) 若節(jié)點n不可擴展，則轉第(2)步； (6) 擴展節(jié)點n，將其子節(jié)點放入Open表的首部，并為每一個子節(jié)點設置 指向父節(jié)點的指針，然后轉第(2)步。 第39頁，共50頁，2022年，5月20日，10點59分，星期日例1 深度優(yōu)先（2級梵塔）S0(1

20、,1)S 3(2,1)S6(3,1)S5(2,3)012S8(3,3)S6(3,1)34S2(1,3)56第40頁，共50頁，2022年，5月20日，10點59分，星期日例2：重排九宮問題例：重排九宮問題。在33的方格棋盤上放置八張牌，初始狀態(tài)和目標狀態(tài)如右圖算符有： R1: 如果滿足條件 則 空格左移R2: 如果滿足條件 則 空格上移R3: 如果滿足條件 則 空格右移R4: 如果滿足條件 則 空格下移注：條件指有位置并且不重復沖突解決方法：算符序號2 8 31 47 6 5 1 2 3 8 47 6 5第41頁，共50頁，2022年，5月20日，10點59分，星期日2 8 31 47 6 5

21、2 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 5 8 32 1 47 6 52 8 37 1 4 6 58 32 1 47 6 58 32 1 47 6 58 1 32 47 6 513456789102深度優(yōu)先搜索圖第42頁，共50頁，2022年，5月20日，10點59分，星期日8 3 42 17 6 5118 3 42 17 6 58 3 42 1 57 6 8 3 4 2 17 6 58 42 3 17 6 58 3 42 6 17 5 3 48 2 17 6 58 3 47 2 1 6 5121314191815163 48 2

22、 17 6 517深度優(yōu)先搜索圖（續(xù)）第43頁，共50頁，2022年，5月20日，10點59分，星期日Open表初始（1）1 （2,3,4,5）2 (6,7,3,4,5)3 (8,7,3,4,5)4 (9,10,7,3,4,5)5 (11,10,7,3,4,5)6 (12,13,10,7,3,4,5)7 (14,15,16,13,10,7,3,4,5)8 (17,18,15,16,13,10,7,3,4,5)9 (19,18,15,16,13,10,7,3,4,5).第44頁，共50頁，2022年，5月20日，10點59分，星期日算法討論存在問題改進方法第45頁，共50頁，2022年，5月20日，10點59分，星期日有界深度優(yōu)先搜索基本思想搜索過程實例第46頁，共50頁，2022年，5月20日，10點59分，星期日有界深度優(yōu)先搜索基本思想對深度優(yōu)先搜索引入搜索深度的限制（設為dm），當搜索深度達到深度界限時，尚未出現目標節(jié)點，就選擇其兄弟節(jié)點進行擴展。節(jié)點按后進入open表的順序排列，即后進入的節(jié)點排在前面深度的確定：固定深度 可變深度 第47頁，共50頁，2022年，5月20日，10點59分，星期日有界深度搜索過程1.將初始節(jié)點S0放