【文章內(nèi)容簡介】 [ ] B [BA] [BCDA] [ ] E [EBA] [EFBCDA] [ ] H [HEBA] [HIEFBCDA] [ ] I [IEBA] [IEFBCDA] [H] F [FBA] [FBCDA] [EIH] J [JFBA] [JFBCDA] [EIH] C [CA] [CDA] [BFJEIH] G [GCA] [GCDA] [BFJEIH] 初值： SL=[A]； NSL=[A]； DE=[ ]； CS=A； 37 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 圖搜索的實現(xiàn) ? 用未處理狀態(tài)表 (NSL)使算法能返回 (回溯 )到其中任一個狀態(tài)。 ? 有一張 壞 狀態(tài)表 (DE)避免算法重新搜索無解的路徑。 ? 有當前解題路徑狀態(tài)表 (SL),當滿足目標時可以將它 〈 作為結(jié)果 〉 返回。 ? 為避免陷入死循環(huán)必須是顯式地對新狀態(tài)進行檢查, 看它是否在三張表中。 38 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring ? Backtrack 是狀態(tài)空間搜索的一個基本算法 ,后面所講的圖搜索算法 ,包括深度優(yōu)先 ,廣度優(yōu)先 ,最好優(yōu)先搜索 ,都有回溯中的思想。 ? 基本思想是用表來保存搜索空間中狀態(tài)軌跡的搜索算法。 39 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 度量問題求解的性能 ?完備性 ?最優(yōu)性 ?時間復(fù)雜度 ?空間復(fù)雜度 當問題有解時，這個算法是否能夠保證找到一個解 這個搜索策略是否能夠找到最優(yōu)解 找到一個解需要花費多長時間 在執(zhí)行搜索的過程中需要多少內(nèi)存 40 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 深度和廣度優(yōu)先搜索 廣度優(yōu)先的基本思想： 從初始節(jié)點 S0開始逐層向下擴展，在第 n層節(jié)點還沒有全部搜索完之前，不進入第 n+1層節(jié)點的搜索。 Open表中的節(jié)點總是按進入的先后排序，先進入的節(jié)點排在前面，后進入的節(jié)點排在后面。 深度優(yōu)先的基本思想： 從初始節(jié)點 S0開始，在其子節(jié)點中選擇一個最新生成的節(jié)點進行考察，如果該子節(jié)點不是目標節(jié)點且可以擴展，則擴展該子節(jié)點，然后再在此子節(jié)點的子節(jié)點中選擇一個最新生成的節(jié)點進行考察，依此向下搜索，直到某個子節(jié)點既不是目標節(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進行考察 。 41 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring J D C G F I H E B A 7 5 4 3 2 1 10 6 8 9 goal 深度和廣度優(yōu)先搜索 42 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring ?在深度優(yōu)先搜索中，當查到某一個狀態(tài)時，它所有的子狀態(tài)以及子狀態(tài)的后裔結(jié)點必須先于該狀態(tài)的兄弟狀態(tài)被查找。盡量往深處走，只有再也找不出其后裔時才考慮兄弟。 ?廣度優(yōu)先搜索是一層一層地搜索空間，僅當某一層的狀態(tài)全部搜索完畢，它才轉(zhuǎn)入下一層搜索。 深度和廣度優(yōu)先搜索 43 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 深度和廣度優(yōu)先搜索 圖 用于廣度及深度優(yōu)先搜索的例圖 A C F E G H I J D B U M L S K N O P R Q T 44 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 深度和廣度優(yōu)先搜索 ?廣度 優(yōu)先搜索 關(guān)于實現(xiàn)： 為了保存狀態(tài)空間搜索的軌跡 ,用到了 : open表和 closed表 ?open表：列出了已經(jīng)產(chǎn)生出來但子狀態(tài)未被查找的狀態(tài)。 ?closed表：記錄了已檢查過的狀態(tài)。 45 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring procedure breadth_first_search lnitialize:open=[start]。closed=[ ]。 while open≠[ ] do begin 從 open表中刪除最左邊的狀態(tài) X。 if X 是目標 ,then 返回 (success)。 生成 X 所有的子狀態(tài) 。 將 X 放入 closed 表中 。 從 X 的子狀態(tài)中刪除已經(jīng)在 open或 closed表中的狀態(tài)； 將其余子狀態(tài)按生成的次序放入 open表的右邊。 end 廣度優(yōu)先搜索 46 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring A C F E G H I J D B U M L S K N O P R Q T 目標狀態(tài) =[A]。 closed=[ ]。 =[B,C,D]。 closed=[A]。 =[C,D,E,F]。 closed=[B,A] =[D,E,F,G,H]。 closed=[C,B,A] =[E,F,G,H,I,J]。 closed=[D,C,B,A] =[F,G,H,I,J,K,L]。 closed=[E,D,C,B,A] =[G,H,I,J,K,L,M]。 closed=[F,E,D,C,B,A] =[H,I,J,K,L,M,N]。 closed=[G,F,E,D,C,B,A] 如此重復(fù)直到 U或 open=[ ] 47 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring ?是完備的 ?所需的時間和內(nèi)存： 廣度優(yōu)先搜索 指數(shù)級復(fù)雜度 深度 節(jié)點數(shù) 時間 內(nèi)存 2 1100 IMB 4 111， 100 11秒 106MB 6 107 19分鐘 10GB 8 10931 小時 1TB 10 1011 129天 101TB 48 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 深度和廣度優(yōu)先搜索 ? 深度優(yōu)先搜索 —— 如果已知解題路徑很長 ,深度優(yōu)先搜索就不會在圖中大量的“淺層”狀態(tài)上浪費時間。 —— 但深度優(yōu)先搜索會在圖的深處“迷失方向” ,找不到目標的更短路徑或陷入到一個不通往目標的無限長的路徑中。 —— 深度優(yōu)先搜索耗費的空間量是路徑長度值的線性函數(shù)。 —— 深度優(yōu)先搜索不是最優(yōu)的，不是完備的。 49 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 有界深度優(yōu)先搜索 ?無邊界的搜索樹問題可以通過對深度優(yōu)先搜索提供一個預(yù)先設(shè)定的深度限制來解決。 ?一旦搜索路徑進入某一層時，深度限制便強迫該路徑上的搜索失敗。 ?解決了無窮路徑問題。 ?又是造成不完備的原因。 ?深度優(yōu)先搜索可以看作是有界深度優(yōu)先搜索的一種特殊情況。 50 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 例： 八數(shù)碼問題 。 在 3 3的方格棋盤上 ， 分別放置了表有數(shù)字 8的八張牌 ， 初始狀態(tài) S0， 目標狀態(tài) Sg，如下圖所示 。 可以使用的操作有： 空格左移 ， 空格上移 ， 空格右移 ， 空格下移 即只允許把位于空格左、上、右、下方的牌移入空格。 2 8 3 1 4 7 6 5 1 2 3 8 4 7 6 5 S0 Sg ?廣度優(yōu)先搜索策略 ?深度優(yōu)先搜索策略 51 Department of Computer Science amp。 Technology, Nanjing University Artificial Intelligence Spring 2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 2 8 3 7 4 6