日本大百科全書(ニッポニカ) 「アルゴリズム」の意味・わかりやすい解説
アルゴリズム
あるごりずむ
algorithm
計算や問題解決の手順のこと。定められた手続に従って計算していけばいつかは答えが得られ、それが正解であることが保証されている手続である。最大公約数を求めるユークリッドの互除法などがその例。ただし計算量や記憶容量の問題を考えたときに、それが現実的に実行可能であることは意味しない。よくいわれるNP完全問題は、要素の数nに対して指数関数的に資源(計算時間や記憶容量のこと)が増加するので、計算時間が宇宙の寿命より長かったり、メモリー容量が宇宙の分子の数より大きかったりして、現実的には解けないことが多い。
したがってアルゴリズムは正解が求められるというだけでは不足で、その計算量が問題とされる。たとえば大量のデータを整列する(大きさの順とかアルファベット順とかで並べ替える)「ソート」のアルゴリズムは、要素数nに対しnlog(n)のオーダーで計算できるものが最善であり、場合によってはn2のものも多用されている。
人工知能(AI)などでは、ヒューリスティクスとよばれる擬似アルゴリズムが使われることが多い。これは、平均的には効率よく解を求められるが、場合によっては間違っていたり、最適の解ではなかったりすることがあるというものである。しかし、日常生活を送るうえではこれで十分なことが多い。たとえば、カーナビゲーションで経路探索を行った場合、最短経路より数%長い探索結果が出てしまうことなどは許容されるであろう(実際、交通状況に依存するので、カーナビの最短経路がもっとも早いとは限らない)。
また、多くの都市をどの順で回れば最適かという「巡回セールスマン問題」の最適解を求めるにはn!に比例する時間がかかり、20都市程度でも現実的な計算はできない。
一般的に計算量が膨大になる問題でも、最適解でなくてよければ、現実的に計算可能なヒューリスティクスはいくつかある。ニューラルネットワークを使って近似解を求める方法も知られている。
[中島秀之 2019年7月19日]