1、浅析解 “对策问题 ” 的两种思路 从取石子问题谈起浅析解 “对策问题 ” 的两种思路内容提要：运 筹 学规划论动态规划图 论对策论 排队论存储论等等线性规划整数规划等等本文所要探讨的正是此类 “对策问题 ” 。运筹学是一门十分年轻的学科，内容包括：规划论、图论、对策论、排队论等。 竞赛中最常出现的对策问题是：有两个局中人，在对方时刻采取最优策略的情况下，己方要么有必胜策略，要么必败。由于对局的复杂性和取胜的多样性，文章将从一道经典的 “对策问题 ” 取石子谈起，着重阐述两种基本思想方法。 浅析解 “对策问题 ” 的两种思路问 题 描 述有 N粒石子，甲乙两人轮流从中拿取，一次至少拿一粒，至多
2、拿先前对方一次所取石子数目的两倍。甲先拿，开始甲可以拿任意数目的石子（但不得拿完）。最先没有石子可拿的一方为败方。请问，甲能否获胜？（ 1 N 100）解 析在本题中，影响胜败的有两个关键因素：l 当前石子总数 Nl 当前一次最多可拿的石子数 K用这两个因素 （ N， K） 来表示当前局面的 “ 状态 ” 。题目要求的是判断状态 （ N， N-1） 是先手必胜还是必败。 浅析解 “对策问题 ” 的两种思路用一个简单例子分析：假设有 N = 4粒石子，则一开始甲最多能取 3粒，用 （ 4， 3） 来表示初始状态。 状态转移的拓扑结构甲取 1粒 甲取 2粒 甲取 3粒乙取 1粒 乙取 2粒 乙取
3、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、个状态没有子状态，是结局，则根据题目条件判定胜负浅析解 “对策问题 ” 的两种思路胜胜 胜胜胜胜（ 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
5、, 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 实现方法 “一
6、般性方法 ”是从初始状态出发，自顶向下，考察所有状态，逐步构造出 “状态转移的拓扑结构 ”， 有通行的胜败规则和实现方法，因此应用十分广泛。例如 IOI96的 取数字 ， IOI2001 Ioiwari 都可以用 “ 一般性方法 ” 来解决。 浅析解 “对策问题 ” 的两种思路思路一： 一般性方法l 状 态列举影响结局胜负的所有因素，综合描述成 “ 状态 ” 。根据对局时状态之间的变化， 自顶而下 构造出 “ 状态转移的拓扑结构 ” 。l 胜负规则一个状态的胜负取决于其所有子状态的胜负。1 如果一个状态没有子状态，是结局，则根据题目条件判定胜负1 如果一个状态至少有一个子状态是先手败，则该状态是先手胜1 如果一个状态的所有子状态都是先手胜，则该状态是先手败
