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