分割統治アルゴリズム

コンピュータサイエンスにおいて、分割統治法はアルゴリズム設計パラダイムです。分割統治法アルゴリズムは、問題が直接解決できるほど単純になるまで、問題を同じまたは関連するタイプの 2 つ以上のサブ問題に再帰的に分割します。次に、サブ問題の解決策を組み合わせて、元の問題の解決策を作成します。

分割統治法は、ソート（クイックソート、マージソートなど）、大きな数の乗算（カラツバアルゴリズムなど）、最も近い点のペアの検索、構文解析（トップダウンパーサーなど）、離散フーリエ変換（FFT）の計算など、多くの問題に対する効率的なアルゴリズムの基礎となっています。^[1]

効率的な分割統治アルゴリズムを設計するのは難しい場合があります。数学的帰納法と同様に、再帰的な解決法を適用できるように問題を一般化することがしばしば必要になります。分割統治アルゴリズムの正しさは通常、数学的帰納法によって証明され、その計算コストは再帰関係を解くことによって決定されることがよくあります。

分割して征服する

分割統治法は、問題の最適解を見つけるためによく使用されます。その基本的な考え方は、与えられた問題を 2 つ以上の類似しているがより単純なサブ問題に分解し、それらを順に解決して、それらの解決策を組み合わせて与えられた問題を解決するというものです。十分に単純な問題は直接解決されます。たとえば、与えられたn 個の 自然数のリストをソートするには、それを約n /2 個の数からなる 2 つのリストに分割し、それぞれを順にソートし、両方の結果を適切にインターリーブして、与えられたリストのソート済みバージョンを取得します (図を参照)。このアプローチは、マージソートアルゴリズムとして知られています。

「分割統治」という名前は、ソートされたリスト内のレコードを見つけるための二分探索アルゴリズム（または数値計算における類似物である根を見つけるための二分アルゴリズム）など、各問題を 1 つのサブ問題にのみ縮小するアルゴリズムに適用されることがあります。^[2]これらのアルゴリズムは、一般的な分割統治アルゴリズムよりも効率的に実装できます。特に、末尾再帰を使用する場合は、単純なループに変換できます。ただし、この広い定義では、再帰またはループを使用するすべてのアルゴリズムが「分割統治アルゴリズム」と見なされる可能性があります。したがって、一部の著者は、各問題が 2 つ以上のサブ問題を生成する可能性がある場合にのみ、「分割統治」という名前を使用する必要があると考えています。^{[3]代わりに、単一のサブ問題クラスに対して、}減少統治という名前が提案されています。^[4]

分割統治法の重要な応用は最適化です。^{[例が必要]}各ステップで検索空間が定数係数で縮小 (「剪定」) されると、アルゴリズム全体の漸近的複雑度は剪定ステップと同じになり、定数は剪定係数 (等比級数を合計することによって) に依存します。これは、剪定と検索として知られています。

初期の歴史的例

これらのアルゴリズムの初期の例としては、主に減少と征服があります。つまり、元の問題が単一のサブ問題に連続的に分割され、実際に反復的に解決できます。

二分探索は、サブ問題が元のサイズのおよそ半分になる減少統治アルゴリズムであり、長い歴史があります。コンピューター上のアルゴリズムの明確な説明は、1946年にジョン・モークリーの論文で登場しましたが、検索を容易にするためにアイテムのソートされたリストを使用するというアイデアは、少なくとも紀元前200年のバビロニアにまで遡ります。 ^[5]もう1つの古代の減少統治アルゴリズムは、数をより小さな同等のサブ問題に減らすことによって2つの数の最大公約数を計算するユークリッドの互除法であり、紀元前数世紀に遡ります。

複数の部分問題を持つ分割統治アルゴリズムの初期の例としては、ガウスが1805年に記述した、現在ではクーリー・テューキー高速フーリエ変換（FFT）アルゴリズムと呼ばれるものがありますが、^[6]彼はその演算回数を定量的に分析しておらず、FFTは1世紀以上後に再発見されるまで広く普及しませんでした。

コンピュータ専用に開発され、適切に分析された初期の2つのサブ問題D&Cアルゴリズムは、 1945年にジョン・フォン・ノイマンによって発明されたマージソートアルゴリズムです。 ^[7]

もう一つの注目すべき例は、1960年にアナトリー・A・カラツバによって発明されたアルゴリズム^[8]で、2つのn桁の数字を演算（ビッグオー記法）で乗算することができました。このアルゴリズムは、そのタスクには演算が必要であるというアンドレイ・コルモゴロフの1956年の予想を反証しました。 $O(n^{\log _{2}3})$ $\オメガ (n^{2})$

もともとコンピュータを伴わなかった分割統治アルゴリズムの別の例として、ドナルド・クヌースは郵便局が郵便物を配送するために通常使用する方法を挙げています。手紙は地理的な地域ごとに別々の袋に分類され、これらの袋のそれぞれはさらに小さなサブ地域ごとにバッチに分類され、配達されるまでこれを繰り返します。 ^[5]これは、 1929年にパンチカードソートマシン用に説明された基数ソートに関連しています。 ^[5]

利点

難しい問題を解決する

分割統治法は、概念的に難しい問題を解決するための強力なツールです。必要なのは、問題をサブ問題に分割し、些細なケースを解決し、サブ問題を元の問題に結合する方法だけです。同様に、減少統治法では、古典的なハノイの塔パズルのように、問題を 1 つの小さな問題に減らすだけで済みます。このパズルでは、高さの塔を動かすことが、高さの塔を動かすことに減ります。 $n$ $n-1$

アルゴリズムの効率

分割統治法は、効率的なアルゴリズムの発見に役立つことがよくあります。たとえば、Karatsubaの高速乗算法、クイックソートおよびマージソートアルゴリズム、行列乗算のStrassen アルゴリズム、高速フーリエ変換などの鍵となりました。

これらすべての例では、D&C アプローチによってソリューションの漸近的コストが改善されました。たとえば、(a)基本ケースのサイズが一定で、問題を分割して部分ソリューションを組み合わせる作業が問題のサイズに比例し、(b)各ステージにサイズが ~ のサブ問題の数が制限されている場合、分割統治アルゴリズムのコストはになります。 $n$ $p$ $n/p$ $O(n\log _{p}n)$

並列処理

分割統治アルゴリズムは、マルチプロセッサマシン、特に異なるサブ問題を異なるプロセッサで実行できるため、プロセッサ間のデータ通信を事前に計画する必要がない共有メモリシステムでの実行に自然に適合します。

メモリアクセス

分割統治アルゴリズムは、当然のことながら、メモリキャッシュを効率的に使用する傾向があります。その理由は、サブ問題が十分に小さければ、原理的には、そのサブ問題とそのすべてのサブ問題は、より遅いメインメモリにアクセスすることなく、キャッシュ内で解決できるからです。このようにキャッシュを活用するように設計されたアルゴリズムは、キャッシュサイズを明示的なパラメーターとして含まないため、キャッシュ無視アルゴリズムと呼ばれます。^[9]さらに、D&C アルゴリズムは、重要なアルゴリズム (ソート、FFT、行列乗算など) が最適なキャッシュ無視アルゴリズムとなるように設計できます。つまり、キャッシュサイズに関係なく、漸近的な意味でおそらく最適な方法でキャッシュを使用します。対照的に、キャッシュを活用する従来のアプローチは、ループネストの最適化のように、問題が適切なサイズのチャンクに明示的に分割されるブロッキングです。これもキャッシュを最適に使用できますが、アルゴリズムが特定のマシンの特定のキャッシュサイズに合わせて調整されている場合に限られます。

NUMAや仮想メモリなどの他の階層型ストレージシステムや、複数レベルのキャッシュに関しても同じ利点があります。つまり、サブ問題が十分に小さければ、上位 (低速) レベルにアクセスすることなく、階層の特定のレベル内で解決できます。

丸め制御

浮動小数点数などの丸め演算では、分割統治アルゴリズムは表面上は同等の反復法よりも正確な結果をもたらす可能性がある。例えば、N 個の数値を加算するには、各データを単一の変数に追加する単純なループを使用するか、データセットを 2 つに分割し、各半分の合計を再帰的に計算してから 2 つの合計を加算するペアワイズ合計と呼ばれる D&C アルゴリズムを使用する。2 番目の方法は最初の方法と同じ回数の加算を実行し、再帰呼び出しのオーバーヘッドを支払うが、通常はより正確である。^[10]

実装上の問題

再帰

分割統治アルゴリズムは、当然、再帰的手順として実装されます。その場合、現在解決中の問題につながる部分的なサブ問題は、手順呼び出しスタックに自動的に保存されます。再帰関数とは、定義内で自分自身を呼び出す関数です。

明示的なスタック

分割統治アルゴリズムは、部分的なサブ問題をスタック、キュー、または優先キューなどの明示的なデータ構造に格納する非再帰プログラムによって実装することもできます。このアプローチでは、次に解決するサブ問題の選択に自由度が増します。これは、幅優先再帰や関数最適化のための分岐限定法など、一部のアプリケーションで重要な機能です。このアプローチは、再帰手順をサポートしないプログラミング言語の標準的なソリューションでもあります。

スタックサイズ

D&C アルゴリズムの再帰実装では、再帰スタックに十分なメモリが割り当てられていることを確認する必要があります。そうしないと、スタックオーバーフローが原因で実行が失敗する可能性があります。時間効率の高い D&C アルゴリズムは、再帰の深さが比較的小さいことがよくあります。たとえば、クイックソートアルゴリズムは、アイテムをソートするためにネストされた再帰呼び出し以上を必要としないように実装できます。 $\log_{2}n$ $n$

多くのコンパイラは再帰スタックが連続したメモリ領域であると想定し、一部のコンパイラは再帰スタックに固定量のスペースを割り当てるため、再帰プロシージャを使用する場合、スタックオーバーフローを回避することは難しい場合があります。また、コンパイラは、戻りアドレス、不変のパラメータ、プロシージャの内部変数など、厳密に必要な情報よりも多くの情報を再帰スタックに保存することもあります。したがって、再帰プロシージャのパラメータと内部変数を最小限に抑えるか、明示的なスタック構造を使用することで、スタックオーバーフローのリスクを軽減できます。

ベースケースの選択

どのような再帰アルゴリズムでも、再帰を終了するために直接解決される小さなサブ問題である基本ケースの選択にはかなりの自由度があります。

可能な限り最小または最も単純な基本ケースを選択する方が洗練されており、通常はプログラムが単純になります。これは、考慮すべきケースが少なくなり、解決が容易になるためです。たとえば、高速フーリエ変換アルゴリズムは、入力が単一のサンプルである場合に再帰を停止できます。また、クイックソートリストソートアルゴリズムは、入力が空のリストである場合に停止できます。どちらの例でも、考慮すべき基本ケースは 1 つだけであり、処理は必要ありません。

一方、比較的大きな基本ケースで再帰を停止し、これらを非再帰的に解決すると、効率が向上することが多く、ハイブリッドアルゴリズムになります。この戦略により、ほとんどまたはまったく作業を行わない再帰呼び出しのオーバーヘッドが回避され、それらの基本ケースでは明示的な再帰よりも効率的な特殊な非再帰アルゴリズムの使用も可能になります。単純なハイブリッド再帰アルゴリズムの一般的な手順は、基本ケースの短絡、つまりアームズレングス再帰です。この場合、関数呼び出しの前に次のステップで基本ケースになるかどうかがチェックされるため、不要な関数呼び出しが回避されます。たとえば、ツリーでは、子ノードに再帰してから null かどうかを確認するのではなく、再帰の前に null をチェックすると、バイナリツリーの一部のアルゴリズムで関数呼び出しの半分が回避されます。 D&C アルゴリズムは、最終的に各問題またはサブ問題インスタンスを多数の基本インスタンスに削減するため、分割/結合のオーバーヘッドが低い場合は特に、これらがアルゴリズムの全体的なコストの大部分を占めることになります。これらの考慮事項は、再帰がコンパイラによって実装されるか、明示的なスタックによって実装されるかには依存しないことに注意してください。

したがって、たとえば、クイックソートの多くのライブラリ実装は、ソートする項目の数が十分に少なくなると、単純なループベースの挿入ソート(または同様の) アルゴリズムに切り替わります。空のリストが唯一の基本ケースである場合、エントリを含むリストをソートすると、何もせずにすぐに戻るクイックソート呼び出しが最大限に必要になることに注意してください。基本ケースをリストのサイズが 2 以下に増やすと、何もしない呼び出しのほとんどが排除されます。より一般的には、関数呼び出しのオーバーヘッドやスタック操作に費やされる時間の割合を減らすために、2 より大きい基本ケースが通常使用されます。 $n$ $n$

あるいは、分割統治アルゴリズムを使用する大規模なベースケースを採用し、所定の固定サイズセットに対してアルゴリズムを実装することもできます。この場合、アルゴリズムは、再帰、ループ、または条件文(部分評価の手法に関連) のないコードに完全に展開できます。たとえば、このアプローチは、ベースケースが固定サイズのセットに対する分割統治 FFT アルゴリズムの展開された実装である、いくつかの効率的な FFT 実装で使用されます。^[11]ソースコード生成方法を使用して、この戦略を効率的に実装するために必要な多数の個別のベースケースを作成できます。^[11]

この考え方の一般化されたバージョンは再帰「アンローリング」または「粗大化」として知られており、基本ケースを拡大する手順を自動化するためのさまざまな手法が提案されています。^[12]

重複する部分問題に対する動的計画法

問題によっては、分岐再帰によって同じサブ問題を何度も評価することになる場合があります。そのような場合、これらの重複するサブ問題の解を特定して保存する価値があるかもしれません。これは一般にメモ化と呼ばれる手法です。これを極限まで追求すると、動的プログラミングなどのボトムアップの分割統治アルゴリズムにつながります。

参照

参考文献

^ Blahut, Richard (2014年5月14日).信号処理のための高速アルゴリズム. ケンブリッジ大学出版局. pp. 139–143. ISBN 978-0-511-77637-3。
^ トーマス・H・コーメン;チャールズ・E・ライザーソン。ロナルド・L・リベスト。クリフォード・スタイン (2009 年 7 月 31 日)。アルゴリズムの紹介。 MITプレス。ISBN 978-0-262-53305-8。
^ Brassard, G.、および Bratley, P. 『アルゴリズムの基礎』、Prentice-Hall、1996 年。
^ Anany V. Levitin、「アルゴリズムの設計と分析入門」（Addison Wesley、2002年）。
^ abc Donald E. Knuth、『コンピュータプログラミングの芸術：第3巻、ソートと検索』、第2版（Addison-Wesley、1998年）。
^ Heideman, MT, DH Johnson、CS Burrus、「ガウスと高速フーリエ変換の歴史」、IEEE ASSP Magazine、1、(4)、14–21 (1984)。
^ クヌース、ドナルド(1998)。コンピュータプログラミングの芸術: 第3巻ソートと検索。p. 159。ISBN 0-201-89685-0。
^ カラツバ、アナトリイ A. ;ユーリ・P・オフマン（1962年）。「Умножение многозначных чисел на автоматах」。ドクラディ・アカデミ・ナウクSSSR。146 : 293–294。Karatsuba, A.; Ofman, Yu. (1963)に翻訳。「オートマトンによる多桁数の乗算」。Soviet Physics Doklady。7 : 595–596。Bibcode : 1963SPhD ....7..595K。
^ M. Frigo、CE Leiserson、H. Prokop (1999)。「キャッシュを意識させないアルゴリズム」。第 40 回コンピュータサイエンスの基礎に関する年次シンポジウム (カタログ番号 99CB37039) 。pp . 285–297。doi :10.1109 / SFFCS.1999.814600。ISBN 0-7695-0409-4. S2CID 62758836。
^ Nicholas J. Higham、「浮動小数点加算の精度」、SIAM J. Scientific Computing 14 (4)、783–799 (1993)。
^ ab Frigo, M.; Johnson, SG (2005 年 2 月). 「FFTW3 の設計と実装」(PDF) . Proceedings of the IEEE . 93 (2): 216–231. CiteSeerX 10.1.1.66.3097 . doi :10.1109/JPROC.2004.840301. S2CID 6644892.
^ Radu Rugina と Martin Rinard、「分割統治プログラムの再帰展開」、Languages and Compilers for Parallel Computing、第 3 章、34 ～ 48 ページ。Lecture Notes in Computer Science vol. 2017 (ベルリン: Springer、2001 年)。

[1] Blahut, Richard (2014年5月14日).信号処理のための高速アルゴリズム. ケンブリッジ大学出版局. pp. 139–143. ISBN 978-0-511-77637-3。

[CormenLeiserson2009-2] トーマス・H・コーメン;チャールズ・E・ライザーソン。ロナルド・L・リベスト。クリフォード・スタイン (2009 年 7 月 31 日)。アルゴリズムの紹介。 MITプレス。ISBN 978-0-262-53305-8。

[3] Brassard, G.、および Bratley, P. 『アルゴリズムの基礎』、Prentice-Hall、1996 年。

[4] Anany V. Levitin、「アルゴリズムの設計と分析入門」（Addison Wesley、2002年）。

[Knuth3-5] Donald E. Knuth、『コンピュータプログラミングの芸術：第3巻、ソートと検索』、第2版（Addison-Wesley、1998年）。

[Heideman84-6] Heideman, MT, DH Johnson、CS Burrus、「ガウスと高速フーリエ変換の歴史」、IEEE ASSP Magazine、1、(4)、14–21 (1984)。

[7] クヌース、ドナルド(1998)。コンピュータプログラミングの芸術: 第3巻ソートと検索。p. 159。ISBN 0-201-89685-0。

[8] カラツバ、アナトリイ A. ;ユーリ・P・オフマン（1962年）。「Умножение многозначных чисел на автоматах」。ドクラディ・アカデミ・ナウクSSSR。146 : 293–294。Karatsuba, A.; Ofman, Yu. (1963)に翻訳。「オートマトンによる多桁数の乗算」。Soviet Physics Doklady。7 : 595–596。Bibcode : 1963SPhD ....7..595K。

[cahob-9] M. Frigo、CE Leiserson、H. Prokop (1999)。「キャッシュを意識させないアルゴリズム」。第 40 回コンピュータサイエンスの基礎に関する年次シンポジウム (カタログ番号 99CB37039) 。pp . 285–297。doi :10.1109 / SFFCS.1999.814600。ISBN 0-7695-0409-4. S2CID 62758836。

[10] Nicholas J. Higham、「浮動小数点加算の精度」、SIAM J. Scientific Computing 14 (4)、783–799 (1993)。

[fftw-11] Frigo, M.; Johnson, SG (2005 年 2 月). 「FFTW3 の設計と実装」(PDF) . Proceedings of the IEEE . 93 (2): 216–231. CiteSeerX 10.1.1.66.3097 . doi :10.1109/JPROC.2004.840301. S2CID 6644892.

[12] Radu Rugina と Martin Rinard、「分割統治プログラムの再帰展開」、Languages and Compilers for Parallel Computing、第 3 章、34 ～ 48 ページ。Lecture Notes in Computer Science vol. 2017 (ベルリン: Springer、2001 年)。