不属于随机算法的是

A. 概率搜索算法有哪些，除了遗传算法和蚁群

遗传算法(Genetic Algorithm，GA)是由Holland J．H．于20世纪70年代提出的一种优化方法，其最优解的搜索过程模拟达尔文的进化论和“适者生存”的思想。

蚁群算法(Ant Colony Optimization, ACO)，是一种用来在图中寻找优化路径的机率型算法。

两种算法从概念上都属于随机优化算法，遗传算法是进化算法，主要通过选择、变异和交叉算子，其中每个基因是由二进制串组成；蚁群算法是基于图论的算法，通过信息素选择交换信息。

B. 随机算法的基本概念

随机算法是算法本身包含了随机数生成器的算法。根据《算法导论（中文第二版）》描述，在进行算法分析的时，有时可以在获得了一定输入分布信息之后对输入的分布进行一定的假定，在此基础上进行平均情况分析得到算法的时间复杂度。然而有时候无法获得输入分布的信息，这时可以在算法本身增加一定的随机性，继而实现对算法进行平均情况分析。通过设计随机算法有效地避免较多的较坏情况输入的出现，从而提高算法的平均情况下的性能。

C. 蒙特卡洛算法和拉斯维加斯算法

一、定义：

特卡罗是一类随机方法的统称。这类方法的特点是，可以在随机采样上计算得到近似结果，随着采样的增多，得到的结果是正确结果的概率逐渐加大，但在（放弃随机采样，而采用类似全采样这样的确定性方法）获得真正的结果之前，无法知道目前得到的结果是不是真正的结果。​

拉斯维加斯方法是另一类随机方法的统称。这类方法的特点是，随着采样次数的增多，得到的正确结果的概率逐渐加大，如果随机采样过程中已经找到了正确结果，该方法可以判别并报告，但在但在放弃随机采样，而采用渣竖类似全采样这样的确定性方法之前，不保证能找到任何结果（包括近似结果）​

二、场景举例​

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

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

三、结论​

•蒙特卡罗算法   

：采样越多，越近似最优解；

•拉斯维加斯算法：采样越多，越有机会找到最优解；​

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

D. 遗传算法、粒子群、模拟退火相比于普通的蒙特卡洛算法有什么优势他们相互的优缺点都是什么

他们有类似之处，但差别也不小。
蒙特卡洛算法是数值计算方法，原理是利用随机数来解决计算问题。与它对应的是确定性算法。也就是说该种算法属于随机算法，得到的解是近似解。
而遗传算法、粒子群、模拟退火虽然也是随机近似算法，但这三种都是仿生智能算法，且比蒙特卡洛算法要复杂，应用的领域也不太相同。
显然，蒙特卡洛算法很轻巧，求解问题更快速。

E. 随机性数学方法有哪些

随机数学是研究随机现象统计规律性的一个数学分支，涉及四个主要部分：概率论、随机过程、数理统计、随机运筹。概率论是后三者的基础。则睁厅

4、舍伍德算法 Sherwood

利用随机算法改造已有算法，使得算法的性能尽量与输入数据无关，即平滑算法的性能。它总能求得问题的一个解，且求得的解总是正确的。

F. 随机算法

相关总结参见 http://www.jianshu.com/p/60ea83ea17cc

一个随机算法的最坏运行时间几乎总是和非随机化算法的最坏情形运行时间相同。重要的区别在于，好的随机化算法没有不好的输入，而只有坏的随机数（相对于特定的输入）。
比如说：对于快速排序，方法A用第一个元素作为枢纽元，方法B使用随机选出的元素作为枢纽元。

通过随机化算法，特定的输入不再重要。重要的是随机数，我们可以山败前得到一个期望的运行时间，此时我们是对所有可能的随机数取平均而不是对所有可能的输入求平均。

随机数有许多已知的统计性质；逗清伪随机数满足这些性质的大枯蔽部分。
真正需要的是随机数的序列。这些数应该独立地出现。

线性同余数发生器
产生随机数的最简单的方法是线性同余数发生器，由Lehmer于1951年提出：

例如：M = 11，x0 = 1
A = 7： 7， 5， 2， 3， 10， 4， 6， 9， 8， 1， 7 ，5 ，2... （周期为10 = M-1）
A = 5： 5， 3， 4， 9， 1， 5， 3， 4...（周期为5 < M -1）

一个有问题的随机数发生器（返回(0,1)开区间值）：乘法溢出

工作在32位机器上的随机数发生器

证明：为什么δ(xi)或者是0，或者是1
为什么仅当余项的值小于0时，δ(xi)=1
说明：因为这里是对M取余，所以是M的倍数则自然消掉；并且δ(xi)两项都是取整函数，因此肯定为整数，另外xi+1总是介于1~M-1之间，因此当余项小于0，则取1

随机化的第一个用途是以O(lgn)期望时间支持查找和插入的数据结构。
每个2^i 结点就有一个指针指向下一个2^i结点，总的指针个数仅仅是加倍，但现在在一次查找中最多考察floor(lgn)个结点。因此总的时间消耗为O(lgn)。
本质上是二分查找：

放松上面数据结构的结构条件，就构成了跳跃表：

如果我们想查找19是否存在？如何查找呢？我们从头结点开始，首先和9进行判断，此时大于9，然后和21进行判断，小于21，此时这个值肯定在9结点和21结点之间，此时，我们和17进行判断，大于17，然后和21进行判断，小于21，此时肯定在17结点和21结点之间，此时和19进行判断，找到了。

1）实现

2）空间大小耗费

3）查找
1-2-3跳跃表的实现特点：
在同一层级的链表（不超过3个结点）中找到首个大于item的结点，然后向下移一层。

4）插入
必须保证当一个高度为h的新结点加入进来时不会产生具有四个高度为h的结点的间隙。
插入采用2-3-4树的自顶向下的方法（保证当前结点不是4-结点）：（参考 http://www.jianshu.com/p/8258ed821859 ）
设在第L层，并要降到下一层。如果下一层的间隙容量是3，则提高该间隙的中间项使其高度为L，从而形成两个容量为1的间隙。由于这使得朝下删除的道路上消除了容量为3的间隙，因此插入式安全的。

5）删除
删除采用2-3-4树的自顶向下的方法（保证当前结点不是2-结点）：（参考 http://www.jianshu.com/p/8258ed821859 ）

确定一个大数是否是素数的问题。

结点包括：

具有最低优先级的结点必然是根。树是根据优先级的N!种可能的排列而不是根据项的N!中排列形成的。

1）插入

插入之后，通过左旋和右旋恢复堆序性质：

2）删除
这个删除方法也可以采用红黑树的删除方法，将删除归结为叶子节点的删除。（使用后继，这样可以节省很多旋转）