算法思想-随机化

大家好，欢迎来到IT知识分享网。

随机化算法(randomized algorithm)

现实中有许多问题的解决过程并无标准数学公式可以遵循，即便可以通过公式计算，但是复杂度较高，因此可以使用随机思想，利用随机化结果去逼近实际问题的记过，概率算法允许在执行过程中随机的选择下一步的计算步骤。可使算法大大降低复杂度，提高算法效率，但有时也可能得不到问题的准确答案，随机化算法包括四类：数值概率算法，蒙特卡洛算法，拉斯维加斯算法，舍伍德算法。

使用数值概率思想求积分问题

设f（x）=1-x^2，计算定积分
分析：要计算定积分的值的几何含义就是f（x）与x轴y轴所围得面积（设为阴影）。又因为x，y轴所围的面积为1（X、Y坐标范围的乘积），所以随机点落入阴影的概率（在上下限所围成的区域内）即为定积分的近似解。这里将一个求面积问题转化为了求概率问题，而概率的计算就是通过规定条件下的随机数计算的。

计算过程

假设向单位正方形中随机投入n个点（xi，yi）i=1,2,3,…n。随机点是否落入阴影区域内，可由yi<=f(xi)=1-x2i来判断。如果有m个点落入阴影，则概率p=m/n

#include"stdio.h" #include"math.h" #include"stdlib.h" #include"time.h" double Darts(int n) { 
    double x,y; time_t t; int i,count=0; srand((unsigned)time(&t)); for(i=0;i<n;i++) { 
    x=rand()%100/100.0; //将x，y控制在（0，1）内 y=rand()%100/100.0; if(y<=1-pow(x,2)) count++; } return (double)count/(double)n; } main() { 
    int n; printf("Please input the accuracy\n"); scanf("%d",&n); printf("The result is about\n"); printf("%f\n",Darts(n)); getche(); } 

使用不同的随机数数量，得到结果如下：

Please input the accuracy 10 The result is about 0. -------------------------------- Please input the accuracy 100 The result is about 0. -------------------------------- Please input the accuracy 1000 The result is about 0. -------------------------------- Please input the accuracy 10000 The result is about 0. -------------------------------- Please input the accuracy  The result is about 0. 

舍伍德随机思想

作为其他算法的性能改善手段，例如快速排序的原理决定其时间复杂度最坏为排序数量的平方，原因是快速排序进行到末尾时，选择key值极有可能为最小或者最大，因为随着排序的进行，序列逐渐有序了，key值还是固定选区的化就会高概率的选到极值。假如使用某一种随机策略去选择key值，那么就会降低key值为极端值的可能，在这里蒙特卡洛思想并不是用作逼近最优解，而是帮助平均其它算法的最坏情况出现的概率。
实例参考：舍伍德优化快速排序

蒙特卡洛随机思想

• 蒙特卡洛与拉斯维加斯算法均是采用随机方法去尝试获得问题答案，但是两者的效果并不一致，蒙特卡洛算法的每一次随机化尝试都离最终结果进一步，即便尝试次数有限，且在有限的次数内未找到最优解，但是当前产生的结果也是离最优解接近的，其实，数值随机算法是带有蒙特卡算思想的；而拉斯维加斯算法，随机尝试的结果只有成功与失败两种情况，因此可能尝试次数要足够大，否则很有可能找不到最优解。
• 举个例子，假如筐里有100个苹果，让我每次闭眼拿1个，挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个……我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。这个挑苹果的算法，就属于蒙特卡罗算法——尽量找好的，但不保证是最好的。而拉斯维加斯算法，则是另一种情况。假如有一把锁，给我100把钥匙，只有1把是对的。于是我每次随机拿1把钥匙去试，打不开就再换1把。我试的次数越多，打开（最优解）的机会就越大，但在打开之前，那些错的钥匙都是没有用的。这个试钥匙的算法，就是拉斯维加斯的——尽量找最好的，但不保证能找到。

两种算法的差异可总结如下：

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

围棋的复杂度过高，可以使用其他的博弈游戏代替分析，下面的图展示了一个简化的取物游戏（有一堆石子，包含5个石子，每次你可以取走1，2或3个石子，最后一人拿完后剩余石子数为0则失败）的完整博弈树。每个节点中的数值是走棋后石堆中剩下的石子数，每个节点旁的字母是对于Max的极小极大值（W=win, L=lose）。注意，这里博弈值（根节点的值）是L —— 即Max始终会输掉（实际上，假如玩游戏的两个人智商都ok，那么这个简化版的取物游戏的赢家，始终是第二个下的那位）。这个游戏可采用极小加大搜索在博弈树中找到获胜的玩法。
博弈树（解空间树）的构造是从上到下进行的：

1. 第一层 Max走第一步，此时石堆中剩余石子5块，Max可以选则取出1、2、3块石头，给予他的选择，会出现第二层的三种情况。
2. 第二层 Minnie走第二步，基于Max的选择，Minnie可以从三种情况选择其一若上一步Max选择取出1块，那么这次Minnie可以选择取出1、2、3块，形成第三层最左册的三种case；若上一步Max选择取出2块，那么这次Minnie可以选择取出1、2、3块，形成第三层中间的三种case；若上一步Max选择取出3块，那么这次Minnie可以选择取出1、2块，形成第三层最右册的三种case。
3. 第三层再次轮到Max选择取出几块石子，此时有些case下石堆剩余的石子已经为0，这些case游戏已经结束，其他case按照规则再次生成第四层的10种case。
4. 第四、五、六层依次按照上述规则生成。

有了博弈树，就需要按照树的路径计算，找出沿各个路径进行游戏的最终胜负结果。极小极大搜索的思想是在本方选择时尽可能做对自己有利的选择，即极大值；在对方选择时，假定对方足够聪明，因此他会做出对他而言的最佳选择，相反对于本方则是最差选择，即极小值。

拉斯维加斯随机思想

拉斯维加斯随机注重的是要找到正确的结果，而不是靠近最优值。比如之前提到的回溯解决4皇后问题，回溯类似于改进型的穷举，但是假如是128皇后，采用回溯有时耗时是不被允许的，如果此时游戏的要求是可以尝试多次，只要其中有一次成功，则按照成功的一次的时间当作游戏耗时。此时则可以尝试拉斯维加斯思想。即128皇后的前几步采用随机选择方式以减少遍历数量，后面再使用回溯。随机放置一部分棋子后并不能保证后续的回溯可以找到正确答案，但是一旦成功耗时就一定小于完全回溯的方式。这一思想我认为可以通过多线程手段解决更加实际的问题，因为一般回溯只能串行去做，无法发挥多线程的思想，但是如果我们同时让多个线程同时去跑同一个回溯，但是前几步利用拉斯维加斯随机思想代替，那么在小于完全回溯方式的耗时条件下找到正确解的概率则可提高。即使不幸，所有线程都没能跑出正确结果，我们也可将随机步数将为0，保证完全退化为回溯后一定可以找到最终解。