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

《浅析解 “对策问题” 的两种思路》由会员分享，可在线阅读，更多相关《浅析解 “对策问题” 的两种思路（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粒甲

3、取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

4、）（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如果一个状态的所有子状态都是先手胜，则该状态是先手败浅析解 “对策问题” 的两种思路“动态规划” 或“记忆化

5、搜索” 空间复杂度 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都可以用“一般性方 法”来解决。 浅析解 “对策问题” 的

6、两种思路思路一：一般性方法l 状 态 列举影响结局胜负的所有因素，综合描述成“状态状态”。根据对局时状态之间的变化，自顶而下自顶而下构造出“状态转移的拓扑结构状态转移的拓扑结构”。l 胜负规则 一个状态的胜负取决于其所有子状态的胜负。 1如果一个状态没有子状态，是结局，则根据题目条件判定胜负 1如果一个状态至少有一个子状态是先手败，则该状态是先手胜 1如果一个状态的所有子状态都是先手胜，则该状态是先手败浅析解 “对策问题” 的两种思路思路一：一般性方法l 扩展规则 在某些场合下，还可以记录一个状态先手胜（负）的最大（最小）利益，以数值形式描述，再根据题目中相应的条件，构成新的具有针针对性对性的

7、推算规则。例如IOI2001Score一题就是用扩展规则解决的。l 实现方法 1预先处理（关键） 列举状态；构造“状态转移的拓扑结构”；动态规划或记忆化搜索求状态先手胜负。 1对局策略 依据已知的状态胜负，时刻把先手必败的状态留给对方。浅析解 “对策问题” 的两种思路思路一：一般性方法“一般性方法”也有它的不足： l 基 础 “一般性方法”是以“状态转移的拓扑结构状态转移的拓扑结构”为基础设计的。l 空 间 “一般性方法”要考察所有所有状态的先手胜负。如果状态数目过多，甚至是无穷多，那“一般性方法”就无能为力了。l 时 间 “一般性方法”还要通过胜负规则来研究状态之间的关系。 如果状态过多，关

8、系复杂，就可能导致算法效率下降。浅析解 “对策问题” 的两种思路思路一：一般性方法 由此可见，“一般性方法”并不能解决所有的“对策问题”。于是，各种各样的针对单独问题的特殊解法应运而生，不妨总的称之为“特殊性方法”。 为了弥补“一般性方法”的缺陷， “特殊性方法” 势必是寻找一种“决策规律决策规律”，能依据当前状态，按照“决策规律决策规律”直接决定下一步的走法。浅析解 “对策问题” 的两种思路思路二：特殊性方法 先看一个简单的例子： 在一个圆形桌面上，甲、乙轮流放5分硬币，不许重叠，甲先放，首先放不下硬币的一方为负。甲如何取胜呢？ 事实上，甲只要先在圆桌中心放下一枚硬币，此后无论乙怎么放，甲总

9、在其关于中心对称处放一枚，最终甲必然获胜。甲乙浅析解 “对策问题” 的两种思路思路二：特殊性方法 在这个例子中，甲找到了一种必胜的状态。这种状态是具有某种“平衡性”的，称之为“平衡状态平衡状态”。每当乙破坏了“平衡”后，甲立即使其恢复“平衡”，直到结局。 先看一个简单的例子： 在一个圆形桌面上，甲、乙轮流放5分硬币，不许重叠，甲先放，首先放不下硬币的一方为负。甲如何取胜呢？甲乙浅析解 “对策问题” 的两种思路思路二：特殊性方法 那么怎样寻找“对策问题”中的“平平衡状态衡状态”呢？如何确定“决策规律决策规律”使我方在平衡被破坏后必然能恢复呢？ 先看一个简单的例子： 在一个圆形桌面上，甲、乙轮流放