算法之蒙特卡洛Demo求PI值

PI的值大家小学就接触过，那么这个值怎么得到的呢？我们今天来尝试一下从计算机的角度利用蒙特卡罗算法求解PI的近似值。如有兴趣可以查阅详情。

我们呢先不说结果，来跟着这个小Demo尝试一下自己探索吧。

首先还是介绍一下蒙特卡罗思想：

蒙特卡罗方法于20世纪40年代美国在第二次世界大战中研制原子弹的“曼哈顿计划”计划的成员S.M.乌拉姆和J.冯·诺伊曼首先提出。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的Monte Carlo—来命名这种方法，为它蒙上了一层神秘色彩。在这之前，蒙特卡罗方法就已经存在。1777年，法国数学家布丰（Georges Louis Leclere de Buffon，1707—1788）提出用投针实验的方法求圆周率π。这被认为是蒙特卡罗方法的起源。

在解决实际问题的时候应用蒙特·卡罗方法主要有两部分工作：

用蒙特·卡罗方法模拟某一过程时，需要产生某一概率分布的随机变量。
用统计方法把模型的数字特征估计出来，从而得到实际问题的数值解。

环境介绍：

语言：Java
使用JDK：java 1.8
工具：eclipse或者IDEA都可。
主要技术：Swing awt

我们这里不介绍swing和awt的实现，而是直接借用模板来操作。模板中封装好了需要的一些简要实现。
需要的可以在这里下载模板源代码。

https://gitee.com/xiangzi1019/template_code/tree/master

再介绍一下模板：

1.主要包含了一个框架AlgoFrame，其中内容主要用于绘制内部信息，和双缓存的实现。
2.AlgoVishelper看名称也可以知道，主要封装了一些帮助函数，例如绘制实体或者空心的圆、矩形、颜色等函数
3.AlgoVisualizer主要就是视图可见的操作，例如你想事先声明功能都可以写在这里，然后调用数据和帮助类就可以实现。

导入文档包之后呢，我们就先操作AlgoVisualizer类。

首先呢我们要创建一个Circle类，用来生成正方形中的内切圆。

import java.awt.*;
import javax.swing.*;
public class Circle {

    private int x, y, r;

    public Circle(int x, int y, int r){
        this.x = x;
        this.y = y;
        this.r = r;
    }

    public int getX(){ return x; }
    public int getY(){ return y; }
    public int getR(){ return r; }

    public boolean contain(Point p){
        return Math.pow(p.x - x, 2) + Math.pow(p.y - y, 2) <= r*r;
    }
}

然后我们再创建一个MonteCarloPiData类专门用来保存和计算点的个数。我们呢在里面画抑恶个圆，并且设计方法得到正方形以及圆内的point的个数。分别用insideCircle表示圆内的点的个数，再用estimatePi方法返回当前得到的PI的值。

import java.util.LinkedList;
import java.awt.*;

public class MonteCarloPiData {

    private Circle circle;
    private LinkedList<Point> points;
    private int insideCircle = 0;

    public MonteCarloPiData(Circle circle){
        this.circle = circle;
        points = new LinkedList<Point>();
    }

    public Circle getCircle(){
        return circle;
    }

    public int getPointsNumber(){
        return points.size();
    }

    public Point getPoint(int i){
        if(i < 0 || i >= points.size())
            throw new IllegalArgumentException("out of bound in getPoint!");

        return points.get(i);
    }

    public void addPoint(Point p){
        points.add(p);
        if(circle.contain(p))
            insideCircle ++;
    }

    public double estimatePi(){

        if(points.size() == 0)
            return 0.0;

        int circleArea = insideCircle;
        int squareArea = points.size();
        return (double)circleArea * 4 / squareArea;
    }
}

有了前面的铺垫，我们再去设计框架里面的数据，这里我们呢传入三个数据，分别是生成的高和宽以及传入的点数：

private static int DELAY = 40;
private MonteCarloPiData data;
private AlgoFrame frame;
private int N;

public AlgoVisualizer(int sceneWidth, int sceneHeight, int N){

    if(sceneWidth != sceneHeight)
        throw new IllegalArgumentException("This demo must be run in a square window!");

    this.N = N;
    //圆心位置以及半径大小
    Circle circle = new Circle(sceneWidth/2, sceneHeight/2, sceneWidth/2);
    data = new MonteCarloPiData(circle);

    // 初始化视图
    EventQueue.invokeLater(() -> {
        frame = new AlgoFrame("Monte Carlo", sceneWidth, sceneHeight);

        new Thread(() -> {
            run();
        }).start();
    });
}

run函数呢就是我们要对数据执行操作，每增加100个点我们就打印依次现在的PI值，并且使运行延迟40ms。我们的点也要生成，生成的位置设为x，y，然后再在界面中画出这个点。

public void run(){

    for(int i = 0 ; i < N ; i ++){

        if( i % 100 == 0) {
            frame.render(data);
            AlgoVisHelper.pause(DELAY);
            System.out.println(data.estimatePi());
        }

        int x = (int)(Math.random() * frame.getCanvasWidth());
        int y = (int)(Math.random() * frame.getCanvasHeight());
        data.addPoint(new Point(x, y));
    }

}

最后呢我们要对界面的类进行数据操作：

private MonteCarloPiData data;
public void render(MonteCarloPiData data){
    this.data = data;
    repaint();
}

并且在我们的绘画中我们实际的绘制为，意思使我们先确定绘制的粗细，然后选择绘制圆的颜色，随后呢我们在for循环中绘制points,如果圆中包含，我们就绘制红色，不包含就就绘制绿色，并且绘制的圆为实心大小为3个像素点：

AlgoVisHelper.setStrokeWidth(g2d, 3);
AlgoVisHelper.setColor(g2d, AlgoVisHelper.Blue);
Circle circle = data.getCircle();
AlgoVisHelper.strokeCircle(g2d, circle.getX(), circle.getY(), circle.getR());

for(int i = 0 ; i < data.getPointsNumber() ; i ++){
    Point p = data.getPoint(i);
    if(circle.contain(p))
        AlgoVisHelper.setColor(g2d, AlgoVisHelper.Red);
    else
        AlgoVisHelper.setColor(g2d, AlgoVisHelper.Green);

    AlgoVisHelper.fillCircle(g2d, p.x, p.y, 3);
}

基本上呢我们这样就实现了简单的PI的操作，当然随着我们测试用例数据的增大，我们的值趋向于正确。