トップ > 最適化とは > アルゴリズム

アルゴリズム入門

アルゴリズムとは日本語では処理手順のことを言います。汎用数理計画法パッケージ Numerical Optimizer が 色々な問題を解くことができるのは様々なアルゴリズムがプログラムされているからです。ここでは 数理計画法・最適化の仕組みを理解する上で必要な情報を分かりやすくご説明致します。 あくまで入門的な位置づけですので数学的に厳密な説明を行う訳ではございませのでご了承ください。

数理計画法で代表的なアルゴリズムについての簡単な解説

アルゴリズムの説明

アルゴリズムの説明を具体例を見ながら行いたいと思います。

例題

8 枚の金貨を袋に入れた金貨セットを 1000 袋販売します。 袋に 8 枚の金貨を入れる作業をある業者に依頼したのですが、 その業者は 1 袋あたり 1 枚の偽造金貨を混入させました。業者を逮捕し、 横領した合計 1000 枚の本物の金貨を押収したのですが、それぞれの袋の偽金貨 を取り出し本物を 1 枚入れるという作業をする羽目になりました。偽造金貨は本物の 金貨よりも微妙に軽いことが調べから分かっています。 道具は天秤 1 つです。8 枚の金貨から偽金貨を特定する方法を考えてください。 偽コイン発見問題

アルゴリズムの作成例

この問題の場合にアルゴリズムは "必ず誰がやっても成功するマニュアル" のようなもの であると言えます。

<アルゴリズム>
金貨を 4 枚ずつに分けて天秤で比較する
軽い方の 4 枚を 2 枚ずつに分けて天秤で比較する
さらに軽いほうの 2 枚を 1 枚ずつに分けて天秤で比較する
最後に軽いほうが偽物の金貨!

偽コイン発見アルゴリズム

アルゴリズムの工夫

上で作成したマニュアル(アルゴリズム)に沿って金貨の詰め替え作業を行っているが、締め切りが 迫ってきてしまいました。作業員を追加で投入しても、結局天秤が一つしかないので 作業ははかどりません。そこでマニュアル(アルゴリズム)を見直すことにしました。

<新アルゴリズム1>
金貨を 3 枚ずつ天秤で比較する
天秤が釣り合えば <CASE A> へ、釣り合わなければ <CASE B> へ

・CASE A
天秤に乗せなかった 2 枚のうち 1 枚が偽物であるのでもう一度天秤にかけて終了

・CASE B
軽かった 3 枚から 1 枚ずつを天秤にかける。釣り合った場合は残りが偽物、釣り合わなければ軽い方が偽物

偽コイン発見新アルゴリズム

なんとこの新アルゴリズムでは一袋あたりの天秤の利用回数を 1 回減らすことが出来、 2 回使うのみで判別できるようになります。 これで全体の処理スピードが 1.5 倍に上がり、締め切りまでになんとかなりそうです。
ここで以下の新たなアルゴリズムを提案する者が現れました。

<新アルゴリズム2>
金貨を 1 枚ずつ天秤で比較する
天秤が釣り合わなければ即終了、釣り合った場合は両方本物
釣り合わなかった場合は残りの金貨から 1 枚ずつ天秤で比較する
天秤が釣り合わなければ終了、釣り合った場合は両方本物
...

このアルゴリズムを提案した者はこのように主張しました。

「運が良ければ 1 度の試行で終了だから新アルゴリズム1より性能が よいのではないか!?」

この者の主張はそういう場合もあるし、そうでない場合もあるということになります。 アルゴリズムとして安定していないわけですので、ひとつの賭けです。 アルゴリズムを構築するときには "ある条件(この場合勘が冴えている)のときにだけ速い" というのは好ましくありません。平均的な速度 最悪のケースの速度 を 見積りながらアルゴリズムは構築するものです。 偽コイン発見新アルゴリズム2


おまけ

問題の条件を少し変えて考えてみましょう。これまでは天秤は一台しかありませんでしたので、 その一台をどのように効率的に利用できるかという点がアルゴリズムの 評価そのものでした。では、天秤が無限(コインが 8000 枚なので 4000 台あれば十分)で作業する人間も 十分にいたとします。この場合の一番最速なアルゴリズムはどうなるでしょう。 4000 人の作業員が、それぞれコインを 2 枚ずつ手に取り、皆で一斉に天秤で重さを比較すればそれで 終了です。当然 4000 人が一気に作業するスペースが必要ですので、込み合って時間が かかる可能性もありますし、そもそも 4000 台の天秤を並べるだけでも大変そうです。
これは実際のプログラムのアルゴリズムに例えると、利用してよいメモリ領域の大きさ や、同時に利用できるプロセス数にあたります。そういった条件によってもアルゴリズムの 評価は変わっていくものなのです。

アルゴリズムまとめ