読み込み中...アルゴリズム
アルゴリズム（）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための効率的手順を定式化した形で表現したものを意味する。算法（さんぽう）と訳されることもある。
コンピュータにアルゴリズムを指示するための（電子）文書をプログラムという。人間より早く大量に正しい結果を導くことができるのがコンピュータの強みであるが、そのためには正しいアルゴリズムにもとづくプログラムが必要である。
歴史
記録に残る最古のアルゴリズムは、エウクレイデスの原論に載っているユークリッドの互除法であるといわれている。これは、二つの整数の最大公約数を求めるアルゴリズムである。
アルゴリズムという名称は、9世紀の現在のイラクのバグダードの数学者アル・フワーリズミー (al-Khwarizmi、الخوارزمي) の名前から来ているといわれている。彼の著作『インドの数の計算法』825年が、12世紀にチェスターのロバート（あるいはバスのアデレード）によってラテン語に翻訳され、『Algoritmi de numero Indorum』（アルゴリトミ・デ・ヌーメロ・インドルム、直訳すると「インドの数に関して」）という題で、以後500年間にわたってヨーロッパ各国の大学で数学の主要な教科書として用いられた。この書は、冒頭にある「Algoritmi dicti」（「アル・フワリズミに曰く」）の一節のため『Algoritmi』（アルゴリトミ）と呼ばれていた。
大雑把な定義
「アルゴリズム」の広く受け入れられている形式的定義はまだ存在しない。しかし、その手がかりはいくつかあり、その大まかな意味は次の引用に表されている。
人間は、何らかの記法で1つの可算無限集合の全ての元の名前を、十分に速く、あるいは長く、あるいは小さく、順に記述することはできない。しかし、特定の可算無限集合について、同程度に役に立つことはできる。例えば、任意の有限な n について、集合の n 番目の元を決定する明確な指示を与えることができる。そのような指示は極めて明示的にすることができ、計算機械が実行できる形式にもできるし、記号について初歩的な操作しかできない人が実施できる形式にもできる。「可算無限」とは、「無限にまで拡張した整数で数えられる」という意味である。つまり、ここで言うアルゴリズムは、理論的には 0 から無限大までを含む任意の整数（群）の「入力」から、出力すべき整数を「生成」する過程についての指示を「含む」ものとされている。従って例えば、y = m + n のような（2つの任意の入力変数 m と n から出力 y を生成する）代数方程式もアルゴリズムと見ることができる。実際には、アルゴリズムの意味はもっと広く、方程式の例で言うと、次のようになる。
- （計算主体が理解できる言語で書かれた）正確な指示であり、計算主体（適当な情報と機能を内包した機械や人）の動作を示した効率的な過程を表す。その過程には、任意の入力の m と n といった整数/記号や + と = といった記号を受け付けて、復号化し、妥当な時間内に出力整数 y を指定された位置に指定された形式で確実かつ効率的に生成することが含まれる。
アルゴリズムの概念は、決定可能性の概念定義にも使われる。その概念は、小さな公理群と規則群を始点として形式体系が如何に形成されるかを説明する際の重要な部分となる。論理学では、アルゴリズムが完了するまでに要する時間は、一般的な物理的次元とは関連していないため、測定できない。そのような不確実性があるため、アルゴリズムという用語を正確に定義できないという側面もある。
厳密な定義
1920〜30年代、アルゴリズムの概念を定式化する為の数学モデル（計算モデル）がいくつも提案された（チューリングマシン、帰納的関数、λ計算など）。のちにこれらの定義はすべて同等であることがわかり、チャーチはこれらの同値な概念をアルゴリズムと考えることを提案した（チャーチの提唱）。このため現在では、チューリング機械の状態遷移図（もしくはそれと等価なもの）をアルゴリズムと呼ぶ。
アルゴリズムの定式化
アルゴリズムはコンピュータが情報を処理する基盤である。すなわち、プログラムは本質的にはアルゴリズムであり、コンピュータが特定のタスク（従業員の給与計算、学生の成績表の印刷など）を（指定された順序で）実行するためのステップをコンピュータに指示する。従って、アルゴリズムはチューリング完全なシステムで実行可能な操作の並びと見做すこともできる。
…チューリングの命題についての非形式的な論証から、より強い命題が正当化される。すなわち、全てのアルゴリズムはチューリング機械でシミュレート可能である…Savage Sequential, ACM Transactions on Computational Logic, Vol 1, no 1 (July 2000), pages 77?111.
アルゴリズムは情報処理と結びついていることが多く、データは何らかの入力源/機器から読み込まれ、結果は何らかの出力先/機器に書かれるか、更なる処理の入力となるよう保持される。保持されたデータはアルゴリズムを実行する実体の内部状態の一部と見做される。実際、コンピュータでは状態をデータ構造に保持したりする。
このような計算過程について、アルゴリズムは厳密に定義されなければならず、ありうる全ての状況に適用可能な形で指定される。すなわち、どのような条件のステップでも、ケースバイケースで体系的に扱われなければならず、各ケースの扱い方は明確で（計算可能で）なければならない。
アルゴリズムは明確なステップの明確なリストであるため、その計算順序は最も重要である。命令列は、先頭から最後尾に向かって逐次的に実行されるよう記述される。この考え方をより形式的にしたものが制御構造である。
以上の説明は、命令型プログラミングを前提としてアルゴリズムを定式化する場合である。これは、最も典型的な概念であり、タスクを離散的かつ機械的なものとして表すものである。その場合に特有の操作として、変数に値を設定する「代入」がある。これは、直観的にはメモリをメモ帳のようなものと見做すところから生まれた。
これ以外のアルゴリズムの概念化として、関数型プログラミングや論理プログラミングがある。
停止性
アルゴリズムは最終的に必ず停止しなければならないとする定義もある。例えば、クリーネは停止性のあるアルゴリズムを "decision procedure or decision method or algorithm for the question" とした。停止しない可能性のある手続きについては、クヌースは "computational method"と呼び、クリーネは "calculation procedure or algorithm"と呼んでいる。
ミンスキーは、（特定の状態から開始された）アルゴリズムの停止性について次のように述べている。しかしもし実行中のプロセスの長さが不明ならば、それを試すことは得策ではないかもしれない。何故なら、もしプロセスが永遠に続くなら、我々は答えを得られないかもしれないのだから。
アラン・チューリングが停止性問題として提起した通り、任意のアルゴリズムと初期状態が与えられたとき、それが停止するかどうかを判定するアルゴリズム的手続きは存在しない。なお、アルゴリズムの停止性を解析するtermination analysisというものもある。
不完全な（あるいは間違った）アルゴリズムは、次のいずれかの結果となる。- 停止しない。
- 解の範囲を逸脱した値を返して停止する。
- 間違った解を返して停止する。
- 解を返さずに停止する。
- これらの組合せ。
- 乱択アルゴリズム - 選択を無作為（あるいは擬似無作為）的に行う。問題によっては、無作為性を持った解法が最も性能がよいと証明されているものもある。
- 遺伝的アルゴリズム - 生物の進化過程を真似た手法で解を求めるもの。無作為な突然変異を加えて、次世代の解を生成していく。つまり、自然淘汰と自己複製をエミュレートしている。遺伝的プログラミングでは、この考え方をアルゴリズム生成にまで拡大している（アルゴリズム自体を問題の解とみなす）。
- ヒューリスティクス - リソースが限られている状況での近似解を求めることを目的としている。正解を求めるのには適さない。例えば、局所探索法、タブーサーチ、焼きなまし法といった、何らかの無作為性を導入して確率的に解を発見しようとするアルゴリズムがある。例えば焼きなまし法という名前は、冶金学の焼きなましに由来する。加熱と冷却によって金属結晶の欠陥がなくなるように、無作為性を与えて局所的な最適解に陥るのを防ぎ、徐々に無作為性を小さくすることで最終的に1つの解に落ち着くというアルゴリズムである。
通常、これ（アルゴリズムがμ再帰関数を正しく定義しているかという問題）には補助的な証拠を必要とする。それは例えば、個々の引数の値について、計算が一意な値で終了するかという帰納的証明の形式で示される。
アルゴリズムの表現
アルゴリズムには様々な記法があり、自然言語、擬似コード、フローチャート、プログラミング言語などがある。アルゴリズムの自然言語表現は冗長であいまいになる傾向があり、複雑なアルゴリズムや技術的な場面では単独ではほとんど使用されない。擬似コードやフローチャートはアルゴリズムを構造的に表現でき、自然言語のようなあいまいさもほとんどない。プログラミング言語でアルゴリズムを示すこともよくある。
アルゴリズムの記述は、チューリング機械に関する記述として以下の3つに分類される。- 自然言語でアルゴリズムを説明したもの。実装の詳細は省かれている。このレベルでは、テープやヘッドの動きまでは説明しない。
- チューリング機械のヘッドの動きやテープへのデータ格納方法を自然言語で説明する。このレベルでは機械の状態や遷移関数の詳細は説明しない。
- 最も詳しい説明。チューリング機械の「状態表」を提示する。
実装
多くのアルゴリズムは、プログラムとして実装されることを意図している。しかしアルゴリズムの実装手段は他にもあり、電気回路で実装したり、機械で実装したりすることもある。人間が算術を覚えるのも、脳内の神経網にアルゴリズムが実装されたものと見ることもできる。
例
簡単なアルゴリズムの例として、（整列されていない）数列から最大の数を見つけ出すアルゴリズムを考える。ここでは、リスト上の全ての数を調べる必要があるが、一度に調べられるのは1つだけとする。ここから得られるアルゴリズムを、日本語で記述すると次のようになる。
概念的記述: # 最初の要素（数）が最大と仮定する。 # 残りのリスト上の数を順に見ていき、最大の数よりも大きい数が見つかったら、それを新たな最大として記憶する。# 最後に記憶した数がそのリストでの最大の数であり、これで処理が完了する。
次に、プログラミング言語的にやや形式的に記述すると、次のような擬似コードになる（"←" は代入を表し、"return" はその後に記された値を返し、アルゴリズムが終了することを意味する）。
擬似形式的記述: 入力: 数の空でないリスト L 出力: リスト L 内の最大（largest）の数 Algorithm LargestNumber largest ← L0 for each item in リスト L?1, do if item > largest, then largest ← item return largestアルゴリズム解析
あるアルゴリズムが必要とする計算資源（時間や記憶領域）の量を知ることは重要である。そのような定量的な値を求める手法はアルゴリズム解析と呼ばれ、研究されてきた。例えば、上記のアルゴリズムの必要とする時間をO記法とリストの長さを表す n を使って表すと O(n) となる。このアルゴリズムでは、常に2つの値だけを記憶しておけばよい（その時点での最大の数と現在見ているリスト上の位置）。従って、必要とする領域は O(1) となるが、入力となっているリスト上の要素数を数える記憶領域も含めるなら O(log n) となる。
同じ問題であっても、アルゴリズムが異なれば、必要とする時間や記憶領域の量も異なる。例えば、ソートには様々なアルゴリズムがあるが、それぞれ必要な時間や記憶領域の量が異なる。
アルゴリズム解析は計算機科学の一部であり、特定のプログラミング言語や実装を前提とせずに、抽象的に解析を行うことが多い。これは、アルゴリズムの様々な属性に注目した他の数学的分野とも共通する。一般に非常に単純化した汎用的表現として擬似コードが使われる。
分類
アルゴリズムには様々な分類方法があり、それぞれに利点がある。
実装による分類
アルゴリズム分類の1つの方法として、実装手段による分類がある。- 再帰アルゴリズムは、ある条件が成り立つまで自身を再帰的に呼び出すもので、関数型言語でよく使われる。反復アルゴリズムは、ループのような反復構造と場合によってはスタックなどのデータ構造を補助的に使い、問題を解く。一部の問題はどちらか一方の実装が自然である。例えば、ハノイの塔は再帰的実装の方が分かりやすい。再帰アルゴリズムは全て反復アルゴリズムでも実装可能であり、逆も同じである（ただし、複雑さは変化する）。
- アルゴリズムは、制御された演繹であるとも言われる。これを アルゴリズム = 論理 + 制御 と表現することもある。論理部分は計算で使われる公理を表し、制御部分は公理に演繹が適用される方法を決定する。これは論理プログラミングというパラダイムの基本である。純粋な論理プログラミングでは、制御部分が固定されていて、アルゴリズムは論理部分のみで指定される。この手法の魅力は、プログラム意味論的なエレガントさがある点である。公理の変化は定式化されたアルゴリズムの変更を伴う。
- アルゴリズムは通常、コンピュータが一度に1つのアルゴリズム内の1つの命令だけを実行するものと仮定して議論される。このようなコンピュータは、シリアル・コンピュータなどと呼ばれることもある。そういった環境向けに設計されたアルゴリズムは逐次アルゴリズムと呼ばれ、それとは対照的な分類として並列アルゴリズムや分散アルゴリズムがある。並列アルゴリズムは、複数のプロセッサが同時並行して同じ問題を解くのに使えるコンピュータアーキテクチャで有効である。また、分散アルゴリズムは、複数のマシンがコンピュータネットワークで相互接続された環境で使われる。並列/分散アルゴリズムは、問題を分割して解き、その結果を集めて最終的な結果を得る。その場合、個々のプロセッサの計算時間（実行命令数）だけでなく、プロセッサ間の通信オーバーヘッドもリソース消費量として問題になる。例えば、ソートアルゴリズムは効率的に並列化できるものもあるが、通信オーバーヘッドは高くつく（部分数列をソートした結果を集めるには、結局部分数列そのものをやりとりしなくてはならない）。反復アルゴリズムは一般に並列化可能である。並列アルゴリズムがない問題は、本質的に逐次的な問題である。
- 決定的アルゴリズムでは解法の全ステップが常に正確に決定されるが、非決定的アルゴリズムは言わば推量や推測で問題を解くもので、ヒューリスティクスを使ってより正確に推測する。
- 多くのアルゴリズムは正確な解を得るものだが、近似アルゴリズムは真の解に近い近似値を探す。近似には決定性の戦略もあれば、乱択の戦略もある。多くの難しい問題では、近似アルゴリズムしか実用的な解法が存在しない。
設計パラダイムによる分類
別の分類方法として、アルゴリズムの設計方法論やパラダイムで分類する方法がある。それぞれ異なるいくつかのパラダイムが存在する。さらに、個々のパラダイムの中にも様々な異なる形式のアルゴリズムが含まれている。以下に主なパラダイムを挙げる。- 分割統治法は、問題を（通常再帰的に）複数または単一の同じ種類のもっと小さい問題に還元していき、最終的に容易に解ける程度の大きさにする。分割統治の例としてはマージソートがある。ソートは入力データを分割してそれぞれに対して行われ、統治フェーズではそれらの結果をマージする。分割統治法を単純化したものとして decrease and conquer algorithm がある。これは、問題を全く同じ複数の部分問題に分割し、その解をより大きな問題を解くのに利用する。分割統治法では一般に分割された個々の部分問題は全く同じではないため、統治フェーズは decrease and conquer algorithm よりも複雑になる。decrease and conquer algorithm の例として二分探索がある。
- 部分問題の最適解から全体の最適解が得られるような構造の問題や、同じ部分問題の最適解が様々な問題の解法に有効であるような問題の場合、動的計画法を使って既に計算済みの解を再計算するのを避けることができ、解法を効率化できる。例えば重み付けのあるグラフでの最短経路を求める場合、始点に隣接する全ての頂点について最短経路が分かっていれば、容易に最短経路を求められる。動的計画法とメモ化は密接な関係がある。分割統治法との違いは、分割統治法では部分問題は多少なりとも独立しているのに対して、動的計画法では部分問題が重複している。単純な再帰との違いは、再帰部分をキャッシュ化またはメモ化する点である。部分問題が互いに独立している場合、メモ化は何の役にも立たない。従って、動的計画法はあらゆる複雑な問題の解法とはならない。動的計画法では、メモ化あるいは既に解かれた部分問題のテーブルを使うことで、指数関数的性質を持つ問題を多項式レベルの複雑性にする削減することができる。
- 貪欲法は動的計画法に似ているが、部分問題の解を各段階では知る必要がないという点が異なる。その代わりに各時点で最もよい選択と思われるものを選んでいく。貪欲法では、それまでの選択と現時点の局所最適解から最適と思われる解を構築していくのであって、考えられるあらゆる解を評価することはない。従って網羅的ではなく、必ずしも正解にたどり着けるわけではない。しかし、性能は非常によい。貪欲法としてよく知られている例として、最短経路木を求めるクラスカル法がある。
- 線形計画法で解ける問題では、制約条件として入力に関する線形の不等式があり、入力に関するある線形の関数を最大化（または最小化）する値の組合せを求めるものである。有向グラフに関する最大フロー問題など、多くの問題が線形計画問題として記述でき、シンプレックス法などの汎用アルゴリズムで解くことができる。線形計画法の解空間を整数に限定したものを整数計画法と呼ぶ。
- この技法は、難しい問題をほぼ最適なアルゴリズムが既知の別の問題に変換するものである。例えば、ソートされていない数列から中央値を求める選択アルゴリズムとして、まずその数列をソートし、そこから真ん中に位置する値を取り出すという方式がある。
- 探索と数え上げ
- チェスの手を考えるなどといった問題は、グラフ問題としてモデル化できる。そのような問題では、比較的よく研究されているグラフ探索アルゴリズムを使うことができる。このカテゴリーには、探索アルゴリズム、分枝限定法、バックトラッキングも含まれる。
- 確率的パラダイムとヒューリスティクス
- ここに分類されるのは広義のアルゴリズムである。
研究分野による分類
科学のどんな分野にも固有の問題があり、効率的なアルゴリズムが必要とされている。ある分野の問題はまとめて研究されることが多い。そのような分類として、探索アルゴリズム、ソートアルゴリズム、マージアルゴリズム、数値アルゴリズム、グラフアルゴリズム、文字列アルゴリズム、計算幾何アルゴリズム、組合せアルゴリズム、機械学習、暗号理論、データ圧縮アルゴリズム、構文解析などがある。
各分野はオーバーラップしており、ある分野でのアルゴリズムの進歩が、時には全く異なる分野での改善に繋がることがある。例えば、動的計画法は本来、産業における資源消費の最適化のために発明されたが、現在では様々な分野での各種問題に適用されている。
計算量による分類
アルゴリズムは、入力長に対する計算時間で分類される。あるアルゴリズムは入力長に対して線形時間で完了する。また別のアルゴリズムは指数時間以上かかるし、場合によっては完了しないこともある。さらに、問題によっては計算量の異なる複数のアルゴリズムが存在するし、効率的なアルゴリズムが全く知られていない問題もある。問題によっては、別の問題への写像が存在する。以上のようなことから、計算量による分類は、アルゴリズムについてではなく、問題について行うのが適当とされている。つまり、問題を解く最善のアルゴリズムの計算量に基づいて、問題を分類する。
計算能力による分類
アルゴリズムは計算能力によっても分類される。一般にアルゴリズムは計算能力によって階層的に分類される。「再帰的クラス」とは、全てのチューリング計算可能関数についてのアルゴリズムを含むクラスである。このような階層化によって計算に必要とされる計算資源（時間とメモリ）を制限できる可能性が生じる。「部分再帰クラス」は、全てのチューリング計算可能関数を得ることはできない。例えば、多項式時間で実行されるアルゴリズムには多くの重要な計算が含まれるが、チューリング計算可能関数全体を含むことはない。原始再帰関数で実装されるアルゴリズムのクラスは、別の部分再帰的クラスの例である。
Burgin (2005, p. 24)Burgin, M. Super-recursive algorithms, Monographs in computer science, Springer, 2005. ISBN 0387955690 は、関数を計算するアルゴリズムは有限ステップ後に必ず出力が決定されなければならないという一般的条件を緩めたアルゴリズムの汎用的定義を行った。彼は「超再帰的クラス」を「チューリングマシンで計算可能でない関数を計算可能なアルゴリズムのクラス」と定義した(Burgin 2005, p. 107)。これはハイパーコンピュータの手法の研究と密接に関係している。
法的問題
アルゴリズム自体は一般に特許化できない。アメリカ合衆国では、抽象概念、数、信号の単純な操作だけから成る請求項は「プロセス」を構成しないとされるため米国特許商標庁 (2006), 2106.02, Manual of Patent Examining Procedure (MPEP).、アルゴリズムは特許化できない。しかし、アルゴリズムの具体的応用は特許化可能な場合がある。例えば、Diamond v. Diehrのケースでは、単純なフィードバックアルゴリズムを使った合成ゴムの硬化処理が特許として認められた。データ圧縮アルゴリズムの分野では、ソフトウェア特許が論争の元になることが多く、例えばユニシスのLZWアルゴリズムの特許問題が有名である。
また、暗号アルゴリズムには輸出規制されているものもある。
代表的なアルゴリズム
- ガウスの消去法 - 線形方程式系の解を求める
- ニュートン法 - 非線型方程式系の解を1つ求める
- ガウス＝ルジャンドルのアルゴリズム - 円周率を求める
- 線形合同法 - 擬似乱数を生成する
- 素数判定法 - 与えられた自然数が素数かどうかを判定する
- 素因数分解 - 与えられた自然数を素因数分解する
