top page > computer > haskell > web_lecture > for_programmer > about_montecarlo.html
更新日:
文責: 重城良国

モンテカルロ法の説明

はじめに

ここまで学んできた知識だけでできる例題だ。

モンテカルロ法とは

多項式時間で処理が終了するが答えの正しさが保証されない乱択アルゴリズムだ。カジノで有名なモナコ公国の地区にちなんでモンテカルロ法と呼ぶ。正確な答えを得るのに時間がかかりすぎる問題への近似的なアプローチとして有用だ。

ウィキペディア: モンテカルロ法

円周率を求める

円周率の計算には効率の良い方法があるので本当はモンテカルロ法を使う必要はない。

半径1の円の面積

半径1の円の面積は円周率と等しい。

[半径1の円の面積] = 1 * 1 * [円周率]

モンテカルロ法で円の面積を求める

1辺が2の正方形内に半径1の円を描く。正方形内のランダムな点について円の内側にあるか外側にあるかを調べる。調べた点の数と円の内側にある点の数の比が正方形と円の面積の比にほぼ等しくなると予想できる。正方形の面積は4なので以下の近似式が成り立つ。

[円周率] = 4 * [円内の点] / [全ての点]

[点の数が100のときの図] [点の数が1000のときの図] [点の数が10000のときの図]

点の数を100, 1000, 10000とふやすと確率的に正しい値に近づく。

「無限リスト」へもどる 「2種類の整数型」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics