Java プログラミングスキル - データ構造とアルゴリズム「分割統治アルゴリズム」

[[398991]]

アルゴリズムの紹介

分割統治アルゴリズムは非常に重要です。文字通りの説明は「分割統治」であり、複雑な問題を 2 つ以上の同一または類似のサブ問題に分割し、サブ問題をさらに小さなサブ問題に分割することを意味します。最後のサブ問題が単純かつ直接的に解決されるまで、元の問題の解決策はサブ問題に対する解決策の組み合わせになります。この手法は、ソートアルゴリズム (クイックソート、マージソート)、フーリエ変換 (高速フーリエ変換) など、多くの効率的なアルゴリズムの基礎となります。
分岐アルゴリズムで解決できるいくつかの古典的なテキストとグラフ: バイナリ検索、大きな整数の乗算、チェス盤カバー、マージソート、クイックソート、線形時間選択、最近接ペア問題、ラウンドロビンスケジュール、ハノイの塔。

分割統治アルゴリズムの基本手順

分割統治法では、再帰の各レベルに 3 つのステップがあります。

分解: 元の問題を、元の問題と同じ形式のいくつかのより小さな独立したサブ問題に分解する
解決策: 一部のサブ問題が小さく簡単に解決できる場合は、それらを直接解決します。そうでない場合は、各サブ問題を再帰的に解決します。
マージ: 各サブ問題の解決策を元の問題の解決策にマージします。

分割統治アルゴリズム設計パターン

分割統治 (P) アルゴリズムモデルは次のとおりです。

ここで、|P| は問題 P の規模を表し、n0 は閾値です。これは、問題 p の規模が n0 を超えない場合、問題をそれ以上分解せずに簡単に直接解決できることを意味します。 ADHOC(P) は、分割統治アルゴリズムの基本的なサブアルゴリズムであり、小規模な問題 P を直接解決するために使用されます。したがって、P のサイズが n0 を超えない場合は、ADHOC(P) が直接使用され、解決されます。アルゴリズム MERGE(y1,y2,…yk) は、分割統治法のマージサブアルゴリズムであり、P のサブ問題 P1、P2、…Pk の対応するソリューション y1、y2、…yk を P のソリューションにマージするために使用されます。

分割統治アルゴリズムの実践 - ハノイの塔

柱の上に、64枚の金色の円盤を下から上へ、大きさの順に並べ、次に別の柱の上に、下から大きさの順に並べ直します。大きな円盤を小さな円盤の上に置くことはできず、3本の柱間では一度に1枚の円盤しか移動できないという規定があります。

思考分析:

ディスクが1つの場合、A->C
n>=2 のディスクの場合、常に 2 つのディスクとして表示できます。1 つは下部のディスク、もう 1 つはその上のすべてのディスクです。まず、上部のディスクをすべて A から B に移動し、下部のディスクを A から C に移動し、タワー B のすべてのディスクを B から C に移動します。

パッケージ com.xie.algorithm; 
 
パブリッククラスHanoiTower {
公共 静的void main(String[] args) {
        ハノイタワー(3, 'A' , 'B' , 'C' );
        /**
         * 最初のディスクはA->Cです
         * 2番目のディスクはA->Bです
         * 最初のディスクはC->Bです
         * 3番目のディスクはA->Cです
         * 最初のディスクはB->Aです
         * 2番目のディスクはB->Cです
         * 最初のディスクはA->Cです
         */
    } 
 
公共 静的void hanoiTower( int num, char a, char b, char c) {
        //ディスクが1つしかない場合
        数値 == 1 の場合
            System.out.println ( "" +a+ "->" +cからの最初のディスク);
        }それ以外{
            //n>=2 ディスクの場合、常に 2 つのディスクとして表示され、1 つは一番下のディスク、もう 1 つはその上のすべてのディスクです。
            //1. まず一番上のディスクをAからBに移動します。移動プロセスではCを使用します。
            ハノイタワー(数値 - 1, a, c, b);
            //2. 下のディスクをAからCに移動する
            システム.out.println ( "the" + num + "disk from" + a + "->" + c);
            //3. タワーBのすべてのディスクをBからCに移動し、移動プロセスでタワーAを使用します。
            ハノイタワー(数値 - 1, b, a, c);
        }
    }
 }