浅析解“对策问题”的两种思路

浅析解“对策问题”的两种思路——从《取石子》问题谈起浅析解“对策问题”的两种思路内容提要：运筹学规划论动态规划图论对策论排队论存储论等等线性规划整数规划等等本文所要探讨的正是此类“对策问题”。运筹学是一门十分年轻的学科，内容包括：规划论、图论、对策论、排队论等。竞赛中最常出现的对策问题是：有两个局中人，在对方时刻采取最优策略的情况下，己方要么有必胜策略，要么必败。由于对局的复杂性和取胜的多样性，文章将从一道经典的“对策问题”——《取石子》谈起，着重阐述两种基本思想方法。浅析解“对策问题”的两种思路问题描述有N粒石子，甲乙两人轮流从中拿取，一次至少拿一粒，至多拿先前对方一次所取石子数目的两倍。甲先拿，开始甲可以拿任意数目的石子（但不得拿完）。最先没有石子可拿的一方为败方。请问，甲能否获胜？（1N100）解析在本题中，影响胜败的有两个关键因素：l当前石子总数Nl当前一次最多可拿的石子数K用这两个因素（N，K）来表示当前局面的“状态”。题目要求的是判断状态（N，N-1）是先手必胜还是必败。浅析解“对策问题”的两种思路用一个简单例子分析：假设有N=4粒石子，则一开始甲最多能取3粒，用（4，3）来表示初始状态。状态转移的拓扑结构甲取1粒甲取2粒甲取3粒乙取1粒乙取2粒乙取1粒乙取2粒乙取1粒甲取1粒甲取2粒甲取1粒甲取1粒乙取1粒（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）自顶而下构造浅析解“对策问题”的两种思路（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）败败败败败败注：这里的胜败指的均是先手胜败。1如果一个状态没有子状态，是结局，则根据题目条件判定胜负浅析解“对策问题”的两种思路胜胜胜胜胜胜（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）败败败败败败注：这里的胜败指的均是先手胜败。1如果一个状态至少有一个子状态是先手败，则该状态是先手胜浅析解“对策问题”的两种思路胜败胜胜胜胜胜胜（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）败败败败败败注：这里的胜败指的均是先手胜败。1如果一个状态的所有子状态都是先手胜，则该状态是先手败浅析解“对策问题”的两种思路“动态规划”或“记忆化搜索”空间复杂度O(N2)时间复杂度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）浅析解“对策问题”的两种思路思路一：一般性方法l状态l胜负规则l扩展规则l实现方法“一般性方法”是从初始状态出发，自顶向下，考察所有状态，逐步构造出“状态转移的拓扑结构”，有通行的胜败规则和实现方法，因此应用十分广泛。例如IOI96的取数字，IOI2001《Ioiwari》都可以用“一般性方法”来解决。浅析解“对策问题”的两种思路思路一：一般性方法l状态列举影响结局胜负的所有因素，综合描述成“状态”。根据对局时状态之间的变化，自顶而下构造出“状态转移的拓扑结构”。l胜负规则一个状态的胜负取决于其所有子状态的胜负。1如果一个状态没有子状态，是结局，则根据题目条件判定胜负1如果一个状态至少有一个子状态是先手败，则该状态是先手胜1如果一个状态的所有子状态都是先手胜，则该状态是先手败浅析解“对策问题”的两种思路思路一：一般性方法l扩展规则在某些场合下，还可以记录一个状态先手胜（负）的最大（最小）利益，以数值形式描述，再根据题目中相应的条件，构成新的具有针对性的推算规则。例如IOI2001《Score》一题就是用扩展规则解决的。l实现方法1预先处理（关键）列举状态；构造“状态转移的拓扑结构”；动态规划或记忆化搜索求状态先手胜负。1对局策略依据已知的状态胜负，时刻把先手必败的状态留给对方。浅析解“对策问题”的两种思路思路一：一般性方法“一般性方法”也有它的不足：l基础“一般性方法”是以“状态转移的拓扑结构”为基础设计的。l空间“一般性方法”要考察所有状态的先手胜负。如果状态数目过多，甚至是无穷多，那“一般性方法”就无能为力了。l时间“一般性方法”还要通过胜负规则来研究状态之间的关系。如果状态过多，关系复杂，就可能导致算法效率下降。浅析解“对策问题”的两种思路思路一：一般性方法由此可见，“一般性方法”并不能解决所有的“对策问题”。于是，各种各样的针对单独问题的特殊解法应运而生，不妨总的称之为“特殊性方法”。为了弥补“一般性方法”的缺陷，“特殊性方法”势必是寻找一种“决策规律”，能依据当前状态，按照“决策规律”直接决定下一步的走法。浅析解“对策问题”的两种思路思路二：特殊性方法先看一个简单的例子：在一个圆形桌面上，甲、乙轮流放5分硬币，不许重叠，甲先放，首先放不下硬币的一方为负。甲如何取胜呢？事实上，甲只要先在圆桌中心放下一枚硬币，此后无论乙怎么放，甲总在其关于中心对称处放一枚，最终甲必然获胜。甲乙浅析解“对策问题”的两种思路思路二：特殊性方法在这个例子中，甲找到了一种必胜的状态。这种状态是具有某种“平衡性”的，称之为“平衡状态”。每当乙破坏了“平衡”后，甲立即使其恢复“平衡”，直到结局。先看一个简单的例子：在一个圆形桌面上，甲、乙轮流放5分硬币，不许重叠，甲先放，首先放不下硬币的一方为负。甲如何取胜呢？甲乙浅析解“对策问题”的两种思路思路二：特殊性方法那么怎样寻找“对策问题”中的“平衡状态”呢？如何确定“决策规律”使我方在平衡被破坏后必然能恢复呢？先看一个简单的例子：在一个圆形桌面上，甲、乙轮流放5分硬币，不许重叠，甲先放，首先放不下硬币的一方为负。甲如何取胜呢？甲乙浅析解“对策问题”的两种思路思路二：特殊性方法“一般性方法”是从初始状态开始，自顶而下建立“状态转移的拓扑结构”。现在，不妨反其道而行之，从结局或小规模残局开始，自底向上分析。甲必败：甲必胜：2345678…………浅析解“对策问题”的两种思路思路二：特殊性方法Fibonacci数列“一般性方法”是从初始状态开始，自顶而下建立“状态转移的拓扑结构”。现在，不妨反其道而行之，从结局或小规模残局开始，自底向上分析。甲必败：甲必胜：2345678…………浅析解“对策问题”的两种思路思路二：特殊性方法猜想：设{F}为Fibonacci数列（F1=2，F2=3，FK=FK-1+FK-2）初始时有N粒石子，若N∈{F}则先手必败，否则先手必胜。浅析解“对策问题”的两种思路思路二：特殊性方法性质1：若K≥N，则状态（N,K）先手必胜。性质2：若状态（N,N-1）先手必败，则状态（N,K）KN先手必败。性质3：若状态（N,K）KN，则最后一次取走的石子数目不超过2N/3。性质4：4Fi-1/3Fi（F1=2，F2=3，FK=FK-1+FK-2）。浅析解“对策问题”的两种思路思路二：特殊性方法结论1：状态(Fi，A）AFi先手必败。浅析解“对策问题”的两种思路思路二：特殊性方法证明：（一）F1(=2)，F2(=3)时，显然成立。Fi-1FiFi+1（二）若F1至Fi成立，则Fi+1成立。设先手取K粒石子。（1）若K≥Fi-1后手得状态(N-K,2K)2K≥2Fi-1≥Fi-1+Fi-2=FiN-K由性质1，后手获胜。后手获胜，先手败K(N-K,2K)浅析解“对策问题”的两种思路思路二：特殊性方法证明：Fi-1FiFi+1K（一）F1(=2)，F2(=3)时，显然成立。（二）若F1至Fi成立，则Fi+1成立。设先手取K粒石子。（1）若K≥Fi-1后手得状态(N-K,2K)后手获胜，先手败（2）若KFi-1根据假设（Fi-1,K）KFi-1必败，所以后手可以使先手面临(Fi，X)状态。(Fi,X)浅析解“对策问题”的两种思路思路二：特殊性方法证明：（一）F1(=2)，F2(=3)时，显然成立。（二）若F1至Fi成立，则Fi+1成立。设先手取K粒石子。（1）若K≥Fi-1后手得状态(N-K,2K)后手获胜，先手败（2）若KFi-1Fi-1FiFi+1K(Fi,X)由性质3：X≤2Fi-1/3×2=4Fi-1/3由性质4：X≤4Fi-1/3Fi因此(Fi,X)是必败后手获胜，先手败浅析解“对策问题”的两种思路思路二：特殊性方法证明：（一）F1(=2)，F2(=3)时，显然成立。（二）若F1至Fi成立，则Fi+1成立。设先手取K粒石子。（1）若K≥Fi-1后手得状态(N-K,2K)后手获胜，先手败（2）若KFi-1Fi-1FiFi+1后手获胜，先手败由（1）（2）得Fi+1时，结论成立。由（一）（二）得结论1成立。浅析解“对策问题”的两种思路思路二：特殊性方法结论2：状态(N，N-1）N∈{F}且N2，先手必胜。浅析解“对策问题”的两种思路思路二：特殊性方法FF’NF’’平衡状态:Fibonacci数决策规律:反复缩小范围，找最大Fibonacci数浅析解“对策问题”的两种思路思路二：特殊性方法空间复杂度O(1)时间复杂度O(logN)特殊性方法空间复杂度O(N2)时间复杂度O(N3)一般性方法大大降低平衡状态:Fibonacci数决策规律:反复缩小范围，找最大Fibonacci数浅析解“对策问题”的两种思路思路二：特殊性方法l状态l逆向分析“特殊性方法”是从结局或残局出发，自底而上分析，无须构造“状态转移的拓扑结构”，无须考察所有可能的状态与策略，时间和空间复杂度相对于“一般性方法”都不高。例如POI99《多边形》，IOI96的取数字也可以用“特殊性方法”来解决。浅析解“对策问题”的两种思路思路二：特殊性方法l状态列举影响结局胜负的所有因素，综合描述成“状态”，但并不需要构造出“状态转移的拓扑结构”。浅析解“对策问题”的两种思路思路二：特殊性方法l逆向分析从简单的结局或残局开始，自底向上分析。考察特殊情况下（譬如小规模，对称，极大极小等特殊值），先手胜或先手败的一类状态，并尝试从以下几个方面寻找共性：1对称性1简捷性1奇异性通过分析，将所得性质推广到一般情况，从而找出一类必胜或必败的“平衡状态”，同时也得到保持状态“平衡”的“决策规律”。浅析解“对策问题”的两种思路一般性方法与特殊性方法1一次可取先前对方所取石子数的3倍《取石子》问题的推广：1一次可取先前对方所取石子数的4倍1一次可取先前对方所取石子数的5倍1一次可取先前对方所取石子数的K倍1…………一般性方法特殊性方法VS浅析解“对策问题”的两种思路一般性方法与特殊性方法l思路方向一般性方法：自顶而下考察所有状态胜负特殊性方法：自底而上研究一类平衡状态浅析解“对策问题”的两种思路一般性方法与特殊性方法l思路方向一般性方法：有通行胜负规则特殊性方法：无通行胜负规则l胜负规则浅析解“对策问题”的两种思路一般性方法与特殊性方法l思路方向l胜负规则一般性方法：关键是动态规划或记忆化搜索的预处理。特殊性方法：着重于事先的思考，再将“决策规律”转化成程序。l实现方法浅析解“对策问题”的两种思路一般性方法与特殊性方法l思路方向l胜负规则一般性方法：有通行规则可套用，应用面十分广泛；但是受“拓扑结构”限制，而且需考察所有状态，时空复杂度也有可能很高。特殊性方法：不受“拓扑结构”限制，无须考察所有状态，时空复杂度低，编程简单；但是无通行规则，思考难度大。l优点缺点l实现方法浅析解“对策问题”的两种思路一般性方法与特殊性方法l思路方向l胜负规则在“对策问题”中，一个状态要么是先手必胜，要么是先手必败！因此，在对局时，我方要做的就是占据必胜，把必败留给对方。l优点缺点l实现方法这正是解“对策问题”的核心思想！l核心思想浅析解“对策问题”的两种思路一般性方法与特殊性方法l思路方向l胜负规则l优点缺点l实现方法“一般性方法”