アルゴリズム (英 : algorithm [注 1] )とは、解 が定まっている「計算可能 」問題に対して、その解 を正しく求める手続きをさす[注 2] 。あるいはそれを形式的に表現したもの。
実用上は、アルゴリズムの実行に要する記憶領域の大きさや完了までに要する時間(空間計算量と時間計算量 )が小さいこと、特に問題の規模を大きくした際に必要な記憶領域や計算量が急激に大きくならないことが重要となる。
アルゴリズムの実行は形態によらない。コンピュータプログラム はコンピュータ 上に実装されたアルゴリズムの例である。
概要 フローチャート はアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。岩波 国語辞典「算法」に、まず「計算の方法」とした後に2番目の詳細な語義でalgorithmの訳として、
特に、同類の問題一般に対し、有限回の基本的操作を、指示の順を追って実行すれば、解がある場合にはその解が得られ、解がない場合にはそのことが確かめられるように、はっきりと仕組んである手順。
とある。一見では国語辞典らしい平易な日本語で書かれた説明だが、例えば解が無いと無限ループ に陥るといったようなものは除外されるし、「アルゴリズムの視覚的表現」としてよく使われるフローチャート のようなもので書いてあっても、基本的操作がはっきりと書いてなければそれはアルゴリズムではない、というわけである。これは、#形式化 の節で述べるような、理論計算機科学 での「アルゴリズム」の扱いに沿っている。
歴史 記録に残る最古のアルゴリズムは、エウクレイデス の原論 のものである。その中でも、二つの整数の最大公約数 を求めるユークリッドの互除法 [1] は、典型的なアルゴリズムとして知られている。
「アルゴリズム」という名称は、現在のイラク のバグダード における9世紀の数学者アル=フワーリズミー [注 3] の名前から来ているといわれている。彼がインド数学 を紹介した著作『インドの数の計算法』(825年 )が、12世紀にチェスターのロバート (あるいはバースのアデラード )によってラテン語に翻訳され、『algoritmi de numero Indorum アルゴリトミ・デ・ヌーメロ・インドルム』[2] (直訳すると「インドの数におけるアルゴリトミ」)という題で、以後500年間にわたってヨーロッパ各国の大学で数学の主要な教科書として用いられた。この書は、冒頭に「algoritmi dicti (アル・フワリズミーに曰く)」という一節があるので『algoritmi ( アルゴリトミ ) 』と呼ばれていた。
1920〜30年代、計算可能性のための数学モデル(計算モデル )がいくつも提案された(チューリングマシン 、帰納的関数 、ラムダ計算 など)。後にこれらの定義はすべて同等であることがわかり、それらにより同値な概念を「計算可能」とすることが提案された(チャーチ=チューリングのテーゼ 、提案者はスティーヴン・コール・クリーネ 。なお、チューリング のほうを先とする専門家もいる)。したがって、現在では「これらによって『計算可能なもの』を計算する手続き」をアルゴリズムと呼ぶ。
形式化 ここではまず非形式的にアルゴリズムについて述べた後で、停止性など形式的(フォーマル)な議論を続ける。
アルゴリズムはコンピュータ が情報を処理する基盤である。すなわち、プログラム は本質的にはアルゴリズムであり、コンピュータが特定のタスク(従業員の給与計算、学生の成績表の印刷など)を(指定された順序で)実行するためのステップをコンピュータに指示する。したがって、アルゴリズムはチューリング完全 なシステムで実行可能な操作の並びとみなすこともできる。
…チューリングの命題についての非形式的な論証から、より強い命題が正当化される。すなわち、全てのアルゴリズムはチューリング機械でシミュレート可能である…Savage [1987] によれば、アルゴリズムはチューリング機械によって定義される計算過程である。
[3] アルゴリズムは情報処理 と結びついていることが多く、データは何らかの入力源(機器)から読み込まれ、結果は何らかの出力先(機器)に書かれるか、次の処理の入力となるよう保持される。保持されたデータはアルゴリズムを実行する実体の内部状態の一部とみなされる。実際、コンピュータでは状態をデータ構造 に保持したりする。
このような計算過程について、アルゴリズムは厳密に定義されなければならず、ありうる全ての状況に適用可能な形で指定される。すなわち、どのような条件のステップでも、ケースバイケースで体系的に扱わなければならず、各ケースの扱い方は明確で(計算可能で)なければならない。
アルゴリズムは明確なステップの明確なリストなので、その計算順序は最も重要である。命令列は、先頭から最後尾に向かって逐次的に実行されるよう記述される。この考え方をより形式的にしたものが制御構造 である。
以上の説明は、命令型プログラミング を前提としてアルゴリズムを定式化する場合である。これは、最も典型的な概念であり、タスクを離散的かつ機械的なものとして表すものである。その場合に特有の操作として、変数に値を設定する「代入」がある。これは、直観的にはメモリをメモ帳のようなものとみなすところから生まれた。
これ以外のアルゴリズムの概念化として、関数型プログラミング や論理プログラミング がある。
アルゴリズムの記述 プログラマは擬似コード などを使うことが多いが、理論計算機科学 での形式的[注 4] で厳密[注 5] な議論には計算モデル を使う。もちろん相互に得失があり、必要であれば互いにどちらも使う。
停止性 アルゴリズムは最終的に必ず停止しなければならないとする定義もある。というより形式的で厳密な議論では停止するものだけがアルゴリズムである(チャーチ=チューリングのテーゼ も参照)。
そのため、そうでないものと呼び分ける必要があることもあり、クリーネ は停止性のあるアルゴリズムを「decision procedure for the question 」「decision method for the question 」「algorithm for the question 」とした[4] 。停止しない可能性のある手続きについては、クヌース は「computational method 」[5] と呼び、クリーネは「calculation procedure 」「algorithm 」[4] と呼んでいる。
ミンスキー は、(特定の状態から開始された)アルゴリズムの停止性について次のように述べている。
しかしもし実行中のプロセスの長さが不明ならば、それを試すことは得策ではないかもしれない。何故なら、もしプロセスが永遠に続くなら、我々は答えを得られないかもしれないのだから。
[6] アラン・チューリング が停止性問題 として提起したとおり、任意のプロシージャと初期状態が与えられたとき、それが停止するかどうかを判定するアルゴリズムは存在しない(この前半を「任意のアルゴリズムと初期状態が」としてはいけない。この記事の他の部分では完全に混用されているが、この文の後半の「アルゴリズムは」という表現は、必ず停止するもののみを指してそう言っているのだから。せめて1文の中では混用はまずい)。
不完全な(あるいは間違った)アルゴリズムは、次のいずれかの結果となる。
停止しない。 解の範囲を逸脱した値を返して停止する。 誤った解を返して停止する。 解を返さずに停止する。 これらの組合せ。 クリーネはこれらをアルゴリズム内で検出してエラーメッセージを返すか、可能ならば無限ループに入らせることを提案した[4] 。また、結果が真理値である場合についてクリーネは第三の論理記号「 u {\displaystyle u} 」[注 6] を使うことも提案している[4] 。そうすれば、命題を扱うアルゴリズムで何らかの値を常に生成できるとした。誤った答えを返す問題は、帰納法を使ったアルゴリズムに関する個別の「証明」で解決される。
通常、これ(アルゴリズムが
μ再帰関数 を正しく定義しているかという問題)には補助的な証拠を必要とする。それは例えば、個々の引数の値について、計算が一意な値で終了するかという帰納的証明の形式で示される。
[6] その他の表現 アルゴリズムには様々な記法があり、自然言語 、擬似コード 、フローチャート 、プログラミング言語 などがある。アルゴリズムの自然言語表現は冗長であいまいになる傾向があり、複雑なアルゴリズムや技術的な場面では単独ではほとんど使用されない。擬似コードやフローチャートはアルゴリズムを構造的に表現でき、自然言語のようなあいまいさもほとんどない。プログラミング言語でアルゴリズムを示すこともよくある。
アルゴリズムの記述は、例えばチューリング機械 を使ったならば、として次の3つに分類している書籍などがある[7] 。
高レベルな記述 自然言語でアルゴリズムを説明したもの。実装の詳細は省かれている。このレベルでは、チューリング機械のテープやヘッドの動きまでは説明しない。 実装レベルの記述 チューリング機械のヘッドの動きやテープへのデータ格納方法を自然言語で説明する。このレベルでは機械の状態や遷移関数の詳細は説明しない。 (以上の2つのような内容では、そもそも概要で説明したように「はっきり」していない可能性もあるし、詳細が無ければ無限ループに陥らないことを証明することもできない。従ってそもそも実際には「アルゴリズムを記述」してはいない)
形式的記述 チューリングマシン#形式的な定義 を参照。実装 多くのアルゴリズムは、コンピュータプログラム として実装されることを意図している。しかし、アルゴリズムの実装手段はほかにもあり、電気回路 で実装したり、機械で実装したりすることもある。人間が算術 を覚えるのも、脳 内の神経網にアルゴリズムが実装されたものと見ることもできる。
例 簡単なアルゴリズムの例として、(整列されていない)有限長の数列(リスト)に含まれる(大きさが一定値以下の整数の)最大の数を見つけ出すアルゴリズムを考える。ここでは、リストに含まれる全ての数を調べる必要があるが、一度に調べらることができるのは1つだけであるとする。ここから得られるアルゴリズムを、日本語で記述すると次のようになる。
概念的記述 最初の要素(数)が最大と仮定する。 残りのリスト上の数を順に見ていき、最大の数よりも大きい数が見つかったら、それを新たな最大として記憶する。 最後に記憶した数がそのリストでの最大の数であり、これで処理が完了する。 次に、プログラミング言語的にやや形式的に記述すると、次のような擬似コード になる(「←」は代入を表し、「return 」はその後に記された値を返してアルゴリズムが終了することを意味する)。
擬似形式的記述 入力: 空でない数リスト L 、出力: リスト L 内の最大(largest )の数。
algorithm 最大値を求める is largest ← L0 for each item ∈ リスト L≧1 do if largest < item then largest ← item end end return largest end
アルゴリズム解析 あるアルゴリズムの実行に必要な計算資源(時間や記憶領域)の量を見積もることは重要である。そのような量を定量的に求める分析法はアルゴリズム解析 と呼ばれ、研究がなされてきた。例えば、上記のアルゴリズムの実行に必要な時間はリストの長さを n {\displaystyle n} とするときO記法 を用いて表せば O ( n ) {\displaystyle O(n)} となる。このアルゴリズムでは、(与えられたリスト以外には)常に(その時点での最大の数と、現在見ているリスト上の位置)2つの値だけを記憶しておけばよい。したがって、必要となる記憶領域の量は O ( 1 ) {\displaystyle O(1)} となるが、リストの長さn を記憶して入力として与える場合にはそのための領域も含めるとすると O ( log n ) {\displaystyle O(\log n)} になる。
同じ問題であっても、アルゴリズムが異なれば、必要とする時間や記憶領域の量も異なる。例えば、ソート には様々なアルゴリズムがあり、それぞれ必要な時間や記憶領域の量が異なる。
アルゴリズム解析 は計算機科学 の一部であり、特定のプログラミング言語 や実装を前提とせずに、抽象的に解析を行うことも多いが、特定のプログラミング言語や実装を前提として、具体的に解析を行うことも多い。これは、アルゴリズムの様々な属性に注目した他の数学的分野とも共通する。
分類 アルゴリズムには様々な分類方法があり、それぞれに利点がある。
実装による分類 アルゴリズム分類の1つの方法として、実装手段による分類がある。
再帰 / 反復 再帰アルゴリズムは、ある条件が成り立つまで自身を再帰的に呼び出すものであって、関数型言語 でよく使われる。反復 アルゴリズムは、ループのような反復構造と場合によってはスタック などのデータ構造 を補助的に使い、問題を解く。一部の問題は、どちらか一方の実装が自然である。例えば、ハノイの塔 は再帰的実装の方が分かりやすい。再帰アルゴリズムは全て反復アルゴリズムでも実装可能であり、逆も同じである(ただし、複雑さは変化する)。 論理 アルゴリズムは、制御された演繹 であるとも言われる。これを アルゴリズム = 論理 + 制御 と表現することもある[8] 。論理部分は計算で使われる公理を表し、制御部分は公理に演繹が適用される方法を決定する。これは論理プログラミング というパラダイムの基本である。純粋な論理プログラミングでは、制御部分が固定されていて、アルゴリズムは論理部分だけで指定される。この手法の魅力は、プログラム意味論 的なエレガントさがある点である。公理の変化は定式化されたアルゴリズムの変更を伴う。 逐次 / 並列 / 分散 アルゴリズムは通常、コンピュータが一度に1つのアルゴリズム内の1つの命令だけを実行するものと仮定して議論される。このようなコンピュータは、シリアル・コンピュータなどと呼ばれることもある。そういった環境向けに設計されたアルゴリズムは逐次アルゴリズムと呼ばれ、それとは対照的な分類として並列アルゴリズム や分散アルゴリズム がある。並列アルゴリズムは、複数のプロセッサが同時並行して同じ問題を解くのに使えるコンピュータアーキテクチャ で有効である。また、分散アルゴリズムは、複数のマシンがコンピュータネットワーク で相互接続された環境で使われる。並列/分散アルゴリズムは、問題を分割して解き、その結果を集めて最終的な結果を得る。その場合、個々のプロセッサの計算時間(実行命令数)だけでなく、プロセッサ間の通信オーバーヘッドも計算資源 の消費量として問題になる。例えば、ソート アルゴリズムは効率的に並列化できるものもあるが、通信オーバーヘッドは高くつく(部分数列をソートした結果を集めるには、結局部分数列そのものをやりとりしなくてはならない)。反復アルゴリズムは一般に並列化可能である。並列アルゴリズムがない問題は、本質的に逐次的な問題である。 決定性 / 非決定性 決定性アルゴリズム では解法の全ステップが常に正確に決定されるが、非決定性アルゴリズムはいわば推量や推測で問題を解くものであり、ヒューリスティクス を使ってより正確に推測する。正解 / 近似解 一般にアルゴリズムは正解を得るものだが、近似アルゴリズム は近似解を求め、その近似性に一定の根拠があれば、これも広義のアルゴリズムとして含めて考えることができる。近似には、決定性の戦略もあれば、乱択の戦略もある。多くの難しい問題では、近似アルゴリズムしか実用的な解法が存在しない。近似アルゴリズムはその近似解の近似性能も評価・保証などがされる必要がある。 設計パラダイムによる分類 別の分類方法として、アルゴリズムの設計方法論やパラダイムで分類する方法がある。それぞれ異なるいくつかのパラダイムが存在する。さらに、個々のパラダイムの中にも様々な異なる形式のアルゴリズムが含まれている。以下に主なパラダイムを挙げる。
分割統治法 分割統治法は、問題を(通常再帰的 に)複数または単一の同じ種類のもっと小さい問題に還元していき、最終的に容易に解ける程度の大きさにする。分割統治の例としてはマージソート がある。ソートは入力データを分割してそれぞれに対して行われ、統治フェーズではそれらの結果をマージする。分割統治法を単純化したものとして decrease and conquer algorithm がある。これは、問題を全く同じ複数の部分問題に分割し、その解をより大きな問題を解くのに利用する。分割統治法では一般に分割された個々の部分問題は全く同じではないため、統治フェーズは decrease and conquer algorithm よりも複雑になる。decrease and conquer algorithm の例として二分探索 がある。 動的計画法 部分問題の最適解から全体の最適解が得られるような構造の問題や、同じ部分問題の最適解が様々な問題の解法に有効であるような問題の場合、動的計画法を使って既に計算済みの解を再計算するのを避けることができ、解法を効率化できる。例えば重み付けのあるグラフ での最短経路を求める場合、始点に隣接する全ての頂点について最短経路が分かっていれば、容易に最短経路が求められる。動的計画法とメモ化 は密接な関係がある。分割統治法との違いは、分割統治法では部分問題は多少なりとも独立しているのに対して、動的計画法では部分問題が重複している。単純な再帰との違いは、再帰部分をキャッシュ化またはメモ化する点である。部分問題が互いに独立している場合、メモ化は何の役にも立たない。したがって、動的計画法はあらゆる複雑な問題の解法とはならない。動的計画法では、メモ化あるいは既に解かれた部分問題の表を使うことによって、指数関数的性質をもつ問題を多項式レベルの複雑性 に削減することができる。 貪欲法 貪欲法は動的計画法 に似ているが、部分問題の解を各段階では知る必要がないという点が異なる。その代わりに、各時点で最もよい選択と思われるものを選んでいく。貪欲法では、それまでの選択と現時点の局所最適解から最適と思われる解を構築していくのであって、考えられるあらゆる解を評価することはない。したがって網羅的ではなく、必ずしも正解にたどり着けるわけではない。しかし、性能は非常によい。貪欲法としてよく知られている例として、最短経路木 を求めるクラスカル法 、プリム法 、ダイクストラ法 などがある。 線型計画法 線型計画法で解ける問題では、制約条件として入力に関する線型の不等式 があり、入力に関するある線型の関数を最大化(または最小化)する値の組合せを求めるものである。有向グラフ に関する最大フロー問題 など、多くの問題が線型計画問題として記述でき、シンプレックス法 などの汎用アルゴリズムで解くことができる。線型計画法の解空間を整数 に限定したものを整数計画法と呼ぶ。 還元 この技法は、難しい問題をほぼ最適なアルゴリズムが既知の別の問題に変換するものである。例えば、ソートされていない数列から中央値を求める選択アルゴリズム として、まずその数列をソート し、そこから真ん中に位置する値を取り出すという方式がある。 探索 と数え上げチェス の手を考えるなどといった問題は、グラフ 問題としてモデル化できる。そのような問題では、比較的よく研究されているグラフ探索アルゴリズムを使うことができる。このカテゴリーには、探索アルゴリズム 、分枝限定法 、バックトラッキング も含まれる。確率的パラダイムとヒューリスティクス ここに分類されるのは広義のアルゴリズム、ないし、遺伝的アルゴリズム のように(名前に反して)アルゴリズムではないものである。乱択アルゴリズム - 選択を無作為(あるいは擬似無作為)的に行う。問題によっては、無作為性 をもった解法が最も性能がよいと証明されているものもある。遺伝的アルゴリズム - 生物の進化 過程をまねた手法で解を求めるもの。無作為な突然変異を加えて、次世代の解を生成していく。自然淘汰と自己複製をエミュレートしているものと看做す視点から「遺伝的」という命名がされた。ヒューリスティクス - 計算資源 が限られている状況での近似解を求めることを目的としている。正解を求めるのには適さない。例えば、局所探索法 、タブーサーチ 、焼きなまし法 といった、何らかの無作為性を導入して確率的に解を発見しようとするアルゴリズムがある。例えば焼きなまし法という名前は、冶金学の焼きなまし に由来する。加熱と冷却によって金属結晶の欠陥がなくなるように、無作為性を与えて局所的な最適解に陥るのを防ぎ、徐々に無作為性を小さくすることによって最終的に1つの解に落ち着くという手法である。 研究分野による分類 科学のどんな分野にも固有の問題があり、効率的なアルゴリズムが必要とされている。ある分野の問題はまとめて研究されることが多い。そのような分類として、探索アルゴリズム 、ソートアルゴリズム 、マージアルゴリズム 、数値アルゴリズム 、グラフアルゴリズム 、文字列アルゴリズム 、計算幾何アルゴリズム 、組合せアルゴリズム 、機械学習 、暗号理論 、データ圧縮 アルゴリズム、構文解析 などがある。
各分野はオーバーラップしており、ある分野でのアルゴリズムの進歩が、時には全く異なる分野での改善につながることがある。例えば、動的計画法は、本来、産業における資源消費の最適化のために発明されたが、現在では様々な分野での各種問題に適用されている。
計算量による分類 アルゴリズムは、入力長に対する計算時間で分類される。あるアルゴリズムは入力長に対して線形時間で完了する。また別のアルゴリズムは指数時間以上かかるし、場合によっては完了しないこともある。さらに、問題によっては計算量の異なる複数のアルゴリズムが存在するし、効率的なアルゴリズムが全く知られていない問題もある。問題によっては、別の問題への写像が存在する。以上のようなことから、計算量による分類は、アルゴリズムについてではなく、問題について行うのが適当とされている。つまり、問題を解く最善のアルゴリズムの計算量に基づいて、問題を分類する。
計算能力による分類 アルゴリズムは計算能力によっても分類される。一般にアルゴリズムは計算能力によって階層的に分類される。「再帰的クラス」とは、全てのチューリング計算可能関数についてのアルゴリズムを含むクラスである。このような階層化によって、計算に必要とされる計算資源 (時間とメモリ)を制限できる可能性が生じる。「部分再帰クラス」は、全てのチューリング計算可能な関数を得ることはできない。例えば、多項式時間 で実行されるアルゴリズムには多くの重要な計算が含まれるが、チューリング計算可能な関数全体を含むことはない。原始再帰関数 で実装されるアルゴリズムのクラスは、別の部分再帰的クラスの例である。
Burgin (2005, p. 24)[9] は、関数を計算するアルゴリズムは有限ステップ後に必ず出力が決定されなければならないという一般的条件を緩めたアルゴリズムの汎用的定義を行った。彼は「超再帰的クラス」を「チューリングマシンで計算可能でない関数を計算可能なアルゴリズムのクラス」と定義した(Burgin 2005, p. 107)[9] 。これはハイパーコンピュータ の手法の研究と密接に関係している。
法的問題 特許 アルゴリズム自体は一般に特許化できない。アメリカ合衆国 では、抽象概念、数、信号の単純な操作だけから成る請求項は「プロセス」を構成しないとされるので[10] 、アルゴリズムは特許化できない。
しかし、アルゴリズムの具体的応用は特許化可能な場合がある。例えば、Diamond v. Diehr のケースでは、単純なフィードバック アルゴリズムを使った合成ゴムの硬化処理が特許として認められた。
データ圧縮 アルゴリズムの分野では、ソフトウェア特許が論争の元になることが多く、例えばユニシス のLZWアルゴリズムの特許問題 が有名である。
圧縮アルゴリズムで有名な特許問題は他に算術符号も挙げられる。算術符号で取得されている特許の範囲は3点であるとされている。算術符号によって断念されたソフトウェアやファイル形式は多く、代替品が相次いで開発された。
線型計画問題 の解法であるカーマーカーのアルゴリズム は日本において特許無効審判がなされたが、2000年12月11日付けで特許庁に当該特許の放棄による特許権抹消の登録が行われたため、最終的に審判が却下された。
著作権 著作権 の観点では、日本 において著作権法 10条 3項にて明示的にアルゴリズムが同法の保護対象外であることが定められている[11] 。ただしアルゴリズムを記した文書や、アルゴリズムを実装したプログラムは著作物として保護対象となる[12] (文書やプログラムを通して「アルゴリズムが保護」されるわけではない。つまりこの文章は、アルゴリズムについて書いてあるわけではない)。
登録商標 アルゴリズム自体が保護される訳では無いが、商標の基準を満たしていればアルゴリズム名称を商標として登録することはできる。ただしアルゴリズム名称はその性質上から通常は一般名詞として通用するものであり、一般名詞と同じ語について商標の基準を満たして商標として登録しても、一般名詞の一般名詞としての(すなわちごく当然の)使用を妨げるという通念に反するような権利の濫用はできないような商標法上の制限があるため、通常の、商品名などを登録した場合と違い権利は制限される。
その他 暗号アルゴリズムには輸出規制されているものもある(アメリカでの例 )。
代表的なアルゴリズム 数学の問題に対するアルゴリズム 設計パラダイム 各分野の固有の問題に対するアルゴリズム データ圧縮 (デジタル圧縮)ファイル圧縮(ZIP)、画像圧縮(JPEG、GIF)、音声圧縮(MP3)、動画圧縮(MPEG-4、H.264)。 誤り検出訂正 リード・ソロモン符号 - 最も実用化されている誤り訂正符号の一つ。身近なところではQRコードに使われている。アルゴリズムには有限体の理論が応用されている。ターボ符号 - 第三世代携帯電話の規格や、宇宙探査機での通信などに使われている。LDPC符号 - 最も効率的な誤り訂正符号の一つ。復号法に確率伝播法 が応用されているところが特徴。実用化も進められていて、デジタルテレビの衛星通信の標準として採用されている。ページランク - Google社が開発したウェブページの重要度の判定技術脚注 注釈 出典 関連項目 計算可能性と複雑性の理論の関連 計算モデル関連 外部リンク