姓名：李嘉蔚 学号16020520034
【嵌牛导读】:其实人下棋也是随机试几步，找赢棋概率最大的走。Alphago就是用这个蒙特卡洛算法的。应用这种思想的算法都是蒙特卡洛算法，它有很大的应用，因为现实中有很多的问题都不需要求最优解，也就是不用拉斯维加斯算法。蒙特卡罗方法于20世纪40年代美国在第二次世界大战中研制原子弹的“曼哈顿计划”计划的成员S.M.乌拉姆
和J.冯·诺伊曼首先提出。数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的Monte Carlo—来命名这种方法，
为它蒙上了一层神秘色彩。在这之前，蒙特卡罗方法就已经存在。
【嵌牛鼻子】：随机数生成，大数定律，蒙特卡洛算法，近似最优解。
【嵌牛提问】：什么是蒙特卡洛算法？有什么简单应用？
【嵌牛正文】:什么是蒙特卡洛算法？
我们通俗的来解释一下蒙特卡洛算法：
假如篮子里有1000个苹果，让你每次闭着眼睛找一个最大的，可以不限制挑选次数。于是，你可以闭着眼随机拿了一个，然后再随机拿一个与第一个比，留下大的，再随机拿一个，与前次留下的比较，又可以留下大的。循环往复这样，拿的次数越多，挑出最大苹果的可能性也就越大，但除非你把1000个苹果都挑一遍，否则你无法肯定最终挑出来的就是最大的一个。
也就是说，蒙特卡洛算法是样本越多，越能找到最佳的解决办法 ，不过不保证是最好的，因为如果有10000个苹果的话，说不定就能找到更大的。
可以和他形成对比的是拉斯维加斯算法：
通俗的说，假如有一把锁，有1000把钥匙进行选择，但只有1把是对的。于是每次随机拿1把钥匙去试，打不开就再换1把。试的次数越多，打开最优解的机会就越大，但在打开之前，那些错“它们的任务在于合作‘挑选’出那些比较有前途的棋步，抛弃明显的差棋，从而将计算量控制在计算机可以完成的范围内。在本质上，这和人类棋手所做的是一样的。 ”中国科学院自动化研究所博士研究生刘加奇说。的钥匙都是没有用的。
“它们的任务在于合作‘挑选’出那些比较有前途的棋步，抛弃明显的差棋，从而将计算量控制在计算机可以完成的范围内。在本质上，这和人类棋手所做的是一样的。 ”中国科学院自动化研究所博士研究生刘加奇说。
比如算圆周率：
蒙特卡洛算法
用的就是先随机再比较的方法。
import java.util.Random;
/**
* 随机数计算圆周率π 蒙特卡洛算法的简单应用,还可用来计算积分等信息
*
* @author admin
*
*/
public class PI {
/**
* 判断落点是否在圆内部 勾股定理 x² + y² = r² ,那么 x² + y² <= r² 都视作在圆内
*
* @param x
* @param y
* @return
*/
public boolean isInCycle(double x, double y) {
if (x * x + y * y <= 1) {
return true;
} else {
return false;
}
}
public double getPi(int count) {
Random random = new Random();
double in = 0;
for (int i = 0; i < count; i++) {
double x = random.nextDouble();
double y = random.nextDouble();
if (isInCycle(x, y)) {
in++;
}
}
System.out.println(in + "/" + count);
return 4 * in / count;
}
/**
* 判断落点在积分线下的区域
*
* @param x
* @param y
* @return
*/
public boolean isInRegion(double x, double y) {
if (y <= x * x) {
return true;
} else {
return false;
}
}
public double getJifen(int count) {
Random random = new Random();
double in = 0;
for (int i = 0; i < count; i++) {
double x = random.nextDouble();
double y = random.nextDouble();
if (isInRegion(x, y)) {
in++;
}
}
System.out.println(in + "/" + count);
return in / count;
}
public static void main(String[] args) {
PI p = new PI();
// 求π,可以增加循环次数获取更精确结果
System.out.println(p.getPi(1000000));
// 求积分
System.out.println(p.getJifen(1000000));
}
}
输出结果:
785238.0/1000000
3.140952
332700.0/1000000
0.3327
任何本质上属随机组员的过程或系统的仿真都需要一种产生或获得随机数的方法。这种仿真的例子在中子随机碰撞，数值统计，队列模型，战略游戏，以及其它竞赛活动中都会出现。Monte Carlo 计算方法需要有可得的、服从特定概率分布的、随机选取的数值序列。
其中较为普遍应用的产生随机数的方法是选取一个函数，使其将整数变换为随机数。以某种方法选取，并按照产生下一个随机数。
1777年，法国数学家布丰提出用投针实验
的方法求圆周率，这被认为是蒙特卡罗方法的起源。
用拟蒙特卡罗方法求解问题的关键是如何找到一个均匀散布的点集。目前常用的点集有GLP点集(好格
子点集，good lattice point set)、GP点集(好点集，good point set)、Halton点集及其变体、
Hammersley点集等。
蒙特卡洛方法的理论基础是大数定律。大数定律是描述相当多次数重复试验的结果的定律，根据这个定律知道
样本数量越多，其平均就越趋近于真实值。
接下来用蒙特卡洛积分求自然常数。这是2015年阿里的一道笔试题。
首先考虑如下积分
蒙特卡洛算法
接下来分别用蒙特卡洛积分和牛顿莱布尼兹公式计算，在蒙特卡洛方法中样本很多时，它们的值应该相等。
利用蒙特卡洛方法，图像大致如下
蒙特卡洛算法
上述积分的目的是求阴影部分的面积，所以先在所标矩形内取对随机点，
对于每一对，考察是否满足如下条件
蒙特卡洛算法
假设满足上述条件的点有个，而全部的点有个，所以得到近似公式为
蒙特卡洛算法
而依据牛顿莱布尼兹公式可以得到
蒙特卡洛算法
这两种方法结果应该是相等的，即有
蒙特卡洛算法
接下来写写代码吧！
代码：
1 #include 2 3#define MAX_ITERS 10000000
4 5usingnamespace std;
6 7struct Point
8{
9double x, y;
10};
1112double Rand(double L, double R)
13{
14return L + (R - L) * rand() * 1.0 / RAND_MAX;
15}
1617Point getPoint()
18{
19 Point t;
20 t.x = Rand(1.0, 2.0);
21 t.y = Rand(0.0, 1.0);
22return t;
23}
2425double getResult()
26{
27int m = 0;
28int n = MAX_ITERS;
29 srand(time(NULL));
30for(int i = 0; i < n; i++)
31 {
32 Point t = getPoint();
33double res = t.x * t.y;
34if(res <= 1.0)
35 m++;
36 }
37return pow(2.0, 1.0 * n / m);
38}
3940int main()
41{
42for(int i = 0; i < 20; i++)
43 cout << fixed<< setprecision(6) << getResult() << endl;
44return0;
45 }
观察一下运行结果，效果还是不错的。如下图
蒙特卡洛算法
网友评论