人工智能3課件

1、人工智能一種現(xiàn)代方法,第二部份問題求解 PROBLEM -SOLVING,第三章 用搜索法對(duì)問題求解,3.1 問題求解智能體 3.2 問題實(shí)例 3.3 對(duì)解的搜索 3.4 無(wú)信息的搜索策略 3.5 避免重復(fù)狀態(tài) 3.6 使用不完全信息搜索 3.5 小結(jié) 3.6 參考文獻(xiàn)與歷史注釋 習(xí)題,問題求解智能體,目標(biāo)形式化 問題形式化：對(duì)于給定的目標(biāo)需要考慮哪些行動(dòng)和狀態(tài) 的過程。生成狀態(tài)空間，通過搜索獲得解。 搜索,形式化,執(zhí)行,搜索,行動(dòng)序列 （問題的解）,問題求解實(shí)質(zhì)是通過搜索找到行動(dòng)序列以達(dá)到目標(biāo).,一個(gè)問題可形式化的定義為四個(gè)組成部分,初始狀態(tài):智能體的起始狀態(tài) 對(duì)智能體可采納的可能行動(dòng)的描述

2、： 后續(xù)函數(shù)Successor-FN(x) 給定一個(gè)狀態(tài)x，返回一個(gè)由有序?qū)M成的集合，其中每個(gè)行動(dòng)都是狀態(tài)x下的合法行動(dòng) 目標(biāo)測(cè)試：確定給定的狀態(tài)是不是目標(biāo)狀態(tài) 路徑耗散：為每條路徑分配一個(gè)數(shù)值化的耗散值,問題的解：從初始狀態(tài)到目標(biāo)狀態(tài)的路徑 最優(yōu)解：路徑耗散最小的解,初始狀態(tài)和它的后續(xù)函數(shù)隱含地定義了問題的狀態(tài)空間,狀態(tài)空間：從初始狀態(tài)可以達(dá)到的所有狀態(tài)的集合。,一個(gè)問題可形式化的定義為四個(gè)組成部分,初始狀態(tài):智能體的起始狀態(tài) 對(duì)智能體可采納的可能行動(dòng)的描述： 后續(xù)函數(shù)Successor-FN(x) 給定一個(gè)狀態(tài)x，返回一個(gè)由有序?qū)M成的集合，其中每個(gè)行動(dòng)都是狀態(tài)x下得合法行動(dòng) 目標(biāo)測(cè)試：

3、確定給定的狀態(tài)是不是目標(biāo)狀態(tài) 路徑耗散：為每條路徑分配一個(gè)數(shù)值化的耗散值,問題的解：從初始狀態(tài)到目標(biāo)狀態(tài)的路徑 最優(yōu)解：路徑耗散最小的解,問題實(shí)例,玩具問題(真空吸塵器) 八皇后問題 旅行商問題,真空吸塵器世界,狀態(tài)：8個(gè)可能的狀態(tài),后續(xù)函數(shù)：用來產(chǎn)生通過左移、右移、吸塵能夠到達(dá)的合法狀態(tài) 目標(biāo)測(cè)試：用來檢測(cè)是否所有的方格都干凈 路徑耗散：假設(shè)每一步的耗散值為1,皇后問題,增量形式化 初始狀態(tài)：空棋盤 完全狀態(tài)形式化 初始狀態(tài)：所有棋子在棋盤上，但有沖突。,尋徑問題,狀態(tài)：位置和當(dāng)前時(shí)間 初始狀態(tài) 后續(xù)函數(shù)： 乘坐的航班、飛行時(shí)間、候機(jī)時(shí)間狀態(tài) 目標(biāo)測(cè)試：是否在預(yù)定時(shí)間到達(dá)目的地 路徑耗散：等

4、待時(shí)間、飛行時(shí)間、座位的質(zhì)量、費(fèi)用 旅行商問題： 狀態(tài)：當(dāng)前位置和已經(jīng)訪問過的城市集合 目標(biāo)測(cè)試：是否在目的地且已訪問過所有城市,搜索樹,由初始狀態(tài)和后續(xù)函數(shù)產(chǎn)生,搜索樹,擴(kuò)展：把后續(xù)函數(shù)應(yīng)用于當(dāng)前狀態(tài)，生成新的狀態(tài)集。即生成該節(jié)點(diǎn)的所有后續(xù)節(jié)點(diǎn)，并給出它們之間的耗散值。,樹 = 狀態(tài)空間？,節(jié)點(diǎn)-包含5個(gè)元素的數(shù)據(jù)結(jié)構(gòu)： 狀態(tài)：狀態(tài)空間中和該節(jié)點(diǎn)相對(duì)應(yīng)的狀態(tài) 父節(jié)點(diǎn)：搜索樹中產(chǎn)生該節(jié)點(diǎn)的父節(jié)點(diǎn) 行動(dòng)：由父節(jié)點(diǎn)產(chǎn)生該節(jié)點(diǎn)所用的行動(dòng) 路徑耗散：從初始狀態(tài)到達(dá)該節(jié)點(diǎn)的路徑耗散，路徑由父指針表示 路徑長(zhǎng)度：從初始狀態(tài)到達(dá)該節(jié)點(diǎn)所經(jīng)路徑上的步數(shù),搜索樹,節(jié)點(diǎn)深度：根節(jié)點(diǎn)深度=0 其他節(jié)點(diǎn)深度=父節(jié)點(diǎn)深

5、度+1 邊緣：已經(jīng)出現(xiàn)但還未被擴(kuò)展的節(jié)點(diǎn)集合。 邊緣的每個(gè)元素都是葉節(jié)點(diǎn)，即沒有后續(xù)的節(jié)點(diǎn) 搜素策略就是從邊緣集合中選擇下一個(gè)被擴(kuò)展的節(jié)點(diǎn)的函數(shù),搜索策略,根據(jù)實(shí)際問題按照一定的策略和規(guī)則，利用現(xiàn)有的知識(shí)一步一步摸索前進(jìn)，構(gòu)造出一條使問題獲得解決的路徑，即搜索。,搜索的種類： 無(wú)信息搜索（盲目搜索） 啟發(fā)式搜索（有信息搜索）,回溯,（）,（）,(（1,1）),（）,(（1,1）),(（1,1）,(2,3),（）,(（1,1）),(（1,1）,(2,3),（）,(（1,1）),(（1,1）,(2,3),(（1,1）,(2,4),（）,(（1,1）),(（1,1）,(2,3),(（1,1）,(2,

6、4),(（1,1）,(2,4), (3,2),（）,(（1,1）),(（1,1）,(2,3),(（1,1）,(2,4),(（1,1）,(2,4), (3,2),（）,(（1,1）),(（1,1）,(2,3),(（1,1）,(2,4),(（1,1）,(2,4), (3,2),（）,(（1,1）),(（1,1）,(2,3),(（1,1）,(2,4),(（1,1）,(2,4), (3,2),（）,(（1,1）),(（1,1）,(2,3),(（1,1）,(2,4),(（1,1）,(2,4), (3,2),(（1,2）),（）,(（1,1）),(（1,1）,(2,3),(（1,1）,(2,4),(（1,

7、1）,(2,4), (3,2),(（1,2）),(（1,2）,(2,4),（）,(（1,1）),(（1,1）,(2,3),(（1,1）,(2,4),(（1,1）,(2,4), (3,2),(（1,2）),(（1,2）,(2,4),(（1,2）,(2,4),(3,1),（）,(（1,1）),(（1,1）,(2,3),(（1,1）,(2,4),(（1,1）,(2,4), (3,2),(（1,2）),(（1,2）,(2,4),(（1,2）,(2,4),(3,1),(（1,2）,(2,4),(3,1),(4,3),度量問題求解的性能,完備性：當(dāng)問題有解時(shí)，算法是否能保證找到一個(gè)解 最優(yōu)性：找到的解是最

8、優(yōu)解 時(shí)間復(fù)雜度：找到一個(gè)解需要花多長(zhǎng)時(shí)間 搜索中產(chǎn)生的節(jié)點(diǎn)數(shù) 空間復(fù)雜度：在執(zhí)行搜索過程中需要多少內(nèi)存 在內(nèi)存中存儲(chǔ)的最大節(jié)點(diǎn)數(shù),狀態(tài)空間的復(fù)雜度： 分支因子：任何節(jié)點(diǎn)的后續(xù)的最大個(gè)數(shù) 最淺的目標(biāo)節(jié)點(diǎn)的深度 狀態(tài)空間中任何路徑的最大長(zhǎng)度,首先擴(kuò)展根節(jié)點(diǎn)，接著擴(kuò)展根節(jié)點(diǎn)的所有后續(xù)，然后在擴(kuò)展它們的后續(xù)，依次類推。在下一層的任何節(jié)點(diǎn)擴(kuò)展之前搜索樹上本層深度的所有節(jié)點(diǎn)都已經(jīng)擴(kuò)展過。,廣度優(yōu)先搜索,邊緣為先進(jìn)先出隊(duì)列，使得先訪問的節(jié)點(diǎn)先被擴(kuò)展,首先擴(kuò)展根節(jié)點(diǎn)，接著擴(kuò)展根節(jié)點(diǎn)的所有后續(xù)，然后在擴(kuò)展它們的后續(xù)，依次類推。在下一層的任何節(jié)點(diǎn)擴(kuò)展之前搜索樹上本層深度的所有節(jié)點(diǎn)都已經(jīng)擴(kuò)展過。,廣度優(yōu)先搜索,邊

9、緣為先進(jìn)先出隊(duì)列，使得先訪問的節(jié)點(diǎn)先被擴(kuò)展,首先擴(kuò)展根節(jié)點(diǎn)，接著擴(kuò)展根節(jié)點(diǎn)的所有后續(xù)，然后在擴(kuò)展它們的后續(xù)，依次類推。在下一層的任何節(jié)點(diǎn)擴(kuò)展之前搜索樹上本層深度的所有節(jié)點(diǎn)都已經(jīng)擴(kuò)展過。,廣度優(yōu)先搜索,邊緣為先進(jìn)先出隊(duì)列，使得先訪問的節(jié)點(diǎn)先被擴(kuò)展,首先擴(kuò)展根節(jié)點(diǎn)，接著擴(kuò)展根節(jié)點(diǎn)的所有后續(xù)，然后在擴(kuò)展它們的后續(xù)，依次類推。在下一層的任何節(jié)點(diǎn)擴(kuò)展之前搜索樹上本層深度的所有節(jié)點(diǎn)都已經(jīng)擴(kuò)展過。,廣度優(yōu)先搜索,邊緣為先進(jìn)先出隊(duì)列，使得先訪問的節(jié)點(diǎn)先被擴(kuò)展,首先擴(kuò)展根節(jié)點(diǎn)，接著擴(kuò)展根節(jié)點(diǎn)的所有后續(xù)，然后在擴(kuò)展它們的后續(xù)，依次類推。在下一層的任何節(jié)點(diǎn)擴(kuò)展之前搜索樹上本層深度的所有節(jié)點(diǎn)都已經(jīng)擴(kuò)展過。,廣度優(yōu)先搜

10、索,邊緣為先進(jìn)先出隊(duì)列，使得先訪問的節(jié)點(diǎn)先被擴(kuò)展,完備的 如果路徑耗散是節(jié)點(diǎn)深度的非遞減函數(shù)時(shí)才是最優(yōu)的 復(fù)雜度 當(dāng)每個(gè)狀態(tài)有b個(gè)后續(xù)，當(dāng)解在d層，最壞情況生成節(jié)點(diǎn)數(shù)： b+b2+b3+bd+bd+1-b,廣度優(yōu)先搜索,廣度優(yōu)先搜索,代價(jià)一致搜索,擴(kuò)展路徑消耗最低的節(jié)點(diǎn) 邊緣=依據(jù)路徑耗散排序的隊(duì)列 完備的 最優(yōu)的 若單步耗散相等，則等價(jià)于廣度優(yōu)先搜索算法,深度優(yōu)先搜索,擴(kuò)展搜索樹的當(dāng)前邊緣中最深的節(jié)點(diǎn),搜索直接推進(jìn)到搜索樹的最深層，當(dāng)最深層節(jié)點(diǎn)擴(kuò)展完沒達(dá)到目標(biāo)節(jié)點(diǎn)則將向上回到下一個(gè)還有未擴(kuò)展后續(xù)節(jié)點(diǎn)的稍淺的節(jié)點(diǎn)。 邊緣為一個(gè)棧，即后進(jìn)先出,深度優(yōu)先搜索,深度優(yōu)先搜索,深度優(yōu)先搜索,深度優(yōu)先搜

11、索,深度優(yōu)先搜索,深度優(yōu)先搜索,深度優(yōu)先搜索,深度優(yōu)先搜索,深度優(yōu)先搜索,深度優(yōu)先搜索,深度優(yōu)先搜索,深度優(yōu)先搜索,內(nèi)存需求少： 一條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑 該路徑上每個(gè)節(jié)點(diǎn)的所有未被擴(kuò)展的兄弟節(jié)點(diǎn) 分支因子為b，最大深度為m的狀態(tài)空間，僅需存儲(chǔ)bm+1個(gè)節(jié)點(diǎn)。 不是完備的 不是最優(yōu)的,深度優(yōu)先搜索,深度有限搜索,深度為l的節(jié)點(diǎn)被當(dāng)做沒有后續(xù)的節(jié)點(diǎn)對(duì)待。,迭代深入深度優(yōu)先搜索,不斷增大深度限制，直到找到目標(biāo)節(jié)點(diǎn)。,迭代深入深度優(yōu)先搜索,迭代深入深度優(yōu)先搜索,迭代深入深度優(yōu)先搜索,迭代深入深度優(yōu)先搜索,結(jié)合了深度優(yōu)先和廣度有限的優(yōu)點(diǎn)： 空間需求和深度優(yōu)先一樣小 完備的 當(dāng)路徑耗散是節(jié)點(diǎn)深度的非遞

12、減函數(shù)時(shí)是最優(yōu)的 當(dāng)搜索空間很大且解的深度未知，迭代深入搜索是首先。,迭代深入深度優(yōu)先搜索,代價(jià)一致搜索的迭代搜索,不斷增加的路徑耗散限制,雙向搜索,運(yùn)行兩個(gè)同時(shí)的搜索： 向前搜索從初始狀態(tài)向前搜索 向后搜索-從目標(biāo)狀態(tài)向后搜索 擴(kuò)展節(jié)點(diǎn)前檢查該節(jié)點(diǎn)是否在另一棵樹的邊緣。,空間需求大 當(dāng)兩個(gè)搜索都是廣度優(yōu)先搜索時(shí)是完備的和最優(yōu)的,雙向搜索,b：分支因子 d: 目標(biāo)節(jié)點(diǎn)深度 m (l)：最大深度,圖搜索,保留已搜索過的所有路徑,G=G0 (G0 = s), OPEN:=(s); CLOSED:=(); LOOP: IF OPEN=() THEN EXIT(FAIL); n:=FIRST(OPEN

13、), REMOVE(n, OPEN) ADD(n, CLOSED); 5. IF GOAL(n) THEN EXIT(SUCCESS); 6. EXPAND(n)-Mi, G=ADD(Mi, G); 7. 標(biāo)記和修改指針 ADD(j, OPEN), 并標(biāo)記j到n的指針； 計(jì)算是否要修改k、l到n的指針，l到其后續(xù)節(jié)點(diǎn)的指針； 8. 對(duì)OPEN中的節(jié)點(diǎn)按某種原則重新排序 9. GO LOOP,節(jié)點(diǎn)類型,修改指針舉例,修改指針舉例,修改指針舉例,廣度優(yōu)先搜索,開始,初始化：把S0放入open表,open表為空？,把open表中的第一個(gè)結(jié)點(diǎn)（n)放入closed表中,n為目標(biāo)節(jié)點(diǎn)？,擴(kuò)展節(jié)點(diǎn)n，將其

14、子節(jié)點(diǎn)放入open表尾部，為每一個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)n的指針,n可擴(kuò)展節(jié)點(diǎn)？,失敗，退出,成功，退出,Y,Y,N,重排九宮問題, , , , , , , , , , , , , , , , , , , , , , , , , ,深度優(yōu)先搜索,開始,初始化：把S0放入open表,open表為空？,把open表中的第一個(gè)結(jié)點(diǎn)（n)放入closed表中,n為目標(biāo)節(jié)點(diǎn)？,擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入open表首部，為每一個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)n的指針,N可擴(kuò)展節(jié)點(diǎn)？,失敗，退出,成功，退出,Y,Y,N,重排九宮問題, , , , , , , , , , , ,有界深度優(yōu)先搜索,開始,初始化：把S0放入open表,open表為空？,把open表中的第一個(gè)結(jié)點(diǎn)（n)放入closed表中,n為目標(biāo)節(jié)點(diǎn)？,擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入open表首，為每一個(gè)子節(jié)點(diǎn)配置指向節(jié)點(diǎn)n的指針，深度加。,N可擴(kuò)展節(jié)點(diǎn)？,失敗，退出,成功，退出,Y,Y,N,深度達(dá)深度界限？,Y,重排九宮問題, , , , , , , , , , , , , , , , , , , , , , , , , ,迭代深入深度優(yōu)先搜索,不斷增大深度限制，直到找到目標(biāo)節(jié)點(diǎn)。 和樹搜索