以赌城命名蒙特卡洛算法到底有多神奇？
以赌城命名蒙特卡洛算法到底有多神奇？
& &&人机大战&虽已落幕，但热度依然不减，有专家表示，AlphaGo的胜利只能说是算法的胜利。据悉，AlphaGo主要使用了深度学习+强化学习+蒙特卡洛树搜索，而&蒙特卡洛&算法成为隐藏的&撒手锏&之一。在AlphaGo问世之前，计算机与人类的棋类比赛中，蒙特卡洛这一算法同样发挥着重要作用。那么，这一算法到底有何神奇之处？
以赌城命名的概率算法
& 据了解，蒙特卡洛算法问世由来已久，很早就被人们发现和利用。东南大学物理系教师白羽告诉记者，20世纪40年代美国在第二次世界大战中参与研制原子弹的&曼哈顿计划&的成员乌拉姆和冯&诺伊曼首先提出蒙特卡洛方法。数学家冯&诺伊曼更是用摩纳哥的赌城Monte Carlo来命名这种方法，为它蒙上了一层神秘色彩。
& 不过在此之前，蒙特卡洛算法就已经存在，1777年，法国布冯提出用投针实验的方法求圆周率，这被认为是蒙特卡洛算法的起源。
& 白羽表示，蒙特卡洛算法是一种&随机化&的方法，名字来源于赌城，是因为赌博中体现了许多随机算法，所以借以命名。&比如，可用民意测验来作一个不严格的比喻。民意测验的人不是征询每一个登记选民的意见，而是通过对选民进行小规模的抽样调查来确定可能的优胜者，其基本思想是一样的。&
& &其实，一把黄豆就可以完成蒙特卡洛算法。&白羽告诉记者，比如在广场上画一个边长一米的正方形，在正方形内部随意用粉笔画一个不规则的形状，现在要计算这个不规则图形的面积，怎么计算呢？蒙特卡洛算法告诉我们，均匀地向该正方形内撒N个黄豆（N是一个很大的自然数），随后数数有多少个黄豆在这个不规则几何形状内部，比如说有M个，那么，这个奇怪形状的面积便近似于M/N，N越大，算出来的值便越精确。在这里我们假定黄豆都在一个平面上，相互之间没有重叠，而且是均匀撒出。
&抢红包&就用到了蒙特卡洛算法
& 说了这么多，这种算法到底有何魔力？白羽告诉记者，就蒙特卡洛算法本质而言，是用类似于物理实验的近似方法求解问题，它的魔力在于模拟，&模拟真实的实验场景，然后可以研究进行中的实验到底会发生什么。蒙特卡洛需要巨量的计算资源，不仅仅因为处理问题有多复杂，另一方面它需要很大的统计量，统计量越大结果则越精确。&
& 不过，现实生活中的问题要比实验室中复杂得多。比如金融衍生产品（期权、期货、掉期等）的定价及交易风险估算，问题的维数（即变量的个数）可能高达数百甚至数千。对这类问题，传统的数值方法难以对付（即使使用速度最快的计算机）。蒙特卡洛算法则能很好地用来对付维数，因为该方法的计算复杂性不再依赖于维数，可以基于随机仿真的过程给出近似的结果。以前那些本来是无法计算的问题现在也能够计算出。
& 目前，蒙特卡洛算法在金融工程学、宏观经济学、生物医学、计算物理学（如粒子输运计算、量子热力学计算、空气动力学计算）等领域应用广泛。
& 那么，日常生活中人们是否接触到这么&高大上&的算法？&有没有发现微信抢红包时，你抢到的金额都是随机发放的，这些随机金额怎么生成的，这其中就运用到了蒙特卡洛算法。&白羽告诉记者，生活中一些生成随机数领域，多运用到蒙特卡洛算法。
计算机对弈的&撒手锏&
& 蒙特卡洛算法和计算机棋类游戏颇有渊源。可以说，计算机在棋类游戏中&精进&得益于蒙特卡洛算法的不断发展。
& 不像五子棋等简单棋类游戏，国际象棋和围棋这样的复杂棋类，从初始盘面出发穷尽所有变化的复杂度(也称穷举复杂度)更是大得难以想象。信息论创始人克劳德&香农在1950年曾第一个估计出国际象棋的穷举复杂度大概在10120种变化左右，具体数字被后人称为&香农数&。而围棋的穷举复杂度又远远超出国际象棋，达到了惊人的10360。
& 有人会问，有没有可能存在一个高效的算法，可以在棋面呈指数级增长状况的同时，仍然对当前盘面做出准确评估呢？
& 于是，蒙特卡洛算法开始被应用于围棋盘面评估。专家表示，每个围棋盘面都有一个&最优值&，对于围棋已经证明，计算这个最优值的时间至少随该盘面到终盘之间的步数呈指数级数增长(平均200步，每步平均增长200倍数量的可能盘面)，从理论上是无法得到最优值。那么，可不可以根据蒙特卡洛思想对整个可能性空间进行某种采样，然后通过统计估值的方法逼近这个最优值呢？人们对这个问题的思考在2006年终于取得了突破性进展，提出了一种称为蒙特卡洛树搜索的动态评估方法。在围棋弈棋系统的实践中，蒙特卡洛树搜索在比赛时间受限的情况下确实表现出远远超过传统方法的棋力。
& 不过，虽然&蒙特卡洛树搜索&方法在此前一些弈棋程序中有采用，在相对较小的棋盘中能够很好地发挥作用，但在正规的全尺寸棋盘上，这种方法的缺陷也体现出来了，因为涉及的搜索树实在太大了。最近几年人们开始在空间选择策略中加入更多和围棋相关的专家知识，使得基于蒙特卡洛树搜索的围棋弈棋系统水平不断提高。
& 此次AlphaGo则采用了更聪明的策略，即利用深度学习的方法降低搜索树的复杂性。因此&深度学习&和&蒙特卡洛树搜索&就成为它的两个关键因素，在每个模拟游戏中，AlphaGo都有两个大脑指引它进行搜索：价值网络和政策网络。&政策网络&观察棋盘布局企图找到较好的下法，&价值网络&则预测这样下的话对方棋手赢棋的可能。结合这两个建议，AlphaGo最终决定了怎样落子才是胜算最大的。
20世纪十大算法
& 本世纪初，美国物理学会和IEEE计算机社团的一本联合刊物《科学与工程中的计算》发表了由田纳西大学和橡树岭国家实验室两位专家联名撰写的&世纪十大算法&一文，该文&试图整理出在20世纪对科学和工程领域的发展产生最大影响力的十大算法&。两位作者苦于&任何选择都将是充满争议的，因为实在是没有最好的算法&，他们只好用编年顺序依次列出了这十项算法领域人类智慧的巅峰之作&&给出了一份算法排行榜。有趣的是，该期杂志还专门邀请了这些算法相关领域的&大拿&为这十大算法撰写十篇综述文章，这十大算法依次为：
1.1946年，计算蒙特卡洛过程度伦敦算法；
2.1947年，单纯形法；
3.1950年，Krylov子空间迭代法；
4.1951年，矩阵计算的分解方法；
5.1957年，优化的Fortran编译器；
6.年，计算矩阵特征值的QR算法；
7.1962年，快速排序算法；
8.1965年，快速傅立叶变换；
9.1977年，整数关系探测算法；
10.1987年，快速多极算法。3474人阅读
算法与数据结构（7）
本篇文章介绍计算圆周率的几种算法，都是应用蒙特卡罗思想：或称计算机随机模拟方法，是一种基于“随机数”的计算方法。
方法一：蒙特卡罗方法，内切圆
&&&&&&&& 有一个以（0,0）为中心的2*2的正方形，及这个正方形的半径为1的内接圆，取这个正方形范围内的一点，则这个点落入内接圆的概率为PI/4。
程序分为两部分：（1）随机生成正方形内的一点（2）计算落入内接圆的概率，从而求得PI。
import java.util.R
public class MonteCarlo
int m = 0;//落入内接圆的次数
int n = ;//试验进行次数
//点的x坐标值
//点的y坐标值
double result = 0;//结果，即为PI
Random r = new Random();//Random对象，用于生成随机数
public static void main(String[] args){
MonteCarlo c = new MonteCarlo();
c.calculatePI();
public float getNum(){
float tmp = 1-r.nextFloat()*2;//nextFloat生成[0,1]的浮点数
public void calculatePI(){
for(int i = 0; i&n;i++){//进行n次试验
x=getNum();
y=getNum();
float tmp = (float) java.lang.Math.sqrt(x*x+y*y);//开根号
if(tmp&=1)
m++;//落入内接圆的次数
result = (4*(float)m)/n;//PI
System.out.println(&m: &+m);
System.out.println(&n: &+n);
System.out.println(&pi: &+result);
方法二：蒲丰投针方法
&&&&&&&& 在平面上画一组间距为d的平行线，将一根长度为l（l&d）的阵任意掷在这个平面上，此阵与平行线中任一条相交的概率是：p = 2l/(PI*d)
程序分为如下几个步骤：（1）随机得到一个点和一个角度（2）计算另一个点位置（都只考虑垂直位置）（3）计算这两个点分别跨越了几条平行线
import java.util.R
public class PuFeng {
int n = ;//试验进行次数
int m = 0;//相交次数
double l = 2;//针的长度
double d = 5;//平行线间距
double pi = 0;//结果
int lNum = 10000;//线的条数
Random r = new Random();//用于生成随机数
public static void main(String[] args){
PuFeng p = new PuFeng();
p.calculatePI();
public void calculatePI(){
for(int i = 0; i &n;i++){
double point = getPoint();
double angle = getAngle();
double anotherPoint = point+l*java.lang.Math.sin(angle);//得到第二个点垂直位置
int crossNum1 = (int) (point/d);//第一个点前面有几条平行线
int crossNum2 = (int) (anotherPoint/d);//第二个点前面有几条平行线
if((crossNum1-crossNum2)!=0)//若差等于0，则与平行线不相交
pi= (2*n*l)/(m*d);
System.out.println(&m: &+m);
System.out.println(&n: &+n);
System.out.println(&result: &+pi);
//随机得到平行线范围内的一点
public double getPoint(){
double tmp = r.nextDouble()*lNum*l;
//随机得到0~360角度
public double getAngle(){
double tmpAngle = (double) (r.nextDouble()*Math.PI);;
return tmpA
方法三：互质方法
&&&&&&&& 随机取两个自然数，则这两个数互质的概率为：6/(PI*PI)
&&&&&&&& 该程序分为几个步骤：（1）生成两个自然数（2）判断是否互质（3）计算互质的概率
import java.util.R
public class PrimeNum {
Random r = new Random();//用于生成随机数
int m = 0;//互质的次数
int n = 1000000;//实验次数
float result = 0;//结果，即PI
public static void main(String[] args){
PrimeNum p = new PrimeNum();
p.calculatePI();
public int getNum(){
int tmp = r.nextInt();
while(tmp&1){//r.nextInt()得到了的可能是负数
tmp = r.nextInt();
public Boolean checkPrime(int a, int b){//判断两个数是否互质
int c = 0;
while((c = a%b)!= 0){
if(b == 1)
public void calculatePI(){
for(int i = 0; i &n;i++){//进行n次实验
int num1=getNum();//随机获得两个自然数
int num2 = getNum();
if(checkPrime(num1,num2))//判断是否互质
m++;//若互质，则m+1
result = (float) java.lang.Math.sqrt((6*n)/(float)m);
System.out.println(&m: &+ m);
System.out.println(&n: &+ n);
System.out.println(&result: &+result);
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：43425次
排名：千里之外
原创：35篇
评论：81条
(3)(2)(3)(6)(1)(3)(4)(4)(2)(2)(1)(4)C语言 用蒙特卡洛法求圆周率 帮忙修改一下程序_百度知道
C语言 用蒙特卡洛法求圆周率 帮忙修改一下程序
d=0.h&time.h&gt,4*d/int c=0;#include&}在visual studio 2010中运行的.h&#define N 30000main(){}printf(&quot,y;=N){x=rand()/srand(time(0));while(c++&(double)RAND_MAX;n&y=rand()/N);(double)RAND_MAX;if(x*x+y*y&=1)d++;pi=%f\，菜鸟，不知道错在哪里，帮帮忙#include&#include&lt
提问者采纳
h& /n&quot.h&#include&time.h&N);#include&lt.int c=0;/标准C++写法{,会丢失数据,y; &#47.000000*d//不提倡用if(x*x+y*y&lt,因为你已经显式转换成了&#47,d=0;srand((time_t)time(0));强制类型转换while(c++&}printf(&=N){x=rand()&#47,4;(double)RAND_MAX;y=rand()/(double)RAND_MAX;=1)d++;pi=%lf\return 0; /&#47#include&#define N 30000int main() &#47
请问srand((time_t)time(0)); 中的(time_t)是什么意思？
强制转换到time_t类型
提问者评价
好的，谢了好像用unsigned int
也可以是不？time_t`````我还没见过唉·······
其他类似问题
为您推荐：
蒙特卡洛法的相关知识
其他2条回答
pi=%f\N);n&,4*d/N);改成printf(&pi=%f\n&,4.0*d/就可以了printf(&quot
#include&stdlib.h&#include&time.h&#include&stdio.h&#define N 30000void main(){float x,y;int c=0,d=0;srand(unsigned(time(0)));while(c++&=N){x=rand()/(double)RAND_MAX;y=rand()/(double)RAND_MAX;if(x*x+y*y&=1)d++;}printf(&pi=%f\n&,4*d*1.0/N);}4*d/N这里的除法是整数相除的，除出来的结果是整数的，应该用浮点数相除
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁matlab上机报告_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
matlab上机报告
上传于||文档简介
&&本​科​课​程​m​a​t​l​a​b​的​上​机​报​告
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩7页未读，继续阅读
你可能喜欢7652人阅读
机器学习（32）
从今天开始要研究Sampling Methods，主要是MCMC算法。本文是开篇文章，先来了解蒙特卡洛算法。
&& 1. 蒙特卡洛介绍
&& 2. 蒙特卡洛的应用
&& 3. 蒙特卡洛积分
1. 蒙特卡洛介绍
&& 蒙特卡罗方法（Monte Carlo method），也称统计模拟方法，是二十世纪四十年代中期由于科学技术的
&& 发展和电子计算机的发明，而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使
&& 用随机数（或伪随机数）来解决很多计算问题的方法。与它对应的是确定性算法。蒙特卡罗方法在金融工程
&& 学，宏观经济学，计算物理学（如粒子输运计算、量子热力学计算、空气动力学计算）等领域应用广泛。
&& 蒙特卡罗方法于20世纪40年代美国在第二次世界大战中研制原子弹的“曼哈顿计划”计划的成员S.M.乌拉姆
&&&和J.冯·诺伊曼首先提出。数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的Monte Carlo—来命名这种方法，
&& 为它蒙上了一层神秘色彩。在这之前，蒙特卡罗方法就已经存在。1777年，法国数学家布丰提出用投针实验
&&&的方法求圆周率，这被认为是蒙特卡罗方法的起源。
&& 另外，拟蒙特卡洛算法在近几年也获得迅速发展。这种方法是用确定性的超均匀分布代替蒙特卡洛算法中的
&& 随机数序列，对于某些特定问题计算速度比普通的蒙特卡洛算法高几百倍。
&& 由于产生随机数的随机性，当我们用N个随机点以蒙特卡罗方法来求解具体的问题时，其计算得到近似解的误
&& 差值有大有小，但是肯定有一个确定的平均值，即一些误差大于此值，而其余误差小于此值。鉴于此，显然肯
&& 定存在这样的N个点，使得误差的绝对值不大于平均值。如果我们能够构造这样的点集，就可以对原有的方法
&& 进行较大的改进。拟蒙特卡罗方法就是至于此而提出的，它致力于构造其误差比平均误差显著要好的那种点集，
&&&而其求解形式与蒙特卡罗方法一致，只不过所用的随机数不一样。用蒙特卡罗方法求解问题时，影响结果好坏
&& 的主要是随机数序列的均匀性。而拟蒙特卡罗方法中的具有低偏差的一致分布点集较伪随机数序列更为均匀，
&& 而且用拟蒙特卡罗方法求解得到的是真正的误差，避免了蒙特卡罗方法得到概率误差的缺陷。
&& 由此可见用拟蒙特卡罗方法求解问题的关键是如何找到一个均匀散布的点集。目前常用的点集有GLP点集(好格
&& 子点集，good lattice point set)、GP点集(好点集，good point set)、Halton点集及其变体、
&& Hammersley点集等。
&& 蒙特卡洛方法的理论基础是大数定律。大数定律是描述相当多次数重复试验的结果的定律，根据这个定律知道
&& 样本数量越多，其平均就越趋近于真实值。
2. 蒙特卡洛的应用
&& 最经典的应用就是利用蒙特卡洛算法求圆周率。代码如下
#include &bits/stdc++.h&
#define MAX_ITERS 1000000
double Rand(double L, double R)
return L + (R - L) * rand() * 1.0 / RAND_MAX;
double GetPi()
srand(time(NULL));
int cnt = 0;
for(int i = 0; i & MAX_ITERS; i++)
double x = Rand(-1, 1);
double y = Rand(-1, 1);
if(x * x + y * y &= 1)
return cnt * 4.0 / MAX_ITERS;
int main()
for(int i = 0; i & 10; i++)
cout && GetPi() &&
3. 蒙特卡洛积分
&& 关于蒙特卡洛求积分，可以先参照如下文章。
&& 链接：&
&& 接下来用蒙特卡洛积分求自然常数。这是2015年阿里的一道笔试题。
&& 首先考虑如下积分
&&&接下来分别用蒙特卡洛积分和牛顿莱布尼兹公式计算，在蒙特卡洛方法中样本很多时，它们的值应该相等。
&& 利用蒙特卡洛方法，图像大致如下
&&& 上述积分的目的是求阴影部分的面积，所以先在所标矩形内取对随机点，
&&& 对于每一对，考察是否满足如下条件
&&& 假设满足上述条件的点有个，而全部的点有个，所以得到近似公式为
&&&&而依据牛顿莱布尼兹公式可以得到
&&& 这两种方法结果应该是相等的，即有
&&&&&&&&&&
&&&&接下来写写代码吧！
#include &bits/stdc++.h&
#define MAX_ITERS
struct Point
double Rand(double L, double R)
return L + (R - L) * rand() * 1.0 / RAND_MAX;
Point getPoint()
t.x = Rand(1.0, 2.0);
t.y = Rand(0.0, 1.0);
double getResult()
int m = 0;
int n = MAX_ITERS;
srand(time(NULL));
for(int i = 0; i & i++)
Point t = getPoint();
double res = t.x * t.y;
if(res &= 1.0)
return pow(2.0, 1.0 * n / m);
int main()
for(int i = 0; i & 20; i++)
cout && fixed && setprecision(6) && getResult() &&
&&& 观察一下运行结果，效果还是不错的。如下图
&&&&&&&&&&&&&
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1193349次
积分：17076
积分：17076
排名：第352名
原创：478篇
转载：42篇
评论：299条
(1)(4)(3)(4)(38)(4)(1)(2)(5)(1)(4)(2)(1)(7)(10)(8)(8)(12)(16)(31)(20)(28)(49)(28)(17)(42)(18)(29)(26)(15)(3)(8)(9)(8)(11)(3)(46)