人工智能第二章與或圖搜索問題68-全文預(yù)覽
【正文】 若 CLOSED表為空 ， 則轉(zhuǎn) 8；否則取出CLOSED表中的第一個節(jié)點(diǎn) ， 記為 np； Open為空，即已經(jīng)擴(kuò)展完節(jié)點(diǎn) 步 2 45 若 np 屬于 MAX層 ， 且對于它的屬于 MIN層的子節(jié)點(diǎn) nci 的 e ( nci )有值 ， 則： e ( np ) =max { nci } 46 （ 續(xù) ） 若 np 屬于 MIN層 ， 且對于它的屬于 MAX層的子節(jié)點(diǎn) nci 的 e ( nci )有值 ， 則： e ( np )=min{ nci } 47 轉(zhuǎn) 5； 根據(jù) e (S) 的值，標(biāo)記走步或者結(jié)束（ ∞，∞或 0）。 極大 極小 63 極大極小過程是先生成與 /或樹 ， 然后再計(jì)算各節(jié)點(diǎn)的估值 ， 這種生成節(jié)點(diǎn)和計(jì)算估值相分離的搜索方式 ， 需要生成規(guī)定深度內(nèi)的所有節(jié)點(diǎn) ， 因此搜索效率較低 。 ? 極小節(jié)點(diǎn)的上界為 ?。 記 C的倒推值的下界為 4，不可能再比 4小，故 C的 α值為 4。因此對 G的其它分支不必再搜索，相當(dāng)于把這些分枝剪去。 以此類推 ， 最終推出 S0的倒推值為 4。 另外 ， 由節(jié)點(diǎn) P、 Q推出的節(jié)點(diǎn) H的倒推值為 5， 因此 D的倒推值 ≥5， 即 D的 α值為 5。因此， 1是 G的倒推值的上界，所以 G的值 ≦ 1 。 其中最下面一層端節(jié)點(diǎn)旁邊的數(shù)字是假設(shè)的估值 。 剪枝的概念 : 如果能邊生成節(jié)點(diǎn)邊對節(jié)點(diǎn)估值 ， 并剪去一些沒用的分枝 ， 這種技術(shù)被稱為 αβ剪枝 。 算法分成兩個階段 ： 49 等對手走出相應(yīng)的棋，再以當(dāng)前的格局作為初始節(jié)點(diǎn)，重復(fù)此過程，選擇對自己有利的走法。 符號 ： 41 ?極大極小過程的基本思想： (1)當(dāng)輪到 MIN走步的節(jié)點(diǎn)時 ， MAX應(yīng)考慮最壞的情況 （ 即 f(p)取極小值 ） ； (2)當(dāng)輪到 MAX走步的節(jié)點(diǎn)時 ， MAX應(yīng)考慮最好的情況 （ 即 f(p)取極大值 ） ； (3)評價往回倒推時 ， 相應(yīng)于兩位棋手的對抗策略 ， 交替使用 （ 1） 和 （ 2） 兩種方法傳遞倒推值 。 37 ③ 對于每一個端節(jié)點(diǎn) ， 計(jì)算出它們的靜態(tài)估價函數(shù) ， 然后自下而上地逐層計(jì)算倒推值 ， 直到 MAX開始的格局 。 ? 需要定義一個靜態(tài)估價函數(shù) e,以便對棋局的態(tài)勢做出評估 。 ? 結(jié)論：不可能窮舉 。 所有可能的分法 (7,MIN) (6,1,MAX) (5,2,MAX) (4,3,MAX) (5,1,1,MIN) (4,2,1,MIN) (3,2,2,MIN) (3,3,1,MIN) (4,1,1,1,MAX) (3,2,1,1,MAX) (2,2,2,1,MAX) (2,2,1,1,1,MIN) (3,1,1,1,1,MIN) (2,1,1,1,1,1,MAX) 29 分錢幣問題 （ 7） （ 6,1） （ 5,2） （ 4,3） （ 5,1,1） （ 4,2,1） （ 3,2,2） （ 3,3,1） （ 4,1,1,1） （ 3,2,1,1） （ 2,2,2,1） （ 3,1,1,1,1） （ 2,2,1,1,1） （ 2,1,1,1,1,1） 對方先走 我方必勝 30 對于比較復(fù)雜的博弈問題 ， 只能模擬人的思維“ 向前看幾步 ” ， 然后作出決策 ， 選擇最有利自己的一步 。 但是 ， 從 MAX的角度出發(fā) ， 所有使 MAX獲勝的狀態(tài)格局都是本原問題 ， 是 可解節(jié)點(diǎn) ， 而使 MIN獲勝的狀態(tài)格局是 不可解節(jié)點(diǎn) 。 為什么與節(jié)點(diǎn)、或節(jié)點(diǎn)隔層交替出現(xiàn) ？ 21 從 MAX方的角度來看 ： 所有 MIN方節(jié)點(diǎn)都是 與節(jié)點(diǎn) 理由 ： 因?yàn)?MIN方必定選擇最不利于 MAX方的方式來擴(kuò)展節(jié)點(diǎn) ， 只要 MIN方節(jié)點(diǎn)的子節(jié)點(diǎn) （ 下出棋局 ） 中有一個對 MAX方不利 ， 則該節(jié)點(diǎn)就對MAX方不利 ， 故為 “ 與節(jié)點(diǎn) ” 。 博弈的特點(diǎn)： 18 如何根據(jù)當(dāng)前的棋
職業(yè)教育相關(guān)推薦
鄂ICP備17016276號-1