【正文】 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 1/79 目錄 ? 第一章 緒論 ? 第二章 知識表示 ? 第三章 搜索技術(shù) ? 第四章 推理技術(shù) ? 第五章 機器學(xué)習(xí) ? 第六章 專家系統(tǒng) ? 第七章 自動規(guī)劃系統(tǒng) ? 第八章 自然語言理解 ? 第九章 智能控制 ? 第十章 人工智能程序設(shè)計 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 2/79 盲目搜索 盲目搜索：即 無信息搜索 寬度優(yōu)先與深度優(yōu)先 圖搜索策略 圖搜索策略可看作一種在圖中尋找路徑的方法。初始節(jié)點和目標(biāo)節(jié)點分別代表初始數(shù)據(jù)庫和滿足終止條件的數(shù)據(jù)庫。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價于求得圖中的一條路徑問題。研究圖搜索的一般策略，能夠給出圖搜索過程的一般步驟。 合肥工業(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)的一般過程 (1) 建立一個只含有起始節(jié)點 S的搜索圖 G，把 S放到一個叫做OPEN的未擴展節(jié)點表中。 (2) 建立一個叫做 CLOSED的已擴展節(jié)點表，其初始為空表。 (3) LOOP：若 OPEN表是空表，則失敗退出。 (4) 選擇 OPEN表上的第一個節(jié)點，把它從 OPEN表移出并放進CLOSED表中。稱此節(jié)點為節(jié)點 n。 (5) 若 n為一目標(biāo)節(jié)點，則有解并成功退出，此解是追蹤圖 G中沿著指針從 n到 S這條路徑而得到的 (指針將在第 7步中設(shè)置 )。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 5/79 盲目搜索 圖搜索策略 (GRAPHSEARCH)的一般過程 (6) 擴展節(jié)點 n，同時生成不是 n的祖先的那些后繼節(jié)點的集合M。把 M的這些成員作為 n的后繼節(jié)點添入圖 G中。 (7) 對那些未曾在 G中出現(xiàn)過的 (既未曾在 OPEN表上或CLOSED表上出現(xiàn)過的 )M成員設(shè)置一個通向 n的指針。把 M的這些成員加進 OPEN表。對已經(jīng)在 OPEN或 CLOSED表上的每一個 M成員，確定是否需要更改通到 n的指針方向。對已在CLOSED表上的每個 M成員，確定是否需要更改圖 G中通向它的每個后裔節(jié)點的指針方向。 (8) 按某一任意方式或按某個探試值，重排 OPEN表。 (9) GO LOOP。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 6/79 盲目搜索 節(jié)點 父輩節(jié)點 圖搜索策略 （ 1） OPEN表與 CLOSE表 OPEN表 CLOSED表 編號 節(jié)點 父輩節(jié)點 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 7/79 盲目搜索 圖搜索策略 3. 搜索圖與搜索樹 搜索過程框圖 開 始 初始化 ： S 放入 OPEN 表 ， CLOES 表置空 , n = 1 OPEN 表中的第一個結(jié)點 n 移至 CLOSE 表 若 n 的后繼未曾在搜索圖 G 中出現(xiàn) ， 則將其放入 OPEN 表的末端 ， 并提供返回結(jié)點 n 的指針 , 置 n = n + 1 根據(jù)后繼結(jié)點在搜索圖 G 中的出現(xiàn)情況 修改指針方向 依某種準(zhǔn)則重新排序 OPEN 表 失敗 成功 N Y N OPEN 為空表 NULL ？ n = 目標(biāo)結(jié)點 D 嗎 ? Y 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 8/79 盲目搜索 圖搜索策略 ： 圖搜索過程的第 8步對 OPEN表上的節(jié)點進行排序，以便能夠從中選出一個“最好”的節(jié)點作為第 4步擴展用。這種排序可以是任意的即盲目的 (屬于盲目搜索 )，也可以用以后要討論的各種啟發(fā)思想或其它準(zhǔn)則為依據(jù) (屬于啟發(fā)式搜索 )。每當(dāng)被選作擴展的節(jié)點為目標(biāo)節(jié)點時，這一過程就宣告成功結(jié)束。這時，能夠重現(xiàn)從起始節(jié)點到目標(biāo)節(jié)點的這條成功路徑，其辦法是從目標(biāo)節(jié)點按指針向 S返回追溯。當(dāng)搜索樹不再剩有未被擴展的端節(jié)點時，過程就以失敗告終 (某些節(jié)點最終可能沒有后繼節(jié)點，所以 OPEN表可能最后變成空表 )。在失敗終止的情況下，從起始節(jié)點出發(fā)，一定達不到目標(biāo)節(jié)點。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 9/79 盲目搜索 寬度優(yōu)先搜索 定義 如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索（ breadthfirst search) 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 10/79 盲目搜索 寬度優(yōu)先搜索 寬度優(yōu)先搜索算法 (1) 把起始節(jié)點放到 OPEN表中 (如果該起始節(jié)點為一目標(biāo)節(jié)點，則求得一個解答 )。 (2) 如果 OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。 (3) 把第一個節(jié)點 (節(jié)點 n)從 OPEN表移出，并把它放入CLOSED的擴展節(jié)點表中。 (4) 擴展節(jié)點 n。如果沒有后繼節(jié)點，則轉(zhuǎn)向上述第 (2)步。 (5) 把 n的所有后繼節(jié)點放到 OPEN表的末端，并提供從這些后繼節(jié)點回到 n的指針。 (6) 如果 n的任一個后繼節(jié)點是個目標(biāo)節(jié)點，則找到一個解答，成功退出；否則轉(zhuǎn)向第 (2)步。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 11/79 盲目搜索 寬度優(yōu)先搜索 例 八數(shù)碼問題 操作規(guī)定 : 允許空格四周上 、 下 、 左 、 右的數(shù)碼塊移入空格中 ， 不許斜方向移動 ， 不許返回先輩結(jié)點 。 初始布局 S和目標(biāo)狀態(tài) D如下圖所示： 2674138516748325S D合肥工業(yè)大學(xué) 人工智能與數(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è)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 13/79 盲目搜索 深度優(yōu)先搜索 深度優(yōu)先算法步驟： (1) 初始結(jié)點 S放到未擴展節(jié)點 OPEN中； (2) 若 OPEN為空，則搜索失敗，問題無解； (3) 彈出 OPEN表中最頂端結(jié)點放到 CLOSE表中，并給出順序編號 n； (4) 若 n為目標(biāo)結(jié)點 D，則搜索成功，問題有解； (5) 若 n無子結(jié)點，轉(zhuǎn) (2)； (6) 擴展 n結(jié)點，將其所有子結(jié)點配上返回 n的指針，并按次序壓入 OPEN堆棧，轉(zhuǎn) (2) 。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 14/79 盲目搜索 深度優(yōu)先搜索 2 8 31 6 47 52 8 31 6 4 7 52 8 31 47 6 52 8 31 6 47 5 2 8 31 6 7 5 42 8 31 67 5 42 8 1 6 37 5 42 81 6 37 5 4 2 81 6 37 5 42 6 81 37 5 42 6 8 1 37 5 42 6 81 3 7 5 42 6 81 5 37 42 6 81 5 3 7 42 6 81 5 37 4 2 6 81 5 7 4 32 6 1 5 87 4 32 6 81 57 4 32 5 61 87 4 3 2 61 5 87 4 32 61 5 87 4 32 5 6 1 87 4 32 5 61 8 7