人工智能第三章(參考版)
2024-08-04 21:56本頁(yè)面
【正文】 8．直到 S變空， do： 9． begin 10．從 S中刪除節(jié)點(diǎn) m，這個(gè) m在 G中的后裔不出現(xiàn)在 S中 與 /或圖搜索 …… 算法 AO* 8/21/2022 60 11． 按以下步驟修改 m的費(fèi)用 q（ m）：對(duì)于每一個(gè)從 m出發(fā)的指向節(jié)點(diǎn)集合 {n1i， … ， nki}的連接符計(jì)算 qi(m)=ci+q(n1i)+…+q(nki) ，這里的 q(nji)或者是在本循環(huán)內(nèi)部的上述某步驟中算出的值或者是在步驟 6中被指定的值，設(shè) q(m)是所有 qi(m)中的最小者，標(biāo)記實(shí)現(xiàn)這個(gè)最小值的連接符，如果本次標(biāo)記與以前的不同，抹去先前的標(biāo)記，如果這個(gè)連接符指向的所有后繼節(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的通過(guò)標(biāo)記的連接的所有父親加到 S中． 13． end 14． end 與 /或圖搜索 …… 算法 AO* 。 8/21/2022 58 3． begin 4． 通過(guò)跟蹤從 s出發(fā)的有標(biāo)記的連接符計(jì)算部分解圖 G’（ G的連接符將在以后的步驟中標(biāo)記） 5．在 G’中選一個(gè)非終止的葉節(jié)點(diǎn) n. 6．?dāng)U展節(jié)點(diǎn) n產(chǎn)生 n的所有后繼，并把這些后繼連到圖 G上，對(duì)于每一個(gè)不曾在 G中出現(xiàn)的后繼 nj，設(shè)其費(fèi)用 q(nj)=h(nj)，如果這些后繼中某些節(jié)點(diǎn)是終止節(jié)點(diǎn)，則用 SOLVED標(biāo)記。 8/21/2022 57 與 /或圖搜索 …… 算法 AO* Procedure AO* 1．建立一個(gè)只由根節(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． 通過(guò)跟蹤從 s出發(fā)的有標(biāo)記的連接符計(jì)算部分解圖 G’（ G的連接符將在以后的步驟中標(biāo)記） 5．在 G’中選一個(gè)非終止的葉節(jié)點(diǎn) n（以后我們將討論怎樣選這樣一個(gè)節(jié)點(diǎn)）． 6．?dāng)U展節(jié)點(diǎn) n產(chǎn)生 n的所有后繼，并把這些后繼連到圖 G上，對(duì)于每一個(gè)不曾在 G中出現(xiàn)的后繼 nj，設(shè)其費(fèi)用 q(nj)=h(nj)，如果這些后繼中某些節(jié)點(diǎn)是終止節(jié)點(diǎn)，則用 SOLVED標(biāo)記。在AND/OR圖中，對(duì)任意連接符的單調(diào)限制是 h(n)≤c+h(n1)+…+h(n k) 其中， n是任意節(jié)點(diǎn)， c是從 n出發(fā)的連接符的費(fèi)用，是 n的在此連接符下的后繼節(jié)點(diǎn)。使用連接符的費(fèi)用可以計(jì)算解圖的費(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ā)的一個(gè)連接符指向它的解圖后繼節(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)的估計(jì)值。 啟發(fā)能力的度量 …… 滲透度 8/21/2022 40 啟發(fā)能力的度量 …… 有效分枝系數(shù) 有效分技系數(shù)就是這樣一棵樹的平均分枝數(shù)． 設(shè)搜索樹的深度是 L，算法所產(chǎn)生的總節(jié)點(diǎn)數(shù)為 T，有效分枝系數(shù)是 B，則有 B＋ B2十 … ＋ BL=T 或 B（ BL1） /（ B1） =T 8/21/2022 41 啟發(fā)能力的度量 …… 有效分枝系數(shù) 圖 L值 B與 T的關(guān)系 當(dāng) L=18， T=43時(shí) , 搜索樹的有效分校系數(shù) B大約為 : ． 8/21/2022 42 啟發(fā)能力的度量 …… 有效分枝系數(shù) 有效分枝系數(shù)與路徑的長(zhǎng)度無(wú)關(guān) ， 可以利用這一事實(shí)預(yù)測(cè)不同深度的搜索所需產(chǎn)生的節(jié)點(diǎn)個(gè)數(shù) 。 當(dāng)最佳解路短時(shí)，可能有較高的滲透度； 當(dāng)最佳解路長(zhǎng)時(shí)，算法產(chǎn)生節(jié)點(diǎn)的數(shù)目將以更快的速度增加，可能有較低的滲透度。 定義為： P = L / T 其中， L是算法發(fā)現(xiàn)的解路徑的長(zhǎng)度， T是算法在尋找這條解路徑期間所產(chǎn)生的節(jié)點(diǎn)數(shù)（不包括初始節(jié)點(diǎn)，包括目標(biāo)節(jié)點(diǎn)） 啟發(fā)能力的度量 …… 滲透度 8/21/2022 38 例 圖 ， L=18， T=43，
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1