算法合集之浅析解对策问题的两种思路.pptx

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