人工智能3課件

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

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

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

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

5、度+1 邊緣：已經(jīng)出現(xiàn)但還未被擴展的節(jié)點集合。 邊緣的每個元素都是葉節(jié)點，即沒有后續(xù)的節(jié)點 搜素策略就是從邊緣集合中選擇下一個被擴展的節(jié)點的函數(shù),搜索策略,根據(jù)實際問題按照一定的策略和規(guī)則，利用現(xiàn)有的知識一步一步摸索前進，構(gòu)造出一條使問題獲得解決的路徑，即搜索。,搜索的種類： 無信息搜索（盲目搜索） 啟發(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),度量問題求解的性能,完備性：當問題有解時，算法是否能保證找到一個解 最優(yōu)性：找到的解是最

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

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

10、索,邊緣為先進先出隊列，使得先訪問的節(jié)點先被擴展,完備的 如果路徑耗散是節(jié)點深度的非遞減函數(shù)時才是最優(yōu)的 復雜度 當每個狀態(tài)有b個后續(xù)，當解在d層，最壞情況生成節(jié)點數(shù)： b+b2+b3+bd+bd+1-b,廣度優(yōu)先搜索,廣度優(yōu)先搜索,代價一致搜索,擴展路徑消耗最低的節(jié)點 邊緣=依據(jù)路徑耗散排序的隊列 完備的 最優(yōu)的 若單步耗散相等，則等價于廣度優(yōu)先搜索算法,深度優(yōu)先搜索,擴展搜索樹的當前邊緣中最深的節(jié)點,搜索直接推進到搜索樹的最深層，當最深層節(jié)點擴展完沒達到目標節(jié)點則將向上回到下一個還有未擴展后續(xù)節(jié)點的稍淺的節(jié)點。 邊緣為一個棧，即后進先出,深度優(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é)點到葉節(jié)點的路徑 該路徑上每個節(jié)點的所有未被擴展的兄弟節(jié)點 分支因子為b，最大深度為m的狀態(tài)空間，僅需存儲bm+1個節(jié)點。 不是完備的 不是最優(yōu)的,深度優(yōu)先搜索,深度有限搜索,深度為l的節(jié)點被當做沒有后續(xù)的節(jié)點對待。,迭代深入深度優(yōu)先搜索,不斷增大深度限制，直到找到目標節(jié)點。,迭代深入深度優(yōu)先搜索,迭代深入深度優(yōu)先搜索,迭代深入深度優(yōu)先搜索,迭代深入深度優(yōu)先搜索,結(jié)合了深度優(yōu)先和廣度有限的優(yōu)點： 空間需求和深度優(yōu)先一樣小 完備的 當路徑耗散是節(jié)點深度的非遞

12、減函數(shù)時是最優(yōu)的 當搜索空間很大且解的深度未知，迭代深入搜索是首先。,迭代深入深度優(yōu)先搜索,代價一致搜索的迭代搜索,不斷增加的路徑耗散限制,雙向搜索,運行兩個同時的搜索： 向前搜索從初始狀態(tài)向前搜索 向后搜索-從目標狀態(tài)向后搜索 擴展節(jié)點前檢查該節(jié)點是否在另一棵樹的邊緣。,空間需求大 當兩個搜索都是廣度優(yōu)先搜索時是完備的和最優(yōu)的,雙向搜索,b：分支因子 d: 目標節(jié)點深度 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. 標記和修改指針 ADD(j, OPEN), 并標記j到n的指針； 計算是否要修改k、l到n的指針，l到其后續(xù)節(jié)點的指針； 8. 對OPEN中的節(jié)點按某種原則重新排序 9. GO LOOP,節(jié)點類型,修改指針舉例,修改指針舉例,修改指針舉例,廣度優(yōu)先搜索,開始,初始化：把S0放入open表,open表為空？,把open表中的第一個結(jié)點（n)放入closed表中,n為目標節(jié)點？,擴展節(jié)點n，將其

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