km算法是通過(guò)給每個(gè)頂點(diǎn)一個(gè)標(biāo)號(hào)(叫做頂標(biāo))來(lái)把求最大-資料下載頁(yè)
2025-01-11 08:26本頁(yè)面
【正文】 “游戲理論 ”。不妨說(shuō)，博弈論是通過(guò) “玩游戲 ”獲得人生競(jìng)爭(zhēng)知識(shí)的。研究領(lǐng)域n 博弈算法168。計(jì)算機(jī)的優(yōu)勢(shì)n 快速，內(nèi)存大n 更嚴(yán)密168。人工智能領(lǐng)域n 主要研究領(lǐng)域n 挑戰(zhàn)168。條件：兩方、公平。博弈樹(shù)n 雙方博弈背后168。隱式圖：我們可以把所處的局面看作是一個(gè)狀態(tài)。那么博弈的過(guò)程就可以看成是在狀態(tài)空間中遍歷。168。博弈樹(shù)：由于雙方博弈的過(guò)程具有明顯的層次關(guān)系，我們可以依此構(gòu)建一棵博弈樹(shù)?！?圖 】 象棋的 4層博弈樹(shù)博弈樹(shù)n 博弈樹(shù)上的搜索168。數(shù)量級(jí)極大n 中國(guó)象棋，平均一次 40種走法 ,5層就有 10^8個(gè)節(jié)點(diǎn)。168。只能向下搜索幾層n 為幾層后的狀態(tài)給出估值n 自下而上依次對(duì)每個(gè)狀態(tài)進(jìn)行估值極大極小過(guò)程n 約定雙方都用最好的策略n 把 (甲方得分 乙方得分 )作為一個(gè)局面的估值。n MAX/MIN節(jié)點(diǎn)168。甲方：在子節(jié)點(diǎn)中選擇估值最大的節(jié)點(diǎn) (MAX)。即 Score(A)=Max{Ai|Ai∈ F(A)}。168。乙方：在子節(jié)點(diǎn)中選擇估值最小的節(jié)點(diǎn) (MIN)。即 Score(B)=Min{Bi|Bi∈ F(B)}?！?圖 】 一字棋極大極小過(guò)程【 圖 】 偽代碼(極大極小算法)負(fù)極大值算法n 極大極小算法的改進(jìn)168。修改了返回估值的符號(hào)168。避免了極大極小的交替【 圖 】 偽代碼（負(fù)極大值算法）αβ剪枝n α， β值168。MAX節(jié)點(diǎn)的 α值：當(dāng)前已經(jīng)展開(kāi)的幾個(gè)后繼節(jié)點(diǎn)中的最大值。它是該結(jié)點(diǎn)估值的下界。168。MIN節(jié)點(diǎn)的 β值：當(dāng)前已經(jīng)展開(kāi)的幾個(gè)后繼節(jié)點(diǎn)中的最小值。它是該結(jié)點(diǎn)估值的上界。168。易見(jiàn)規(guī)律：n 一個(gè)正在展開(kāi)的 MAX結(jié)點(diǎn)的 α值 永不下降 。n 一個(gè)正在展開(kāi)的 MIN結(jié)點(diǎn)的 β值 永不上升 。αβ剪枝n αβ剪枝168。α剪枝：如果當(dāng)前 MIN結(jié)點(diǎn)的 β值不大于任何祖先節(jié)點(diǎn)的 α值，則不再繼續(xù)搜索該結(jié)點(diǎn)。168。β剪枝：如果當(dāng)前 MAX結(jié)點(diǎn)的 α值不小于任何祖先節(jié)點(diǎn)的 β值，則不再繼續(xù)搜索該結(jié)點(diǎn)?！?圖 】 αβ剪枝【 圖 】 偽代碼(α剪枝)【 圖 】 偽代碼 (β剪枝 )168。注意 12月 1號(hào)提交期中大作業(yè)！168。ftp期中作業(yè) 目錄168。壓縮包用學(xué)號(hào)命名。168。兩人組就用兩個(gè)學(xué)號(hào)命名。168。歡迎覺(jué)得有創(chuàng)新的同學(xué)直接把大作業(yè)報(bào)告發(fā)給演講完畢，謝謝觀看！
外語(yǔ)相關(guān)推薦
鄂ICP備17016276號(hào)-1