张春成

V2

2022/02/27阅读:40主题:默认主题

蒙特卡洛方法

蒙特卡洛方法

蒙特卡洛(Monte Carlo)方法是一种无奈, 却高效的遍历方法。 本文是该方法的一个样例。


一个简单的游戏

这是一个简单的“翻数字”的游戏, 就是说有一个棋盘, 每个格子上写着0或者1两个数字

Monte Carlo 1
Monte Carlo 1

如果你在某个格子上点击一下, 这个格子本身及其上、下、左、右的4个格子会变成相反的数字

Monte Carlo 2
Monte Carlo 2

游戏的规则很简单, 我们随机生成一个棋盘, 上面每个格子随机写着01的数字, 玩家每次点击一个格子, 直到所有格子中的数字全都变为0, 即游戏结束。

那么问题来了, 如果这个游戏交给你来做, 你是否有办法生成一个棋盘, 确保这个游戏一定有解?

如何可行空间

这其实是一个数学问题,

棋盘设置的01的初始分布为 , 经过操作 之后,可以将棋盘变为全零的形式,即

假设 ,即意味着 有解。

要证明 很简单, 只要找到一个可行的 即可。 但要证否 则是一个相当艰巨的任务, 要么用反证法

要么穷举所有可能的 ,证明均不可行

但很遗憾,数学方法不太容易解决我们的游戏问题。 因为它代表一个极其非规范的计算

异或

即,我们在翻转01的过程中,用到了离散数学中的异或操作

因此,我们要翻转一个格子就很简单, 将它的值与1进行异或就可以了。

但这导致了在棋盘的角度,每次操作等价于

其中, 代表玩家点击的位置附近为1的异或掩码。 (不要问我掩码[1]是什么)。

由于它是位操作,与加法类似,却没有加法的进位, 因此,数学上有理数的理论对它来讲几乎没有效果, 所以给定一个任意的“局势”, 我们无法快速判断它是否一定“可解”。

不过,纯数学的方法虽然没有出路, 但计算机本身可以解决由它的二进制计算所产生的问题, 一个可行的方法就是“蒙特卡洛”模拟。

蒙特卡洛模拟

简单来说, 蒙特卡洛模拟就是通过大量随机迭代的方式, 对全部的可行空间进行遍历。

当迭代的数量足够大时, 那么,如果一个“局势”没有被遍历到, 就说明它没有可行解。

能够这样说,背后的原理还是异或运算服从分配率,

而如果某个“局势”是由一系列操作得到的, 那么再进行同样的操作,就能够把它变回去。

我设置了一个 5 X 5 的棋盘, 全部“局势”的数量为

大约有 3 千万个。

我们关心的是这些局势是否全部都有解, 进行蒙特卡洛模拟的结果如下图所示

Monte Carlo 3
Monte Carlo 3

可以看到,随着模拟的进行,找到的可行解数量逐渐增多; 最终找到 2 百万个解时,数量不再明显提升, 这意味着这个游戏中,只有少量的(约 6%)局势是可解的。

参考资料

[1]

掩码: https://bbs.csdn.net/topics/390146243

分类:

后端

标签:

后端

作者介绍

张春成
V2