人工智能與或圖搜索(文件)
【正文】 在任一個(gè) MIN節(jié)點(diǎn)， 如果發(fā)現(xiàn)了其 beta值小于或者等于它的一個(gè) MAX祖先節(jié)點(diǎn)的 alpha值，則可以剪枝 2。 為提高效率， 我們可以按深度優(yōu)先方式， 從左邊開始， 先對最左分支擴(kuò)展到給定深度， 定出極大和極小的取值界限，即alpha值和 beta值， 然后一邊擴(kuò)展一邊估值， 并把估值同 alpha值和 beta值相比較，這樣就可以省掉許多節(jié)點(diǎn)的估值， 當(dāng)然這些節(jié)點(diǎn)也不必產(chǎn)生了， 因此提高了算法的效率， 這就是 Alphabeta 過程。 知識表示， 二元組《 s, p》 ,其中 s為一集合， 表示桌面上各堆的硬幣數(shù)， p表示對當(dāng)前狀態(tài)應(yīng)該移動(dòng)的游戲者。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 與或圖的啟發(fā)式搜索 AND/OR圖的啟發(fā)搜索過程 AO* 1. 建立一個(gè)只由根節(jié)點(diǎn) s構(gòu)成的搜索圖 G, 設(shè)從 s 出發(fā)的解圖的費(fèi)用為 q(s)=h(s), 如果 s是目標(biāo)節(jié)點(diǎn)， 用 SOLVED標(biāo)記 s. 2. until s 被標(biāo)上 SOLVED, do: 3. begin 4. 通過跟蹤從 s出發(fā)的有標(biāo)記的超弧計(jì)算候選解圖 G’ (這些標(biāo)記在后 面的步驟 11中給出 ) 5. 在 G’中選一個(gè)不是目標(biāo)節(jié)點(diǎn)的葉節(jié)點(diǎn) n, 6. 擴(kuò)展節(jié)點(diǎn) n, 產(chǎn)生節(jié)點(diǎn) n的所有兒子 {n1, n2, ..., nk}, 并把這些兒子連到圖 G上 ,對于每一個(gè)不曾在 G中出現(xiàn)的兒子 nj, 設(shè)q(nj)=h(nj), 如果這些兒子節(jié)點(diǎn)中的某些節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn) ,則把這些節(jié)點(diǎn)標(biāo)記為 SOLVED. 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 7. 建立一個(gè)由 n構(gòu)成的單元素集合 S. 8. 直到 S變空 , do: 9. begin 10. 從 S中刪除其兒子節(jié)點(diǎn)不在 S中的節(jié)點(diǎn) , 記此節(jié)點(diǎn)為 m. 11. 按以下步驟修改 m的費(fèi)用 q(m), 對于每一個(gè)從 m出發(fā)的 12. 指向節(jié)點(diǎn)集合 {ni1, ni2, ..., nik}超弧 ai，計(jì)算 qi(m)= c(ai)+ q(ni1)+…+ q(nik), 這里的 q( nij)或者是在本循環(huán)內(nèi)部的前面步驟計(jì)算出的值，或者是在步驟 6中指定的值。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 與或圖 ? 設(shè)從節(jié)點(diǎn) n到目標(biāo)節(jié)點(diǎn)集
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1