【正文】 義 )。因此，起始節(jié)點棋局 的 f值等于 0+4=4。對于等代價搜索， f(i)是從起始節(jié)點至節(jié)點 i這段路徑的代價。 (iii) 如果節(jié)點 j在 CLOSED表中，則把它移回 OPEN表。從 j加一指向其父輩節(jié)點 i的指針，以便一旦找到目標節(jié)點時記住一個解答路徑。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 23/79 啟發(fā)式搜索 有序搜索 (5) 如果 i是個目標節(jié)點，則成功退出，求得一個解。 (2) 如果 OPEN是個空表，則失敗退出，無解。 f(n)—— 表示節(jié)點 n的估價函數(shù)值 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 21/79 啟發(fā)式搜索 有序搜索 用估價函數(shù) f來排列 GRAPHSEARCH第 8步中 OPEN表上的節(jié)點。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 20/79 啟發(fā)式搜索 有序搜索（ ordered search）：利用第一種啟發(fā)信息，總是選擇“最有希望”的節(jié)點作為下一個被擴展的節(jié)點。 啟發(fā)式搜索：利用問題域特性的信息（啟發(fā)信息）進行搜索。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 18/79 盲目搜索 等代價搜索 寬度優(yōu)先搜索可被推廣用來解決尋找從起始狀態(tài)至目標狀態(tài)的具有最小代價的路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價搜索算法 。 初始布局 S和目標狀態(tài) D如下圖所示： 2674138516748325S D合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 12/79 盲目搜索 寬度優(yōu)先搜索 例 八數(shù)碼問題 2 8 3 1 47 6 52 31 8 47 6 52 8 31 47 6 5 8 32 1 47 6 52 8 37 1 4 6 58 32 1 47 6 58 3 2 1 47 6 52 81 4 37 6 52 31 8 47 6 52 8 31 4 57 6 2 31 8 47 6 52 8 31 6 4 7 58 1 32 47 6 58 3 42 1 7 6 58 1 3 2 47 6 58 1 32 47 6 5 8 32 6 41 7 52 8 37 46 1 52 8 1 6 37 5 42 8 37 1 46 52 8 31 67 5 41 2 38 47 6 51 2 37 8 4 6 52 3 41 87 6 52 3 41 8 57 6 2 81 4 37 6 52 4 81 37 6 52 8 31 4 5 7 62 8 36 41 7 52 8 31 57 4 68 1 32 6 47 52 8 3 7 46 1 52 37 8 46 1 52 8 37 46 1 52 8 37 16 5 42 8 31 6 7 5 42 8 3 6 41 7 52 8 31 4 57 62 81 4 37 6 52 3 41 87 6 51 2 3 8 47 6 52 8 37 1 46 52 8 31 6 47 5 2 8 31 6 47 52 8 31 47 6 5S12 3 4 512 131110987614 15 16 1722 23 24 252618 19 20 21D合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 13/79 盲目搜索 深度優(yōu)先搜索 深度優(yōu)先算法步驟： (1) 初始結(jié)點 S放到未擴展節(jié)點 OPEN中； (2) 若 OPEN為空，則搜索失敗，問題無解； (3) 彈出 OPEN表中最頂端結(jié)點放到 CLOSE表中，并給出順序編號 n； (4) 若 n為目標結(jié)點 D，則搜索成功，問題有解； (5) 若 n無子結(jié)點，轉(zhuǎn) (2)； (6) 擴展 n結(jié)點，將其所有子結(jié)點配上返回 n的指針，并按次序壓入 OPEN堆棧，轉(zhuǎn) (2) 。如果沒有后繼節(jié)點，則轉(zhuǎn)向上述第 (2)步。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 9/79 盲目搜索 寬度優(yōu)先搜索 定義 如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索（ breadthfirst search) 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 10/79 盲目搜索 寬度優(yōu)先搜索 寬度優(yōu)先搜索算法 (1) 把起始節(jié)點放到 OPEN表中 (如果該起始節(jié)點為一目標節(jié)點，則求得一個解答 )。每當被選作擴展的節(jié)點為目標節(jié)點時，這一過程就宣告成功結(jié)束。 (8) 按某一任意方式或按某個探試值，重排 OPEN表。 (7) 對那些未曾在 G中出現(xiàn)過的 (既未曾在 OPEN表上或CLOSED表上出現(xiàn)過的 )M成員設置一個通向 n的指針。稱此節(jié)點為節(jié)點 n。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 3/79 盲目搜索 圖搜索策略 例 從王某家族的四代中找王 A的后代且其壽命為 X的人 A,47 B1,77 A3,52 B2,65 C2,87 C1,96 D1,77 E1,57 E2,92 F1,32 G1,27 H1,51 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 4/79 盲目搜索 圖搜索策略 (GRAPHSEARCH)的一般過程 (1) 建立一個只含有起始節(jié)點 S的搜索圖 G，把 S放到一個叫做OPEN的未擴展節(jié)點表中。合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 1/79 目錄 ? 第一章 緒論 ? 第二章 知識表示 ? 第三章 搜索技術 ? 第四章 推理技術 ? 第五章 機器學習 ? 第六章 專家系統(tǒng) ? 第七章 自動規(guī)劃系統(tǒng) ? 第八章 自然語言理解 ? 第九章 智能控制 ? 第十章 人工智能程序設計 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 2/79 盲目搜索 盲目搜索：即 無信息搜索 寬度優(yōu)先與深度優(yōu)先 圖搜索策略 圖搜索策略可看作一種在圖中尋找路徑的方法。研究圖搜索的一般策略，能夠給出圖搜索過程的一般步驟。 (4) 選擇 OPEN表上的第一個節(jié)點，把它從 OPEN表移出并放進CLOSED表中。把 M的這些成員作為 n的后繼節(jié)點添入圖 G中。對已在CLOSED表上的每個 M成員，確定是否需要更改圖 G中通向它的每個后裔節(jié)點的指針方向。這種排序可以是任意的即盲目的 (屬于盲目搜索 )，也可以用以后要討論的各種啟發(fā)思想或其它準則為依據(jù) (屬于啟發(fā)式搜索 )。在失敗終止的情況下，從起始節(jié)點出發(fā)，一定達不到目標節(jié)點。 (4) 擴展節(jié)點 n。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 11/79 盲目搜索 寬度優(yōu)先搜索 例 八數(shù)碼問題 操作規(guī)定 : 允許空格四周上 、 下 、 左 、 右的數(shù)碼塊移入空格中 ， 不許斜方向移動 ， 不許返回先輩結(jié)點 。 合肥工業(yè)大學 人工智能與數(shù)據(jù)挖掘研究室 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è)大學 人工智能與數(shù)據(jù)挖掘研究室 17/79