人工智能之與或圖搜索問(wèn)題-資料下載頁(yè)
2025-02-19 13:05本頁(yè)面
【正文】 ? ? ? 1 2 2 1 0 1 ? ? ? 1 1 1 1 1 1 2 ? 1 1 59 O O MAX MIN 60 MAX MIN O O 61 極大極小搜索過(guò)程由兩個(gè)完全分離的兩個(gè)步驟組成： 第一 、 用寬度優(yōu)先算法生成一棵博弈搜索樹(shù) 第二 、估計(jì)值的倒推計(jì)算 缺點(diǎn) ：這種分離使得搜索的效率比較低 62 極小極大過(guò)程 0 5 3 3 3 3 0 2 2 3 0 2 3 5 4 1 3 0 6 8 9 3 0 3 3 3 3 2 1 3 6 0 3 1 6 0 1 1 極大 極小 a b 注：用□表示 MAX，用○表示 MIN，端節(jié)點(diǎn)上的數(shù)字表示它對(duì)應(yīng)的估價(jià)函數(shù)的值。 極大 極小 63 極大極小過(guò)程是先生成與 /或樹(shù) ， 然后再計(jì)算各節(jié)點(diǎn)的估值 ， 這種生成節(jié)點(diǎn)和計(jì)算估值相分離的搜索方式 ， 需要生成規(guī)定深度內(nèi)的所有節(jié)點(diǎn) ， 因此搜索效率較低 。 改進(jìn) ： 在博弈樹(shù)生成過(guò)程中同時(shí)計(jì)算端節(jié)點(diǎn)的估計(jì)值及倒推值 ， 以減少搜索的次數(shù) ， 這就是 αβ過(guò)程的思想 ， 也稱(chēng)為 αβ剪枝法 。 剪枝的概念 : 如果能邊生成節(jié)點(diǎn)邊對(duì)節(jié)點(diǎn)估值 ， 并剪去一些沒(méi)用的分枝 ， 這種技術(shù)被稱(chēng)為 αβ剪枝 。 64 ??剪枝 ? 極大節(jié)點(diǎn)的下界為 ?。 ? 極小節(jié)點(diǎn)的上界為 ?。 ? 剪枝的條件： ? 后輩節(jié)點(diǎn)的 ?值 ≤祖先節(jié)點(diǎn)的 ?值時(shí) ， ?剪枝 ? 后輩節(jié)點(diǎn)的 ? 值 ≥祖先節(jié)點(diǎn)的 ?值時(shí) ， ?剪枝 ? 簡(jiǎn)記為： ? 極小 ≤極大 ， ?剪枝 ? 極大 ≥極小 ， ?剪枝 65 一個(gè) αβ剪枝的具體例子 ， 如下圖所示 。 其中最下面一層端節(jié)點(diǎn)旁邊的數(shù)字是假設(shè)的估值 。 在該圖中 ， L、 M、 N的估值推出節(jié)點(diǎn) F的倒推值為 4， 即 F的 β值為 4， 由此可推出節(jié)點(diǎn) C的倒推值 ≥4。 記 C的倒推值的下界為 4，不可能再比 4小，故 C的 α值為 4。 由節(jié)點(diǎn) N的估值推知節(jié)點(diǎn) G的倒推值小于 ≤1,無(wú)論 G的其它子節(jié)點(diǎn)的估只是多少， G的倒推值都不可能比 1大。因此， 1是 G的倒推值的上界，所以 G的值 ≦ 1 。另已知 C的倒推值 ≥4， G的其它子節(jié)點(diǎn)又不可能使 C的倒推值增大。因此對(duì) G的其它分支不必再搜索，相當(dāng)于把這些分枝剪去。 由 F、 G的倒推值可推出節(jié)點(diǎn) C的倒推值 ≥4 ， 再由 C可推出節(jié)點(diǎn) A的倒推值 ≤4， 即 A的 β值為 4。 另外 ， 由節(jié)點(diǎn) P、 Q推出的節(jié)點(diǎn) H的倒推值為 5， 因此 D的倒推值 ≥5， 即 D的 α值為 5。 此時(shí) ， D的其它子節(jié)點(diǎn)的倒推值無(wú)論是多少都不能使 D及 A的倒推值減少或增大 ， 所以 D的其他分枝被減去 ， 并可確定 A的倒推值為 4 。 以此類(lèi)推 ， 最終推出 S0的倒推值為 4。 ≥4 S0 ≤4 A ≦0 11 ≥4 ≥ 5 ≥0 C D E 0 6 I J 4 ≦1 K L N 4 6 1 F G 5 P 5 8 H M 8 β值 α值 β 值 α 值 Q R ≤0 ≦ 6 S 66 8 6 3 1 4 5 3 3 5 0 ??剪枝（續(xù)） 3 3 0 2 2 3 0 2 3 9 3 0 0 3 0 3 3 0 5 4 1 1 3 1 6 6 1 a b c d e f g h i j k m n 0 ? 剪枝 ?剪枝 ? 剪枝 ?剪枝 67 ??剪枝的其他應(yīng)用 ? 故障診斷 A B C D ? 風(fēng)險(xiǎn)投資 68 演講完畢，謝謝觀看！
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1