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

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

[[398991]]

アルゴリズムの紹介

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

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

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

  1. 分解: 元の問題を、元の問題と同じ形式のいくつかのより小さな独立したサブ問題に分解する
  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. ディスクが1つの場合、A->C
  2. n>=2 のディスクの場合、常に 2 つのディスクとして表示できます。1 つは下部のディスク、もう 1 つはその上のすべてのディスクです。まず、上部のディスクをすべて A から B に移動し、下部のディスクを A から C に移動し、タワー B のすべてのディスクを B から C に移動します。
  1. パッケージ com.xie.algorithm;
  2.  
  3. パブリッククラスHanoiTower {
  4. 公共 静的void main(String[] args) {
  5. ハノイタワー(3, 'A' , 'B' , 'C' );
  6. /**
  7. * 最初のディスクはA->Cです
  8. * 2番目のディスクはA->Bです
  9. * 最初のディスクはC->Bです
  10. * 3番目のディスクはA->Cです
  11. * 最初のディスクはB->Aです
  12. * 2番目のディスクはB->Cです
  13. * 最初のディスクはA->Cです
  14. */
  15. }
  16.  
  17. 公共 静的void hanoiTower( int num, char a, char b, char c) {
  18. //ディスクが1つしかない場合
  19. 数値 == 1 の場合
  20. System.out.println ( "" +a+ "->" +cからの最初のディスク);
  21. }それ以外{
  22. //n>=2 ディスクの場合、常に 2 つのディスクとして表示され、1 つは一番下のディスク、もう 1 つはその上のすべてのディスクです。
  23. //1. まず一番上のディスクをAからBに移動します。移動プロセスではCを使用します。
  24. ハノイタワー(数値 - 1, a, c, b);
  25. //2. 下のディスクをAからCに移動する
  26. システム.out.println ( "the" + num + "disk from" + a + "->" + c);
  27. //3. タワーBのすべてのディスクをBからCに移動し、移動プロセスでタワーAを使用します。
  28. ハノイタワー(数値 - 1, b, a, c);
  29. }
  30. }
  31. }

【編集者のおすすめ】

  1. 仮想サーバー管理の6つのベストプラクティス
  2. 2021 年にソフトウェア開発業界を支配する 15 のテクノロジー トレンド
  3. コンピュータのインストールに必須のソフトウェア 5 つ。それぞれが他のものよりも強力で、一度使用するとそれなしでは生きていけなくなります。
  4. これは素晴らしい。これは私が今まで見たSpringCloudマイクロサービスアーキテクチャの最も詳細な説明です | 添付の面接の質問
  5. 中国の3大通信事業者はニューヨーク証券取引所から上場廃止されたことで損失を被ったのか?

<<:  5GとAI: 現在と未来の補完的なテクノロジー

>>:  新しいディープラーニングモデルがエッジデバイスに画像セグメンテーションをもたらす方法

ブログ    
ブログ    

推薦する

Facebookの詐欺行為と戦う方法を学び、CopyCatchアルゴリズムがLockstepをどのように解決するかを見てみましょう

[51CTO.com クイック翻訳] インターネットが誕生して以来、あらゆる種類のジャンク情報や悪意...

...

...

...

Facebook Cityは楽しいです!ドローンで遠隔地の山岳地帯にモバイルネットワークを提供

[51CTO.comからのオリジナル記事] Facebookは、インド政府および通信会社と協議し、太...

Yisaqi 9周年: RPA製品の進化を振り返る

現在、国内RPA市場の競争は激化しており、多くのメーカーが独自のRPA製品やブランドを立ち上げていま...

...

...

...

2023年以降を一変させる5G IoTテクノロジートップ10

IoT 分野の拡大と発展により、多くの変革的テクノロジーがもたらされるでしょう。家庭から自動車、ウ...

家庭用ロボットを作り、独自の研究開発の道を歩む

ロボットを作ることは私の子供の頃からの夢でした。 2011年に私はハルビン工業大学に入学し、そこが私...

ウルトラマンが解雇されるのは今回が初めてではない! YCを去った人物は「創設者から去るように言われた」

ウルトラマンニウフルが「追い出される」のは初めてではないでしょうか? ? !予想外にも、OpenAI...

Tmall のプログラマーがハイエンド アルゴリズムを使用して女の子を探す

問題は、アリ・タブロイド紙の公開記事によると: [[93064]] #p#これは本当の、そして少し悲...

ウェブデザインに人工知能を活用する10の方法

[[210916]]今日、Web デザインは絶えず進化しており、トップクラスの Web デザイナーは...

中国ダイビングチームの勝利には人工知能が貢献した

ネットユーザーたちはこのオリンピックについて不満を述べている。たとえ境界線を越えたとしても、高得点を...