专栏首页企鹅号快讯详解各种随机算法

详解各种随机算法

转自:JarvisChu

之前将的算法都是确定的,即对于相同的输入总对应着相同的输出。但实际中也常常用到不确定的算法,比如随机数生成算法,算法的结果是不确定的,我们称这种算法为(随机)概率算法,分为如下四类:

1、数值概率算法

用于数值问题的求解,通常是近似解

2、蒙特卡洛算法Monte Carlo

能得到问题的一个解,但不一定是正确解,正确的概率依赖于算法运行的时间,算法所用的时间越多,正确的概率也越高。求问题的准确解;

3、拉斯维加斯算法 Las Vegas

不断调用随机算法求解,直到求得正确解或调用次数达到某个阈值。所以,如果能得到解,一定是正确解。

4、舍伍德算法 Sherwood

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

随机数

概述

计算机产生的随机数都是伪随机数,通过线性同余法得到。

方法:产生随机序列

d称为种子;m取值越大越好;m,b互质,常取b为质数;

案例

伪随机数

在实际编程中,我们使用rand()函数来产生随机数,rand()函数返回0到一个最大值之间的一个随机数。

#include

#include

#include

//产生[0,100)的随机数

voidGenerateRandomNumber()

{

for(inti=;i

{

printf("%-4d",rand()%100);//产生[0,m)的随机数

}

printf("\n");

}

intmain()

{

GenerateRandomNumber();

return;

}

运行代码,输出:41 67 34 0 69 24 78 58 62 64

如果我们重复运行代码就会发现,每次的输出结果都是这个序列。这就是因为rand产生的随机序列是伪随机序列。解决方法是:使用当前的时间作为随机种子。

时间作为随机种子

在GenerateRandomNumber()函数开头加入下面一条语句。

srand((unsigned)time());//以当前时间作为种子

数值概率算法的应用

(1)随机投点法计算π

(2)计算定积分

(3)解非线性方程组

1. 随机投点法计算π

如下图,正方形及其内切圆,圆半径为r。现向正方形中随机投n个点,所投点均匀分布,则点落入圆内概率为。

考虑第一象限即可,取r=1,投n个点,落入圆中k个点,当n趋近无穷时,k/n 趋近于。

#include

#include

#include

#include

floatCalculatePI(intn)

{

assert(n>);

inti=,k=;

floatx,y;

srand((unsigned)time(NULL));

for(i=;i

{

//随机点

x=(float)(rand()%10000)/10000;//x坐标,[0,1)

y=(float)(rand()%10000)/10000;//y坐标,[0,1)

//判断是否落在圆内

if(x*x+y*y

k++;

}

// pi/4 = k/n , pi=4*(k/n)

printf("n=%-10d k=%-10d ",n,k);

return(float)4*k/n;

}

intmain()

{

printf("pi=%f\n",CalculatePI(10));

printf("pi=%f\n",CalculatePI(1000));

return;

}

一次运行结果如下:

n=10 k=10 pi=4.000000

n=1000 k=825 pi=3.300000

2. 计算定积分

原理和计算π相同,对积分函数f(x)有约束条件:1. 在积分区域内连续;2. 在积分区域内存在最大最小值。

3. 舍伍德(Sherwood)算法

一个算法,对于不同的输入数据,其算法的性能是不一样的。比如快排算法,每次选择第一个元素作为基准,对序列从小到大排序:

平均情况:如果待排序列无序,则算法时间复杂度为O(nlogn);

最坏情况:如果序列有序(正序或逆序),则算法时间复杂度为O(n2)

舍伍德算法的思想是:设计随机算法,使得算法的性能和具体的输入值无关,算法的性能 =平均性能 + 一个很小的随机值。

舍伍德算法是为了得到好的平均性能。

准确的说:它是一种思想,并不是一个具体的实现案例。

利用随机算法可将一个算法改造成舍伍德算法,比如,快速排序时,基准的选择可以使用随机算法得到。

对于不能直接改造的,可以引入随机预处理,即对输入进行随机洗牌。比如,对于通常的排序、查找算法,可以先对待排序、查找的序列进行随机位置置换(洗牌)。

可见舍伍德算法就是一种利用随机算法改造确定性算法,使得算法的性能和输入数据尽量无关。

拉斯维加斯(Las Vegas)算法

算法思想就是不断调用随机算法求解,直到求得正确解或者达到设定的步数。

【理解为:不断掷骰子,直到得到某个值,或掷累了】

如下面的代码:

success=false;steps=;

while(!success&&(steps++)

{

success=RandomSovle();//随机算法求解问题

}

拉斯维加斯算法不一定能获得解,随着运行时间的增加,获得解的概率也越大。

它可以用来求解某些迄今没有有效解法的问题,因为通过不断的随机尝试,也许能够找到正确解。

蒙特卡罗(Monte Carlo)算法

拉斯维加斯算法是:不一定能给出解,给出则必正确

蒙特卡罗算法是:一定能给出解,但不一定正确

蒙特卡罗算法在一般情况下能够保证对问题的所有实例都以高概率给出正确解。但是,通常无法判断一个具体解是否正确。

一个蒙特卡罗算法得到正确解的概率为p,如果0.5

对于用一个实例,如果蒙特卡罗算法不会给出两个不同的正确解,则称算法是一致的。

觉得本文有帮助?请分享给更多人

关注「算法爱好者」,修炼编程内功

本文来自企鹅号 - 算法爱好者媒体

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 04-树5. File Transfer--并查集

      对于一个集合常见的操作有:判断一个元素是否属于一个集合;合并两个集合等等。而并查集是处理一些不相交集合(Disjoint Sets)的合并及查询问题的有利工...

    llhthinker
  • 中文分词研究入门

    导读 本文首先简单介绍了自然语言处理和科研过程中重要的四部曲——调研、思考、编程和写作,然后对中文分词问题进行了说明,介绍了中文分词存在的难点如消歧、颗粒度问题...

    llhthinker
  • 区块链学堂——“遇见”拜占庭将军

    但凡关于区块链或比特币相关的书籍,就算是相关问题深入探讨都绕不开一个永恒的话题——拜占庭将军问题(The Byzantine Generals Problem)...

    企鹅号小编
  • Casper系列01——Casper 简介与概览

    Casper 简介与概览 Casper 是知名开源区块链项目以太坊 (Ethereum) [1] 的共识算法,是以太坊转型为全面 PoS (Proof-of-S...

    企鹅号小编
  • 0-1整数规划与隐枚举法-感受剪枝的魅力

    0-1整数规划与隐枚举法-感受剪枝的魅力 整数规划是线性规划的特殊情况,即当约束条件是变量为整数时,线性规划就变成了整数规划。若要求所有变量都为整数,即为纯整数...

    llhthinker
  • 利用 SVCCA 解释深度神经网络

    文 / Google Brain 团队 Maithra Raghu 深度神经网络 (DNN) 推动视觉、语言理解和语音识别等领域取得了前所未有的进步。但是,这些...

    企鹅号小编
  • Lake Counting(POJ-2386)

    题目链接: http://poj.org/problem?id=2386 题目大意: 计算出相连的'W'有多少块 所需算法: 深度优先搜索(DFS) 主要思路:...

    llhthinker
  • Java设计模式之模板方法设计模式(银行计息案例)

           不知道为什么,这几天对Java中的设计模式非常感兴趣,恰巧呢这几天公司的开发任务还不算太多,趁着有时间昨天又把模板方法模式深入学习了一下,做了一个...

    赵小忠
  • 高级聚类

    FuzzyKmeans 在对数据进行聚类时,最常用的方法应该是kmeans,但是kmean只能保证每一条待聚类的数据划分到一个类别,针对一条数据可以被划分到多个...

    xiangzhihong
  • 04-树4. Root of AVL Tree-平衡查找树AVL树的实现

      对于一棵普通的二叉查找树而言,在进行多次的插入或删除后,容易让树失去平衡,导致树的深度不是O(logN),而接近O(N),这样将大大减少对树的查找效率。一种...

    llhthinker

扫码关注云+社区

领取腾讯云代金券