人工智能原理-文庫吧
2025-07-03 05:54 本頁面
【正文】 比較簡單的問題。 ?寬度優(yōu)先搜索 ?深度優(yōu)先搜索 ?等代價搜索 13 寬度優(yōu)先搜索 ? 回顧上一節(jié)的尋找壽命為 X的人的例子，如果搜索時，從節(jié)點 A開始，對他的三個兒子按從左至右搜索，然后對他的所有孫子按從左至右搜索，依此下去。這種搜索方式就是寬度優(yōu)先搜索。 寬度優(yōu)先搜索 (breadthfirst search)的定義：如果搜索是以 接近 起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索 (breadthfirst search)，如圖 。 14 ? 從圖可見，這種搜索是 逐層進(jìn)行的；在對下一層的任一節(jié)點進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點。 15 16 ? 寬度優(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)步。 17 18 ? 寬度優(yōu)先搜索方法分析： ?寬度優(yōu)先搜索是圖搜索一般過程的 特殊 情況，將圖搜索一般過程中的第 8步具體化為本算法中的第 6步，這實際是將 OPEN表作為“ 先進(jìn)先出 ”的隊列進(jìn)行操作。 ?寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點的 最短途徑 ；這棵搜索樹提供了所有存在的路徑 (如果沒有路徑存在，那么對有限圖來說，我們就說該法失敗退出；對于無限圖來說，則永遠(yuǎn)不會終止 )。 19 ? 例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時所生成的搜索樹，這個問題就是要把初始棋局變?yōu)槿缦履繕?biāo)棋局的問題： ? 搜索樹上的所有節(jié)點都標(biāo)記它們所對應(yīng)的狀態(tài)描述，每個節(jié)點旁邊的數(shù)字表示節(jié)點擴展的順序 (按順時針方向移動空格 )。圖中最后一個節(jié)點是目標(biāo)節(jié)點。 20 圖 八數(shù)碼難題的寬度優(yōu)先搜索樹 21 深度優(yōu)先搜索 ? 另一種盲目 (無信息 )搜索叫做深度優(yōu)先搜索(depthfirst search)。 ? 首先擴展最新產(chǎn)生的節(jié)點。如下圖 22 圖 深度優(yōu)先搜索示意圖 圖 23 ? 分析深度優(yōu)先搜索示意圖可看出，在深度優(yōu)先搜索中，我們首先擴展最新產(chǎn)生的 (即最深的 )節(jié)點。深度相等的節(jié)點可以 任意 排列。 24 ? 我們定義節(jié)點的深度如下： (1) 起始節(jié)點 (即根節(jié)點 )的深度為 0。 (2) 任何其它節(jié)點的深度等于其父輩節(jié)點深度加上 1。 首先，擴展最深的節(jié)點的結(jié)果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點向下進(jìn)行下去；只有當(dāng)搜索到達(dá)一個 沒有后裔 的狀態(tài)時，它才考慮另一條替代的路徑。替代路徑與前面已經(jīng)試過的路徑不同之處僅僅在于改變最后 n步，而且保持 n盡可能小。 25 ? 對于許多問題，其狀態(tài)空間搜索樹的深度可能為無限深，或者可能至少要比某個可接受的解答序列的已知深度上限還要深。為了避免考慮太長的路徑 (防止搜索過程沿著無益的路徑擴展下去 )，往往給出一個節(jié)點擴展的最大深度 —— 深度界限 。任何節(jié)點如果達(dá)到了深度界限，那么都將把它們作為沒有后繼節(jié)點處理。值得說明的是，即使應(yīng)用了深度界限的規(guī)定，所求得的解答路徑并不一定就是最短的路徑。 26 ? 含有深度界限的深度優(yōu)先搜索算法如下： (1) 把起始節(jié)點 S放到未擴展節(jié)點 OPEN表中。如果此節(jié)點為一目標(biāo)節(jié)點，則得到一個解。 (2) 如果 OPEN為一空表，則失敗退出。 (3) 把第一個節(jié)點 (節(jié)點 n)從 OPEN表移到CLOSED表。 (4) 如果節(jié)點 n的深度等于最大深度，則轉(zhuǎn)向(2)。 (5) 擴展節(jié)點 n，產(chǎn)生其全部后裔，并把它們放入 OPEN表的 前頭 。如果沒有后裔，則轉(zhuǎn)向 (2)。 (6) 如果后繼節(jié)點中有任一個為目標(biāo)節(jié)點，則求得一個解，成功退出；否則，轉(zhuǎn)向 (2)。 27 算法演示圖 28 ? 例：按深度優(yōu)先搜索生成的八數(shù)碼難題搜索樹，我們設(shè)置深度界限為 5。 圖 ，粗線條的路徑表明含有 5條應(yīng)用規(guī)則的一個解。從圖可見，深度優(yōu)先搜索過程是沿著一條路徑進(jìn)行下去，直到深度界限為止，然后再考慮只有最后一步有差別的相同深度或較淺深度可供選擇的路徑，接著再考慮最后
公司管理相關(guān)推薦
鄂ICP備17016276號-1