実装による分類

ウィキペディア小見出し辞書

実装による分類

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/28 01:04 UTC 版)

「アルゴリズム」の記事における「実装による分類」の解説

アルゴリズム分類の1つの方法として、実装手段による分類がある。 再帰 / 反復 再帰アルゴリズムは、ある条件が成り立つまで自身を再帰的に呼び出すものであって、関数型言語でよく使われる。反復アルゴリズムは、ループのような反復構造と場合によってはスタックなどのデータ構造を補助的に使い、問題を解く。一部の問題は、どちらか一方の実装が自然である。例えば、ハノイの塔は再帰的実装の方が分かりやすい。再帰アルゴリズムは全て反復アルゴリズムでも実装可能であり、逆も同じである（ただし、複雑さは変化する）。 論理 アルゴリズムは、制御された演繹であるとも言われる。これを アルゴリズム = 論理 + 制御 と表現することもある。論理部分は計算で使われる公理を表し、制御部分は公理に演繹が適用される方法を決定する。これは論理プログラミングというパラダイムの基本である。純粋な論理プログラミングでは、制御部分が固定されていて、アルゴリズムは論理部分だけで指定される。この手法の魅力は、プログラム意味論的なエレガントさがある点である。公理の変化は定式化されたアルゴリズムの変更を伴う。 逐次 / 並列 / 分散 アルゴリズムは通常、コンピュータが一度に1つのアルゴリズム内の1つの命令だけを実行するものと仮定して議論される。このようなコンピュータは、シリアル・コンピュータなどと呼ばれることもある。そういった環境向けに設計されたアルゴリズムは逐次アルゴリズムと呼ばれ、それとは対照的な分類として並列アルゴリズムや分散アルゴリズムがある。並列アルゴリズムは、複数のプロセッサが同時並行して同じ問題を解くのに使えるコンピュータアーキテクチャで有効である。また、分散アルゴリズムは、複数のマシンがコンピュータネットワークで相互接続された環境で使われる。並列/分散アルゴリズムは、問題を分割して解き、その結果を集めて最終的な結果を得る。その場合、個々のプロセッサの計算時間（実行命令数）だけでなく、プロセッサ間の通信オーバーヘッドも計算資源の消費量として問題になる。例えば、ソートアルゴリズムは効率的に並列化できるものもあるが、通信オーバーヘッドは高くつく（部分数列をソートした結果を集めるには、結局部分数列そのものをやりとりしなくてはならない）。反復アルゴリズムは一般に並列化可能である。並列アルゴリズムがない問題は、本質的に逐次的な問題である。 決定性 / 非決定性 決定性アルゴリズムでは解法の全ステップが常に正確に決定されるが、非決定性アルゴリズムはいわば推量や推測で問題を解くものであり、ヒューリスティクスを使ってより正確に推測する。 正解 / 近似解 一般にアルゴリズムは正解を得るものだが、近似アルゴリズムは近似解を求め、その近似性に一定の根拠があれば、これも広義のアルゴリズムとして含めて考えることができる。近似には、決定性の戦略もあれば、乱択の戦略もある。多くの難しい問題では、近似アルゴリズムしか実用的な解法が存在しない。近似アルゴリズムはその近似解の近似性能も評価・保証などがされる必要がある。