アルゴリズムとは何か  (企業の人向けの解説)

アルゴリズムの解説

※ 2012年12月24日、テレビ東京系列で放送される「青春アルゴリズム」で、このページの内容が引用されることになりました！

アルゴリズムに挑戦してみたい方、以下のクイズを見てみましょう！

問題１　 　問題２　 　問題３　 　問題４　 　問題５

「アルゴリズム」というのは、コンピューターで計算を行うときの「計算方法」のことなんですが、広く考えれば、何か物事を行うときの「やり方」のことだと言っていいでしょう。その「やり方」を工夫して、より良いやり方を見つけよう、というのが、アルゴリズムの研究です。同じ計算を行うんだったら、いい方法でやればより速く計算できますね、ということです。

例えば、ソーティング。いくつかの数字（あるいはデータ）が並んでいるときに、これを小さい順(大きい順でも)に並べ替える操作をソーティング、あるいはソートといいます。単純な方法でソーティングのプログラムを作ると、10万個の数字のソートをするのにだいたい1分ぐらいかかるのですが、クイックソートという方法でプログラムを組むと、1/100秒くらいでソートできます。2つのプログラム、何が違うかというと、ソートを行うやり方が異なります。このやり方がアルゴリズムなのです。コンピューターの性能を上げなくても、アルゴリズムを改良するだけで
100倍,1000 倍といった高速化が期待できるのです。

具体的な例として、辞書の引き方をみてみましょう。コンピューターのディスクに辞書のデータがあって、この中から、指定した単語（「アルゴリズム」を検索するとしましょう）を探し出すという問題を考えます。まず思いつく簡単な方法は、

・辞書を頭から調べて、一つ一つの単語と「アルゴリズム」を比較する。一致したら「見つけた」

という方法。この方法は、プログラムを組むのがとても簡単です。
ただ、広辞苑第5版の項目数はおよそ23万程度だそうなので、「アルゴリズム」であれば5000回くらいの項目と比較すれば見つかりそうです。ですが、もっと後ろに載っている言葉を検索する場合には、比較の回数は20万くらいになりそうです。

さて、実際に人間が辞書を引くときには、たぶんこんな方法は使いません。普通、辞書というものはあいうえお順でソートされているので、

(1) だいたい真中をえいや、と開く

(2)
調べたい単語がそこより前あれば、そこより前の部分の、後ろにあれば後ろの部分のだいたい半分を、またえいや、と開く

(3) 調べたい単語が見つかるまで、(2)
を繰り返して、範囲を小さくして行く。

ということを行うでしょう。（この方法は、学術的には「2分探索」と呼ばれています）
コンピューターでも、こういう方法で単語を検索できます。一回、真中を開くと、調べる範囲がだいたい半分に減るので、真中を開く回数は、単語数を
n とすると、log_2 n 回になります。広辞苑の23万単語の場合は、18回、真中をえいや、と開けば、調べたい単語が出てきます。簡単なほうは
23万回の参照、こちらは 18 回。1万倍くらい違います。
広辞苑の例だと、どちらも1秒未満で計算が終わるので、見た目にはどっちも同じように見えます。ですが、もっと時間のかかる計算だったらどうでしょう。例えば、インターネット検索など。ホームページは日本だけでも1億程度はあるようです。これを簡単なほうで検索すると
1億回。1時間はかかるでしょう。2分探索のほうは30回程度ですから、替わらず1/1000秒以下で終わります。計算の規模が大きくなれば、アルゴリズムの工夫で、こんなにも差が開くのです。

逆に考えると、今一週間かかる計算が、ひょっとしたらアルゴリズムを工夫したら、1分で解けるようになるかもしれない、ということでもあります。最近のスーパーコンピューターを1億円くらいで買っても、パソコンの1万倍くらいしか速くなりませんから、なにかしらの計算の工夫でスーパーコンピューターを買うのと同じ効果が得られるかもしれないのです。そのために、いろいろな計算が（プログラムの書き方を変えただけで）どこまで高速に計算できるのか、また、高速に計算できる場合は、どんな性質を満たすのか、そんなことを研究するのが、アルゴリズムの研究なのです。

実際、世の中のソフトウェアや計算が全て早くなるわけではありません。しかし、中には改良できるものもあるはずです。どのような計算が、どういう方法で速くなるか、それを、新しいアルゴリズムを作ることによって研究するのが私の研究です。上記の例で述べたような、簡単に改良できるようなソフトウェアに関しては、もはや研究はしつくされています。しかし、もう少し込み入ったソフトに関しては、まだまだ改良の余地はあります。

最近は IT
ブームで、いろいろなことをするソフトが出てます。データベースをいじるソフト、検索をするソフト、工程表や勤務表、スケジュールを作成するソフト、最短経路、配送ルートを探索する（ナビゲーションソフト）ソフトなど、多くのソフトがあります。時間のかかるものもありますし、時間がかかるゆえに、機能を削減しているものもあるでしょう。それらのソフトを改良する可能性が、アルゴリズム研究には秘められているのです。

これら、大規模で時間のかかるソフトは、企業ベースで使われているものが多いです。例えば、ここで解説をしているスケジューリング問題や配送計画、生産計画などです。その他にも、勤務表作成問題、割当問題、施設配置問題、時間割作成問題、板取問題など、多くのものがあります。しかし、現在のところ、これら大規模な問題を解くソフトウェアというものは、あまり存在していません。コスト削減の可能性のある分野がまだ未開拓なわけです。これからの研究と開発が期待されるところです。

宇野毅明のホームページへ
情報学研究所のホームページへ