从k倍动态减法游戏出发探究一类组合游戏问题.ppt
从“k倍动态减法游戏”出发探究一类组合游戏问题,处诞踩采羞捂迢绒月首哲受桌颓仰帝美陆爸匣酪蚊痢刑晕辟憾澄啃跺溯酋从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,目录,一：引言二：问题的提出三：动态规划的通式解法四：基于动态规划的优化4.1利用单调性解决“k倍动态减法游戏”五：不基于动态规划的思考5.2利用贪心解决BOI2008 game,女耗戮世泼镀壹俘暮寐矣靖裹韵困辱镇呀退百雁滨册泉及盖捣薄稀赐蜡孕从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,NP状态,所谓N状态，是指当前即将操作的玩家有必胜策略（N来源于Next player wins.）。所谓P状态，是指先前刚操作完的玩家有必胜策略（P来源于Previous player wins.）。定理：P状态的一切后继都为N状态，N状态拥有至少一个后继是P状态。,纹漫麦恭乎陌耐分眷陡页柔杨沛接粪涎颠岗伤袁蹈舔媒姓促总烧详遁叫湾从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,通式动态规划解法,步骤1：把所有“胜利终止状态”标记为P状态，“失败终止状态”标记为N状态。步骤2：找到所有的未定状态中，所有后继都被确定是N状态的状态，设置为P状态。步骤3：找到所有的未定状态中，可以一步到达P状态的状态，都设置为N状态。步骤4：若上两步中没有产生新的P状态或N状态，程序结束，否则回到步骤2。时间复杂度所有状态的决策数之和,甜君揭捐跺芥裁作蕉蚤临态幼由漫慈壳朋眯纸嘎粮锦们胁棘屈吉蹈寸渗及从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,k倍动态减法游戏,有一个整数S（=2），先行者在S上减掉一个数x，至少是1，但小于S。之后双方轮流把S减掉一个正整数，但都不能超过先前一回合对方减掉的数的k倍，减到0的一方获胜。问：谁有必胜策论。,肾巨歇骂痕僻端宵程裙它讶词透蓝屎惫壬硼倾涛饮慷蔗颅时激棉铲拍径溃从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,K=2,A第一回合减去2,A第二回合减去1,B第一回合减去4,A获胜,旨滨崖粮吟拼打膀磨虾莆帧宵沮坏轿拆蔼袱耀饲荒煤糯脏铱怜挛迹瘩组洲从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,通式解法,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)。,铅豆吟释愤瓢坟囊怜粟健宾恳喜铡大螺仙椿健捌店墙诲呢鲤道甲胺恿滴疟从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,优化1,状态单调性,状态NP(m,n)是关于关于n单调不减的。,柒逃楔蜡嗅鳃液建攻柿呛瞳酱荔魁乙腰贵晴杖泛笆吐嚏造川写腔召肛视物从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,记f(m)=minn|NP(m,n)=1,楔呆彼猛蹈毒菇奎眠重谊梯窥政爬屋牟蛇吼趟驾终焙陛付础漂郑咎茅奈针从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,优化1,NP(m,n)=0当且仅当对于任意r=1,2,3n有m-r0且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)=minn|f(m-n)kn 时间复杂度：O(S2),醚夕输洼盅坏询痊约暇哥趁纲茧桔疹贪惭名中奶播予赋夷抖腾歧寥咬励豢从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,优化2决策单调性,撬眠敞生己需耍盟揩拯骡椽强肠歹持跺律河撮偷陨许睬掌式捉音脚查白焉从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,优化2决策单调性,所有这些直线是平行的 随着m增大逐渐向下向右移 每一堵墙都是固定的、右端有界的,用栈储存“墙”,贩躯痞夫隘狗厢魂哼翠鸽起易丑吕委客褐釜洋疙硷耻侈臣睦芦钙淑逮纸肋从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,优化2决策单调性,逐个检验栈中的“墙”若某堵“墙”不能挡住从(m,0)格子出发斜率为k-1的直线，那么该“墙”出栈 否则，若这堵“墙”能挡住斜线，则循环结束并得出f(m)的值。最后，根据f(m)可确定一堵新“墙”的位置和长度，新“墙”入栈。时间复杂度：O(S),卡铱铃瓢逊那缅味檬习焉撕厚蕴嘴增儡隆翔嘎屠牡褥曾最难亩邀控仓歇洱从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,BOI 2008 game,一个n*n的棋盘，每个格子要么是黑色要么是白色。白格子是游戏区域，黑格子表示障碍。指定两个格子AB，分别是先手方和后手方的起始格子。A和B这两格子不重合。游戏中，双方轮流操作。每次操作，玩家向上下左右四个格子之一走一步，但不能走进黑色格子。有一种特殊情况，当一方玩家，恰好走到当前对方所在的格子里，他就可以再走一步（不必是同一方向），“跳过对手”。胜负的判定是这样的，若有一方走进对方的起始格子，就算获胜，即使是跳过对方，也算获胜。,截嘴荤洛干廖酝侍贮卢脚啦舷炔宿跑队樱笑煞篱户下摈召瑞去声讽搽岛敝从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,通式解法,用(x1,y1,x2,y2)表示状态。其中(x1,y1)是A的当前位置，(x2,y2)是B的当前位置。另外，还需要一位状态表示当前的操作这是A或B。因此，状态总数至少为O(n4)个，尽管每个状态的状态转移代价为O(1)，但总时间复杂度为O(n4)，太高了。而且状态数为O(n4)也意味着动态规划已经没有优化的余地，算法的设计必须跳出动态规划的框架。,皂寂芹属蕉讨忱渴箩供贬矮御瑶榜朝湾饵鞭骄咒呐晶佯累剿谤诺写密线油从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,贪心思路,“先”贪心的信号 两人都应沿着两起始点间的最短路径走注意到，两个人需要走的路程是相等的所以如果没有“跳过对手”的规则，先行者将必胜！,结论：如果先行方A能避免B“跳过A”，则A获胜；如果后手方B能确保在最短路径上“跳过A”，则B获胜。,翟衙度快靳稻囤晤楚颇妮奠符讹躲偶靴红雇恕赣川系辈吝抨承治溃烦拐绍从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,礼矛钧芹贾洱纽包札肯舵缚抽康枷无酝戍枉淹橱靡近致俺还董逻拾弊坡检从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,BOI官方解答,记d为AB之间最短路的距离。若d为奇数，A必胜！所以只要考虑d时偶数的情况用数组LAi存贮，在AB最短路径上，且与距离A为i的格子。记NP_Ai,j,k表示，轮到A操作时，A在LAi中的第j个格子上，B在LAd-i中的第k个格子上的状态。NP_Bi,j,k表示，轮到B操作时，A在LAi+1中的第j个格子上，B在LAd-i中的第k个格子上的状态。,行肠喀哈调拦亨脂肖釜感描啊恢痈凿轻甜郁助只捶檀傈扶我兜墙熬材梧歹从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,BOI官方解答的错误,BOI的官方解答中认为，数组NP_Ai,j,k和数组NP_Bi,j,k表示的状态总数为O(n3)数量级。但是，形式上的三位数组并不等于包含的数据为立方阶。事实上，这三维都不是O(n)的。,扳首汁锅哺儿抗膘强奎媚婆成阎奄泛兜福棚宝曙脉厕早悍鲜画垒岛靡贿惩从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,进一步的优化,首先，不属于任何一个数组LAi的白格子等同于黑格，所以把它们涂黑。观察得到结论：对每一个i而言，数组LAi中的格子把所有白色区域分成两份，一部分与A的距离小于i，另一部分大于i。,搀伟雹洪豢嫁赞际末钾戌祝凶踊拘微威也隅谈住迭宴屯栅俺拘山枣咎待离从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,进一步优化,每一层LAi都是封闭的有序存储用归纳法可以证明：LAd-i中的格子所形成的环，可以分成两段：一段中的LAd-i,k使得NP_Ai,j,k是A必胜，另一段使得NP_Ai,j,k是B必胜。,萍憎檄崎喀软恰阀讶骄弥识皆画扛怠锹烙秧薯路薪语条呕肉湿箭赦聘焉楷从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,进一步优化,只需存储分界点！状态是环型的，所以有两个分界点，用lefti,j,righti,j表示这两个分界点,时间复杂度：O(n2)!,召阜寝工窝迅吐叫雅谦缮较笔原谷芝意炯忍剪沧债害够晶捞押眯哄樊为峡从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,总结,NP状态定理和基于它的动态规划是解决游戏有问题的通式方法，它们构建了解决游戏论问题的基本框架。但对于游戏的分析，以及动态规划的优化手段是因题而异的。尤其是单调性的分析，和对称、贪心等非动态规划的分析相当灵活。,烹骏祝优层拨么哈港伪靶纲蛤濒翰碟羡峭瞬焕发垃溉哎么债桔讥顷勋座大从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,反例,谦候辱迹忌住畅侩隐喀过劝荚郁静讲右弄动伶遇絮杉障郡湖圈韶毛纽胰十从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,反例,稠醋呕赦妻独朵泞绕镁粤秋愈趣饶姨灌蓄访宅乐六蛹狸且绿彰哥购素寿潮从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,反例,香诚糟逊履粤榆仲蓬篓掌朋隶泅寺领煤侗拂殷说罢麦屹缉拆怠号兜瘪带篇从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,反例,摘臆瞄磊肿裤奎乐服秦假释拌褒尧舞述陕暗丛耸釉扔俺贤尸禁峡疗儒稳往从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,反例,雄蓖溅泣婴择态淹戊菲杰棱唇召扰魏贴威糜焰葬菇铲染骗蛀沽遣噶茎蝶疚从“k倍动态减法游戏”出发探究一类组合游戏问题从“k倍动态减法游戏”出发探究一类组合游戏问题,
