Skip to content

L03 减治法

约 1408 个字 1 行代码 3 张图片 预计阅读时间 5 分钟

本文参考链接

  1. 插值查找算法原理分析——及python与C++实现 - 机器学习入坑者的文章 - 知乎
    https://zhuanlan.zhihu.com/p/106059055

  2. https://oi-wiki.org/math/game-theory/impartial-game/

五、减可变规模算法

5.2 插值查找

算法流程

在数据是有序的情况下，我们有二分查找。其流程可简单表示为：

\[mid=\frac{(right+left)}{2}\]

可简单变形为：

\[mid=left+\frac{1}{2}(right-left)\]

上面的½代表区间长度每次缩减一半，也就是控制区间缩减幅度的因子。二分查找并没有考虑数据中数值的情况，仅仅使用了数值是有序的这一信息。

现在，来看下述的数值有序且分布均匀数据：

data = [1, 2, 3, 5, 6, 7, 10, 13, 14,, 17, 19 22, 23, 25, 27]

如果搜索的目标是2，那么区间长度每次都缩减为一半合理吗？显然是不合理的，因为2这个值比较小，明显比较偏向于数据的起始位置；如果搜索的目标是25，区间减半的方式同样不合理。

所以，可以改变二分查找的区间缩减策略，根据搜索的值来确定区间缩减幅度，使其不再是固定的½，这种想法就是“插值查找”，其中间位置计算方式如下：

\[mid=left+alpha \times (right-left)\]

如果alpha用于衡量搜索目标值距离左边界的远近，就可以使用下述公式进行表达，其中tar表示目标值，D表述有序数值：

\(\(mid=left+\frac{(target-D[left])}{(D[right]-D[left])} \times (right-left)\)\)
此时，如果目标值 target 和左边界值D[left]差的多，则中间位置 mid 更靠右；如果目标值target和左边界值差的少，则中间位置 mid 更靠左。也就是说，插值查找算法的中间位置mid不是真的在中间了，而是根据目标值和边界值的关系动态的确定。

插值查找算法和二分查找算法的区别主要就在于中间位置mid的确定，它们在终止条件和判断条件上都是相同，在此不做重复。

时间复杂度

  • Average Case: \(O(\log\log n)\)
  • Worst Case: \(O(n)\)

对于大规模/Expensive Exchange，插值搜索效果更好。

代码

5.4 Nim 游戏

Note

共有 \(n\) 堆石子，第 \(i\) 堆有 \(a_i\) 枚石子。两名玩家轮流取走任意一堆中的任意多枚石子，但不能不取。取走最后一枚石子的玩家获胜。

博弈图和状态

Nim 游戏中，局面可能的变化可以用博弈图来描述。

将每一个可能的状态都看作是图中的一个结点，并将状态向它的后继状态（即通过一次操作可以达到的状态）连边，就得到一个有向无环图，这就是博弈图。图是无环的，因为 Nim 游戏中，每次操作，石子的总数量都是严格减少的。

例如，对于初始局面有 3 堆石子，且每堆石子的数量分别为 1,1,2 的 Nim 游戏，可以绘制如下的博弈图：

|450

马上就会提到，图中的红色结点表示必胜状态，黑色结点表示必败状态。

由于 Nim 游戏是公平组合游戏，每个玩家是否有必胜策略，只取决当前游戏所处的状态，而与玩家的身份无关。因此，所有状态可以分为（先手）必胜状态 \(\mathcal N\) 和（先手）必败状态 \(\mathcal P\)。

Nim 和

通过绘制博弈图，可以在 \(\Omega(\prod_{i=1}^na_i)\) 的时间内求出某一局面是否是先手必胜。但是，这样做的复杂度过高，无法实际应用。实际上，可以发现 Nim 游戏的状态是否先手必胜，只与当前局面的石子数目的 Nim 和有关。

Abstract

自然数 \(a_1,a_2,\cdots,a_n\) 的 Nim 和（Nim sum）定义为 \(a_1\oplus a_2\oplus\cdots\oplus a_n\)。

所谓 Nim 和，就是异或运算。

Note

Nim 游戏中，状态 \((a_1,a_2,\cdots,a_n)\) 是必败状态 \(\mathcal P\)，当且仅当 Nim 和

\[ a_1\oplus a_2\oplus\cdots\oplus a_n = 0. \]
证明

对所有可能的状态应用归纳法：

  1. 如果 \(a_i=0\) 对所有 \(i=1,\cdots,n\) 都成立，该状态没有后继状态，且 Nim 和等于 \(0\)，命题成立。
  2. 如果 \(k = a_1\oplus a_2\oplus\cdots\oplus a_n\neq 0\)，那么，需要证明该状态是必胜状态。

也就是说，需要构造一个合法移动，使得后继状态为必败状态；由归纳假设，只需要证明后继状态满足 \(a'_1\oplus a'_2\oplus\cdots\oplus a'_n=0\)。

利用 Nim 和（即异或）的性质，这等价于说，存在一堆石子，将 \(a_i\) 拿走若干颗石子，可以得到 \(a_i\oplus k\)，亦即 \(a_i>a_i\oplus k\)。

实际上，设 \(k\) 的二进制表示中，最高位的 \(1\) 是第 \(d\) 位。那么，一定存在某个 \(a_i\)，使得它的二进制第 \(d\) 位是 \(1\)。对于相应的石子堆，就一定有 \(a_i>a_i\oplus k\)，因为 \(a_i\oplus k\) 中第 \(d\) 位为 \(0\)，更高位和 \(a_i\) 一样。

  1. 如果 \(a_1\oplus a_2\oplus\cdots\oplus a_n= 0\)，那么，需要证明该状态是必败状态。由归纳假设可知，只要证明它的所有后继状态的 Nim 和都不是 \(0\)。这是必然的，任何合法移动将 \(a_i\) 变为 \(a'_i\neq a_i\)，就必然会使得 Nim 和变为 \(a'_i\oplus a_i\neq 0\)。
    由此，可以在 \(O(n)\) 时间内判断 Nim 游戏的一个状态是否为先手必胜状态。

Comments