見出し画像

🛠減少統治の解説

あたり帳簿

コンピュータサイエンスにおいて、分割統治はアルゴリズム設計のパラダイムの一つである。分割統治アルゴリズムは、ある問題を、直接解けるほど単純になるまで、同じタイプまたは関連するタイプの2つ以上の部分問題に再帰的に分解する。そして、サブ問題の解決策を組み合わせて、元の問題の解決策を導き出す。
分割統治法は、ソート（クイックソート、マージソートなど）、大きな数の掛け算（カラツバアルゴリズムなど）、最も近い点のペアを見つける、構文解析（トップダウンパーサーなど）、離散フーリエ変換（FFT）の計算など、多くの問題に対する効率的アルゴリズムの基礎になっている[1]。
効率的な分割統治アルゴリズムの設計は困難である．数学的帰納法のように、問題を一般化し、再帰的解法に従わせることが必要な場合が多い。分割統治アルゴリズムの正しさは通常数学的帰納法により証明され、その計算コストは再帰関係を解くことにより決定されることが多い。

https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm

問題の最適解を求めるために、分割統治パラダイムがよく利用される。その基本的な考え方は、与えられた問題を2つ以上の類似しているがより単純な部分問題に分解し、それらを順番に解き、それらの解を合成して与えられた問題を解決することである。十分に単純な問題は、直接的に解かれる。

例えば、与えられたn個の自然数のリストをソートするには、それをn/2個程度のリストに分割し、それぞれを順番にソートし、両方の結果を適切にインターリーブすれば、与えられたリストのソート版が得られる（図参照）。この方法は、マージソートアルゴリズムとして知られています。

ソートされたリストのレコードを見つけるためのバイナリサーチ・アルゴリズム（あるいは数値計算におけるその類似のアルゴリズムであるルート探索のためのバイセクション・アルゴリズム）[2]のように、それぞれの問題をただ一つの部分問題に還元するアルゴリズムに「分割統治」という名前が適用されることもある。しかし、この広義の定義では、再帰やループを用いるすべてのアルゴリズムが「分割統治アルゴリズム」とみなされる可能性がある。そのため，1つの問題が2つ以上の部分問題を生成する可能性がある場合にのみ「分割統治」という名称を用いるべきと考える著者もおり[3]，代わりに単一部分問題クラスに対して「減少統治（decrease and conquer
）」という名称が提案されている[4]．

https://amzn.to/3QmtANp

は分割統治アルゴリズムはその名の通り、問題を複数の小さな部分問題に「分割」し、それぞれの部分問題を解いてから「統治」するというアプローチをとります。この手法は、様々な具体的なアルゴリズムに応用されています。以下は、分割統治アルゴリズムの代表的な種類のいくつかを示しています。

  1. マージソート (Merge Sort): 配列を2つの部分配列に分割し、それぞれをソートしてから、2つのソート済み部分配列をマージします。

  2. クイックソート (Quick Sort): ピボットを基準にして配列を分割し、ピボットより小さい部分と大きい部分とに分けてそれぞれをソートします。

  3. 高速フーリエ変換 (Fast Fourier Transform, FFT): 信号処理や画像処理で使われる効率的なアルゴリズムです。

  4. Strassenの行列乗算: 行列の乗算を効率的に行うアルゴリズムの1つ。

  5. クローゼストペア問題: 平面上の点集合から、最も距離が近い2つの点のペアを見つけるアルゴリズム。

  6. Karatsuba法: 多桁の整数の乗算を効率的に行うアルゴリズム。

  7. 樹状再帰: これは特定のアルゴリズムではなく、分割統治の形式の1つです。問題を2つ以上の部分問題に分割し、それらの部分問題がさらに部分問題に分割される、という再帰的な構造を持っています。

「減少統治」（Decrease and Conquer）は「分割統治」（Divide and Conquer）とは異なるアルゴリズム設計パラダイムの一つです。どちらも問題を小さな部分問題に分けることで解を求める手法ですが、そのアプローチには明確な違いがあります。

減少統治 (Decrease and Conquer):

  1. 問題を1つ、またはそれ以上のより小さな部分問題に分ける。

  2. このより小さい部分問題を解く。

  3. 必要に応じて、これらの部分問題の解を組み合わせて元の問題の解を得る。

例:

  • 挿入ソート (Insertion Sort): 1つの要素を選んで、それを正しい位置に挿入することを繰り返します。

  • トポロジカルソート: 1つのノードを選び、そのノードとそれに接続するエッジを除去することを繰り返します。

  • タワーオブハノイ: ディスクを1枚移動する問題に減少させる。

分割統治 (Divide and Conquer):

  1. 問題を複数の同じサイズまたはほぼ同じサイズの部分問題に分割する。

  2. これらの部分問題を独立に解く。

  3. 必要に応じて、これらの部分問題の解を組み合わせて元の問題の解を得る。

例:

  • マージソート: 配列を2つの部分配列に分割し、それぞれをソートしてから組み合わせる。

  • クイックソート: ピボットを基準に配列を2つの部分配列に分割し、それぞれを独立にソートする。

減少統治は問題のサイズを少し小さくするのに対し、分割統治は問題を複数の小さな問題に分割します。


お願い致します