設計パラダイムによる分類

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

設計パラダイムによる分類

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

「アルゴリズム」の記事における「設計パラダイムによる分類」の解説

別の分類方法として、アルゴリズムの設計方法論やパラダイムで分類する方法がある。それぞれ異なるいくつかのパラダイムが存在する。さらに、個々のパラダイムの中にも様々な異なる形式のアルゴリズムが含まれている。以下に主なパラダイムを挙げる。 分割統治法 分割統治法は、問題を（通常再帰的に）複数または単一の同じ種類のもっと小さい問題に還元していき、最終的に容易に解ける程度の大きさにする。分割統治の例としてはマージソートがある。ソートは入力データを分割してそれぞれに対して行われ、統治フェーズではそれらの結果をマージする。分割統治法を単純化したものとして decrease and conquer algorithm がある。これは、問題を全く同じ複数の部分問題に分割し、その解をより大きな問題を解くのに利用する。分割統治法では一般に分割された個々の部分問題は全く同じではないため、統治フェーズは decrease and conquer algorithm よりも複雑になる。decrease and conquer algorithm の例として二分探索がある。 動的計画法 部分問題の最適解から全体の最適解が得られるような構造の問題や、同じ部分問題の最適解が様々な問題の解法に有効であるような問題の場合、動的計画法を使って既に計算済みの解を再計算するのを避けることができ、解法を効率化できる。例えば重み付けのあるグラフでの最短経路を求める場合、始点に隣接する全ての頂点について最短経路が分かっていれば、容易に最短経路が求められる。動的計画法とメモ化は密接な関係がある。分割統治法との違いは、分割統治法では部分問題は多少なりとも独立しているのに対して、動的計画法では部分問題が重複している。単純な再帰との違いは、再帰部分をキャッシュ化またはメモ化する点である。部分問題が互いに独立している場合、メモ化は何の役にも立たない。したがって、動的計画法はあらゆる複雑な問題の解法とはならない。動的計画法では、メモ化あるいは既に解かれた部分問題の表を使うことによって、指数関数的性質をもつ問題を多項式レベルの複雑性に削減することができる。 貪欲法 貪欲法は動的計画法に似ているが、部分問題の解を各段階では知る必要がないという点が異なる。その代わりに、各時点で最もよい選択と思われるものを選んでいく。貪欲法では、それまでの選択と現時点の局所最適解から最適と思われる解を構築していくのであって、考えられるあらゆる解を評価することはない。したがって網羅的ではなく、必ずしも正解にたどり着けるわけではない。しかし、性能は非常によい。貪欲法としてよく知られている例として、最短経路木を求めるクラスカル法、プリム法、ダイクストラ法などがある。 線型計画法 線型計画法で解ける問題では、制約条件として入力に関する線型の不等式があり、入力に関するある線型の関数を最大化（または最小化）する値の組合せを求めるものである。有向グラフに関する最大フロー問題など、多くの問題が線型計画問題として記述でき、シンプレックス法などの汎用アルゴリズムで解くことができる。線型計画法の解空間を整数に限定したものを整数計画法と呼ぶ。 還元 この技法は、難しい問題をほぼ最適なアルゴリズムが既知の別の問題に変換するものである。例えば、ソートされていない数列から中央値を求める選択アルゴリズムとして、まずその数列をソートし、そこから真ん中に位置する値を取り出すという方式がある。 探索と数え上げ チェスの手を考えるなどといった問題は、グラフ問題としてモデル化できる。そのような問題では、比較的よく研究されているグラフ探索アルゴリズムを使うことができる。このカテゴリーには、探索アルゴリズム、分枝限定法、バックトラッキングも含まれる。 確率的パラダイムとヒューリスティクス ここに分類されるのは広義のアルゴリズム、ないし、遺伝的アルゴリズムのように（名前に反して）アルゴリズムではないものである。乱択アルゴリズム - 選択を無作為（あるいは擬似無作為）的に行う。問題によっては、無作為性をもった解法が最も性能がよいと証明されているものもある。 遺伝的アルゴリズム - 生物の進化過程をまねた手法で解を求めるもの。無作為な突然変異を加えて、次世代の解を生成していく。自然淘汰と自己複製をエミュレートしているものと看做す視点から「遺伝的」という命名がされた。 ヒューリスティクス - 計算資源が限られている状況での近似解を求めることを目的としている。正解を求めるのには適さない。例えば、局所探索法、タブーサーチ、焼きなまし法といった、何らかの無作為性を導入して確率的に解を発見しようとするアルゴリズムがある。例えば焼きなまし法という名前は、冶金学の焼きなましに由来する。加熱と冷却によって金属結晶の欠陥がなくなるように、無作為性を与えて局所的な最適解に陥るのを防ぎ、徐々に無作為性を小さくすることによって最終的に1つの解に落ち着くという手法である。