SG函数和SG定理(Sprague_Grundy)

时间 : 2019-05-09
点击次数 : 108

      一、必胜点和必败点的概念

      P点:必败点,换而言之,就是谁处于此位置,则在双方操作正确的情况下必败。

      N点:必胜点,处于此情况下,双方操作均正确的情况下必胜。

      必胜点和必败点的性质:

      1、所有终结点是 必败点 P 。(我们以此为基本前提进行推理,换句话说,我们以此为假设)

      2、从任何必胜点N 操作,至少有一种方式可以进入必败点 P。

      3、无论如何操作,必败点P 都只能进入 必胜点 N。

      我们研究必胜点和必败点的目的时间为题进行简化,有助于我们的分析。通常我们分析必胜点和必败点都是以终结点进行逆序分析。我们以hdu 1847 Good Luck in CET-4 Everybody!为例:

      当 n = 0 时,显然为必败点,因为此时你已经无法进行操作了

      当 n = 1 时,因为你一次就可以拿完所有牌,故此时为必胜点

      当 n = 2 时,也是一次就可以拿完,故此时为必胜点

      当 n = 3 时,要么就是剩一张要么剩两张,无论怎么取对方都将面对必胜点,故这一点为必败点。

      以此类推,最后你就可以得到;

      n    :   0    1    2    3    4   5    6 ...

      position:  P    N   N    P   N   N   P ...

      你发现了什么没有,对,他们就是成有规律,使用了 P/N来分析,有没有觉得问题变简单了。

      二、Sprague-Grundy定理(SG定理)

      游戏和的SG函数等于各个游戏SG函数的Nim和。这样就可以将每一个子游戏分而治之,从而简化了问题。而Bouton定理就是Sprague-Grundy定理在Nim游戏中的直接应用,因为单堆的Nim游戏 SG函数满足 SG(x) = x。

      三、Sprague-Grundy函数(SG函数)

      首先定义mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

      对于任意状态 x , 定义 SG(x) = mex(S),其中 S 是 x 后继状态的SG函数值的集合。如 x 有三个后继状态分别为 SG(a),SG(b),SG(c),那么SG(x) = mex{SG(a),SG(b),SG(c)}。 这样 集合S 的终态必然是空集,所以SG函数的终态为 SG(x) = 0,当且仅当 x 为必败点P时。

上一篇:java后端为什么接受不到前端发送的数据

上一篇:Dell R730服务器 Raid5配置

烟台网云网络科技有限公司 鲁ICP备14027327号-3

回到顶部