【正文】 4 32 5 61 4 87 32 5 61 4 8 7 32 5 61 4 87 3 2 5 61 4 7 3 82 5 61 47 3 82 5 1 4 67 3 8S 123456789101112131415162 51 4 67 3 82 4 51 67 3 8 2 51 4 67 3 82 4 5 1 67 3 82 4 51 6 7 3 82 4 51 3 67 82 4 51 3 6 7 82 4 51 3 67 8 17181920合肥工業(yè)大學 人工智能與數據挖掘研究室 15/79 盲目搜索 深度優(yōu)先搜索 有界深度優(yōu)先搜索 ： 引入搜索深度限制值 d， 使深度優(yōu)先搜索過程具有完備性 。 設定搜索深度限制 d=5， 問題同深度優(yōu)先算法中的八數碼問題(2)。 合肥工業(yè)大學 人工智能與數據挖掘研究室 16/79 盲目搜索 深度優(yōu)先搜索 2 8 31 6 47 512 8 31 6 47 5 22 8 31 6 7 5 432 81 6 37 5 442 8 31 6 4 7 52 8 31 47 6 52 8 31 4 7 6 52 8 3 1 47 6 52 31 8 47 6 52 3 1 8 47 6 5 2 31 8 47 6 51 2 3 8 47 6 52 3 41 8 7 6 51 2 37 8 4 6 51 2 38 47 6 52 3 41 87 6 52 3 41 8 57 6 2 81 4 37 6 52 4 81 37 6 52 81 4 37 6 52 8 1 4 37 6 52 8 31 4 57 6 2 8 31 4 5 7 62 8 31 57 4 62 8 31 4 57 6 8 32 1 67 5 42 8 37 1 6 5 42 8 3 1 67 5 42 8 31 67 5 42 8 31 5 67 4 2 31 8 67 5 42 3 1 8 67 5 42 8 31 5 6 7 42 8 31 5 67 4 2 81 6 37 5 42 6 81 37 5 42 81 6 37 5 42 31 8 67 5 452326273433282930 2524192021 15 1289DS1822 17 16 14 13 11 10 7 636 35 32 31合肥工業(yè)大學 人工智能與數據挖掘研究室 17/79 盲目搜索 深度優(yōu)先搜索 有界深度優(yōu)先算法步驟： (1)初始結點 S放入堆棧 OPEN中； (2)若 OPEN為空，則搜索失敗，問題無解； (3)彈出 OPEN中棧頂結點 n，放入 CLOSE表中，并給出順序編號 n； (4)若 n為目標結點 D，則搜索成功，問題有解； (5)若 n的深度 d(n)=d，則轉 (2) ； (6)若 n無子結點，即不可擴展，轉 (2) ； (7)擴展結點 n，將其所有子結點配上返回 n的指針，并壓入 OPEN堆棧，轉 (2) 。 合肥工業(yè)大學 人工智能與數據挖掘研究室 18/79 盲目搜索 等代價搜索 寬度優(yōu)先搜索可被推廣用來解決尋找從起始狀態(tài)至目標狀態(tài)的具有最小代價的路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價搜索算法 。 等代價搜索中的幾個記號 起始節(jié)點記為 S； 從節(jié)點 i到它的后繼節(jié)點 j的連接弧線代價記為 c(i， j)； 起始節(jié)點 S到任一節(jié)點 i的路徑代價記為 g(i)。 如果所有的連接弧線具有相等的代價，那么等代價算法就簡化為寬度優(yōu)先搜索算法 。 合肥工業(yè)大學 人工智能與數據挖掘研究室 19/79 啟發(fā)式搜索 盲目搜索的不足：效率低，耗費空間與時間。 啟發(fā)式搜索：利用問題域特性的信息（啟發(fā)信息）進行搜索。 啟發(fā)式搜索策略 啟發(fā)式信息按用途分為三種： （ 1）用于確定要擴展的下一個節(jié)點，避免盲目擴展。 （ 2）在擴展一個節(jié)點的過程中，用于確定要生成哪一個或哪幾個后繼節(jié)點，避免盲目生成所有可能節(jié)點。 （ 3）用于確定某些應該從搜索樹中拋棄或修剪得節(jié)點。 合肥工業(yè)大學 人工智能與數據挖掘研究室 20/79 啟發(fā)式搜索 有序搜索（ ordered search）：利用第一種啟發(fā)信息，總是選擇“最有希望”的節(jié)點作為下一個被擴展的節(jié)點。 估價函數（ evaluation function )：估算節(jié)點“希望”的量度，這種量度叫做估價函數。 建立估價函數的一般方法：試圖確定一個處在最佳路徑上的節(jié)點的概率；提出任意節(jié)點與目標集之間的距離量度或差別量度；或者在棋盤式的博弈和難題中根據棋局的某些特點來決定棋局的得分數。這些特點被認為與向目標節(jié)點前進一步的希望程度有關。 f(n)—— 表示節(jié)點 n的估價函數值 合肥工業(yè)大學 人工智能與數據挖掘研究室 21/79 啟發(fā)式搜索 有序搜索 用估價函數 f來排列 GRAPHSEARCH第 8步中 OPEN表上的節(jié)點。應用某個算法 (例如等代價算法 )選擇 OPEN表上具有最小 f值的節(jié)點作為下一個要擴展的節(jié)點。這種搜索方法叫做有序搜索 或 最佳優(yōu)先搜索 (bestfirst search)，而其算法就叫做有序搜索算法 或 最佳優(yōu)先算法 。 合肥工業(yè)大學 人工智能與數據挖掘研究室 22/79 啟發(fā)式搜索 有序搜索 有序狀態(tài)空間搜索算法： (1) 把起始節(jié)點 S放到 OPEN表中，計算 f(S)并把其值與節(jié)點 S聯(lián)系起來。 (2) 如果 OPEN是個空表，則失敗退出，無解。 (3) 從 OPEN表中選擇一個 f值最小的節(jié)點 i。結果有幾個節(jié)點合格，當其中有一個為目標節(jié)點時，則選擇此目標節(jié)點，否則就選擇其中任一個節(jié)點作為節(jié)點 i。 (4) 把節(jié)點 i從 OPEN表中移出，并把它放入 CLOSED的擴展節(jié)點表中。 合肥工業(yè)大學 人工智能與數據挖掘研究室 23/79 啟發(fā)式搜索 有序搜索 (5) 如果 i是個目標節(jié)點，則成功退出，求得一個解。 (6) 擴展節(jié)點 i，生成其全部后繼節(jié)點。對于 i的每一個后繼節(jié)點 j： (a) 計算 f(j)。 (b) 如果 j既不在 OPEN表中，又不在 CLOSED表中，則用估價函數 f把它添入 OPEN表。從 j加一指向其父輩節(jié)點 i的指針，以便一旦找到目標節(jié)點時記住一個解答路徑。 (c) 如果 j已在 OPEN表上或 CLOSED表上，則比較剛剛對 j計算過的 f值和前面計算過的該節(jié)點在表中的 f值。如果新的 f值較小，則 合肥工業(yè)大學 人工智能與數據挖掘研究室 24/79 啟發(fā)式搜索 有序搜索 (i) 以此新值取代舊值。 (ii) 從 j指向 i，而不是指向它的父輩節(jié)點。 (iii) 如果節(jié)點 j在 CLOSED表中，則把它移回 OPEN表。 (7) 轉向 (2)，即 GO TO(2)。 合肥工業(yè)大學 人工智能與數據挖掘研究室 25/79 啟發(fā)式搜索 有序搜索 開始 把 S放入 OPEN表 OPEN為空表？ 失敗 選取 OPEN表中 f值最小 的節(jié)點 i，放入 CLOSED表 i=Sg？ 成功 是 是 擴展 i得后繼節(jié)點 j，計算 f(j)，提 供返回 i的指針，利用 f(j)對 OPEN 表重新排序調整父子關系及指針 合肥工業(yè)大學 人工智能與數據挖掘研究室 26/79 啟發(fā)式搜索 有序搜索 寬度優(yōu)先搜索、等代價搜索和深度優(yōu)先搜索統(tǒng)統(tǒng)是有序搜索技術的特例。對于寬度優(yōu)先搜索，選擇 f(i)作為節(jié)點 i的深度。對于等代價搜索， f(i)是從起始節(jié)點至節(jié)點 i這段路徑的代價。 有序搜索的有效性直接取決于 f的選擇，如果選擇的 f不合適，有序搜索就可能失去一個最好的解甚至全部的解。如果沒有適用的準確的希望量度，那么 f的選擇將涉及兩個方面的內容：一方面是一個時間和空間之間的折衷方案；另一方面是保證有一個最優(yōu)的解或任意解。 合肥工業(yè)大學 人工智能與數據挖掘研究室 27/79 啟發(fā)式搜索 有序搜索 例 ：八數碼難題 , 采用了簡單的估價函數 f(n)=d(n)+W(n) 其中： d(n)是搜索樹中節(jié)點 n的深度； W(n)用來計算對應于節(jié)點 n的數據庫中錯放的棋子個數。因此，起始節(jié)點棋局 的 f值等于 0+4=4。 2 8 3 1 6 4 7 5 合肥工業(yè)大學 人工智能與數據挖掘研究室 28/79 啟發(fā)式搜索 有序搜索 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 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 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 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 合肥工業(yè)大學 人工智能與數據挖掘研究室 29/79 啟發(fā)式搜索 A*算法 A*算法是一種有序搜索算法，