人工智能第1章盲目搜索-文庫吧在線文庫
【正文】 A S0 B S0 C S0 D S0 E A F A ?? CLOSED表變化過程 編號(hào) 節(jié)點(diǎn)號(hào) 父節(jié)點(diǎn)號(hào) 0 S0 空 1 A S0 2 B S0 ?? 圖搜索的一般過程 (1) 建立一個(gè)只含有起始節(jié)點(diǎn) S的搜索圖 G，把 S放到一個(gè)叫做 OPEN表的未擴(kuò)展節(jié)點(diǎn)表中。始節(jié)點(diǎn)叫父節(jié)點(diǎn)或雙親節(jié)點(diǎn)，終節(jié)點(diǎn)叫子節(jié)點(diǎn)。 例如 ， 例子中的八數(shù)碼魔方問題就可以用三元狀態(tài)空間表示為 （ S0， F， Sg） 其中 ， S0代表初始狀態(tài) ， Sg代表目標(biāo)狀態(tài) ， 而 F就是所有能將初始狀態(tài)變化為目標(biāo)狀態(tài)的算符集合 。第 1章 搜索問題 —— 一種在圖中尋找路徑的方法。 操作符可為走步 、 過程 、 規(guī)則 、 數(shù)學(xué)算子 、 運(yùn)算符號(hào)或邏輯符號(hào)等 。這種圖叫做有向圖。 圖搜索策略 1. 圖搜索的定義 ——一種計(jì)算機(jī)在狀態(tài)圖中尋找路徑的方法。 把 M的這些成員作為 n的后繼節(jié)點(diǎn)添入圖G中 。 深度相等的節(jié)點(diǎn)可以任意排列。 ?寬度優(yōu)先 搜索算法是一種 “ 先進(jìn)先出 ” 的算法 。 迷宮問題如下， F是入口， B是出口，試采用均一代價(jià)搜索算法進(jìn)行求解。 均一代價(jià)搜索中的幾個(gè)記號(hào)： 起始節(jié)點(diǎn)記為 S； 從節(jié)點(diǎn) i到它的后繼節(jié)點(diǎn) j的連接弧線代價(jià)記為 c(i， j)； 從起始節(jié)點(diǎn) S到任一節(jié)點(diǎn) i的路徑代價(jià)記為 g(i)。 ?深度優(yōu)先 搜索算法是一種 “ 后進(jìn)先出 ”的算法 。 對(duì)已在 CLOSED表上的每個(gè) M成員 ，確定是否需要更改圖 G中通向它的每個(gè)后裔節(jié)點(diǎn)的指針方向 。 (4) 選擇 OPEN表上的第一個(gè)節(jié)點(diǎn)，把它從 OPEN表移出并放進(jìn) CLOSED表中。路徑中不包含兩個(gè)及以上相同的分枝，如果 n1和nm是同一個(gè)節(jié)點(diǎn)，則稱這種路徑為閉路。 解：問題空間的初始狀態(tài)是節(jié)點(diǎn) (0,0),而目標(biāo)狀態(tài)是節(jié)點(diǎn) (2,2)。 當(dāng) Q中每個(gè)分量取定一個(gè)值時(shí)，就得到一個(gè)具體的狀態(tài)集合，如例子中的 就是 Q0， 而 就是 Qk。 2 8 3 1 4 7 6 5 8 1 3 2 4 7 6 5 ? 問題求解技術(shù)主要是兩個(gè)方面： – 問題的表示 – 求解的方法 問題的狀態(tài)空間 (state space)是一個(gè)表示該問題全部可能狀態(tài)及其關(guān)系的圖 ， 它包含三種說明的集合 ， 即所有可能的問題初始狀態(tài)集合 S、 算符集合 F以及目標(biāo)狀態(tài)集合 G。 從圖 ，從 (0
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1