【正文】 合肥工業(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)先 圖搜索策略 圖搜索策略可看作一種在圖中尋找路徑的方法。初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別代表初始數(shù)據(jù)庫(kù)和滿足終止條件的數(shù)據(jù)庫(kù)。求得把一個(gè)數(shù)據(jù)庫(kù)變換為另一數(shù)據(jù)庫(kù)的規(guī)則序列問(wèn)題就等價(jià)于求得圖中的一條路徑問(wèn)題。研究圖搜索的一般策略，能夠給出圖搜索過(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)的一般過(guò)程 (1) 建立一個(gè)只含有起始節(jié)點(diǎn) S的搜索圖 G，把 S放到一個(gè)叫做OPEN的未擴(kuò)展節(jié)點(diǎn)表中。 (2) 建立一個(gè)叫做 CLOSED的已擴(kuò)展節(jié)點(diǎn)表，其初始為空表。 (3) LOOP：若 OPEN表是空表，則失敗退出。 (4) 選擇 OPEN表上的第一個(gè)節(jié)點(diǎn)，把它從 OPEN表移出并放進(jìn)CLOSED表中。稱此節(jié)點(diǎn)為節(jié)點(diǎn) n。 (5) 若 n為一目標(biāo)節(jié)點(diǎn)，則有解并成功退出，此解是追蹤圖 G中沿著指針從 n到 S這條路徑而得到的 (指針將在第 7步中設(shè)置 )。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 5/79 盲目搜索 圖搜索策略 (GRAPHSEARCH)的一般過(guò)程 (6) 擴(kuò)展節(jié)點(diǎn) n，同時(shí)生成不是 n的祖先的那些后繼節(jié)點(diǎn)的集合M。把 M的這些成員作為 n的后繼節(jié)點(diǎn)添入圖 G中。 (7) 對(duì)那些未曾在 G中出現(xiàn)過(guò)的 (既未曾在 OPEN表上或CLOSED表上出現(xiàn)過(guò)的 )M成員設(shè)置一個(gè)通向 n的指針。把 M的這些成員加進(jìn) OPEN表。對(duì)已經(jīng)在 OPEN或 CLOSED表上的每一個(gè) M成員，確定是否需要更改通到 n的指針?lè)较?。?duì)已在CLOSED表上的每個(gè) M成員，確定是否需要更改圖 G中通向它的每個(gè)后裔節(jié)點(diǎn)的指針?lè)较颉? (8) 按某一任意方式或按某個(gè)探試值，重排 OPEN表。 (9) GO LOOP。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 6/79 盲目搜索 節(jié)點(diǎn) 父輩節(jié)點(diǎn) 圖搜索策略 （ 1） OPEN表與 CLOSE表 OPEN表 CLOSED表 編號(hào) 節(jié)點(diǎn) 父輩節(jié)點(diǎn) 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 7/79 盲目搜索 圖搜索策略 3. 搜索圖與搜索樹(shù) 搜索過(guò)程框圖 開(kāi) 始 初始化 ： S 放入 OPEN 表 ， CLOES 表置空 , n = 1 OPEN 表中的第一個(gè)結(jié)點(diǎn) n 移至 CLOSE 表 若 n 的后繼未曾在搜索圖 G 中出現(xiàn) ， 則將其放入 OPEN 表的末端 ， 并提供返回結(jié)點(diǎn) n 的指針 , 置 n = n + 1 根據(jù)后繼結(jié)點(diǎn)在搜索圖 G 中的出現(xiàn)情況 修改指針?lè)较? 依某種準(zhǔn)則重新排序 OPEN 表 失敗 成功 N Y N OPEN 為空表 NULL ？ n = 目標(biāo)結(jié)點(diǎn) D 嗎 ? Y 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 8/79 盲目搜索 圖搜索策略 ： 圖搜索過(guò)程的第 8步對(duì) OPEN表上的節(jié)點(diǎn)進(jìn)行排序，以便能夠從中選出一個(gè)“最好”的節(jié)點(diǎn)作為第 4步擴(kuò)展用。這種排序可以是任意的即盲目的 (屬于盲目搜索 )，也可以用以后要討論的各種啟發(fā)思想或其它準(zhǔn)則為依據(jù) (屬于啟發(fā)式搜索 )。每當(dāng)被選作擴(kuò)展的節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)時(shí)，這一過(guò)程就宣告成功結(jié)束。這時(shí)，能夠重現(xiàn)從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的這條成功路徑，其辦法是從目標(biāo)節(jié)點(diǎn)按指針向 S返回追溯。當(dāng)搜索樹(shù)不再剩有未被擴(kuò)展的端節(jié)點(diǎn)時(shí)，過(guò)程就以失敗告終 (某些節(jié)點(diǎn)最終可能沒(méi)有后繼節(jié)點(diǎn)，所以 OPEN表可能最后變成空表 )。在失敗終止的情況下，從起始節(jié)點(diǎn)出發(fā)，一定達(dá)不到目標(biāo)節(jié)點(diǎn)。 合肥工業(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è)解答 )。 (2) 如果 OPEN是個(gè)空表，則沒(méi)有解，失敗退出；否則繼續(xù)。 (3) 把第一個(gè)節(jié)點(diǎn) (節(jié)點(diǎn) n)從 OPEN表移出，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中。 (4) 擴(kuò)展節(jié)點(diǎn) n。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第 (2)步。 (5) 把 n的所有后繼節(jié)點(diǎn)放到 OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到 n的指針。 (6) 如果 n的任一個(gè)后繼節(jié)點(diǎn)是個(gè)目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出；否則轉(zhuǎn)向第 (2)步。 合肥工業(yè)大學(xué) 人工智能與數(shù)據(jù)挖掘研究室 11/79 盲目搜索 寬度優(yōu)先搜索 例 八數(shù)碼問(wèn)題 操作規(guī)定 : 允許空格四周上 、 下 、 左 、 右的數(shù)碼塊移入空格中 ， 不許斜方向移動(dòng) ， 不許返回先輩結(jié)點(diǎn) 。 初始布局 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) 。 合肥工業(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