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,
4、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
5、,0)(0,0)(1,1)(0,0)(0,0)(0,0)浅析解“对策问题”的两种思路思路一:一般性方法状态胜负规则扩展规则实现方法“一般性方法”是从初始状态出发,自顶向下,考察所有状态,逐步构造出“状态转移的拓扑结构”,有通行的胜败规则和实现方法,因此应用十分广泛。例如IOI96的取数字,IOI2001《Ioiwari》都可以用“一般性方法”来解决。浅析解“对策问题”的两种思路思路一:一般性方法状态列举影响结局胜负的所有因素,综合描述成“状态”。根据对局时状态之间的变化,自顶而下构造出“状态转移的拓扑结构”。胜负规则一个状态的胜负取决于其所有子状态的胜负。1如果一个状态
6、没有子状态,是结局,则根据题目条件判定胜负1如果一个状态至少有一个子状态是先手败,则该状态是先手胜1如果一个状态的所有子状态都是先手胜,则该状态是先手败浅析解“对策问题”的两种思路思路一:一般性方法扩展规则在某些场合下,还可以记录一个状态先手胜(负)的最大(最小)利益,以数值形式描述,再根据题目中相应的条件,构成新的具有针对性的推算规则。例如IOI2001《Score》一题就是用扩展规则解决的。实现方法1预先处理(关键)列举状态;构造“状态转移的拓扑结构”;动态规划或记忆化搜索求状态先手胜负。1对局策略依据已知的状态胜负,时刻把先手必败的状态留给对方。浅析解“对策问题”
7、的两种思路思路一:一般性方法“一般性方法”也有它的不足:基础“一般性方法”是以“状态转移的拓扑结构”为基础设计的。空间“一般性方法”要考察所有状态的先手胜负。如果状态数目过多,甚至是无穷多,那“一般性方法”就无能为力了。时间“一般性方法”还要通过胜负规则来研究状态之间的关系。如果状态过多,关系复杂,就可能导致算法效率下降。浅析解“对策问题”的两种思路思路一:一般性方法由此可见,“一般性方法”并不能解决所有的“对策问题”。于是,各种各样的针对单独问题的特殊解法应运而生,不妨总的称之为“特殊性方法”。为了弥补“一般性方法”的缺陷,“特殊性方法