人工智能第三章-資料下載頁
2025-07-24 21:56本頁面
【正文】 圖．圖的根節(jié)點(diǎn)表示產(chǎn)生式系統(tǒng)的初始狀態(tài)描述，連接符表示對一狀態(tài)描述應(yīng)用產(chǎn)生式規(guī)則或把這一狀態(tài)描述分解成若干組成部分．滿足終止條件的節(jié)點(diǎn)叫終止節(jié)點(diǎn)． 可分解產(chǎn)生式系統(tǒng)的任務(wù)是找出一個從根節(jié)點(diǎn)出發(fā)的到終止節(jié)點(diǎn)的解圖． 8/21/2022 51 與 /或圖搜索 定義 設(shè) N是 AND／ OR圖 G的終止節(jié)點(diǎn)集合，圖G中無回路，從節(jié)點(diǎn) n出發(fā)到 N的一個解圖是AND／ OR圖 G的一個子圖，用 G’表示，遞歸定義如下： 1. 若 n是 N中的一個元素，則 G’只包括節(jié)點(diǎn) n； 8/21/2022 52 與 /或圖搜索 2. 若 n有一個從 n出發(fā)的連接符 k指向后繼節(jié)點(diǎn)集合｛ n1， … ， nk｝，而每一個 ni都有從 ni出發(fā)的解圖，則 G’由節(jié)點(diǎn) n、連接符 k、節(jié)點(diǎn) n1， … ， nk和由諸 ni出發(fā)的解圖構(gòu)成； 3. 否則， G沒有從 n出發(fā)到 N的解圖． 8/21/2022 53 與 /或圖搜索 假定所有連接符的費(fèi)用均大于某一小的正數(shù) ε，定義 AND／ OR圖中連接符的費(fèi)用。使用連接符的費(fèi)用可以計算解圖的費(fèi)用． 設(shè)從節(jié)點(diǎn) n到終止節(jié)點(diǎn)集合 N的解圖的費(fèi)用用 k(n, N)表示，則 k(n, N)遞歸定義如下： 1. 若 n是 N中的元素，則 k（ n,N） =0； 8/21/2022 54 與 /或圖搜索 2. 若有從 n出發(fā)的一個連接符指向它的解圖后繼節(jié)點(diǎn)｛ n1， … ， ni｝，設(shè)此連接符的費(fèi)用為Cn，則 : k(n, N)= Cn+ k(n1, N)+…+k(n i, N) 最佳解圖：具有最低費(fèi)用的解圖 8/21/2022 55 與 /或圖搜索 假定 h*(n)是從 n出發(fā)的最佳解圖的費(fèi)用，而 h(n)是 h*(n)的估計值。 利用 h(n)指導(dǎo)對 AND/OR圖的啟發(fā)式搜索。在AND/OR圖中，對任意連接符的單調(diào)限制是 h(n)≤c+h(n1)+…+h(n k) 其中， n是任意節(jié)點(diǎn)， c是從 n出發(fā)的連接符的費(fèi)用，是 n的在此連接符下的后繼節(jié)點(diǎn)。 8/21/2022 56 與 /或圖搜索 若對于所有的終止節(jié)點(diǎn)，都有 h（ n）＝ 0，則單調(diào)限制還隱含著 h對所有的節(jié)點(diǎn) n，都有：h(n) ≤h*(n)。 8/21/2022 57 與 /或圖搜索 …… 算法 AO* Procedure AO* 1．建立一個只由根節(jié)點(diǎn)構(gòu)成的搜索圖 G．設(shè)s的費(fèi)用 q(s) = h(s), G’=G． 如果 s是目標(biāo)，標(biāo)記 s為 SOLVED. 2．直到 s被標(biāo)上 SOLVED， do： 3． begin 4． 通過跟蹤從 s出發(fā)的有標(biāo)記的連接符計算部分解圖 G’（ G的連接符將在以后的步驟中標(biāo)記） 5．在 G’中選一個非終止的葉節(jié)點(diǎn) n（以后我們將討論怎樣選這樣一個節(jié)點(diǎn)）． 6．?dāng)U展節(jié)點(diǎn) n產(chǎn)生 n的所有后繼，并把這些后繼連到圖 G上，對于每一個不曾在 G中出現(xiàn)的后繼 nj，設(shè)其費(fèi)用 q(nj)=h(nj)，如果這些后繼中某些節(jié)點(diǎn)是終止節(jié)點(diǎn)，則用 SOLVED標(biāo)記。（對于節(jié)點(diǎn) n沒有后繼的情形，我們將在算法的解釋中加以說明）。 8/21/2022 58 3． begin 4． 通過跟蹤從 s出發(fā)的有標(biāo)記的連接符計算部分解圖 G’（ G的連接符將在以后的步驟中標(biāo)記） 5．在 G’中選一個非終止的葉節(jié)點(diǎn) n. 6．?dāng)U展節(jié)點(diǎn) n產(chǎn)生 n的所有后繼，并把這些后繼連到圖 G上，對于每一個不曾在 G中出現(xiàn)的后繼 nj，設(shè)其費(fèi)用 q(nj)=h(nj)，如果這些后繼中某些節(jié)點(diǎn)是終止節(jié)點(diǎn)，則用 SOLVED標(biāo)記。 與 /或圖搜索 …… 算法 AO* 8/21/2022 59 7．建立一個只由 n構(gòu)成的單元素集合 S。 8．直到 S變空， do： 9． begin 10．從 S中刪除節(jié)點(diǎn) m，這個 m在 G中的后裔不出現(xiàn)在 S中 與 /或圖搜索 …… 算法 AO* 8/21/2022 60 11． 按以下步驟修改 m的費(fèi)用 q（ m）：對于每一個從 m出發(fā)的指向節(jié)點(diǎn)集合 {n1i， … ， nki}的連接符計算 qi(m)=ci+q(n1i)+…+q(nki) ，這里的 q(nji)或者是在本循環(huán)內(nèi)部的上述某步驟中算出的值或者是在步驟 6中被指定的值，設(shè) q(m)是所有 qi(m)中的最小者，標(biāo)記實(shí)現(xiàn)這個最小值的連接符，如果本次標(biāo)記與以前的不同，抹去先前的標(biāo)記，如果這個連接符指向的所有后繼節(jié)點(diǎn)都標(biāo)記了 SOLVED，則把 m標(biāo)上SOLVED． 與 /或圖搜索 …… 算法 AO* 8/21/2022 61 12．如果 m標(biāo)記了 SOLVED或者如果 m的修改的費(fèi)用與以前的費(fèi)用不同，則把 m的通過標(biāo)記的連接的所有父親加到 S中． 13． end 14． end 與 /或圖搜索 …… 算法 AO
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1