人工智能第二章上

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

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

3、部?jī)蓚€(gè)圓盤都堆在柱子1上(最大的在底部,最小的在頂部)。要求把所有 圓盤都移到另一個(gè)柱子上，搬動(dòng)規(guī)則為： (1)一次只能搬一個(gè)圓盤 (2)不能將大圓盤放在小圓盤上 (3)可以利用空柱子。(example,hono)第6頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日用狀態(tài)空間方法來描述問題：狀態(tài)的表示柱的編號(hào)用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頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日初始狀態(tài)S=s0，目標(biāo)狀態(tài)G=s4,s8S0=(1,1)A132BS4=(2,2)123ABS8=(3,3)123AB第8頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)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頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)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)目標(biāo)目標(biāo)初始A(1,2)B(1,3)A(2,3)第10頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日搜索要解決的問題搜索策略：如何找到解的路徑即如何生成進(jìn)一步的狀態(tài)約定：不可走回頭路搜索圖：?jiǎn)栴}求解過程中經(jīng)過的所有路徑最優(yōu)解：使用操作（算符）最少的解例第11頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)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頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)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頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日狀態(tài)空間法求解問題的基本過程首先為問題選擇適當(dāng)?shù)摹盃顟B(tài)”及“操作”的形式化描述方法；然后從某個(gè)初始狀態(tài)出發(fā)，每次使用一個(gè)“操作”，遞增地建立起操作序列，直到達(dá)到目標(biāo)狀態(tài)為止；此時(shí)，由初始狀

7、態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是該問題的一個(gè)解。 第14頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日狀態(tài)空間求解問題的關(guān)鍵選擇合適的狀態(tài)描述形式定義一組算符（操作）搜索策略：決定算符生成進(jìn)一步狀態(tài)的順序第15頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日狀態(tài)空間表示方法的應(yīng)用語法分析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頁(yè)，共50

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

9、年，5月20日，10點(diǎn)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)目標(biāo)目標(biāo)初始A(1,2)B(1,3)A(2,3)第20頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日搜索樹：由初始狀態(tài)出發(fā)進(jìn)行試探，以期找到一條通往目標(biāo)狀態(tài)的路徑. 記錄這搜索過程的狀態(tài)的樹初始節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)，子節(jié)點(diǎn)節(jié)點(diǎn)深度路徑例： 2階“梵塔”問題第21頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日基本術(shù)語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é)點(diǎn)終止節(jié)點(diǎn)路徑第22頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日數(shù)據(jù)結(jié)構(gòu)記錄搜索過程：OPEN表，CLOSED表OPEN表:存放剛生成的節(jié)點(diǎn)OPEN表形式： 狀態(tài)節(jié)點(diǎn)，父節(jié)點(diǎn)CLOSED表:存放將要擴(kuò)展或已擴(kuò)展的節(jié)點(diǎn)CLOSED表形式：編號(hào)，狀態(tài)節(jié)點(diǎn)，父節(jié)點(diǎn)例： 2階“梵塔”問題第23頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)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頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日初始Open表 CLOSE表狀態(tài)節(jié)點(diǎn) 父節(jié)點(diǎn) S0(1,1)編號(hào)狀態(tài)節(jié)點(diǎn)父節(jié)點(diǎn)第25頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日第一次擴(kuò)展Open表 CLOSE表狀態(tài)節(jié)點(diǎn) 父節(jié)點(diǎn) S3(2,1)S0(1,1)S6(3,1)S0(1,1)編號(hào)狀態(tài)結(jié)點(diǎn)父結(jié)點(diǎn)1S0(1,1)第26頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星

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

13、n表為空，則問題無解，失敗退出；(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n；(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問題的解，成功退出；(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第(2)步；(6)擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的尾部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第(2)步。 第30頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日例1 寬度優(yōu)先（2級(jí)梵塔）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頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日例2：重排九宮問題例：重排九宮問題。在33的方格棋盤上放置八張牌，初始狀態(tài)和目標(biāo)狀態(tài)如右圖算符有： R1: 如果滿足條件 則 空格左移R2: 如果滿足條件 則 空格上移R3: 如果滿足條件 則 空格右移R4: 如果滿足條件 則 空格下移注：條件指有位置并且不重復(fù)沖突解決方法：算符序號(hào)2 8 31 47 6 5 1 2 3 8 47 6 5第32頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日寬度優(yōu)先搜索演示演示.ppt（九宮圖）2 8 31 47 6 51 2 3 47 6 5初始狀

15、態(tài)目標(biāo)狀態(tài)第33頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日算法討論存在問題嗎？如何改進(jìn)？算法特點(diǎn)第34頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)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)先搜索圖(改進(jìn))2解的路徑：1381626第35頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日Open表的變化(改進(jìn)的寬度優(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頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日 深度優(yōu)先搜索基本思想搜索過程實(shí)例算法討論第37頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日深度優(yōu)先搜索基本思想從初始節(jié)點(diǎn)S0開始，在其子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察它是否為目標(biāo)節(jié)點(diǎn)，若不是目標(biāo)節(jié)點(diǎn)，則在該子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察，一直如此向下搜索。當(dāng)?shù)竭_(dá)某個(gè)子節(jié)點(diǎn)，且該子節(jié)點(diǎn)即不是目標(biāo)節(jié)點(diǎn)又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)行擴(kuò)展。節(jié)點(diǎn)按后進(jìn)入open表的順

19、序排列，即后進(jìn)入的節(jié)點(diǎn)排在表的最前面第38頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日深度優(yōu)先搜索過程(1) 把初始節(jié)點(diǎn)S0放入Open表中；(2) 如果Open表為空，則問題無解 ，失敗退出；(3) 把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n；(4) 考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問題的解，成功退出；(5) 若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第(2)步； (6) 擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的首部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置 指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第(2)步。 第39頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日例1 深度優(yōu)先（2級(jí)梵塔）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頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日例2：重排九宮問題例：重排九宮問題。在33的方格棋盤上放置八張牌，初始狀態(tài)和目標(biāo)狀態(tài)如右圖算符有： R1: 如果滿足條件 則 空格左移R2: 如果滿足條件 則 空格上移R3: 如果滿足條件 則 空格右移R4: 如果滿足條件 則 空格下移注：條件指有位置并且不重復(fù)沖突解決方法：算符序號(hào)2 8 31 47 6 5 1 2 3 8 47 6 5第41頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)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頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)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頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)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頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日算法討論存在問題改進(jìn)方法第45頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日有界深度優(yōu)先搜索基本思想搜索過程實(shí)例第46頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日有界深度優(yōu)先搜索基本思想對(duì)深度優(yōu)先搜索引入搜索深度的限制（設(shè)為dm），當(dāng)搜索深度達(dá)到深度界限時(shí)，尚未出現(xiàn)目標(biāo)節(jié)點(diǎn)，就選擇其兄弟節(jié)點(diǎn)進(jìn)行擴(kuò)展。節(jié)點(diǎn)按后進(jìn)入open表的順序排列，即后進(jìn)入的節(jié)點(diǎn)排在前面深度的確定：固定深度 可變深度 第47頁(yè)，共50頁(yè)，2022年，5月20日，10點(diǎn)59分，星期日有界深度搜索過程1.將初始節(jié)點(diǎn)S0放