博弈论

在介绍SG函数和SG定理之前我们先介绍介绍必胜点与必败点吧.

必胜点和必败点的概念:

​ 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来分析,有没有觉得问题变简单了。

现在给你一个稍微复杂一点点的: hdu 2147 kiki's game

​ 现在我们就来介绍今天的主角吧。组合游戏的和通常是很复杂的,但是有一种新工具,可以使组合问题变得简单————SG函数和SG定理。 Sprague-Grundy定理(SG定理): 游戏和的SG函数等于各个游戏SG函数的Nim和。

总结:

在用P,N来推必胜和必败的时候,一定要逆推,当前状态的下一个状态全部为N的时候,当前状态为P,当前状态的下一个状态只要出现一个P,那当前状态就是N

results matching ""

    No results matching ""