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