蒙特卡洛和拉斯维加斯

缘起

首先，蒙特卡洛和拉斯维加斯是两座赌城的名字. 所以顾名思义，蒙特卡洛算法和拉斯维加斯算法都是随机化算法.

分析

蒙特卡洛算法

筐里有100个苹果, 我每次从筐中拿一个苹果A, 然后下一次再随机从筐中拿一个苹果B, 如果B比A大的话, 则舍弃A而保留B. 如此这般，很明显，如果我们拿了100次的话, 则最后在手中的就是最大的那个苹果.

如果不允许我们拿100次呢? 但是我们的策略是每次保留较好的. 则我们也有理由相信——经过N次（N<100）之后，留在我们手上的苹果也是接近最大的.

如果将每次拿苹果视作是采样的话, 则

蒙特卡洛算法就是每次采样尽量找好的，但不保证是最好的, 而且采样越多，越近似最优解

拉斯维加斯算法

假如有一把锁，给我100把钥匙，只有1把是对的。于是我每次随机拿1把钥匙去试，打不开就再换1把。我试的次数越多，打开（最优解）的机会就越大，但在打开之前，那些错的钥匙都是没有用的。这个试钥匙的算法，就是拉斯维加斯算法.

拉斯维加斯算法就是每次采样尽量找最好的，但不保证能找到, 采样越多，越有机会找到最优解

####

这两类随机算法之间的选择，往往受到问题的局限。如果问题要求在有限采样内，必须给出一个解，但不要求是最优解，那就要用蒙特卡罗算法。反之，如果问题要求必须给出最优解，但对采样没有限制，那就要用拉斯维加斯算法。

和机器下棋的关系

最近比较热的AI下棋. 因为每一步棋的运算时间、堆栈空间都是有限的，而且不要求最优解，所以阿尔法狗涉及的随机算法，肯定是蒙特卡罗式的。

机器下棋的算法本质都是搜索树，围棋难在它的树宽可以达到好几百（国际象棋只有几十）。在有限时间内要遍历这么宽的树，就只能牺牲深度（俗称“往后看几步”），但围棋又是依赖远见的游戏，甚至不仅是看“几步”的问题。所以，要想保证搜索深度，就只能放弃遍历，改为随机采样——这就是为什么在没有MCTS（蒙特卡罗搜索树）类的方法之前，机器围棋的水平几乎是笑话。

简单的运用

拉斯维加斯算法的一个简单应用是结合dfs求解N较大时的N皇后问题. 即前几行选择用随机法放置皇后，剩下的选择用回溯法解决。

蒙特卡洛算法的典型运用比如蒲丰投针计算pi, 以及计算定积分. 都是用蒙特卡洛采样来解决的.