人工智能第二章與或圖搜索問題68-閱讀頁
2025-03-02 11:32本頁面
【正文】 X X O O X X X X O O O X X X O O X X O X O O X X O X O O X O X O O O X X X O O O X X X O O X X X O O O X X X O O O O X X X O O X X X O O O X X X O O O X X O X O O O X X X O O O X X X O O X X O X O O X O X X O O O X X X O O O X X X O O X X X O O O X O X X ? 0 2 1 ? ? ? 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 極大極小搜索過程由兩個完全分離的兩個步驟組成： 第一 、 用寬度優(yōu)先算法生成一棵博弈搜索樹 第二 、估計(jì)值的倒推計(jì)算 缺點(diǎn) ：這種分離使得搜索的效率比較低 62 極小極大過程 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ù)字表示它對應(yīng)的估價函數(shù)的值。 改進(jìn) ： 在博弈樹生成過程中同時計(jì)算端節(jié)點(diǎn)的估計(jì)值及倒推值 ， 以減少搜索的次數(shù) ， 這就是 αβ過程的思想 ， 也稱為 αβ剪枝法 。 64 ??剪枝 ? 極大節(jié)點(diǎn)的下界為 ?。 ? 剪枝的條件： ? 后輩節(jié)點(diǎn)的 ?值 ≤祖先節(jié)點(diǎn)的 ?值時 ， ?剪枝 ? 后輩節(jié)點(diǎn)的 ? 值 ≥祖先節(jié)點(diǎn)的 ?值時 ， ?剪枝 ? 簡記為： ? 極小 ≤極大 ， ?剪枝 ? 極大 ≥極小 ， ?剪枝 65 一個 αβ剪枝的具體例子 ， 如下圖所示 。 在該圖中 ， L、 M、 N的估值推出節(jié)點(diǎn) F的倒推值為 4， 即 F的 β值為 4， 由此可推出節(jié)點(diǎn) C的倒推值 ≥4。 由節(jié)點(diǎn) N的估值推知節(jié)點(diǎn) G的倒推值小于 ≤1,無論 G的其它子節(jié)點(diǎn)的估只是多少， G的倒推值都不可能比 1大。另已知 C的倒推值 ≥4， G的其它子節(jié)點(diǎn)又不可能使 C的倒推值增大。 由 F、 G的倒推值可推出節(jié)點(diǎn) C的倒推值 ≥4 ， 再由 C可推出節(jié)點(diǎn) A的倒推值 ≤4， 即 A的 β值為 4。 此時 ， D的其它子節(jié)點(diǎn)的倒推值無論是多少都不能使 D及 A的倒推值減少或增大 ， 所以 D的其他分枝被減去 ， 并可確定 A的倒推值為 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)險投資 68 演講完畢，謝謝觀看！
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號-1