大家好,欢迎来到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,那么这个简化版的取物游戏的赢家,始终是第二个下的那位)。这个游戏可采用极小加大搜索在博弈树中找到获胜的玩法。
博弈树(解空间树)的构造是从上到下进行的:
- 第一层 Max走第一步,此时石堆中剩余石子5块,Max可以选则取出1、2、3块石头,给予他的选择,会出现第二层的三种情况。
- 第二层 Minnie走第二步,基于Max的选择,Minnie可以从三种情况选择其一若上一步Max选择取出1块,那么这次Minnie可以选择取出1、2、3块,形成第三层最左册的三种case;若上一步Max选择取出2块,那么这次Minnie可以选择取出1、2、3块,形成第三层中间的三种case;若上一步Max选择取出3块,那么这次Minnie可以选择取出1、2块,形成第三层最右册的三种case。
- 第三层再次轮到Max选择取出几块石子,此时有些case下石堆剩余的石子已经为0,这些case游戏已经结束,其他case按照规则再次生成第四层的10种case。
- 第四、五、六层依次按照上述规则生成。
有了博弈树,就需要按照树的路径计算,找出沿各个路径进行游戏的最终胜负结果。极小极大搜索的思想是在本方选择时尽可能做对自己有利的选择,即极大值;在对方选择时,假定对方足够聪明,因此他会做出对他而言的最佳选择,相反对于本方则是最差选择,即极小值。
拉斯维加斯随机思想
拉斯维加斯随机注重的是要找到正确的结果,而不是靠近最优值。比如之前提到的回溯解决4皇后问题,回溯类似于改进型的穷举,但是假如是128皇后,采用回溯有时耗时是不被允许的,如果此时游戏的要求是可以尝试多次,只要其中有一次成功,则按照成功的一次的时间当作游戏耗时。此时则可以尝试拉斯维加斯思想。即128皇后的前几步采用随机选择方式以减少遍历数量,后面再使用回溯。随机放置一部分棋子后并不能保证后续的回溯可以找到正确答案,但是一旦成功耗时就一定小于完全回溯的方式。这一思想我认为可以通过多线程手段解决更加实际的问题,因为一般回溯只能串行去做,无法发挥多线程的思想,但是如果我们同时让多个线程同时去跑同一个回溯,但是前几步利用拉斯维加斯随机思想代替,那么在小于完全回溯方式的耗时条件下找到正确解的概率则可提高。即使不幸,所有线程都没能跑出正确结果,我们也可将随机步数将为0,保证完全退化为回溯后一定可以找到最终解。
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://haidsoft.com/134881.html