スタッフBLOG

おはようございます、本日のブログ当番、新人プログラマM.I.です。
今日は楽に書けるアルゴリズムの話をします。

2次元の高さマップがここにあります。



明るいところが高い地点で暗いところが低い地点とします。

この中で最も高い地点を探すという問題を考えてみます。

素直にやると画素数の分すべて探し、その中で最高の点を出す、という実装になるだろうと思われます。
これだと画素数が増えると計算量が増えますし、この問題のように2次元の問題ならいいのですが、さらに高次元の問題だと計算時間がどんどん伸びてしまう次元の呪いという問題が出てきます。

この問題を解決する方法のひとつがモンテカルロ法です。
乱数を使って正しい値の近似値を探すアルゴリズムです。
先ほどの問題をモンテカルロ法で解いてみましょう。

といっても手順は簡単です。
「ランダムに場所を選ぶのを数回繰り返して、その中で最高の値を出す」
ただそれだけです。
長所としてはほとんど何も考えなくても計算時間を減らせますし、ある種の面倒な問題もそれなりの精度が出せます。
欠点としては一様な分布の乱数を選ばないと選ぶ点に偏りが出たりすること。
試行回数を上げても精度が余り上がらないことがあります。



赤い点が選ばれた点、9回の試行で偶然にも高い位置を選んでいます。

似たようなアルゴリズムに準モンテカルロ法があります。
「集合の要素をいくつか飛ばして見ていき、その中で最大のものをとる」
という乱数を使わないアルゴリズムです。
1つ飛ばしで探すと半分の計算、2つ飛ばすと1/3の計算で済み、選ぶ場所が偏らなくなるという利点もあります。



赤い点が選ばれた点、1つ飛ばしで選んでいます。

しかしながらこのアルゴリズムも次元の呪いの影響を受けます。

扱う問題にあわせ柔軟にアルゴリズムを切り替えられるのが敏腕プログラマーということなんでしょうね。
これからも精進していきたいものです。