【正文】 考慮只有最后一步有差別的相同深度或較淺深度可供選擇的路徑，接著再考慮最后兩步有差別的那些路徑，等等。 2022/8/21 30 算法動態(tài)演示圖 2022/8/21 31 ? 例：按深度優(yōu)先搜索生成的八數(shù)碼難題搜索樹，我們設(shè)置深度界限為 5。如果沒有后裔，則轉(zhuǎn)向 (2)。 (4) 如果節(jié)點(diǎn) n的深度等于最大深度，則轉(zhuǎn)向(2)。 (2) 如果 OPEN為一空表，則失敗退出。 2022/8/21 29 ? 含有深度界限的深度優(yōu)先搜索算法如下： (1) 把起始節(jié)點(diǎn) S放到未擴(kuò)展節(jié)點(diǎn) OPEN表中。任何節(jié)點(diǎn)如果達(dá)到了深度界限，那么都將把它們作為沒有后繼節(jié)點(diǎn)處理。 2022/8/21 28 ? 對于許多問題，其狀態(tài)空間搜索樹的深度可能為無限深，或者可能至少要比某個可接受的解答序列的已知深度上限還要深。 首先，擴(kuò)展最深的節(jié)點(diǎn)的結(jié)果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點(diǎn)向下進(jìn)行下去；只有當(dāng)搜索到達(dá)一個沒有后裔的狀態(tài)時，它才考慮另一條替代的路徑。 2022/8/21 27 ? 我們定義節(jié)點(diǎn)的深度如下： (1) 起始節(jié)點(diǎn) (即根節(jié)點(diǎn) )的深度為 0。 2022/8/21 25 圖 深度優(yōu)先搜索示意圖 圖 2022/8/21 26 ? 分析深度優(yōu)先搜索示意圖可看出，在深度優(yōu)先搜索中，我們首先擴(kuò)展最新產(chǎn)生的 (即最深的 )節(jié)點(diǎn)。圖中最后一個節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)。 2022/8/21 21 ? 例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時所生成的搜索樹，這個問題就是要把初始棋局變?yōu)槿缦履繕?biāo)棋局的問題： ? 寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的最短途徑；這棵搜索樹提供了所有存在的路徑 (如果沒有路徑存在，那么對有限圖來說，我們就說該法失敗退出；對于無限圖來說，則永遠(yuǎn)不會終止 )。 2022/8/21 19 2022/8/21 20 ? 寬度優(yōu)先搜索方法分析： ? 寬度優(yōu)先搜索是圖搜索一般過程的特殊情況，將圖搜索一般過程中的第 8步具體化為本算法中的第 6步，這實(shí)際是將 OPEN表作為“ 先進(jìn)先出 ”的隊(duì)列進(jìn)行操作。 (5) 把 n的所有后繼節(jié)點(diǎn)放到 OPEN表的末端，并提供從這些后繼節(jié)點(diǎn)回到 n的指針。 (4) 擴(kuò)展節(jié)點(diǎn) n。 (2) 如果 OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。 2022/8/21 16 ? 從圖可見，這種搜索是逐層進(jìn)行的；在對下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。這種搜索方式就是寬度優(yōu)先搜索。在失敗終止的情況下，從起始節(jié)點(diǎn)出發(fā)，一定達(dá)不到目標(biāo)節(jié)點(diǎn)。這時，能夠重現(xiàn)從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的這條成功路徑，其辦法是從目標(biāo)節(jié)點(diǎn)按指針向 S返回追溯。這種排序可以是任意的即盲目的 (屬于盲目搜索 )，也可以用以后要討論的各種啟發(fā)思想或其它準(zhǔn)則為依據(jù) (屬于啟發(fā)式搜索 )。 G中的每個節(jié)點(diǎn) (除 S外 )都有一個只指向 G中一個父輩節(jié)點(diǎn)的指針，該父輩節(jié)點(diǎn)就定為樹中那個節(jié)點(diǎn)的唯一父輩節(jié)點(diǎn)。 2022/8/21 11 圖搜索算法中的幾個重要名詞 ? 1． OPEN表 ? 2． CLOSED表 節(jié)點(diǎn) 父節(jié)點(diǎn) 編號 節(jié)點(diǎn) 父節(jié)點(diǎn) 2022/8/21 12 ? 3．搜索圖與搜索樹 此過程生成一個明確的圖 G(稱為搜索圖 )和一個 G的子集 T(稱為搜索樹 )，樹 T上的每個節(jié)點(diǎn)也在圖 G中。 ? (8) 按某一任意方式或按某個探試值，重排 OPEN表。對已經(jīng)在 OPEN或 CLOSED表上的每一個 M成員，確定是否需要更改通到 n的指針方向。 ? (7) 對那些未曾在 G中出現(xiàn)過的 (既未曾在 OPEN表上或 CLOSED表上出現(xiàn)過的 )M成員設(shè)置一個通向 n的指針。 ? (6) 擴(kuò)展節(jié)點(diǎn) n，同時生成不是 n的祖先的那些后繼節(jié)點(diǎn)的集合 M。稱此節(jié)點(diǎn)為節(jié)點(diǎn) n，它是 CLOSED表中節(jié)點(diǎn)的編號。 ? (3) LOOP：若 OPEN表是空表，則失敗退出。圖示為： 2022/8/21 9 ? 2022/8/21 10 圖搜索 (GRAPHSEARCH)的一般過程如下： ? (1) 建立一個只含有起始節(jié)點(diǎn) S的搜索圖 G，把 S放到一個叫做 OPEN的未擴(kuò)展節(jié)點(diǎn)表中（簡稱 OPEN表）。如果用圖來表示，就很容易了。 王 A：壽命 47，有兒子王 B王 B王 B2 王 B1：壽命 77，有兒子王 C王 C2 王 B3：壽命 52，有兒子王 D1 王 B2：壽命 65，有兒子王 E王 E2 王 F1：壽命 32 王 G1：壽命 96 王 C2：壽命 87，有兒子王 F1 王 D1：壽命 77，沒有兒子 王 E1：壽命 57，有兒子王 G1 2022/8/21 8 ? 王 E2：壽命 92，有兒子王 H1 王 C1：壽命 27，沒有兒子 王 H1：壽命 51 若 X=57，下面討論一種可通用的圖搜索策略求解此問題。 2022/8/21 7 ? 在介紹圖搜索策略之前，讓我們來看一個例子。我們已經(jīng)介紹過有關(guān)圖的表示方法。 ? 我們將學(xué)習(xí)的寬度優(yōu)先搜索和深度優(yōu)先搜索，屬于盲目搜索方法。 ? 本章先介紹 搜索技術(shù) ，將要討論問題求解的搜索原理，包括一些早期的搜索技術(shù)或用于解決比較簡單問題的搜索原理和一些比較新的能夠求解比較復(fù)雜問題的搜索原理，包括 AO*算法、遺傳算法和模擬退火算法等。 2022/8/21 3 ? 從問題表示到問題的解決，有一個求解的過程。接下來要研究的是實(shí)現(xiàn)求解的過程，采用的基本方法包括搜索和推理。2022/8/21 1 人工智能原理 第三講 搜索原理 主講：王祖喜 華中科技大學(xué)圖像所 2022/8/21 2 上一章中我們研究了知識表示方法，為人工智能問題的求解打下了基礎(chǔ)。從問題表示到問題的解決，有一個求解的過程。本章先介紹搜索技術(shù)，將要討論問題求解的搜索原理，包括一些早期的搜索技術(shù)或用于解決比較簡單問題的搜索原理和一些比較新的能夠求解比較復(fù)雜問題的搜索原理，包括算法、遺傳算法和模擬退火算法等。接下來要研究的是實(shí)現(xiàn)求解的過程，采用的基本方法包括 搜索 和 推理 。 2022/8/21 4 ? 盲目搜索 ? 啟發(fā)式搜索 ? 博弈樹搜索 ? 遺傳算法 ? 模擬退火算法 2022/8/21 5 盲目搜索 ? 盲目搜索又叫做無信息搜索，一般只適用于求解比較簡單的問題。 2022/8/21 6 盲目搜索 ? 圖搜索策略 ? 可把圖搜索策略看成一種在圖中尋找路徑的方法。 ? 圖中的節(jié)點(diǎn)對應(yīng)于狀態(tài)，而連線對應(yīng)于操作符。 例子：從某王姓家族的四代中找王 A的后代且其壽命為 X的人。 如果是一個 N代的家族表中找其壽命為 X的人，我們最可能用的手工方法是從家族表的開始往下，例中還要求所找的人是某人的后代，就比較復(fù)雜了。圖中把姓氏省去，每個成員的后代按例子中給出名字的先后順序。 ? (2) 建立一個叫做 CLOSED的已擴(kuò)展節(jié)點(diǎn)表（簡稱 CLOSED表），其初始為空表。 ? (4) 選擇 OPEN表上的第一個節(jié)點(diǎn)，把它從 OPEN表移出并放進(jìn)CLOSED表中。 ? (5) 若 n為一目標(biāo)節(jié)點(diǎn)，則有解并成功退出，此解是追蹤圖 G中沿著指針從 n到 S這條路徑而得到的 (指針將在第 7步中設(shè)置 )。把M的這些成員作為 n的后繼節(jié)點(diǎn)添入圖 G中。把 M的這些成員加進(jìn) OPEN表。對已在 CLOSED表上的每個 M成員，確定是否需要更改圖 G中通向它的每個后裔節(jié)點(diǎn)的指針方向。 ? (9) GO LOOP。搜索樹是由第 7步中設(shè)置的指針來確定的。 2022/8/21 13 2022/8/21 14 ? 圖搜索方法的幾點(diǎn)分析： ? 圖搜索過程的第 8步對 OPEN表上的節(jié)點(diǎn)進(jìn)行排序，以便能夠從中選出一個“最好”的節(jié)點(diǎn)作為第 4步擴(kuò)展用。每當(dāng)被選作擴(kuò)展的節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)時，這一過程就宣告成功結(jié)束。當(dāng)搜索樹不再剩有未被擴(kuò)展的端節(jié)點(diǎn)時，過程就以失敗告終 (某些節(jié)點(diǎn)最終可能沒有后繼節(jié)點(diǎn)，所以O(shè)PEN表可能最后變成空表 )。 2022/8/21 15 寬度優(yōu)先搜索 ? 回顧上一節(jié)的尋找壽命為 X的人的例子，如果搜索時，從節(jié)點(diǎn) A開始，對他的三個兒子按從左至右搜索，然后對他的所有孫子按從左至右搜索，依此下去。 寬度優(yōu)先搜索 (breadthfirst search)的定義：如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜索就叫做寬度優(yōu)先搜索 (breadthfirst search)，如圖 。 2022/8/21 17 2022/8/21 18 ? 寬度優(yōu)先搜索算法如下： (1) 把起始節(jié)點(diǎn)放到 OPEN表中 (如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個解答 )。 (3) 把第一個節(jié)點(diǎn) (節(jié)點(diǎn) n)從 OPEN表移出，并把它放入 CLOSED擴(kuò)展節(jié)點(diǎn)表中。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向上述第 (2)步。 (6) 如果 n的任一個后繼節(jié)點(diǎn)是個目標(biāo)節(jié)點(diǎn)，則找到一個解答，成功退出；否則轉(zhuǎn)向第 (2)步。 ? 寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的最短途徑；這棵搜索樹提供了所有存在的路徑(如果沒有路徑存在，那么對有限圖來說，我們就說該法失敗退出；對于無限圖來說，則永遠(yuǎn)不會終止 )。 搜索樹上的所有節(jié)點(diǎn)都標(biāo)記它們所對應(yīng)的狀態(tài)描述，每個節(jié)點(diǎn)旁邊的數(shù)字表示節(jié)點(diǎn)擴(kuò)展的順序 (按順時針方向移動空格 )。 2022/8/21 22 圖 八數(shù)碼難題的寬度優(yōu)先搜索樹 2022/8/21 23 對應(yīng)動態(tài)演示圖 2022/8/21 24 深度優(yōu)先搜索 ? 另一種盲目 (無信息 )搜索叫做深度優(yōu)先搜索(depthfirst search)。深度相等的節(jié)點(diǎn)可以任意排列。 (2) 任何其它節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)深度加上 1。替代路徑與前面已經(jīng)試過的路徑不同之處僅僅在于改變最后 n步，而且保持 n盡可能小。為了避免考慮太長的路徑 (防止搜索過程沿著無益的路徑擴(kuò)展下去 )，往往給出一個節(jié)點(diǎn)擴(kuò)展的最大深度 —— 深度界限 。值得說明的是，即使應(yīng)用了深度界限的規(guī)定，所求得的解答路徑并不一定就是最短的路徑。如果此節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到一個解。 (3) 把第一個節(jié)點(diǎn) (節(jié)點(diǎn) n)從 OPEN表移到CLOSED表。 (5) 擴(kuò)展節(jié)點(diǎn) n，產(chǎn)生其全部后裔，并把它們放入 OPEN表的前頭。 (6) 如果后繼節(jié)點(diǎn)中有任一個為目標(biāo)節(jié)點(diǎn)，則求得一個解，成功退出；否則，轉(zhuǎn)向 (2)。 圖 ，粗線條的路徑表明含有 5條應(yīng)用規(guī)則的一個解。 2022/8/21 32 圖 八數(shù)碼難題的深度優(yōu)先搜索樹 2022/8/21 33 等代價搜索 ? 有些問題并不要求有應(yīng)用算符序列為最少的解，而是要求具有某些特性的解。寬度優(yōu)先搜索可被推廣用來解決這種尋找從起始狀態(tài)至目標(biāo)狀態(tài)的具有最小代價的路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做 等代價搜索算法。在搜索樹上，我們假設(shè) g(i)也是從起始節(jié)點(diǎn) S到節(jié)點(diǎn) i的最少代價路徑上的代價，因?yàn)樗俏ㄒ坏穆窂剑? 2022/8/21 35 等代價搜索算法 ? 等代價搜索方法以 g(i)的遞增順序擴(kuò)展其節(jié)點(diǎn)，其算法如下： (1) 把起始節(jié)點(diǎn) S放到未擴(kuò)展節(jié)點(diǎn)表 OPEN中。否則令 g(S)=0。 (3) 從 OPEN表中選擇一個節(jié)點(diǎn) i，使其 g(i)為最小。把節(jié)點(diǎn) i從 OPEN表移至擴(kuò)展節(jié)點(diǎn)表 CLOSED中。 (5) 擴(kuò)展節(jié)點(diǎn) i。 (6) 對于節(jié)點(diǎn) i的每個后繼節(jié)點(diǎn) j，計(jì)算 g(j)=g(i)+c(i,j)，并把所有后繼節(jié)點(diǎn) j放進(jìn) OPEN表。 (7) 轉(zhuǎn)向第 (2)步。 分析前面介紹的寬度優(yōu)先、深度優(yōu)先搜索，或等代價搜索算法 ,其主要的差別是 OPEN表中待擴(kuò)展節(jié)點(diǎn)的順序問題。 啟發(fā)信息 ：進(jìn)行搜索技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域的特性的，與具體問題求解過程有關(guān)的，并可指導(dǎo)搜索過程朝著最有希望方向前進(jìn)的控制信息，把此種信息叫做 啟發(fā)信息 。 2022/8/21 38 啟發(fā)式搜索策略 ? 啟發(fā)信息按其用途可分為下列 3種： (1) 用于決定要擴(kuò)展的下一個節(jié)點(diǎn)，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地?cái)U(kuò)展。 (3) 用于決定某些應(yīng)該從搜索樹中拋棄或修剪的節(jié)點(diǎn)。這種搜索總是選擇“最有希望”的節(jié)點(diǎn)作為下一個被擴(kuò)展的節(jié)點(diǎn)。 2022/8/21 39 估價函數(shù) ? 用來估算節(jié)點(diǎn)希望程度的量度，叫做 估價函數(shù) (evaluation f