从“k倍动态减法游戏”出发探究一类组合游戏问题.ppt

从从“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=2A第一回合减去2A第二回合减去1B第一回合减去4A获胜通式解法•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(n3)优化化1状态单调性状态单调性状态状态NP(m,n)是关于是关于关于关于n单调不减的单调不减的记f(m)=min{n|NP(m,n)=1} 优化1NP(m,n)=0当且仅当对于任意r=1,2,3…n有m-r>0且NP(m-r,kr)=1 若n0=f(m)，则NP(m-n0,kn0)=0且NP(m-n0+1,k(n0-1))=1 若n0=f(m)，则f(m-n0)>kn0且f(m-(n0-1))<=k(n0-1) 动态转移方程：f(m)=min{n|f(m-n)>kn} 时间复杂度：O(S2)优化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(n4)个，尽管每个状态的状态转个，尽管每个状态的状态转移代价为移代价为O(1)，但总时间复杂度为，但总时间复杂度为O(n4)，太高了 •而且状态数为而且状态数为O(n4)也意味着动态规划已经没有优化的余也意味着动态规划已经没有优化的余地，算法的设计必须跳出动态规划的框架地，算法的设计必须跳出动态规划的框架贪心思路“先先”  贪心的信号贪心的信号  两两人都应沿着两起始点间的最短路径走人都应沿着两起始点间的最短路径走注意到，两个人需要走的路程是相等的注意到，两个人需要走的路程是相等的所以如果没有所以如果没有“跳过对手跳过对手”的规则，先行者将必胜！的规则，先行者将必胜！结论：结论：如果先行方如果先行方A A能避免能避免B B“跳过跳过A A”，则，则A A获胜；获胜；如果后手方如果后手方B B能确保在最短路径上能确保在最短路径上“跳过跳过A A”，则，则B B获获胜。

胜BOI官方解答•记记d为为AB之间最短路的距离之间最短路的距离•若若d为奇数，为奇数，A必胜！所以只要考虑必胜！所以只要考虑d时偶数的情况时偶数的情况•用数组用数组LAi存贮，在存贮，在AB最短路径上，且与距离最短路径上，且与距离A为为i的格子•记记NP_A[i,j,k]表示，轮到表示，轮到A操作时，操作时，A在在LAi中的第中的第j个格子个格子上，上，B在在LAd-i中的第中的第k个格子上的状态个格子上的状态•NP_B[i,j,k]表示，轮到表示，轮到B操作时，操作时，A在在LAi+1中的第中的第j个格子个格子上，上，B在在LAd-i中的第中的第k个格子上的状态个格子上的状态BOI官方解答的错误•BOI的官方解答中认为，数组的官方解答中认为，数组NP_A[i,j,k]和数组和数组NP_B[i,j,k]表示的状态总数为表示的状态总数为O(n3)数量级•但是，形式上的三位数组并不等于包含的数据为但是，形式上的三位数组并不等于包含的数据为立方阶事实上，这三维都不是立方阶事实上，这三维都不是O(n)的进一步的优化•首先，不属于任何一个数组首先，不属于任何一个数组LAi的白格子等同于黑的白格子等同于黑格，所以把它们涂黑。

格，所以把它们涂黑 •观察得到结论：对每一个观察得到结论：对每一个i而言，数组而言，数组LAi中的格中的格子把所有白色区域分成两份，一部分与子把所有白色区域分成两份，一部分与A的距离的距离小于小于i，另一部分大于，另一部分大于i进一步优化每一层每一层LAi都是封闭的都是封闭的有序存储有序存储用归纳法可以证明：用归纳法可以证明：LAd-i中的格子所形成的环，可以分成两段：中的格子所形成的环，可以分成两段：一段中的一段中的LA[d-i,k]使得使得NP_A[i,j,k]是是A必胜，另一必胜，另一段使得段使得NP_A[i,j,k]是是B必胜 进一步优化•只需存储分界点！只需存储分界点！•状态是环型的，所以有两个分界点，用状态是环型的，所以有两个分界点，用left[i,j],right[i,j]表表示这两个分界点示这两个分界点 •时间复杂度：时间复杂度：O(n2)!总结•NP状态定理和基于它的动态规划是解决游戏有问状态定理和基于它的动态规划是解决游戏有问题的通式方法，它们构建了解决游戏论问题的基题的通式方法，它们构建了解决游戏论问题的基本框架•但对于游戏的分析，以及动态规划的优化手段是但对于游戏的分析，以及动态规划的优化手段是因题而异的。

尤其是单调性的分析，和对称、贪因题而异的尤其是单调性的分析，和对称、贪心等非动态规划的分析相当灵活心等非动态规划的分析相当灵活反例反例反例A……………………中间点M……………………B图5-3反例反例……进水点出水点1出水点2出水点3出水点4图5-5。