牛骨文教育服务平台(让学习变的简单)

概率算法也叫随机化算法。分治算法、贪心算法、动态规划算法、回溯法、分治界限算法这些算法的每一计算步骤都是确定的,概率算法则允许算法在执行过程中随机地选择下一个计算步骤。在很多情况下,算法在执行过程中面临选择时,随机性选择比最优选择省时,因此概率算法可以在很大程度上降低算法的复杂度。
大致可分4类:

  1. 数值随机化算法
  2. 蒙特卡罗(Monte Carlo)算法
  3. 拉斯维加斯(Las Vegas)算法
  4. 舍伍德(Sherwood)算法

各算法特点对比:

1.数值随机化算法

用于数值计算,求得的往往是近似解,比如通过概率投点的思想计算圆周率、计算定积分.

这里写图片描述

如图,向边长为1的正方形内随机投n个点,记落入圆内的点的个数为k,根据几何概型,k/n近似等于圆的面积除以正方形对面积。只计算第一象限,1/4*pi*1*1除以1*1近似等于k/n,pi=4*k/n
程序验证:

#include <iostream>
#include <ctime>
#include <math.h>
using namespace std;
int main(){
   srand((unsigned)time(0));
   double x,y;

   int k=0,n=1000000;
   for(int i=0;i<n;i++){
      x=rand()/(double)(RAND_MAX);     //随机数x
      y=rand()/(double)(RAND_MAX);    //随机数y x、y在0到1之间
      if((pow(x,2)+pow(y,2))<=1) k++; 

   }

    cout<<(double)4*k/n<<endl;
}

n等于100:
这里写图片描述

n等于1000:
这里写图片描述

n等于100000000
这里写图片描述

可以看到,n约大pi的值越精确.当n等于1亿的时候,可以稳定到3.141
可以用相同的方法计算定积分.

2.蒙特卡罗(Monte Carlo)算法

能求得问题的一个解,但是这个解未必正确

3.拉斯维加斯(Las Vegas)算法

要么找到的解是正确的,要么找不到解

4.舍伍德(Sherwood)算法

一定能找到解,而且是正确解

后面三种算法的实例等到有时间再补充。