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

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