28

ある試験で、二分探索は分割統治アルゴリズムかどうか尋ねられました。私の答えはイエスでした。なぜなら、結果に到達するまで、問題をより小さなサブ問題に分割したからです。

しかし、試験官は、征服の部分はどこにあるのかと尋ねましたが、私は答えることができませんでした. 彼らはまた、それが実際には分割統治アルゴリズムであることを認めませんでした。

しかし、私がウェブ上でどこに行っても、そうであると書かれているので、その理由と、その征服部分がどこにあるのか知りたいです?

4

17 に答える 17

20

本

Data Structures and Algorithm Analysis in Java, 2nd edtition, Mark Allen Weiss

D&C アルゴリズムには 2 つの互いに素な再帰呼び出しが必要であると述べています。つまり、QuickSort が好きです。たとえ再帰的に実装できたとしても、二分探索にはこれがないので、これが答えだと思います。

于 2012-01-13T14:16:54.200 に答える
12

分割統治ではないと思います。 http://en.wikipedia.org/wiki/Divide_and_conquer_algorithmの最初の段落を参照してください。

問題を 2 つ以上のサブ問題に再帰的に分解し、それらを組み合わせてソリューションを提供する

二分探索では、ステップごとにデータを半分に減らすだけの問題がまだ 1 つしかないため、結果の征服 (マージ) フェーズは必要ありません。

于 2012-01-13T12:25:37.670 に答える
6

分割統治戦略では:

1.問題は部分に分かれています。

2.これらの各部分は、手元にあるアルゴリズムを適用することにより、個別に攻撃/解決されます (ほとんどの場合、この目的のために再帰が使用されます)。

3.次に、各パーティション/分割のソリューションと組み合わせ/マージして、問題全体の最終的なソリューションに到達します (これは征服されます)

例、クイックソート、マージソート。

基本的に、二分探索アルゴリズムは、反復ごとにワークスペース (サイズ n の入力 (順序付け) 配列) を半分に分割します。したがって、それは間違いなく分割戦略を展開しており、その結果、時間の複雑さは O(lg n) に減少します。したがって、これはその「分割」部分をカバーします。

お気づきのように、最終的な解決策は、最後に行われた比較から得られます。つまり、比較する要素が 1 つだけ残っている場合です。二分探索は解をマージまたは結合しません。

要するに、二分探索は問題のサイズ(それが機能しなければならない) を半分に分割しますが、解決策を少しずつ見つけることはできないため、解決策をマージする必要はありません!

少し長すぎることは承知していますが、お役に立てば幸いです:)

また、以下からアイデアを得ることができます: https://www.khanacademy.org/computing/computer-science/algorithms/binary-search/a/running-time-of-binary-search

また、この質問がずっと前に投稿されたことに今気づきました！悪い！

于 2016-09-09T15:55:54.097 に答える
3

どうやら二分探索を分割統治アルゴリズムと考える人もいれば、そうでない人もいます。これを D&C アルゴリズムと呼んでいる 3 つの参考文献 (すべて学界に関連しているようです) をすぐにグーグルで検索しまし た 。 /C455/html/notes/Chapter2/DivConq.htm http://www.csc.liv.ac.uk/~ped/teachadmin/algor/d_and_c.html

D&C アルゴリズムには、少なくとも次の 3 つのフェーズの最初の 2 つのフェーズが必要であるというのは、一般的な合意だと思います。

  • 分割します。つまり、問題全体をサブ問題に分割する方法を決定します。
  • 征服する、つまり、サブ問題のそれぞれを個別に解決します。
  • [オプション] 組み合わせる、つまり、独立した計算の結果を一緒にマージします。

第 2 段階 - 征服 - は、同じ手法を再帰的に適用して、さらに小さなサブサブ問題に分割するなどして、サブ問題を解決する必要があります。ただし、実際には、小さなサイズの場合と同様に、再帰的アプローチを制限するために、いくつかのしきい値が使用されることがよくあります。問題を解決するには、別のアプローチの方が速い場合があります。たとえば、クイックソートの実装では、ソートする配列部分のサイズが小さくなると、バブルソートなどを使用することがよくあります。

3 番目のフェーズはノーオペレーションである可能性があり、私の意見では、アルゴリズムが D&C として失格になることはありません。for一般的な例は、すべての反復が独立したデータ項目で純粋に機能する (つまり、任意の形式の縮小がない) ループの再帰分解です。一見役に立たないように見えるかもしれませんが、実際にはループを並列に実行するなどの非常に強力な方法であり、Cilk や Intel の TBB などのフレームワークで利用されています。

元の質問に戻ります: アルゴリズムを実装するいくつかのコードを考えてみましょう (私は C++ を使用します; これがあなたが慣れている言語でない場合は申し訳ありません):

int search( int value, int* a, int begin, int end ) {
  // end is one past the last element, i.e. [begin, end) is a half-open interval.
  if (begin < end)
  {
    int m = (begin+end)/2;
    if (value==a[m])
      return m;
    else if (value<a[m])
      return search(value, a, begin, m);
    else
      return search(value, a, m+1, end);
  }
  else // begin>=end, i.e. no valid array to search
    return -1;
}

ここに分割部分がint m = (begin+end)/2;あり、残りはすべて征服部分です。アルゴリズムは、分岐の 1 つだけが取られる場合でも、再帰的な D&C 形式で明示的に記述されています。ただし、ループ形式で記述することもできます。

int search( int value, int* a, int size ) {
  int begin=0, end=size;
  while( begin<end ) {
    int m = (begin+end)/2;
    if (value==a[m])
      return m;
    else if (value<a[m])
      end = m;
    else
      begin = m+1;
  }
  return -1;
}

ループを使用して二分探索を実装するのは非常に一般的な方法だと思います。共通性がわかりやすいように、再帰的な例と同じ変数名を意図的に使用しました。したがって、繰り返しますが、中間点の計算は分割部分であり、ループ本体の残りの部分は征服部分であると言えます。

しかしもちろん、審査官の考え方が異なる場合、それが D&C であると納得させるのは難しいかもしれません。

更新: D&C アルゴリズムの一般的なスケルトン実装を開発する場合、API 適合性テストの 1 つとしてバイナリ検索を使用して、API が十分に強力でありながら簡潔であるかどうかを確認することを考えました。もちろん、それは何も証明しません:)

于 2012-01-13T16:17:18.290 に答える
2

分割統治アルゴリズムは、次の 3 つのステップに基づいています。

  1. 分ける
  2. 征服する
  3. 混ぜる

二分探索問題は、ソートされた配列 A[n] で x を見つけることとして定義できます。この情報によると：

  1. 除算: x を中央と比較する
  2. 征服: 1 つのサブ配列で再帰します。(この配列で x を見つける)
  3. 組み合わせる：必要ありません。
于 2015-11-21T21:36:20.227 に答える
2

分割部分はもちろん、セットを半分に分割することです。

征服部分は、検索された要素があるかどうか、および処理済み部分のどの位置にあるかを判断しています。

于 2012-01-13T12:24:27.497 に答える
2

二分探索は、征服のステップが明示的でないため、分割統治法で説明するのが難しいです。アルゴリズムの結果は、干し草の山にある針のインデックスです。純粋な D&C 実装では、最小の干し草の山 ( 01 つの要素のリスト) にある針のインデックスが返され、大きな干し草の山のオフセットが再帰的に追加されます。分割ステップで分割されました。

説明する疑似コード:

function binary_search has arguments needle and haystack and returns index
    if haystack has size 1
       return 0
    else 
        divide haystack into upper and lower half
        if needle is smaller than smallest element of upper half
            return 0 + binary_search needle, lower half
        else
            return size of lower half + binary_search needle, upper half

追加 (0 +またはsize of lower half) は征服部分です。ほとんどの人は、引数としてより大きなリストにインデックスを提供することでそれをスキップします。そのため、すぐには利用できないことがよくあります。

于 2012-01-13T12:25:10.337 に答える
2

Merge SortandQuick Sortアルゴリズムは、分割統治法を使用し(副問題が 2 つあるため)、減少統治Binary Search法に分類されます(副問題が 1 つあるため)。

したがって、二分探索は実際には、分割統治法ではなく、減少統治法を使用します。

ソース: https://www.geeksforgeeks.org/decrease-and-conquer/

于 2019-11-14T15:13:54.657 に答える
2

コンピューター サイエンスにおける二分法とは、2 つの相反する選択肢の間、つまり 2 つの異なる選択肢の中から選択することを指します。二分法とは、全体を正確に 2 つの重複しない部分に分割することです。つまり、全体を 2 つの部分に分割する手順です。これは、全体 (またはセット) を 2 つの部分 (サブセット) に分割することです: 1. 共同で網羅的: すべてがいずれかの部分に属している必要があります。2. 相互に排他的: 両方の部分に同時に属することはできません。

分割統治は、問題を同じタイプの 2 つ以上のサブ問題に再帰的に分割することによって機能し、これらが直接解決できるほど単純になるまで続けます。

そのため、二分探索は各反復でチェックするアイテムの数を半分にし、その半分で「キー」アイテムを見つける可能性があるかどうか、またはキーの不在を判断できる場合は残りの半分に移動する可能性があるかどうかを判断します。アルゴリズムは本質的に二分法であるため、バイナリ検索は、キーが見つからないことを返す終了条件に到達するまで、「キー」が一部にある必要があると信じます。

于 2012-09-20T07:40:53.827 に答える
1

適切な分割統治アルゴリズムでは、両方の部分を処理する必要があります。

したがって、多くの人は分割統治アルゴリズムを二分探索とは呼びません。それは問題を分割しますが、残りの半分を破棄します。

しかし、おそらく、あなたの審査官はあなたがどのように主張しているかを見たかっただけです。（良い）試験は事実ではなく、チャレンジが元の資料を超えたときにどのように反応するかについてです。

したがって、私見の正しい答えは次のようになります。

まあ、技術的には、それは分割ステップのみで構成されていますが、元のタスクの半分だけを征服する必要があり、残りの半分はすでに簡単に実行されています。

ところで：QuickSelectには、QuickSelectと呼ばれる素晴らしいバリエーションがあります。これは、実際にこの違いを利用して、平均的なO(n)中央値の検索アルゴリズムを取得します。これはQuickSortに似ていますが、関心のある半分にしか下降しません。

于 2012-01-14T16:35:58.943 に答える
0

二分探索は分割統治アルゴリズムです。

1) 分割統治アルゴリズムでは、小さなサブ問題 (分割部分) を解決することによって問題を解決し、そのソリューションを使用してより大きな問題 (征服) のソリューションを構築します。

2) ここでの問題は、ソートされた配列内の要素を見つけることです。これは、同様のサブ問題を解くことで解決できます。(ここでは、検索対象の要素が中央の要素よりも小さいか大きいかという決定に基づいて、サブ問題を作成しています)。したがって、一方の半分で要素が確実に存在できないことがわかったら、もう一方の半分で同様のサブ問題を解決します。

3) このように再帰します。

4) ここでの征服部分は、サブ問題によって返された値を再帰ツリーの先頭に戻すだけです

于 2012-09-17T05:21:48.153 に答える
0

非公式の定義は多かれ少なかれ次のとおりです。問題を小さな問題に分割します。次に、それらを解決してまとめます (征服)。解決とは、実際には次に進むべき場所 (左、右、見つかった要素) を決定することです。

ここにウィキペディアからの引用：

「分割統治」という名前は、ソートされたリスト内のレコードを見つけるためのバイナリ検索アルゴリズムなど、各問題を 1 つのサブ問題だけに縮小するアルゴリズムにも適用されることがあります。

これは、[更新: このフレーズを読み間違えました:)] 分割統治の一部に過ぎないと述べています。

更新： この記事は私にとってそれを明確にしました。定義では、すべてのサブ問題を解決する必要があると書かれているため、混乱しました。しかし、検索を続ける必要がないことがわかっている場合は、サブの問題を解決しました..

于 2012-01-13T12:26:11.493 に答える
0

減少と征服だと思います。

以下はウィキペディアからの引用です。

「名前の減少と征服は、単一サブ問題クラスの代わりに提案されました」

http://en.wikipedia.org/wiki/Divide_and_conquer_algorithms#Decrease_and_conquer

私の理解では、「征服」の部分は、バイナリ検索の目的の要素を見つけたときに最後にあります。「減少」の部分は検索スペースを減らしています。

于 2014-08-09T19:54:58.113 に答える
0

二分探索および三分探索アルゴリズムは、減少と征服の手法に基づいています。問題を分割しないため、実際には 2 で割ることによって問題を減らします (三分探索では 3)。

マージ・ソートおよびクイック・ソート・アルゴリズムは、分割統治技術の例として挙げることができます。問題を 2 つの部分問題に分割し、これらの部分問題のアルゴリズムを再度使用して配列を並べ替えます。ただし、バイナリ検索では配列の半分を破棄します。これは、除算ではなく、配列のサイズを縮小することを意味します。

于 2015-04-12T10:49:06.043 に答える