算法合集之《从“k倍动态减法游戏”出发探究一类组合游戏问题》

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,从“,k,倍动态减法游戏”出发探究一类组合游戏问题,上海市上海中学 曹钦翔,指导教师：上海市上海中学,毛黎莉,目录,一：引言,二：问题的提出,三：动态规划的通式解法,四：基于动态规划的优化,4.1,利用单调性解决“,k,倍动态减法游戏”,五：不基于动态规划的思考,5.2,利用贪心解决,BOI2008 game,NP,状态,所谓,N,状态，是指当前即将操作的玩家有必胜策略（,N,来源于,Next player wins.,）。,所谓,P,状态，是指先前刚操作完的玩家有必胜策略（,P,来源于,Previous player wins.,）。,定理：,P,状态的一切后继都为,N,状态，,N,状态拥有至少一个后继是,P,状态。,通式动态规划解法,步骤,1,：把所有“胜利终止状态”标记为,P,状态，“失败终止状态”标记为,N,状态。,步骤,2,：找到所有的未定状态中，所有后继都被确定是,N,状态的状态，设置为,P,状态。,步骤,3,：找到所有的未定状态中，可以一步到达,P,状态的状态，都设置为,N,状态。,步骤,4,：若上两步中没有产生新的,P,状态或,N,状态，程序结束，否则回到步骤,2,。,时间复杂度,所有状态的决策数之和,k,倍动态减法游戏,有一个整数,S,（,=2,），先行者在,S,上减掉一个数,x,，至少是,1,，但小于,S,。之后双方轮流把,S,减掉一个正整数，但都不能超过先前一回合对方减掉的数的,k,倍，减到,0,的一方获胜。问：谁有必胜策论。,K=2,A,第一回合减去,2,A,第二回合减去,1,B,第一回合减去,4,A,获胜,通式解法,NP(m,n,),表示,S,还剩下,m,且接下去即将操作的玩家最多能减去,n,的状态，则初始状态为,NP(S,S-1),。,规定，若在,NP(m,n,),状态下，即将操作的玩家必胜则,NP(m,n,)=1,，否则,NP(m,n,)=0,。,若用动态规划计算所有,NP(m,n,),，则判定胜负的时间复杂度为,O(n,3,),。,优化,1,状态单调性,状态,NP(m,n,),是关于关于,n,单调不减的。,记,f(m,)=,minn|NP(m,n,)=1,优化,1,NP(m,n,)=0,当且仅当,对于任意,r=1,2,3,n,有,m-r,0,且,NP(m-r,kr,)=1,。,若,n,0,=,f(m,),，,则,NP(m-n,0,kn,0,)=0,且,NP(m-n,0,+1,k(n,0,-1)=1,若,n,0,=,f(m,),，,则,f(m-n,0,)kn,0,且,f(m-(n,0,-1),kn,时间复杂度：,O(S,2,),优化,2,决策单调性,优化,2,决策单调性,所有这些直线是平行的,随着,m,增大逐渐向下向右移,每一堵墙都是固定的、右端有界的,用栈储存“墙”,优化,2,决策单调性,逐个检验栈中的“墙”,若某堵“墙”不能挡住从,(m,0),格子出发斜率为,k,-1,的直线，那么该“墙”出栈,否则，若这堵“墙”能挡住斜线，则循环结束并得出,f(m,),的值。,最后，根据,f(m,),可确定一堵新“墙”的位置和长度，新“墙”入栈。,时间复杂度：,O(S),BOI 2008 game,一个,n*n,的棋盘，每个格子要么是黑色要么是白色。白格子是游戏区域，黑格子表示障碍。,指定两个格子,AB,，分别是先手方和后手方的起始格子。,A,和,B,这两格子不重合。,游戏中，双方轮流操作。每次操作，玩家向上下左右四个格子之一走一步，但不能走进黑色格子。有一种特殊情况，当一方玩家，恰好走到当前对方所在的格子里，他就可以再走一步（不必是同一方向），“跳过对手”。,胜负的判定是这样的，若有一方走进对方的起始格子，就算获胜，即使是跳过对方，也算获胜。,通式解法,用,(x1,y1,x2,y2),表示状态。,其中,(x1,y1),是,A,的当前位置，,(x2,y2),是,B,的当前位置。另外，还需要一位状态表示当前的操作这是,A,或,B,。,因此，状态总数至少为,O(n,4,),个，尽管每个状态的状态转移代价为,O(1),，但总时间复杂度为,O(n,4,),，太高了。,而且状态数为,O(n,4,),也意味着动态规划已经没有优化的余地，算法的设计必须跳出动态规划的框架。,贪心思路,“先”,贪心的信号,两,人都应沿着两起始点间的最短路径走,注意到，两个人需要走的路程是相等的,所以如果没有“跳过对手”的规则，先行者将必胜！,结论：,如果先行方,A,能避免,B“,跳过,A”,，则,A,获胜；,如果后手方,B,能确保在最短路径上“跳过,A”,，则,B,获胜。,BOI,官方解答,记,d,为,AB,之间最短路的距离。,若,d,为奇数，,A,必胜！所以只要考虑,d,时偶数的情况,用数组,LA,i,存贮，在,AB,最短路径上，且与距离,A,为,i,的格子。,记,NP_Ai,j,k,表示，轮到,A,操作时，,A,在,LA,i,中的第,j,个格子上，,B,在,LA,d-i,中的第,k,个格子上的状态。,NP_Bi,j,k,表示，轮到,B,操作时，,A,在,LA,i+1,中的第,j,个格子上，,B,在,LA,d-i,中的第,k,个格子上的状态。,BOI,官方解答的错误,BOI,的官方解答中认为，数组,NP_Ai,j,k,和数组,NP_Bi,j,k,表示的状态总数为,O(n,3,),数量级。,但是，形式上的三位数组并不等于包含的数据为立方阶。事实上，这三维都不是,O(n,),的。,进一步的优化,首先，不属于任何一个数组,LA,i,的白格子等同于黑格，所以把它们涂黑。,观察得到结论：对每一个,i,而言，数组,LA,i,中的格子把所有白色区域分成两份，一部分与,A,的距离小于,i,，另一部分大于,i,。,进一步优化,每一层,LA,i,都是封闭的,有序存储,用归纳法可以证明：,LA,d-i,中的格子所形成的环，可以分成两段：,一段中的,LAd-i,k,使得,NP_Ai,j,k,是,A,必胜，另一段使得,NP_Ai,j,k,是,B,必胜。,进一步优化,只需存储分界点！,状态是环型的，所以有两个分界点，用,lefti,j,righti,j,表示这两个分界点,时间复杂度：,O(n,2,)!,总结,NP,状态定理和基于它的动态规划是解决游戏有问题的通式方法，它们构建了解决游戏论问题的基本框架。,但对于游戏的分析，以及动态规划的优化手段是因题而异的。尤其是单调性的分析，和对称、贪心等非动态规划的分析相当灵活。,反例,反例,反例,A,中间点,M,B,图,5-3,反例,反例,进水点,出水点,1,出水点,2,出水点,3,出水点,4,图,5-5,