算法合集之淺析解對(duì)策問題的兩種思路-在線瀏覽
2025-07-05 01:33本頁面
【正文】 ） （ 0, 0） （ 0, 0） 敗 敗 敗 敗 敗 敗 注：這里的勝敗指的均是先手勝敗。 1如果一個(gè)狀態(tài)的所有子狀態(tài)都是先手勝，則該狀態(tài)是先手?jǐn)? 淺析解 “ 對(duì)策問題 ” 的兩種思路 “動(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ì)策問題 ” 的兩種思路 思路一： 一般性方法 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)用十分廣泛。 淺析解 “ 對(duì)策問題 ” 的兩種思路 思路一： 一般性方法 l 狀 態(tài) 列舉影響結(jié)局勝負(fù)的所有因素，綜合描述成 “ 狀態(tài) ” 。 l 勝負(fù)規(guī)則 一個(gè)狀態(tài)的勝負(fù)取決于其所有子狀態(tài)的勝負(fù)。例如 IOI2021《 Score》一題就是用擴(kuò)展規(guī)則解決的。 1對(duì)局策略 依據(jù)已知的狀態(tài)勝負(fù)，時(shí)刻把先手必?cái)〉臓顟B(tài)留給對(duì)方。 l 空 間 “ 一般性方法 ” 要考察 所有 狀態(tài)的先手勝負(fù)。 l 時(shí) 間 “ 一般性方法 ” 還要通過勝負(fù)規(guī)則來研究狀態(tài)之間的關(guān)系。 淺析解 “ 對(duì)策問題 ” 的兩種思路 思路一： 一般性方法 由此可見 ， “ 一般性方法 ” 并不能解決所有的 “ 對(duì)策問題 ” 。 為了彌補(bǔ) “ 一般性方法 ” 的缺陷 ， “ 特殊性方法 ” 勢必是尋找一種 “ 決策規(guī)律 ” ， 能依據(jù)當(dāng)前狀態(tài) ， 按照“ 決策規(guī)律 ” 直接決定下一步的走法 。 甲如何取勝呢 ？ 事實(shí)上 ， 甲只要先在圓桌中心放下一枚硬幣 ， 此后無論乙怎么放 ， 甲總在其關(guān)于中心對(duì)稱處放一枚 ， 最終甲必然獲勝 。 這種狀態(tài)是具有某種 “ 平衡性 ” 的 ， 稱之為 “ 平衡狀態(tài) ” 。 先看一個(gè)簡單的例子： 在一個(gè)圓形桌面上 ， 甲 、 乙輪流放 5分硬幣 ， 不許重疊 ， 甲先放 ，首先放不下硬幣的一方為負(fù) 。 甲如何取勝呢 ？ 甲 乙 淺析解 “ 對(duì)策問題 ” 的兩種思路 思路二： 特殊性方法 “ 一般性方法 ” 是從初始狀態(tài)開始， 自頂而下 建立 “ 狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu) ” 。 甲必?cái)?： 甲必勝 ： 2 3 4 5 6 7 8 …… …… 淺析解 “ 對(duì)策問題 ” 的兩種思路 思路二： 特殊性方法 Fibonacci 數(shù)列 “ 一般性方法 ” 是從初始狀態(tài)開始， 自頂而下 建立 “ 狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu) ” 。 甲必?cái)?： 甲必勝 ： 2 3 4 5 6 7 8 …… …… 淺析解 “ 對(duì)策問題 ” 的兩種思路 思路二： 特殊性方法 猜 想 ： 設(shè) {F}為 Fibonacci數(shù)列 （ F1=2， F2=3， FK=FK1+FK2） 初始時(shí)有 N粒石子，若 N∈ {F}則先手必?cái)?，否則先手必勝。 性質(zhì) 2： 若狀態(tài)（ N,N1）先手必?cái)?，則狀態(tài)（ N,K）K N 先手必?cái)?。 性質(zhì) 4： 4Fi1/3 Fi （ F1=2， F2=3， FK=FK1+FK2）。 淺析解 “ 對(duì)策問題 ” 的兩種思路 思路二： 特殊性方法
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1