Javaで学ぶアルゴリズム 第5弾：モンテカルロ法

#Javaで学ぶアルゴリズム < モンテカルロ法 >

はじめに

Javaは授業で触れただけで全くの初心者であり，何もわかっていない．なので，基本的なアルゴリズムをJavaで実装し，アルゴリズムの理解を深めるとともに，Javaにも慣れていきたい．
その第5弾としてモンテカルロ法を扱う．

モンテカルロ法

モンテカルロというのは，「モナコ公国の首都モンテカルロ」であり，そこはギャンブルの街として有名である．数値計算のような方法ではなく，乱数を用いた一種の欠けのような方法で問題を解くことからモンテカルロ法と名付けられた．以下に例を示して，その方法を学ぶが，基本は非常にシンプルで，たくさん点をプロットして所望のところにどれだけの点がプロットされたかというのを基に答えを得るというものである．ここでは，$\pi$を求める例と楕円の面積を求める例を示す．

例①：πを求める

この図に基づいて，以下に導出過程を示す．

例②：楕円の面積

まず，色のついた1/4の面積を求めてから4倍して，楕円の面積を求める．

この図に基づいて，以下に導出過程を示す．

実装

先ほどの説明に従い，Javaでの実装を行う．以下にそれぞれの例についてソースコードとそのときの出力を示す．

ソースコード①：π

MonteCarlo_pi.java

//2020/12/16
//@Yuya Shimizu
//-----------------------------------
//*     モンテカルロ法（πの値） *
//-----------------------------------

import java.awt.*;
import java.awt.event.*;

//フレームの設定
class MonteCarlo_pi_Frame extends Frame{
    private Panel p;        //パネル用変数（図を表示する）
    private TextField tf;   //テキストフィールド用変数（出力結果を示す）
    private Button bt;      //ボタン用変数（ユーザの操作ボタン）

    public MonteCarlo_pi_Frame(){
        setSize(200, 200);//200×200の大きさでフレームを作成
        //×ボタンを押したら終了
        addWindowListener(new WindowAdapter(){
            public void windowClosing(WindowEvent e){
                System.exit(0);
            }
        });

        add(p=new Panel(), "Center");               //フレームの中央にパネルを設定
        add(tf=new TextField("", 10), "North");     //フレームの上側にテキストフィールドを設定
        add(bt=new Button("πの計算"), "South"); //フレームの下側にボタンを設定

        //ボタンの設定
        bt.addActionListener(new ActionListener(){
            public void actionPerformed(ActionEvent e){
                Graphics g = p.getGraphics();   //gにパネルpの描画権利を与える
                final int N=100000;             //今回のプロット総数
                double x, y, pi;
                int i, sum=0, px, py;

                g.clearRect(50, 10, 100, 100);  //まず，四角形（いまは正方形）をクリア
                g.drawRect(50, 10, 100, 100);   //まず，四角形（いまは正方形）を描画

                //描画した四角形の中に納まる範囲でプロット
                for (i=1; i<N; i++){
                    x = Math.random();
                    y = Math.random();
                    //円の中に含まれるものだけ実際にプロットしていく
                    if (x*x + y*y < 1){
                        px = 50 + (int)(100*x);     //条件に合うように正規化してプロットするx座標を生成
                        py = 110 - (int)(100*y);    //条件に合うように正規化してプロットするy座標を生成
                        g.drawLine(px, py, px, py); //点プロット
                        sum++;  //円の中に入ったプロット数のカウント
                    }
                }
                pi = (double)4*sum/N;   //プロット総数との割合からπを求める
                tf.setText("π="+pi);   //計算結果をテキストフィールドにセット
                g.dispose();    //gのパネルpへの描画権利を破棄　⇒　描画処理終了
            }
            });
    }
}

//クラス
public class MonteCarlo_pi{
    //メイン関数
    public static void main(String[] args){
        Frame w=new MonteCarlo_pi_Frame();
        w.show();
    }
}

出力

実行前

実行後

ソースコード②：楕円の面積を求める

MonteCarlo_ellipse.java

//2020/12/16
//@Yuya Shimizu
//---------------------------------------
//*     モンテカルロ法（面積の計算）  *
//---------------------------------------

import java.awt.*;
import java.awt.event.*;

//フレームの設定
class MonteCarlo_ellipse_Frame extends Frame{
    private Panel p;        //パネル用変数（図を表示する）
    private TextField tf;   //テキストフィールド用変数（出力結果を示す）
    private Button bt;      //ボタン用変数（ユーザの操作ボタン）

    public MonteCarlo_ellipse_Frame(){
        setSize(200, 200);//200×200の大きさでフレームを作成
        //×ボタンを押したら終了
        addWindowListener(new WindowAdapter(){
            public void windowClosing(WindowEvent e){
                System.exit(0);
            }
        });

        add(p=new Panel(), "Center");               //フレームの中央にパネルを設定
        add(tf=new TextField("", 10), "North");     //フレームの上側にテキストフィールドを設定
        add(bt=new Button("楕円の面積"), "South"); //フレームの下側にボタンを設定

        //ボタンの設定
        bt.addActionListener(new ActionListener(){
            public void actionPerformed(ActionEvent e){
                Graphics g = p.getGraphics();   //gにパネルpの描画権利を与える
                final int N=100000;             //今回のプロット総数
                double x, y, s;
                int i, sum=0, px, py;

                g.clearRect(50, 10, 100, 100);  //まず，四角形（いまは正方形）をクリア
                g.drawRect(50, 10, 100, 100);   //まず，四角形（いまは正方形）を描画

                //描画した四角形の中に納まる範囲でプロット
                for (i=1; i<N; i++){
                    x = 2*Math.random();
                    y = Math.random();
                    //楕円の中に含まれるものだけ実際にプロットしていく
                    if (x*x/4 + y*y <= 1){
                        px = 50 + (int)(50*x);      //条件に合うように正規化してプロットするx座標を生成
                        py = 110 - (int)(50*y);     //条件に合うように正規化してプロットするy座標を生成
                        g.drawLine(px, py, px, py); //点プロット
                        sum++;  //楕円の中に入ったプロット数のカウント
                    }
                }
                s = (double)4*(2.0*sum/N);  //プロット総数との割合から楕円の面積を求める
                tf.setText("楕円の面積="+s);   //計算結果をテキストフィールドにセット
                g.dispose();    //gのパネルpへの描画権利を破棄　⇒　描画処理終了
            }
            });
    }
}

//クラス
public class MonteCarlo_ellipse{
    //メイン関数
    public static void main(String[] args){
        Frame w=new MonteCarlo_ellipse_Frame();
        w.show();
    }
}

出力

実行前

実行後

どちらもそこそこ計算できている．

感想

なぜ，わざわざπにしても楕円にしても第1象限にあたる部分でのプロットの結果を用いて求めているのだろうと思っていたが，実装している中でその理由が分かった．おそらく実装しやすいからである．プロットはランダム関数による擬似乱数を用いるわけだが，デフォルトのランダム関数は0~1の正の数の範囲でのみ乱数を生成する．よって，第1象限だとこれをそのまま使うことができるということだとソースコードを見ていて気付いた．確かにこの方が分かりやすく実装もしやすいと納得できた．

参考文献

Javaによるはじめてのアルゴリズム入門　　河西 朝雄　著　技術評論社