人工智能之與或圖搜索問題-資料下載頁
2025-02-19 13:05本頁面
【正文】 ? ? ? 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)先算法生成一棵博弈搜索樹 第二 、估計值的倒推計算 缺點 ：這種分離使得搜索的效率比較低 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é)點上的數(shù)字表示它對應(yīng)的估價函數(shù)的值。 極大 極小 63 極大極小過程是先生成與 /或樹 ， 然后再計算各節(jié)點的估值 ， 這種生成節(jié)點和計算估值相分離的搜索方式 ， 需要生成規(guī)定深度內(nèi)的所有節(jié)點 ， 因此搜索效率較低 。 改進 ： 在博弈樹生成過程中同時計算端節(jié)點的估計值及倒推值 ， 以減少搜索的次數(shù) ， 這就是 αβ過程的思想 ， 也稱為 αβ剪枝法 。 剪枝的概念 : 如果能邊生成節(jié)點邊對節(jié)點估值 ， 并剪去一些沒用的分枝 ， 這種技術(shù)被稱為 αβ剪枝 。 64 ??剪枝 ? 極大節(jié)點的下界為 ?。 ? 極小節(jié)點的上界為 ?。 ? 剪枝的條件： ? 后輩節(jié)點的 ?值 ≤祖先節(jié)點的 ?值時 ， ?剪枝 ? 后輩節(jié)點的 ? 值 ≥祖先節(jié)點的 ?值時 ， ?剪枝 ? 簡記為： ? 極小 ≤極大 ， ?剪枝 ? 極大 ≥極小 ， ?剪枝 65 一個 αβ剪枝的具體例子 ， 如下圖所示 。 其中最下面一層端節(jié)點旁邊的數(shù)字是假設(shè)的估值 。 在該圖中 ， L、 M、 N的估值推出節(jié)點 F的倒推值為 4， 即 F的 β值為 4， 由此可推出節(jié)點 C的倒推值 ≥4。 記 C的倒推值的下界為 4，不可能再比 4小，故 C的 α值為 4。 由節(jié)點 N的估值推知節(jié)點 G的倒推值小于 ≤1,無論 G的其它子節(jié)點的估只是多少， G的倒推值都不可能比 1大。因此， 1是 G的倒推值的上界，所以 G的值 ≦ 1 。另已知 C的倒推值 ≥4， G的其它子節(jié)點又不可能使 C的倒推值增大。因此對 G的其它分支不必再搜索，相當于把這些分枝剪去。 由 F、 G的倒推值可推出節(jié)點 C的倒推值 ≥4 ， 再由 C可推出節(jié)點 A的倒推值 ≤4， 即 A的 β值為 4。 另外 ， 由節(jié)點 P、 Q推出的節(jié)點 H的倒推值為 5， 因此 D的倒推值 ≥5， 即 D的 α值為 5。 此時 ， D的其它子節(jié)點的倒推值無論是多少都不能使 D及 A的倒推值減少或增大 ， 所以 D的其他分枝被減去 ， 并可確定 A的倒推值為 4 。 以此類推 ， 最終推出 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 ? 風險投資 68 演講完畢，謝謝觀看！
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1