9 随机化
随机化算法
随机算法的概述
将算法必须对所有可能的输入都正确地求解问题的条件放宽，只要求它的可能不正确性解能够相对安全地忽略掉，比如说它的出现可能性非常低;而且也不要求对于特定的输入，算法的每一次运行的输出都必须相同。
随机算法可以做如下定义：它是在接收输入的同时，为了随机选择的目的，还接收一串随机比特流并且在运行过程中使用该比特流的算法。
一个随机算法在不同的运行中对于相同的输入可以有不同的结果。由此得出对于相同的输入两次不同的随机算法的执行时间可能不同。
随机算法的优点
- 首先，较之那些我们所知的解决同一问题最好的确定性算法，随机算法所需的运行时间或空间通常常小一些；
- 其次，观察迄今为止已经发明的各种随机算法，我们发现这些算法总是易于理解和实现。
1 伪随机数
伪随机数的产生
$$
\begin{cases}
a_0=d\
a_n=(ba_{n-1}+c) mod m
\end{cases}
$$
其中$a\geq 0,b\geq0,d\geq m,d$是随机序列种子。
2 数值随机化算法
3 舍伍德算法
确定性算法随机化。
4 蒙特卡洛算法
- 蒙特·卡罗方法（Monte Carlo method），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。与它对应的是确定性算法。蒙特·卡罗方法在金融工程学，宏观经济学，计算物理学（如粒子输运计算、量子热力学计算、空气动力学计算）等领域应用广泛。
随机投点法计算$\pi$
随机投点法计算定积分
5 拉斯维加斯算法
- 拉斯维加斯算法的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。因此通常用一个bool型函数表示拉斯维加斯算法。
拉斯维加斯算法+回溯法 解决N皇后问题
考虑用拉斯维加斯算法解决N皇后问题：
对于n后问题的任何一个解而言，每一个皇后在棋盘上的位置无任何规律，不具有系统性，而更象是随机放置的。由此容易想到下面的拉斯维加斯算法。
在棋盘上相继的各行中随机地放置皇后，并注意使新放置的皇后与已放置的皇后互不攻击，直至n个皇后已相容地放置好，或已没有下一个皇后的可放置位置时为止。注意这里解决的是找到其中一个方法，求不是求出N皇后的全部解。
这里提前说明一下，否则不好理解。
接下来的这个用Las Vegas算法解决N皇后问题，我们采用的是随机放置位置策略和回溯法相结合，具体就是比如八皇后中，前几行选择用随机法放置皇后，剩下的选择用回溯法解决。
这个程序不是很好理解，有的地方我特别说明了是理解程序的关键，大家看时一定要认真了，另外，王晓东的书上先是用单纯的随机法解决，大家可以先去理解书上这个例子。然后再来分析我这个程序。不过那本书上关于这一块错误比较多，大家看时要注意哪些地方他写错了。
6 蒙特卡洛方法与拉斯维加斯算法对比
定义
蒙特卡罗是一类随机方法的统称。这类方法的特点是，可以在随机采样上计算得到近似结果，随着采样的增多，得到的结果是正确结果的概率逐渐加大，但在（放弃随机采样，而采用类似全采样这样的确定性方法）获得真正的结果之前，无法知道目前得到的结果是不是真正的结果。
拉斯维加斯方法是另一类随机方法的统称。这类方法的特点是，随着采样次数的增多，得到的正确结果的概率逐渐加大，如果随机采样过程中已经找到了正确结果，该方法可以判别并报告，但在放弃随机采样，而采用类似全采样这样的确定性方法之前，不保证能找到任何结果（包括近似结果）
场景
假如筐里有100个苹果，让我每次闭眼拿1个，挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个……我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。这个挑苹果的算法，就属于蒙特卡罗算法——尽量找好的，但不保证是最好的。
而拉斯维加斯算法，则是另一种情况。假如有一把锁，给我100把钥匙，只有1把是对的。于是我每次随机拿1把钥匙去试，打不开就再换1把。我试的次数越多，打开（最优解）的机会就越大，但在打开之前，那些错的钥匙都是没有用的。这个试钥匙的算法，就是拉斯维加斯的——尽量找最好的，但不保证能找到。
结论
蒙特卡罗算法：采样越多，越近似最优解；
拉斯维加斯算法：采样越多，越有机会找到最优解；
这两类随机算法之间的选择，往往受到问题的局限。如果问题要求在有限采样内，必须给出一个解，但不要求是最优解，那就要用蒙特卡罗算法。反之，如果问题要求必须给出最优解，但对采样没有限制，那就要用拉斯维加斯算法。
