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