人工智能-第四章(參考版)
2025-08-07 13:39本頁面
【正文】 ? ??過程：保存 ?和 ?值 ， 并且當(dāng)可能時(shí)便進(jìn)行剪枝的整個(gè)過程 ， 當(dāng)初始節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)的最終倒推值都給出時(shí) ， 過程即結(jié)束 ， 而最好的優(yōu)先走步就是走向具有最高倒推值的那個(gè)后繼節(jié)點(diǎn) 。 ? 假設(shè)以深度優(yōu)先方法生成了部分搜索樹 ， 則可使用終止搜索規(guī)則 ??剪枝： ? 1． ?剪枝：若任何極小節(jié)點(diǎn)的 ?值小于或等于任何它的極大父節(jié)點(diǎn)的 ?值 ， 則可以終止該極小節(jié)點(diǎn)以下的搜索 ， 并設(shè)置這個(gè)極小節(jié)點(diǎn)的最終倒推值為 ?。對于圖 ，e(p)=64=2 ? 例： ? (1) (2) (1) ? … … ? … … 65=1 55=0 65=1 55=0 45=1 56=1 54=1 ? ??搜索過程 ? 在極大極小過程中 ， 把生成樹和棋局估值兩個(gè)過程完全分離 ， 使效率大大降低 ， 若同時(shí)進(jìn)行 ，再根據(jù)一定的條件判斷 ， 有可能盡早剪掉一些無用的分支 ， 則可能減少搜索工作量 ， 這是 ??搜索過程的基本思想 。 e(p)定義如下： ? 1） 甲勝 ， e(p)=+? ? 2） 乙勝 ， e(p)=? 圖 井字棋 ? 3） 若 p不是可定勝負(fù)的格局 ， 則 e(p)= e+(p) e(p) ? 其中， e+(p)表示當(dāng)前棋局所有空格都放上甲的棋子后，甲構(gòu)成的行、列和對角線的個(gè)數(shù)。 ? 下面我們以井字棋為例 ， 說明極大極小搜索法 。 ? :IF f(s)≠NIL THEN EXIT(END ? M(Move,T)) 。若 MAX所有子節(jié)點(diǎn)均有值 ,則該 MAX取其極大值 . ? IF(nd ?MIN)? (f(nci? MAX)有值 ) ? THEN f(nd):=min{f(nci)},REMOVE(Nd， CLOSED)。 ni達(dá)到深度 k,計(jì)算各端節(jié)點(diǎn) f值 . ? ： IF CLOSED=NIL,THEN GO LOOP3 ? ELSE nd=FIRST(CLOSED)。 ? :=FIRST(OPEN) ， REMOVE(n,OPEN) ，ADD(n,CLOSED)。 ? 下面說明極大極小過程 MINLMAX： ? :=(s, MAX)， OPEN:=(s)， CLOSED:=( )。 這需定義一個(gè)評價(jià)函數(shù) f。 ? ? 對簡單的博弈問題 ， 我們可用類似與或圖的搜索技術(shù)求出解圖 。 m 能解或修正的耗散值與原先估算 q0不同 ,則把 m的所有先輩節(jié)點(diǎn) ma,添加到 S中 . ? 13 end ? 14 end ? 我們使用圖 ，并假設(shè)： ? h(n0) = 2， h(n1) = 2， h(n2)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1