「5つの一般的なアルゴリズム」分岐アルゴリズムとアイデアを図解で紹介

[[355166]]

この記事はWeChatの公開アカウント「bigsai」から転載したもので、著者はbigsaiです。この記事を転載する場合はbigsai公開アカウントまでご連絡ください。

序文

分割統治アルゴリズムは、一般的に使用される 5 つのアルゴリズム (分割統治アルゴリズム、動的計画法アルゴリズム、貪欲アルゴリズム、バックトラッキング法、分割統治境界法) の 1 つです。多くの人は、日常の学習で分割統治アルゴリズムを知っているだけで、体系的に分割統治アルゴリズムを学習したことがないかもしれません。この記事では、分割統治アルゴリズムをより包括的に理解できるようにします。

分割統治アルゴリズムを学ぶ前に、質問させてください。誰もが子供の頃に貯金箱を持った経験があると思います。親や親戚からお金をもらったら、自分の宝物にそのお金を貯め、時々そのお金を数えていました。しかし、お金の山を扱うのは、データが大きすぎて頭で理解できず、間違いを起こしやすいので難しいかもしれません。お金をいくつかの小さな部分に分割し、それらを合計してお金の合計額を算出してもよいでしょう。

もちろん、各部分の金額がまだ多すぎると思われる場合は、分割して結合することもできます。なぜこんなにたくさんあるのかというと、

それぞれの小さなお金の山を計算する方法は、最大のお金の山を計算する方法と同じです（違いはサイズです）

そうすると、大きなお金の山の合計は、実際には小さなお金の山の結果の合計になります。これは実際には一種の分割統治の考え方です。

もちろん、このお金はすべて考え抜かれたものです...

分割統治アルゴリズムの紹介

分割統治アルゴリズムは、分割統治の考え方を使用するアルゴリズムです。分割統治とは何ですか?

分割統治とは、文字通り「分割して統治する」という意味で、複雑な問題を 2 つ以上の同一または類似のサブ問題に分割し、そのサブ問題をさらに小さなサブ問題に分割することを意味します。最後のサブ問題が単純かつ直接的に解決できるまで、分割していき、元の問題の解決策はサブ問題の解決策の組み合わせになります。コンピュータサイエンスにおいて、分割統治法は分割統治の考え方を採用した非常に重要なアルゴリズムです。分割統治法は、ソートアルゴリズム (クイックソート、マージソート)、フーリエ変換 (高速フーリエ変換) など、多くの効率的なアルゴリズムの基礎となります。

親問題をサブ問題に分解し、同じ方法で解決することは再帰の概念と一致しているため、分割統治アルゴリズムは通常、再帰的に実装されます (もちろん、非再帰的な実装もあります)。分割統治アルゴリズムの説明も文字通り理解しやすいです。実際、分割統治にはマージプロセスもあります。

分割: 小さな問題を再帰的に解決する (終了層に到達するか、解決できるようになった時点で停止する)
征服: 問題を再帰的に解決します。問題が十分に小さい場合は、直接解決します。
組み合わせる: サブ問題の解決策から親問題を構築する

一般的に、分割統治アルゴリズムは本文で 2 つ以上の再帰呼び出しに分解され、サブクラスの問題は一般に分離されています (互いに影響を及ぼしません)。問題が大きすぎて直接解決できないが、小規模であれば簡単に解決でき、分割統治アルゴリズムの適用条件を満たす場合は、分割統治アルゴリズムを使用できます。

では、分割統治アルゴリズムを使用して問題を解決するには、どのような条件 (特性) を満たす必要があるのでしょうか?

1. 元の問題は通常、規模が大きく、直接解決するのは困難ですが、問題をある程度の大きさに縮小すればより簡単に解決できます。

2. 問題は、同じ（類似の）解決方法を持ついくつかの小さなサブ問題に分解できます。さらに、サブ問題に対する解決策は独立しており、相互に影響を与えません。

3. 問題分解のサブ問題をマージすると、問題の解決策が得られます。

分割統治アルゴリズムと再帰の間にはどのような関係があるのか疑問に思うかもしれません。実際、分割統治は、問題を分割、統治、統合するプロセスに焦点を当てた重要なアイデアです。再帰とは、自分自身を呼び出すことで往復のプロセスを形成する方法（ツール）であり、分割統治法では、このような往復のプロセスを複数利用することがあります。

分割統治アルゴリズムの古典的な問題

分割統治アルゴリズムの古典的な問題では、そのアイデアが重要です。実装には主に再帰を使用するため、コード実装はほとんどが非常に単純であり、この記事でもアイデアの説明に重点を置いています。

分割統治アルゴリズムの典型的な問題ですが、私はそれを 2 つのカテゴリに分類します。サブ問題が完全に独立しているものと、サブ問題が完全に独立していないものです。

1. 元の問題に対する答えがサブ問題の結果から完全に推測できる場合、サブ問題は完全に独立しています。

2. サブ問題は完全に独立しているわけではありません。一部の区間問題や区間をまたぐ問題では、分割統治法の結果が区間をまたぐことがあります。問題を検討する際には、これらを注意深く参照する必要があります。

バイナリ検索

バイナリ検索は分割統治法の一例ですが、バイナリ検索には独自の特殊性があります。

シーケンス順序
結果は価値である

通常のバイナリ検索では、完全な区間を 2 つの区間に分割します。2 つの区間で個別に値を検索し、結果を確認する必要があります。ただし、順序付けられた区間では、結果がどの区間にあるかを直接判断できるため、2 つの区間のうちの 1 つだけを計算し、最後まで続行する必要があります。実装方法には再帰的と非再帰的の 2 つがありますが、非再帰的の方が一般的に使用されます。

公共  int searchInsert( int [] 数値, intターゲット) {
  if(nums[0]>=target) return 0; // プルーニング
  if(nums[nums.length-1]==target) return nums.length-1; // プルーニング
  if(nums[nums.length-1]<target) nums.lengthを返します。
整数 左=0、右=nums.length-1;
  （左<右）{
 int中央 = (左+右)/2;
    if(nums[mid]==target)
ミッドに戻ります。
そうでない場合 (nums[mid]>target) {
右= 中央;
    }
それ以外{
左= 中央 + 1;
    }
  }
戻る 左;
 }

クイックソート

クイックソートも分割統治法の一例です。クイックソートの各ラウンドでは、数字が選択され、この数字より小さい数字は左側に配置され、この数字より大きい数字は右側に配置されます。次に、2つのサブ区間は再帰的な分割統治法によって解決されます。もちろん、クイックソートは分割時に多くの作業を行い、すべての数字が最下層に分割されると、シーケンスの値がソートされた値になります。これは分割統治の現れです。

パブリックvoidクイックソート( int []a, int  左、 int  右）
 {
 int低 =左;
 int高さ =右;
  // 次の 2 つの文の順序を混在させることはできません。混在させると、配列が範囲外になります。 ！ ！とても重要です！ ！ ！
  if(low>high)//カットオフかどうかを判断する条件として
戻る;
 int k=a[low]; //余分なスペースk、左端のものを基準として、最終的に左側がそれより小さく、右側がそれより大きいことを要求します。
  while(low<high) //このラウンドでは、左側がa[low]より小さく、右側がa[low]より大きい必要があります。
  {
    while(low<high&&a[high]>=k)//右側にkより小さい最初のものが見つかったら停止します
    {
      高い- ;  
    }
    //これはそれより小さい最初のものを見つけます
    a[low]=a[high]; // 低い位置にする
    while(low<high&&a[low]<=k)//lowの右側でkより大きい最初のものを探し、右側のa[high]に配置します。
    {
      低++;
    }
    a[高]=a[低];
  }
  a[low]=k; //値を割り当て、左と右の再帰で分割統治する
  クイックソート(a,左, 下位1);
  クイックソート(a, low+1, right );
 }

マージソート（逆順）

クイックソートは分割時に多くの作業を行いますが、マージはその逆です。分割の場合、マージは数に応じて均等に分割し、マージの場合は、2 つずつ順番にマージします。これは、2 つの順序付けられたシーケンスに対して O(n) レベルの複雑さで必要な結果が得られるためです。マージソートに基づく逆数の変換も分割統治の考え方によって解決されます。

プライベート静的voidマージソート( int []配列、 int  左、 int  右） {
 int中央 = (左+右)/2;
  if(左<右)
  {
    マージソート(配列、左、中央);
    マージソート(配列、中央+1、右);
    配列をマージします。左、中央、右。
  }
 } 
 
プライベート静的voidマージ( int []配列、 int l、 int mid、 int r) {
 int lindex=l; int rindex=mid+1;
 intチーム[] = 新しいint [r-l+1];
 intチームインデックス = 0;
  while (lindex<=mid&&rindex<=r){//まず左と右を比較する
    if(配列[lindex]<=配列[rindex])
    {
      チーム[チームインデックス++]=配列[lindex++];
    }
それ以外{
      チーム[チームインデックス++]=配列[rindex++];
    }
  }
  while(lindex<=mid) // 1つが制限を超えたら、残りを順番に追加できます
  {
    チーム[チームインデックス++]=配列[lindex++]; 
 
  }
  while(rindex<=r)
  {
    チーム[チームインデックス++]=配列[rindex++];
  }
 ( int i=0;i<teamindex;i++)の場合
  {
    配列[l+i]=チーム[i];
  }
 }

最大部分列合計

最大部分列合計の問題を解決するには、動的プログラミングを使用できますが、分割統治アルゴリズムを使用して問題を解決することもできます。ただし、最大部分列合計は、部分列合計に長さの問題が関係するため、マージ時に単純なマージではありません。そのため、正しい結果がすべて左端または右端にあるとは限らず、結果が表示される可能性のある領域は次のとおりです。

完全に中央より左
完全に中央より右
中央の左側と右側に2つのノードを含むシーケンス

これはグラフで表すことができます:

そのため、具体的に考えると、再帰的に求めることができない真ん中の最大値の文字列の結果を計算し、それを左右と比較する必要があります。

53. 最大部分列の合計は次のコードで実装されています。

パブリックint maxSubArray( int [] nums) {
整数  max =maxsub(nums,0,nums.length-1);
戻る 最大;
 }
 int maxsub( int数値[], int  左、 int  右）
 {
    if(左==右)
 nums[ left ]を返します。
 int中央 = (左+右)/2;
 int leftmax=maxsub(nums, left ,mid); // 左の最大値
int rightmax=maxsub(nums,mid+1, right );//右側の最大値
 
 int midleft=nums[mid]; //中央から左
int midright=nums[mid+1]; //右中央
チーム=0;
 ( int i=mid;i>= left ;i --)の場合 
    {
        チーム+=数値[i];
        if(チーム>ミッドレフト)
            左中=チーム;
    }
    チーム=0;
 ( int i=mid+1;i<= right ;i++)の場合
    {
        チーム+=数値[i];
        if(チーム>ミッドライト)
            中央右=チーム;
    }
整数  max = midleft+midright; // 中央の最大値
    if(最大値< 左最大値 )
最大=左最大;
    if(最大値< 右最大値 )
最大=右最大;
戻る  最大;
 }

最も近い点

最も近いペアは、分割統治の最も成功した応用例の 1 つです。 2 次元の座標軸上には複数の点座標があり、最も近い 2 点間の距離を求める必要があります。直接求める場合、列挙型ブルートフォース法では非常に多くの計算が必要になります。通常、この問題を最適化するために分割統治法を使用します。

計算を直接 2 つの部分に分割すると、最も短い部分が左側にあり、もう 1 つが右側にある場合、問題が発生することが確実にわかります。最適化できます。

具体的な最適化計画では、x または y の次元を考慮し、データを 2 つの領域に分割し、最初に (同じ方法を使用して) 左側と右側の領域でそれぞれ最短のポイントペアを計算します。次に、2 つの距離のうち短い方に基づいて、左と右にカバーし、カバーした左と右のポイント間の距離を計算し、最小の距離を見つけて、現在の最短距離と比較します。

このように、この 1 つの操作だけで (状況を考慮せずに)、左側の赤い点は右側のほとんどの赤い点との距離計算を回避できることがわかります (時間計算量は O(n2))。実際、左右の区間内で計算を行う際も、分割統治の計算を何度も再帰的に実行します。図に示すように:

この方法により、多くの計算を節約できます。

ただし、この分割統治法には、2 次元座標がすべて特定の軸に沿って密集する可能性があるため、効果が明らかでない可能性がある (ポイントがすべて x=2 の近くにある場合、x 分割の効果は小さくなる) という問題があるため、この点に注意してください。

杭州Dianzi 1007はどなたにもお勧めです。エアコンのコードは次のとおりです。

 java.io.BufferedReader をインポートします。
 java.io.IOException をインポートします。
 java.io.InputStreamReader をインポートします。
 java.io.OutputStreamWriter をインポートします。
 java.io.PrintWriter をインポートします。
 java.io.StreamTokenizer をインポートします。
 java.util.ArrayList をインポートします。
 java.util.Arrays をインポートします。
 java.util.Comparator をインポートします。
 java.util.List をインポートします。
パブリッククラスMain {
静的 整数n;
公共 静的void main(String[] args)はIOExceptionをスローします{
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System. in )));
        PrintWriter出力= 新しい PrintWriter(新しい OutputStreamWriter(System.out ));
        //List<node>list=新しいArrayList();
         while( .nextToken()内!=StreamTokenizer.TT_EOF)
         {
             n=( int ) in .nval;if(n==0) {break;}
            ノード番号[]=新しいノード[n]; 
             
 ( int i=0;i<n;i++ )の場合
             {
 .nextToken()内; .nval内double x = ;
 .nextToken()内; .nval内のdouble y = ;
                // list.add (新しいノード(x,y));
 [i]=新しいノード(x,y)なし
             }
             Arrays.sort( no , com );
ダブル  min = search( no ,0,n-1);
出力.println(String.format( "%.2f" , Math.sqrt( min )/2));出力.flush();
         }
    }
    プライベートスタティック ダブルサーチ(ノード[] no , int  左、 int  右） {
 int中央 = (右+左) / 2;
ダブルminleng=0;
        if(左==右) {戻り値 ダブル.MAX_VALUE;}
そうでない場合、(左+1==右) {minleng= ( no [左].x- no [右].x)*( no [左].x- no [右].x)+( no [左].y- no [右].y)*( no [左].y- no [右].y);}
そうでない場合、 minleng = min (search( no , left ,mid),search( no ,mid, right ));
 int ll=mid; int rr=mid+1;
        while( no [mid].y - no [ll].y <= Math.sqrt(minleng)/2&&ll-1> = left ) {ll --;}  
        while( no [rr].y- no [mid].y<=Math.sqrt(minleng)/2&&rr+1<= right ) {rr++;}
 ( int i=ll;i<rr;i++ )の場合
        {
 ( int j=i+1;j<rr+1;j++)の場合
            {
ダブルチーム=0;
                if( Math.abs (( [i].xなし- [j].xなし)*( [i].xなし- [j].xなし))>minleng) {続行;}
それ以外 
                {
                    チーム=( [i].xなし- [j].xなし)*( [i].xなし- [j].xなし)+( [i].yなし- [j].yなし)*( [i].yなし- [j].yなし);
                    チーム<minleng)minleng=チーム;
                }
            }
        }
 minlengを返します。 
     
    }
    プライベートスタティック ダブル  min (ダブルa、ダブルb) {
        //TODO 自動生成されたメソッドスタブ
a<b?a:b;を返します。
    }
静的コンパレータ<node>com=新しいコンパレータ<node>() { 
 
        @オーバーライド
公共  int compare(ノードa1, ノードa2) {
            //TODO 自動生成されたメソッドスタブ
a1.y-a2.y>0?1:-1を返します。
        }};
静的クラス Node
    {
ダブルx;
ダブルy;
パブリックノード( double x, double y)
        {
            .x = x;
            y = y;
        }
    }
 }

結論

分割統治アルゴリズムについて私が言いたいことはこれだけです。分割統治アルゴリズムで重要なのは、そのアイデアを理解することだからです。また、大きな整数の乗算、シュトラッセン行列の乗算、チェス盤のカバー、線形時間選択、ラウンドロビンスケジュール、ハノイの塔など、分割統治アルゴリズムによって解決される典型的な問題もいくつかあります。分割統治アルゴリズムのアイデアと原理を自分で研究することができます。

オリジナルリンク: https://mp.weixin.qq.com/s/jHiBOjfyMvuvGzSecsdNPw

<<: AIを使って新薬を「発見」し、研究開発を加速させる

>>: 業界規模のナレッジグラフ：経験と課題