算法合集之《淺析解對(duì)策問(wèn)題的兩種思路》-文庫(kù)吧
2025-04-12 01:33 本頁(yè)面
【正文】 0） （ 0, 0） （ 0, 0） （ 1, 1） （ 0, 0） （ 0, 0） （ 0, 0） 敗 敗 敗 敗 敗 敗 注：這里的勝敗指的均是先手勝敗。 1如果一個(gè)狀態(tài)的所有子狀態(tài)都是先手勝，則該狀態(tài)是先手?jǐn)? 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 “動(dòng)態(tài)規(guī)劃” 或 “記憶化搜索” 空間復(fù)雜度 O(N2) 時(shí)間復(fù)雜度 O(N3) （ 4, 3） （ 3, 2） （ 2, 2） （ 1, 1） （ 2, 2） （ 1, 1） （ 1, 1） （ 0, 0） （ 0, 0） （ 0, 0） （ 1, 1） （ 0, 0） （ 0, 0） （ 0, 0） 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路一： 一般性方法 l 狀 態(tài) l 勝負(fù)規(guī)則 l 擴(kuò)展規(guī)則 l 實(shí)現(xiàn)方法 “ 一般性方法 ” 是從初始狀態(tài)出發(fā)，自頂向下，考察所有狀態(tài)， 逐步構(gòu)造出 “ 狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu) ”， 有通行的勝敗規(guī)則和實(shí)現(xiàn)方 法，因此應(yīng)用十分廣泛。 例如 IOI96的 取數(shù)字 ， IOI2021《 Ioiwari》 都可以用 “ 一般性方 法 ” 來(lái)解決。 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路一： 一般性方法 l 狀 態(tài) 列舉影響結(jié)局勝負(fù)的所有因素，綜合描述成 “ 狀態(tài) ” 。根據(jù)對(duì)局時(shí)狀態(tài)之間的變化， 自頂而下 構(gòu)造出 “ 狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu) ” 。 l 勝負(fù)規(guī)則 一個(gè)狀態(tài)的勝負(fù)取決于其所有子狀態(tài)的勝負(fù)。 1如果一個(gè)狀態(tài)沒(méi)有子狀態(tài)，是結(jié)局，則根據(jù)題目條件判定勝負(fù) 1如果一個(gè)狀態(tài)至少有一個(gè)子狀態(tài)是先手?jǐn)。瑒t該狀態(tài)是先手勝 1如果一個(gè)狀態(tài)的所有子狀態(tài)都是先手勝，則該狀態(tài)是先手?jǐn)? 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路一： 一般性方法 l 擴(kuò)展規(guī)則 在某些場(chǎng)合下，還可以記錄一個(gè)狀態(tài)先手勝（負(fù)）的最大（最?。├妫詳?shù)值形式描述，再根據(jù)題目中相應(yīng)的條件，構(gòu)成新的具有 針對(duì)性 的推算規(guī)則。例如 IOI2021《 Score》一題就是用擴(kuò)展規(guī)則解決的。 l 實(shí)現(xiàn)方法 1預(yù)先處理（關(guān)鍵） 列舉狀態(tài)；構(gòu)造“狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu)”；動(dòng)態(tài)規(guī)劃或記憶化搜索求狀態(tài)先手勝負(fù)。 1對(duì)局策略 依據(jù)已知的狀態(tài)勝負(fù)，時(shí)刻把先手必?cái)〉臓顟B(tài)留給對(duì)方。 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路一： 一般性方法 “ 一般性方法 ” 也有它的不足： l 基 礎(chǔ) “ 一般性方法 ” 是以 “ 狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu) ” 為基礎(chǔ)設(shè)計(jì)的。 l 空 間 “ 一般性方法 ” 要考察 所有 狀態(tài)的先手勝負(fù)。如果狀態(tài)數(shù)目過(guò)多，甚至是無(wú)窮多，那 “ 一般性方法 ” 就無(wú)能為力了。 l 時(shí) 間 “ 一般性方法 ” 還要通過(guò)勝負(fù)規(guī)則來(lái)研究狀態(tài)之間的關(guān)系。 如果狀態(tài)過(guò)多，關(guān)系復(fù)雜，就可能導(dǎo)致算法效率下降。 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路一： 一般性方法 由此可見(jiàn) ， “ 一般性方法 ” 并不能解決所有的 “ 對(duì)策問(wèn)題 ” 。 于是 ， 各種各樣的針對(duì)單獨(dú)問(wèn)題的特殊解法應(yīng)運(yùn)而生 ， 不妨總的稱(chēng)之為 “ 特殊性方法 ” 。 為了彌補(bǔ) “ 一般性方法 ” 的缺陷 ， “ 特殊性方法 ” 勢(shì)必是尋找一種 “ 決策規(guī)律 ” ， 能依據(jù)當(dāng)前狀態(tài) ， 按照“ 決策規(guī)律 ” 直接決定下一步的走法 。 淺析解 “ 對(duì)策問(wèn)題 ” 的兩種思路 思路二： 特殊性方法 先看一個(gè)簡(jiǎn)單的例子： 在一個(gè)圓形桌面上 ， 甲 、 乙輪流放 5分硬幣 ， 不許重疊 ， 甲先放 ，首先放不下硬幣的一方為負(fù) 。 甲如
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1