|
(n) Monte Carlo method =========================== ・ モンテカルロ法 ： [もんてかるろほう] (n) Monte Carlo method ・ 法 ： [ほう] 1. (n,n-suf) Act (law: the X Act)
モンテカルロ法 (モンテカルロほう、Monte Carlo method, MC) とはシミュレーションや数値計算を乱数を用いて行う手法の総称。元々は、中性子が物質中を動き回る様子を探るためにスタニスワフ・ウラムが考案しジョン・フォン・ノイマンにより命名された手法。カジノで有名な国家モナコ公国の4つの地区（カルティ）の1つであるモンテカルロから名付けられた。ランダム法とも呼ばれる。 == 計算理論 == 計算理論の分野において、モンテカルロ法とは多項式時間で処理が終了されることは保証されるが、導かれる答えが必ずしも正しいとは限らない乱択アルゴリズム（ランダム・アルゴリズム）と一般に定義される〔http://www.nist.gov/dads/HTML/monteCarlo.html〕。一例として素数判定問題におけるミラー-ラビン素数判定法がある。このアルゴリズムは与えられた数値が素数の場合は確実に Yes と答えるが、合成数の場合は非常に少ない確率ではあるが No と答えるべきところを Yes と答える場合がある。 なお、これとは対照的に理論上処理の終了時間が必ずしも多項式時間で終了するとは限らないが、もし答えが得られれば必ず正しい乱択アルゴリズムをラスベガス法と呼ぶ。 計算複雑性理論では、確率的チューリング機械によるモデル化によってモンテカルロ法を用いて解決できる問題のクラスをいくつか定義している。代表的なところでは RPやBPP、PP などがある。これらのクラスと Pや NP との関連性を解明していくことによって、モンテカルロ法のようにランダム性を含むアルゴリズムによって解ける問題の範囲が拡大しているのか（P≠BPP なのか）、それとも単に決定的アルゴリズムで解ける問題の多項式時間の次数を減らしているだけなのか（P=BPP なのか）は計算複雑性理論における主要課題の1つである。現在、NP ⊂ PP 、RP ⊆ NPであることは解っているが BPP と NPとの関係は解っていない。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「モンテカルロ法」の詳細全文を読む スポンサード リンク
|