アルゴリズム（読み）あるごりずむ（英語表記）algorithm

日本大百科全書(ニッポニカ)

アルゴリズム
あるごりずむ
algorithm

計算や問題解決の手順のこと。定められた手続に従って計算していけばいつかは答えが得られ、それが正解であることが保証されている手続である。最大公約数を求めるユークリッドの互除法などがその例。ただし計算量や記憶容量の問題を考えたときに、それが現実的に実行可能であることは意味しない。よくいわれるNP完全問題は、要素の数nに対して指数関数的に資源（計算時間や記憶容量のこと）が増加するので、計算時間が宇宙の寿命より長かったり、メモリー容量が宇宙の分子の数より大きかったりして、現実的には解けないことが多い。

　したがってアルゴリズムは正解が求められるというだけでは不足で、その計算量が問題とされる。たとえば大量のデータを整列する（大きさの順とかアルファベット順とかで並べ替える）「ソート」のアルゴリズムは、要素数nに対しnlog（n）のオーダーで計算できるものが最善であり、場合によってはn²のものも多用されている。

　人工知能（AI）などでは、ヒューリスティクスとよばれる擬似アルゴリズムが使われることが多い。これは、平均的には効率よく解を求められるが、場合によっては間違っていたり、最適の解ではなかったりすることがあるというものである。しかし、日常生活を送るうえではこれで十分なことが多い。たとえば、カーナビゲーションで経路探索を行った場合、最短経路より数％長い探索結果が出てしまうことなどは許容されるであろう（実際、交通状況に依存するので、カーナビの最短経路がもっとも早いとは限らない）。

　また、多くの都市をどの順で回れば最適かという「巡回セールスマン問題」の最適解を求めるにはn!に比例する時間がかかり、20都市程度でも現実的な計算はできない。

　一般的に計算量が膨大になる問題でも、最適解でなくてよければ、現実的に計算可能なヒューリスティクスはいくつかある。ニューラルネットワークを使って近似解を求める方法も知られている。

［中島秀之　2019年7月19日］

[参照項目] | カーナビゲーション | ヒューリスティクス | ユークリッドの互除法

出典　小学館　日本大百科全書(ニッポニカ)

ブリタニカ国際大百科事典 小項目事典

アルゴリズム
algorithm

数学や情報科学，あるいは関連する分野において，有限回の手続きによって，問題を解決するための一定の手順。語源は，アラビアの数学者ムハンマド・イブン＝ムーサー・アル＝フワーリズミーの著書名の一部に由来するといわれている。ユークリッドの互除法は，二つの整数に対して，その最大公約数（→約数）を求める手順を与える方法であり，アルゴリズムの例である。具体的には次のように記述される。整数 a，b に対して，a を b で割った余りを r とする。このとき a，b の最大公約数は，b，r の最大公約数に等しくなるので，（a，b）を（b，r）に置き換えて同じ操作を繰り返す。余りは必ず小さくなっていくので，有限回の操作で 0になり，最終的に（d，0）となったときの d が a，b の最大公約数となる。アルゴリズムの概念を厳密に定式化する数学モデルとしてテューリング機械が知られている。アルゴリズムはコンピュータが情報処理を行なう場合の基盤となる。コンピュータにアルゴリズムを指示するための，操作の並びを記述したものがプログラムにほかならない。

出典　ブリタニカ国際大百科事典 小項目事典