概率算法
最后更新于：2022-04-01 15:56:38
概率算法也叫随机化算法。分治算法、贪心算法、动态规划算法、回溯法、分治界限算法这些算法的每一计算步骤都是确定的，概率算法则允许算法在执行过程中随机地选择下一个计算步骤。在很多情况下，算法在执行过程中面临选择时，随机性选择比最优选择省时，因此概率算法可以在很大程度上降低算法的复杂度。
大致可分4类：
1. 数值随机化算法
1. 蒙特卡罗(Monte Carlo)算法
1. 拉斯维加斯(Las Vegas)算法
1. 舍伍德(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)算法
> 一定能找到解，而且是正确解
后面三种算法的实例等到有时间再补充。