淺析解對(duì)策問(wèn)題的兩種思路

1、淺析解 “對(duì)策問(wèn)題” 的兩種思路,——從《取石子》問(wèn)題談起,淺析解 “對(duì)策問(wèn)題” 的兩種思路,內(nèi)容提要：,本文所要探討的正是此類“對(duì)策問(wèn)題” 。,運(yùn)籌學(xué)是一門十分年輕的學(xué)科，內(nèi)容包括：規(guī)劃論、圖論、對(duì)策論、排隊(duì)論等。,競(jìng)賽中最常出現(xiàn)的對(duì)策問(wèn)題是：有兩個(gè)局中人，在對(duì)方時(shí)刻采取最優(yōu)策略的情況下，己方要么有必勝策略，要么必?cái)　?由于對(duì)局的復(fù)雜性和取勝的多樣性，文章將從一道經(jīng)典的“對(duì)策問(wèn)題”——《取石子》談起，著重闡述兩種基本思想方法。,淺析解

2、 “對(duì)策問(wèn)題” 的兩種思路,問(wèn) 題 描 述 有N粒石子，甲乙兩人輪流從中拿取，一次至少拿一粒，至多拿先前對(duì)方一次所取石子數(shù)目的兩倍。甲先拿，開始甲可以拿任意數(shù)目的石子（但不得拿完）。最先沒有石子可拿的一方為敗方。 請(qǐng)問(wèn)，甲能否獲勝？（1 < N < 100）,解 析 在本題中，影響勝敗的有兩個(gè)關(guān)鍵因素： l 當(dāng)前石子總數(shù) N l 當(dāng)前一次最多可拿的石子數(shù) K 用這兩個(gè)因素（

3、N，K）來(lái)表示當(dāng)前局面的“狀態(tài)”。題目要求的是判斷狀態(tài)（N，N-1）是先手必勝還是必?cái)　?淺析解 “對(duì)策問(wèn)題” 的兩種思路,用一個(gè)簡(jiǎn)單例子分析：假設(shè)有N = 4粒石子，則一開始甲最多能取3粒，用（4，3）來(lái)表示初始狀態(tài)。,狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu),淺析解 “對(duì)策問(wèn)題” 的兩種思路,1如果一個(gè)狀態(tài)沒有子狀態(tài)，是結(jié)局，則根據(jù)題目條件判定勝負(fù),淺析解 “對(duì)策問(wèn)題” 的兩種思路,1如果一個(gè)狀態(tài)至少有一個(gè)子狀態(tài)是先手?jǐn)。瑒t該狀態(tài)是先手勝,淺析解 “對(duì)策

4、問(wèn)題” 的兩種思路,勝,敗,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),淺析解 “對(duì)策問(wè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ù)字，IO

5、I2001《Ioiwari》都可以用“一般性方法”來(lái)解決。,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路一：一般性方法,狀 態(tài) 列舉影響結(jié)局勝負(fù)的所有因素，綜合描述成“狀態(tài)”。根據(jù)對(duì)局時(shí)狀態(tài)之間的變化，自頂而下構(gòu)造出“狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu)”。,勝負(fù)規(guī)則 一個(gè)狀態(tài)的勝負(fù)取決于其所有子狀態(tài)的勝負(fù)。 1如果一個(gè)狀態(tài)沒有子狀態(tài)，是結(jié)局，則根據(jù)題目條件判定勝負(fù) 1如果一個(gè)狀態(tài)至少有一個(gè)子狀態(tài)是先手?jǐn)。瑒t該狀態(tài)是先手勝 1如果一個(gè)狀態(tài)

6、的所有子狀態(tài)都是先手勝，則該狀態(tài)是先手?jǐn)?淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路一：一般性方法,擴(kuò)展規(guī)則 在某些場(chǎng)合下，還可以記錄一個(gè)狀態(tài)先手勝（負(fù)）的最大（最?。├?，以數(shù)值形式描述，再根據(jù)題目中相應(yīng)的條件，構(gòu)成新的具有針對(duì)性的推算規(guī)則。例如IOI2001《Score》一題就是用擴(kuò)展規(guī)則解決的。,實(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ù)已

7、知的狀態(tài)勝負(fù)，時(shí)刻把先手必?cái)〉臓顟B(tài)留給對(duì)方。,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路一：一般性方法,“一般性方法”也有它的不足：,基 礎(chǔ) “一般性方法”是以“狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu)”為基礎(chǔ)設(shè)計(jì)的。,空 間 “一般性方法”要考察所有狀態(tài)的先手勝負(fù)。如果狀態(tài)數(shù)目過(guò)多，甚至是無(wú)窮多，那“一般性方法”就無(wú)能為力了。,時(shí) 間 “一般性方法”還要通過(guò)勝負(fù)規(guī)則來(lái)研究狀態(tài)之間的關(guān)系。 如果狀態(tài)過(guò)多，關(guān)系復(fù)雜，就可能導(dǎo)致算法

8、效率下降。,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路一：一般性方法,由此可見，“一般性方法”并不能解決所有的“對(duì)策問(wèn)題”。于是，各種各樣的針對(duì)單獨(dú)問(wèn)題的特殊解法應(yīng)運(yùn)而生，不妨總的稱之為“特殊性方法”。,為了彌補(bǔ)“一般性方法”的缺陷， “特殊性方法” 勢(shì)必是尋找一種“決策規(guī)律”，能依據(jù)當(dāng)前狀態(tài)，按照“決策規(guī)律”直接決定下一步的走法。,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,先看一個(gè)簡(jiǎn)單的例子： 在一個(gè)圓形桌面上，

9、甲、乙輪流放5分硬幣，不許重疊，甲先放，首先放不下硬幣的一方為負(fù)。甲如何取勝呢？,事實(shí)上，甲只要先在圓桌中心放下一枚硬幣，此后無(wú)論乙怎么放，甲總在其關(guān)于中心對(duì)稱處放一枚，最終甲必然獲勝。,,,,,,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,在這個(gè)例子中，甲找到了一種必勝的狀態(tài)。這種狀態(tài)是具有某種“平衡性”的，稱之為“平衡狀態(tài)”。每當(dāng)乙破壞了“平衡”后，甲立即使其恢復(fù)“平衡”，直到結(jié)局。,先看一個(gè)簡(jiǎn)單的例子： 在

10、一個(gè)圓形桌面上，甲、乙輪流放5分硬幣，不許重疊，甲先放，首先放不下硬幣的一方為負(fù)。甲如何取勝呢？,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,先看一個(gè)簡(jiǎn)單的例子： 在一個(gè)圓形桌面上，甲、乙輪流放5分硬幣，不許重疊，甲先放，首先放不下硬幣的一方為負(fù)。甲如何取勝呢？,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,“一般性方法”是從初始狀態(tài)開始，自頂而下建立“狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu)”。現(xiàn)在，不妨反其道而行之，從結(jié)局

11、或小規(guī)模殘局開始，自底向上分析。,甲必?cái)。?甲必勝：,2,3,4,5,6,7,8,……,……,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,Fibonacci 數(shù)列,“一般性方法”是從初始狀態(tài)開始，自頂而下建立“狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu)”。現(xiàn)在，不妨反其道而行之，從結(jié)局或小規(guī)模殘局開始，自底向上分析。,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,猜 想： 設(shè){F}為Fibonacci數(shù)列（F1=2，F(xiàn)2=3，F(xiàn)K=

12、FK-1+FK-2）初始時(shí)有N粒石子，若N∈{F}則先手必?cái)。駝t先手必勝。,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,性質(zhì)1：若K≥N，則狀態(tài)（N,K）先手必勝。,性質(zhì)2：若狀態(tài)（N,N-1）先手必?cái)。瑒t狀態(tài)（N,K）K< N 先手必?cái)　?性質(zhì)3：若狀態(tài)（N,K）K< N，則最后一次取走的石子數(shù)目不超過(guò)2N/3。,性質(zhì)4：4Fi-1/3 < Fi （F1=2，F(xiàn)2=3，F(xiàn)K=FK-1+FK-2）。,淺析

13、解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,結(jié)論1：狀態(tài)(Fi，A） A < Fi 先手必?cái)　?淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,證 明：,（一）F1(=2)，F(xiàn)2(=3)時(shí)，顯然成立。,,（二）若F1至Fi成立，則Fi+1成立。,設(shè)先手取K粒石子。,（1）若K≥Fi-1 后手得狀態(tài)(N-K,2K),2K≥2Fi-1≥Fi-1+Fi-2= Fi > N-K 由性質(zhì)1，后手獲勝。,后手獲勝，先手?jǐn)?

14、淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,證 明：,（2）若K < Fi-1,根據(jù)假設(shè)（Fi-1,K）K < Fi-1 必?cái)。院笫挚梢允瓜仁置媾R(Fi，X)狀態(tài)。,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,證 明：,（2）若K < Fi-1,由性質(zhì)3： X≤2Fi-1/3 ×2 = 4Fi-1/3,由性質(zhì)4： X≤4Fi-1/3 < Fi 因此(Fi,X)是必?cái)?后手

15、獲勝，先手?jǐn)?淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,證 明：,（2）若K < Fi-1,后手獲勝，先手?jǐn)?由（1） （2）得Fi+1時(shí)，結(jié)論成立。,由（一）（二）得結(jié)論1成立。,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,,,,,平衡狀態(tài): Fibonacci數(shù),決策規(guī)律: 反復(fù)縮小范圍，找最大Fibonacci數(shù),淺析解 “對(duì)策問(wèn)題” 的兩種思路,

16、思路二：特殊性方法,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,“特殊性方法”是從結(jié)局或殘局出發(fā)，自底而上分析，無(wú)須構(gòu)造“狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu)”，無(wú)須考察所有可能的狀態(tài)與策略，時(shí)間和空間復(fù)雜度相對(duì)于“一般性方法”都不高。 例如POI99 《多邊形》 ，IOI96的取數(shù)字也可以用“特殊性方法”來(lái)解決。,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,狀 態(tài) 列舉影響結(jié)局勝負(fù)的所有因素，綜合描述成“狀態(tài)”，

17、但并不需要構(gòu)造出“狀態(tài)轉(zhuǎn)移的拓?fù)浣Y(jié)構(gòu)”。,淺析解 “對(duì)策問(wèn)題” 的兩種思路,思路二：特殊性方法,逆向分析 從簡(jiǎn)單的結(jié)局或殘局開始，自底向上分析。 考察特殊情況下（譬如小規(guī)模，對(duì)稱，極大極小等特殊值），先手勝或先手?jǐn)〉囊活悹顟B(tài)，并嘗試從以下幾個(gè)方面尋找共性：,1 對(duì)稱性,1 簡(jiǎn)捷性,1 奇異性,通過(guò)分析，將所得性質(zhì)推廣到一般情況，從而找出一類必勝或必?cái)〉摹捌胶鉅顟B(tài)”，同時(shí)也得到保持狀態(tài)“平衡”的“決策規(guī)律”。,淺析解

18、 “對(duì)策問(wèn)題” 的兩種思路,一般性方法 與 特殊性方法,1一次可取先前對(duì)方所取石子數(shù)的3倍,《取石子》問(wèn)題的推廣：,1一次可取先前對(duì)方所取石子數(shù)的4倍,1一次可取先前對(duì)方所取石子數(shù)的5倍,1一次可取先前對(duì)方所取石子數(shù)的K倍,1…………,淺析解 “對(duì)策問(wèn)題” 的兩種思路,一般性方法 與 特殊性方法,思路方向,一般性方法： 自頂而下 考察所有狀態(tài)勝負(fù) 特殊性方法： 自底而上 研究一類平衡狀態(tài),淺析解 “

19、對(duì)策問(wèn)題” 的兩種思路,一般性方法 與 特殊性方法,思路方向,一般性方法： 有通行勝負(fù)規(guī)則 特殊性方法： 無(wú)通行勝負(fù)規(guī)則,勝負(fù)規(guī)則,淺析解 “對(duì)策問(wèn)題” 的兩種思路,一般性方法 與 特殊性方法,思路方向,勝負(fù)規(guī)則,一般性方法： 關(guān)鍵是動(dòng)態(tài)規(guī)劃或記憶化搜索的預(yù)處理。 特殊性方法： 著重于事先的思考，再將“決策規(guī)律”轉(zhuǎn)化成程序。,實(shí)現(xiàn)方法,淺析解 “對(duì)策問(wèn)題” 的兩種思路,一般性

20、方法 與 特殊性方法,思路方向,勝負(fù)規(guī)則,一般性方法： 有通行規(guī)則可套用，應(yīng)用面十分廣泛；但是受“拓?fù)浣Y(jié)構(gòu)”限制，而且需考察所有狀態(tài)，時(shí)空復(fù)雜度也有可能很高。 特殊性方法： 不受“拓?fù)浣Y(jié)構(gòu)”限制，無(wú)須考察所有狀態(tài)，時(shí)空復(fù)雜度低，編程簡(jiǎn)單；但是無(wú)通行規(guī)則，思考難度大。,優(yōu)點(diǎn)缺點(diǎn),實(shí)現(xiàn)方法,淺析解 “對(duì)策問(wèn)題” 的兩種思路,一般性方法 與 特殊性方法,思路方向,勝負(fù)規(guī)則,在“對(duì)策問(wèn)題”中，一個(gè)狀態(tài)要么是先手必勝，要么是

21、先手必?cái)?！因此，在?duì)局時(shí)，我方要做的就是占據(jù)必勝，把必?cái)×艚o對(duì)方。,優(yōu)點(diǎn)缺點(diǎn),實(shí)現(xiàn)方法,這正是解“對(duì)策問(wèn)題”的核心思想！,核心思想,淺析解 “對(duì)策問(wèn)題” 的兩種思路,一般性方法 與 特殊性方法,思路方向,勝負(fù)規(guī)則,優(yōu)點(diǎn)缺點(diǎn),實(shí)現(xiàn)方法,“一般性方法”從統(tǒng)一的角度，考察所有狀態(tài)，來(lái)決定對(duì)局策略。 “特殊性方法”從特殊的角度，考察一類狀態(tài)，來(lái)決定對(duì)局策略。,核心思想,延伸類比,淺析解 “對(duì)策問(wèn)題” 的兩種思路,結(jié) 語(yǔ),“對(duì)策論”是運(yùn)

22、籌學(xué)的一個(gè)重要分支。本文通過(guò)《取石子》問(wèn)題，簡(jiǎn)單的闡述了解決一類“對(duì)策問(wèn)題”的兩種思路，也是我的一點(diǎn)心得，但并不能涵蓋萬(wàn)一。,文中介紹的“一般性方法”與“特殊性方法” 既是方法，也是思路，更是一種思想。在解其他類型的題目時(shí)，也同樣可以應(yīng)用這兩種思考方法。,淺析解 “對(duì)策問(wèn)題” 的兩種思路,結(jié) 語(yǔ),“ 紙上得來(lái)終覺淺，絕知此事要躬行?！?我們還需要不斷努力，不斷實(shí)踐，不斷探索。只有實(shí)踐多了，方能：,1充分運(yùn)用正向與逆向的思維,