人工智能第二章上

人工智能第二章上第1頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月2.1搜索問(wèn)題問(wèn)題提出 人工智能要解決的問(wèn)題是非結(jié)構(gòu)化問(wèn)題；難以獲得求解所需的全部信息；

更沒(méi)有現(xiàn)成的算法可供求解使用。應(yīng)用第2頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月搜索需要解決的問(wèn)題知識(shí)表示（狀態(tài)空間表示）搜索策略（如何搜索，知識(shí)的使用）最優(yōu)搜索(如何找到最優(yōu)路徑）第3頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月2.2狀態(tài)空間表示法表示方法

(1)狀態(tài)(State):Sk=［Sk1,Sk2,…Skn］

(2)操作(Operator):操作描述了狀態(tài)之間的關(guān)系

表示：F:{f1,f2,……fn｝(3)狀態(tài)空間(StateSpace)三元組表示〈S,F,G〉其中：S初始狀態(tài)集G：目標(biāo)狀態(tài)集合

F：操作的集合。第4頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月?tīng)顟B(tài)空間圖可有相應(yīng)的賦值有向圖節(jié)點(diǎn)表示狀態(tài)，有向邊表示操作問(wèn)題求解過(guò)程轉(zhuǎn)化為在圖中尋找從初始狀態(tài)S出發(fā)到達(dá)目標(biāo)狀態(tài)G的路徑問(wèn)題，也就是尋找操作序列的問(wèn)題第5頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月舉例（用狀態(tài)空間方法）

2階“梵塔”問(wèn)題(TowerofHanoiProblem):有三個(gè)柱子(1，2和3)和兩個(gè)不同尺寸的圓盤(pán)(A，B)。在每個(gè)圓盤(pán)的中心有個(gè)孔，所以圓盤(pán)可以堆疊在柱子上,最初,全部?jī)蓚€(gè)圓盤(pán)都堆在柱子1上(最大的在底部,最小的在頂部)。要求把所有圓盤(pán)都移到另一個(gè)柱子上，搬動(dòng)規(guī)則為：(1)一次只能搬一個(gè)圓盤(pán)(2)不能將大圓盤(pán)放在小圓盤(pán)上(3)可以利用空柱子。(example,hono)第6頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月用狀態(tài)空間方法來(lái)描述問(wèn)題：狀態(tài)的表示柱的編號(hào)用i,j來(lái)代表

(i,j)表示問(wèn)題的狀態(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=(3,3)第7頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月初始狀態(tài)S={s0}，目標(biāo)狀態(tài)G={s4,s8}S0=(1,1)A132BS4=(2,2)123ABS8=(3,3)123AB第8頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月操作（算符）定義操作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)約束：不能將大圓盤(pán)（B）放在小圓盤(pán)（A）上第9頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月?tīng)顟B(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)第10頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月搜索要解決的問(wèn)題搜索策略：如何找到解的路徑即如何生成進(jìn)一步的狀態(tài)約定：不可走回頭路搜索圖：?jiǎn)栴}求解過(guò)程中經(jīng)過(guò)的所有路徑最優(yōu)解：使用操作（算符）最少的解例第11頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月搜索策略1：寬度優(yōu)先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)S4(2,2)1112S1(1,2)13第12頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月搜索策略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è)，創(chuàng)作于2023年2月?tīng)顟B(tài)空間法求解問(wèn)題的基本過(guò)程首先為問(wèn)題選擇適當(dāng)?shù)摹盃顟B(tài)”及“操作”的形式化描述方法；然后從某個(gè)初始狀態(tài)出發(fā)，每次使用一個(gè)“操作”，遞增地建立起操作序列，直到達(dá)到目標(biāo)狀態(tài)為止；此時(shí)，由初始狀態(tài)到目標(biāo)狀態(tài)所使用的算符序列就是該問(wèn)題的一個(gè)解。

第14頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月?tīng)顟B(tài)空間求解問(wèn)題的關(guān)鍵選擇合適的狀態(tài)描述形式定義一組算符（操作）搜索策略：決定算符生成進(jìn)一步狀態(tài)的順序第15頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月?tīng)顟B(tài)空間表示方法的應(yīng)用語(yǔ)法分析a:Thedogskicktheball.b:Thesmalldogskicktheball.c:Thesmallblackdogskicktheball.d:Thesmallblackdogskicktheredball.第16頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月搜索策略分類(lèi)無(wú)信息搜索過(guò)程寬度優(yōu)先深度優(yōu)先啟發(fā)式搜索過(guò)程代價(jià)樹(shù)的廣度優(yōu)先搜索動(dòng)態(tài)規(guī)劃法（改進(jìn)的代價(jià)樹(shù)廣度優(yōu)先搜索)代價(jià)樹(shù)的深度優(yōu)先搜索(局部?jī)?yōu)先搜索)代價(jià)樹(shù)有界深度優(yōu)先搜索局部擇優(yōu)A算法A算法(全局優(yōu)先搜索)第17頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月2.3無(wú)信息搜索基本術(shù)語(yǔ)廣（寬）度優(yōu)先搜索深度優(yōu)先搜索有界深度優(yōu)先搜索第18頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月基本術(shù)語(yǔ)圖搜索：實(shí)現(xiàn)從一個(gè)隱含圖中,生成出一部分確實(shí)含有一個(gè)目標(biāo)節(jié)點(diǎn)的顯式表示子圖的搜索過(guò)程.例：2階“梵塔”問(wèn)題第19頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月?tīng)顟B(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è)，創(chuàng)作于2023年2月搜索樹(shù)：由初始狀態(tài)出發(fā)進(jìn)行試探，以期找到一條通往目標(biāo)狀態(tài)的路徑.記錄這搜索過(guò)程的狀態(tài)的樹(shù)初始節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)，子節(jié)點(diǎn)節(jié)點(diǎn)深度路徑例：2階“梵塔”問(wèn)題第21頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月基本術(shù)語(yǔ)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)S4(2,2)1112S1(1,2)13初始節(jié)點(diǎn)終止節(jié)點(diǎn)路徑第22頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月數(shù)據(jù)結(jié)構(gòu)記錄搜索過(guò)程：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階“梵塔”問(wèn)題第23頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月搜索樹(shù)：寬度優(yōu)先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)S4(2,2)1112S1(1,2)13第24頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月初始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è)，創(chuàng)作于2023年2月第一次擴(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è)，創(chuàng)作于2023年2月第二次擴(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è)，創(chuàng)作于2023年2月廣（寬）度優(yōu)先搜索基本思想搜索過(guò)程實(shí)例算法討論第28頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月寬度優(yōu)先搜索基本思想從初始節(jié)點(diǎn)S0開(kāi)始，逐層地對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察它是否為目標(biāo)節(jié)點(diǎn)，在第n層節(jié)點(diǎn)沒(méi)有全部擴(kuò)展并考察前，不對(duì)第n+1層的節(jié)點(diǎn)進(jìn)行擴(kuò)展。節(jié)點(diǎn)按進(jìn)入open表的先后順序排列第29頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月廣（寬）度優(yōu)先搜索過(guò)程(1)把初始節(jié)點(diǎn)S0放入Open表中；(2)如果Open表為空，則問(wèn)題無(wú)解，失敗退出；(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n；(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問(wè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è)，創(chuàng)作于2023年2月例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)S4(2,2)1112S1(1,2)13第31頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月例2：重排九宮問(wèn)題例：重排九宮問(wèn)題。在3×3的方格棋盤(pán)上放置八張牌，初始狀態(tài)和目標(biāo)狀態(tài)如右圖算符有：R1:如果滿(mǎn)足條件則空格左移R2:如果滿(mǎn)足條件則空格上移R3:如果滿(mǎn)足條件則空格右移R4:如果滿(mǎn)足條件則空格下移注：條件指有位置并且不重復(fù)沖突解決方法：算符序號(hào)2831476512384765第32頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月寬度優(yōu)先搜索演示演示.ppt

（九宮圖）283147651234765初始狀態(tài)目標(biāo)狀態(tài)第33頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月算法討論存在問(wèn)題嗎？如何改進(jìn)？算法特點(diǎn)第34頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月2831476528314765231847652831476528316475832147652837146523184765231847652814376528314576832147652837146512384765234187652814376528314576283641752831675483214765813247652837461528371465123847651345283164752831647567891011121314151617181920212223242526寬度優(yōu)先搜索圖(改進(jìn))2解的路徑：1－3－8－16－26第35頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月Open表的變化(改進(jìn)的寬度優(yōu)先搜索法）初始(1)1(2,3,4,5)2(3,4,5,6,7)3(4,5,6,7,8,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)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è)，創(chuàng)作于2023年2月深度優(yōu)先搜索基本思想搜索過(guò)程實(shí)例算法討論第37頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月深度優(yōu)先搜索基本思想從初始節(jié)點(diǎn)S0開(kāi)始，在其子節(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表的順序排列，即后進(jìn)入的節(jié)點(diǎn)排在表的最前面第38頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月深度優(yōu)先搜索過(guò)程(1)把初始節(jié)點(diǎn)S0放入Open表中；(2)如果Open表為空，則問(wèn)題無(wú)解，失敗退出；(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n；(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問(wè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è)，創(chuàng)作于2023年2月例1深度優(yōu)先（2級(jí)梵塔）S0(1,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è)，創(chuàng)作于2023年2月例2：重排九宮問(wèn)題例：重排九宮問(wèn)題。在3×3的方格棋盤(pán)上放置八張牌，初始狀態(tài)和目標(biāo)狀態(tài)如右圖算符有：R1:如果滿(mǎn)足條件則空格左移R2:如果滿(mǎn)足條件則空格上移R3:如果滿(mǎn)足條件則空格右移R4:如果滿(mǎn)足條件則空格下移注：條件指有位置并且不重復(fù)沖突解決方法：算符序號(hào)2831476512384765第41頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月2831476528314765231847652831476528316475832147652837146583214765832147658132476513456789102深度優(yōu)先搜索圖第42頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月834217651183421765834215768342176584231765834261753482176583472165121314191815163482176517深度優(yōu)先搜索圖（續(xù)）第43頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月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è)，創(chuàng)作于2023年2月算法討論存在問(wèn)題改進(jìn)方法第45頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月有界深度優(yōu)先搜索基本思想搜索過(guò)程實(shí)例第46頁(yè)，課件共50頁(yè)，創(chuàng)作于2023年2月有界深度優(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è)，創(chuàng)作于2023年2月有界深度搜索過(guò)程1.將初始節(jié)點(diǎn)S0放入OPEN表,置S0的深度d(S0)=02.如果OPEN表為空，則問(wèn)題無(wú)解，退出