2018-06-20

什么是MCMC

以管窥豹。

通俗一点地说，蒙特卡罗算法是一类比较笨的,依靠不停的随机模拟以不停逼近更精确或者在约束条件下更优化的解的算法.

随机算法，在采样不全时，通常不能保证找到最优解，只能说是尽量找。那么根据怎么个“尽量”法儿，我们我们把随机算法分成两类：

蒙特卡罗算法：采样越多，越近似最优解；
拉斯维加斯算法：采样越多，越有机会找到最优解；

举个例子，假如筐里有100个苹果，让我每次闭眼拿1个，挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个……我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。这个挑苹果的算法，就属于蒙特卡罗算法——尽量找好的，但不保证是最好的。

而拉斯维加斯算法，则是另一种情况。假如有一把锁，给我100把钥匙，只有1把是对的。于是我每次随机拿1把钥匙去试，打不开就再换1把。我试的次数越多，打开（最优解）的机会就越大，但在打开之前，那些错的钥匙都是没有用的。这个试钥匙的算法，就是拉斯维加斯的——尽量找最好的，但不保证能找到。

MCMC最优要拿完。
拉斯维加斯则不用拿完

这两个词本身是两座著名赌城，因为赌博中体现了许多随机算法，所以借过来命名。

如果问题要求在有限采样内，必须给出一个解，但不要求是最优解，那就要用蒙特卡罗算法。
反之，如果问题要求必须给出最优解，但对采样没有限制，那就要用拉斯维加斯算法。

例子

下棋

对于机器围棋程序而言，因为每一步棋的运算时间、堆栈空间都是有限的，而且不要求最优解，所以ZEN涉及的随机算法，肯定是蒙特卡罗式的。

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

求无理数 - 投针求pi

针投的越多结果越准，但是找不好最优解，只能找到近似。

求无理数 - 求解积分

求解交通状况堵塞模型

规模零件集成后的不合格率

https://www.zhihu.com/question/20254139/answer/33572009

蒙特卡洛树搜索

蒙特卡洛树搜索（英语：Monte Carlo tree search；简称：MCTS）是一种用于某些决策过程的启发式搜索算法，最引人注目的是在游戏中的使用。一个主要例子是电脑围棋程序[1]，它也用于其他棋盘游戏、即时电子游戏以及不确定性游戏。

不穷举所有组合，找到最优或次优位置

围棋棋面总共有$19 * 19 = 361$
个落子位置。假如电脑有足够的计算能力，理论上来说，我们可以穷举黑白双方所有可能的落子位置，找到最优落子策略。

但是，如果穷举黑白双方所有可能的落子位置，各种组合的总数，大约是 $250^{150}$数量级。这个数太大了，以至于用当今世界最强大云计算系统，算几十年也算不完。

需要说明的是，蒙特卡罗树搜索并不是只有一种算法，而是一类算法。其中最流行的算法之一就是UCT（upper confidence bounds applied to trees）。

下棋其实就是一个马尔科夫决策过程（MDP），根据当前棋面状态，确定下一步动作。

在每个模拟游戏中，AlphaGo都有两个大脑指引它进行搜索：价值网络（value network）和政策网络（policy network）。“政策网络”观察棋盘布局企图找到较好的下法，“价值网络”则预测这样下的话对方棋手赢棋的可能。结合这两个建议，AlphaGo最终决定怎样落子才是胜算最大的。

维特比

为什么不用维特比算法，能把指数级搜索缩小到N^2级。而且是最优化解。