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