《算法合集之《浅析解对策问题的两种思路》》由会员分享,可在线阅读,更多相关《算法合集之《浅析解对策问题的两种思路》(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 胜负规那么 一般性方法:有通行规那么可套用,应用面十分广泛;但是受“拓扑结构限制,而且需考察所有状态,时空复杂度也有可能很高。特殊性方法:不受“拓扑结构限制,无须考察所有状态,时空复杂