概率算法思想是依照概率统计的思路来求解问题的算法，他往往不能得到问题的精确解，但却在数值计算领域得到了广泛应用。因为很多数学问题是很难计算出来精确解的，往往求取近似解。

概率算法思想

概率算法执行的基本过程如下：

将问题转换成对应的几何图形S，S的面积容易计算，问题的结果往往是对应的几何图形的中某一部分的面积。向几何图形中随机撒点。统计和中的点数。根据点数计算得到两部分面积的关系，从而得到计算结果。判断结果是否在需要的精度内，如果未达到精度继续步骤2，如果达到的输出近似结果。

这种问题可以看作是向一个圆盘上扔飞镖，最后统计不同区域内的飞镖的个数，从而得到不同区域的关系。

概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。这两次求解问题所需的时间甚至所得到的结果可能会有相当大的差别。一般情况下，可将概率算法大致分为四类：

数值概率算法蒙特卡罗（Monte Carlo）算法拉斯维加斯（Las Vegas）算法舍伍德（Sherwood）算法算法示例

这里通过一个计算圆周率的示例来看蒙特卡洛（Monte Carlo）概率算法的应用。

算法思想

圆的面积公式可以表示为

圆的半径为1，那么图中阴影部分面积可以表示为

蒙特卡罗算法示意

那样如果均匀的向图中的正方形内撒点，那么落入阴影部分的点数和全部的点数之比应该为

算法可以采用随机数来实现，产生[0,1]之间随机的坐标值[x,y]，利用判断点的个数。

利用python实现蒙特卡洛概率算法实现

import randomdef MotePi(n):    sum = 0    for i in range(n):        x = random.random()     #产生0-1之间的一个随机数        y = random.random()     #产生0-1之间的一个随机数        if x*x+y*y<=1:      #判断是否在阴影区            sum = sum + 1       #在阴影区点的个数统计    pi = 4*sum/n        #面积比例近似等于点的个数比例，×4就是pi的值    return piif __name__ == '__main__':    print('蒙特卡洛概率算法计算Π:')    n = int(input('输入点的数量:'))    pi = MotePi(n)    print('计算结果为:{pi}'.format(pi=pi))

运行结果为

D:\PycharmProjects\algorithm\venv\Scripts\python.exe D:/PycharmProjects/algorithm/randpi.py蒙特卡洛概率算法计算Π:输入点的数量:500000计算结果为:3.14076Process finished with exit code 0

D:\PycharmProjects\algorithm\venv\Scripts\python.exe D:/PycharmProjects/algorithm/randpi.py蒙特卡洛概率算法计算Π:输入点的数量:500000000计算结果为:3.141599736Process finished with exit code 0