人工智能原理-展示頁(yè)
2024-08-02 05:54本頁(yè)面
【正文】 思想或其它準(zhǔn)則為依據(jù) (屬于啟發(fā)式搜索 )。 G中的每個(gè)節(jié)點(diǎn) (除 S外 )都有一個(gè)只指向 G中一個(gè)父輩節(jié)點(diǎn)的指針，該父輩節(jié)點(diǎn)就定為樹中那個(gè)節(jié)點(diǎn)的唯一父輩節(jié)點(diǎn)。 8 圖搜索算法中的幾個(gè)重要名詞 1． OPEN表 2． CLOSED表 節(jié)點(diǎn) 父節(jié)點(diǎn) 編號(hào) 節(jié)點(diǎn) 父節(jié)點(diǎn) 9 3．搜索圖與搜索樹 此過程生成一個(gè)明確的圖 G(稱為搜索圖 )和一個(gè) G的子集 T(稱為搜索樹 )，樹 T上的每個(gè)節(jié)點(diǎn)也在圖 G中。 (8) 按某一任意方式或按某個(gè)探試值， 重排 OPEN表。對(duì)已經(jīng)在 OPEN或 CLOSED表上的每一個(gè) M成員，確定是否需要 更改通 到 n的指針方向。 (7) 對(duì)那些未曾在 G中出現(xiàn)過的 (既未曾在 OPEN表上或 CLOSED表上出現(xiàn)過的 )M成員 設(shè)置 一個(gè)通向 n的指針。 (6) 擴(kuò)展節(jié)點(diǎn) n，同時(shí)生成不是 n的祖先的那些后繼節(jié)點(diǎn)的集合 M。稱此節(jié)點(diǎn)為節(jié)點(diǎn) n，它是 CLOSED表中節(jié)點(diǎn)的編號(hào)。 (3) LOOP：若 OPEN表是空表，則失敗退出。圖示為： 6 ? 7 圖搜索 (GRAPHSEARCH)的一般過程如下： (1) 建立一個(gè)只含有 起始節(jié)點(diǎn) S的搜索圖 G，把 S放到一個(gè)叫做 OPEN的 未擴(kuò)展 節(jié)點(diǎn)表中（簡(jiǎ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 5 ? 王 E2：壽命 92，有兒子王 H1 王 C1：壽命 27，沒有兒子 王 H1：壽命 51 若 X=57，下面討論一種可通用的圖搜索策略求解此問題。這些節(jié)點(diǎn)和連線 (即狀態(tài)與操作符 )又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫(kù)和規(guī)則來標(biāo)記 ? 初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的路徑。 ? 本章先介紹 搜索技術(shù) ，將要討論問題求解的搜索原理，包括一些早期的搜索技術(shù)或用于解決比較簡(jiǎn)單問題的搜索原理和一些比較新的能夠求解比較復(fù)雜問題的搜索原理，包括 A*算法。1 人工智能原理 第三章 搜索推理技術(shù) 2 ? 從問題表示到問題的解決，有一個(gè)求解的過程。接下來要研究的是實(shí)現(xiàn)求解的過程，采用的基本方法包括 搜索 和 推理 。 3 圖搜索策略 ? 可把圖搜索策略看成一種在圖中尋找路徑的方法 ? 圖中的節(jié)點(diǎn)對(duì)應(yīng)于狀態(tài)，而連線對(duì)應(yīng)于操作符。即求得把一個(gè)數(shù)據(jù)庫(kù)變換為另一數(shù)據(jù)庫(kù)的規(guī)則序列問題就等價(jià)于求得圖中的一條路徑問題 4 ? 例子：從某王姓家族的四代中找王 A的后代且其壽命為 X的人。 如果是一個(gè) N代的家族表中找其壽命為 X的人，我們最可能用的 手工方法 是從家族表的開始往下，例中還要求所找的人是某人的后代，就比較復(fù)雜了。圖中把姓氏省去，每個(gè)成員的后代按例子中給出名字的先后順序。 (2) 建立一個(gè)叫做 CLOSED的 已擴(kuò)展 節(jié)點(diǎn)表（簡(jiǎn)稱 CLOSED表），其初始為空表。 (4) 選擇 OPEN表上的第一個(gè)節(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表。對(duì)已在 CLOSED表上的每個(gè) M成員，確定是否需要更改圖 G中通向它的每個(gè) 后裔 節(jié)點(diǎn)的指針方向。 (9) GO LOOP。搜索樹是由第 7步中設(shè)置的指針來確定的。 10 11 ? 圖搜索方法的幾點(diǎn)分析： 圖搜索過程的第 8步對(duì) OPEN表上的節(jié)點(diǎn)進(jìn)行 排序 ，以便能夠從中選出一個(gè)“最好”的節(jié)點(diǎn)作為第 4步擴(kuò)展用。每當(dāng)被選作擴(kuò)展的節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn)時(shí)，這一過程就宣告成功結(jié)束。當(dāng)搜索樹不再剩有未被擴(kuò)展的端節(jié)點(diǎn)時(shí)，過程就以失敗告終 (某些節(jié)點(diǎn)最終可能沒有后繼節(jié)點(diǎn)，所以O(shè)PEN表可能最后變成空表 )。 12 盲目搜索 ? 盲目搜索：無(wú)需重新安排 OPEN表的搜索 ? 盲目搜索又叫做無(wú)信息搜索，一般只適用于求解比較簡(jiǎn)單的問題。這種搜索方式就是寬度優(yōu)先搜索。 14 ? 從圖可見，這種搜索是 逐層進(jìn)行的；在對(duì)下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。 (2) 如果 OPEN是個(gè)空表，則沒有解，失敗退出；否則繼
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1