淺析解對策問題的兩種思路

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

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

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

4、問題” 的兩種思路,勝,敗,1如果一個狀態(tài)的所有子狀態(tài)都是先手勝，則該狀態(tài)是先手敗,淺析解 “對策問題” 的兩種思路,“動態(tài)規(guī)劃” 或“記憶化搜索” 空間復雜度 O(N2) 時間復雜度 O(N3),淺析解 “對策問題” 的兩種思路,思路一：一般性方法,“一般性方法”是從初始狀態(tài)出發(fā)，自頂向下，考察所有狀態(tài)，逐步構(gòu)造出“狀態(tài)轉(zhuǎn)移的拓撲結(jié)構(gòu)”，有通行的勝敗規(guī)則和實現(xiàn)方法，因此應用十分廣泛。 例如IOI96的取數(shù)字，IO

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

6、的所有子狀態(tài)都是先手勝，則該狀態(tài)是先手敗,淺析解 “對策問題” 的兩種思路,思路一：一般性方法,擴展規(guī)則 在某些場合下，還可以記錄一個狀態(tài)先手勝（負）的最大（最?。├?，以數(shù)值形式描述，再根據(jù)題目中相應的條件，構(gòu)成新的具有針對性的推算規(guī)則。例如IOI2001《Score》一題就是用擴展規(guī)則解決的。,實現(xiàn)方法 1預先處理（關鍵） 列舉狀態(tài)；構(gòu)造“狀態(tài)轉(zhuǎn)移的拓撲結(jié)構(gòu)”；動態(tài)規(guī)劃或記憶化搜索求狀態(tài)先手勝負。 1對局策略 依據(jù)已

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

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

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

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

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

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

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

14、淺析解 “對策問題” 的兩種思路,思路二：特殊性方法,證 明：,（2）若K < Fi-1,根據(jù)假設（Fi-1,K）K < Fi-1 必敗，所以后手可以使先手面臨(Fi，X)狀態(tài)。,淺析解 “對策問題” 的兩種思路,思路二：特殊性方法,證 明：,（2）若K < Fi-1,由性質(zhì)3： X≤2Fi-1/3 ×2 = 4Fi-1/3,由性質(zhì)4： X≤4Fi-1/3 < Fi 因此(Fi,X)是必敗,后手

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

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

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

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

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

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

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

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