貪欲なアルゴリズムと例: とは何か、方法とアプローチ

替え： サラ・チェン サラ・チェン
Hours 更新中

貪欲なアルゴリズムとは何ですか?

In 貪欲なアルゴリズム リソースのセットは、実行の任意の段階でのそのリソースの最大かつ即座の可用性に基づいて再帰的に分割されます。

貪欲なアプローチに基づいて問題を解決するには、XNUMX つの段階があります

  1. アイテムのリストをスキャンする
  2. 最適化

これらの段階は、この貪欲アルゴリズム チュートリアルで配列の分割の過程で並行して説明されています。

貪欲なアプローチを理解するには、再帰とコンテキストの切り替えに関する実践的な知識が必要です。 これは、コードをトレースする方法を理解するのに役立ちます。 貪欲なパラダイムは、独自の必要十分なステートメントの観点から定義できます。

貪欲なパラダイムは XNUMX つの条件によって定義されます。

  • 各段階的な解決策では、最も受け入れられる解決策に向けて問題を構造化する必要があります。
  • 問題の構造化が有限数の貪欲なステップで停止できれば十分です。

理論化を続けながら、Greedy 検索アプローチに関連する歴史を説明しましょう。

貪欲の歴史 Algorithms

貪欲アルゴリズムの重要なランドマークは次のとおりです。

  • 貪欲アルゴリズムは、1950 年代に多くのグラフウォーク アルゴリズムのために概念化されました。
  • Esdger Djikstra は、最小限のスパニング ツリーを生成するアルゴリズムを概念化しました。 彼はオランダの首都アムステルダム内の路線の距離を短縮することを目指した。
  • 同じ XNUMX 年に、プリムとクラスカルは、重み付けされたルートに沿ったパス コストの最小化に基づいた最適化戦略を達成しました。
  • 70 年代に、アメリカの研究者であるコーメン、リベスト、スタインらは、アルゴリズムの古典的な入門書の中で、貪欲解の再帰的サブ構造化を提案しました。
  • 貪欲な検索パラダイムは、2005 年に異なるタイプの最適化戦略として NIST の記録に登録されました。
  • これまで、Open-Shortest-Path-First (OSPF) やその他の多くのネットワーク パケット スイッチング プロトコルなど、Web を実行するプロトコルは、ネットワークで費やす時間を最小限に抑えるために貪欲な戦略を使用していました。

貪欲な戦略と決断

最も簡単な形のロジックは、「貪欲である」か「貪欲でない」かに要約されます。 これらのステートメントは、アルゴリズムの各段階を進めるために採用されたアプローチによって定義されています。

たとえば、Djikstra のアルゴリズムは、コスト関数を計算してインターネット上のホストを識別する段階的な貪欲戦略を利用しました。コスト関数によって返される値によって、次のパスが「貪欲」か「非貪欲」かが決まります。

つまり、アルゴリズムは、いずれかの段階で局所的に貪欲ではないステップを実行すると、貪欲でなくなります。 貪欲の問題は、これ以上貪欲の範囲がなくなると止まります。

貪欲なアルゴリズムの特徴

Greedy アルゴリズムの重要な特徴は次のとおりです。

  • リソースの順序付きリストがあり、コストまたは価値の属性が示されています。 これらはシステム上の制約を定量化します。
  • 制約が適用される時間内にリソースを最大量使用することになります。
  • たとえば、アクティビティのスケジュール設定の問題では、リソース コストは時間単位で表され、アクティビティは順番に実行する必要があります。

貪欲なアルゴリズムの特徴

なぜ貪欲なアプローチを使用するのでしょうか?

貪欲なアプローチを使用する理由は次のとおりです。

  • 貪欲なアプローチにはいくつかのトレードオフがあるため、最適化に適している可能性があります。
  • 顕著な理由の XNUMX つは、最も実現可能な解決策を直ちに実現するためです。 アクティビティ選択問題 (以下で説明) では、現在のアクティビティを終了する前にさらにアクティビティを実行できる場合、これらのアクティビティを同じ時間内で実行できます。
  • もう XNUMX つの理由は、すべての解決策を組み合わせる必要がなく、条件に基づいて問題を再帰的に分割できることです。
  • アクティビティ選択問題では、「再帰的分割」ステップは、アイテムのリストを XNUMX 回だけスキャンし、特定のアクティビティを考慮することによって実現されます。

アクティビティ選択問題の解決方法

アクティビティのスケジュール設定の例では、すべてのアクティビティに「開始」時間と「終了」時間があります。 各アクティビティには、参照用の番号が付けられています。 アクティビティには XNUMX つのカテゴリがあります。

  1. 考慮されたアクティビティ: はアクティビティです。これは、残りの XNUMX つ以上のアクティビティを実行する能力を分析するための参照です。
  2. 残りのアクティビティ: 考慮されているアクティビティよりも前の XNUMX つ以上のインデックスにあるアクティビティ。

合計期間は、アクティビティを実行するコストを示します。 つまり、(終了 – 開始) によって、アクティビティのコストとしての期間が得られます。

貪欲な範囲とは、考慮されたアクティビティの時間内に実行できる残りのアクティビティの数であることがわかります。

関連記事

Archi貪欲なアプローチの構造

ステップ1） 検討中のインデックスとしてインデックス 0 から始めて、アクティビティ コストのリストをスキャンします。

ステップ2） 検討中のアクティビティが終了するまでにさらに多くのアクティビティを終了できる場合は、残りの 1 つ以上のアクティビティの検索を開始します。

ステップ3） 残りのアクティビティがなくなった場合、現在残っているアクティビティが次に考慮されるアクティビティになります。 新しく検討したアクティビティについて、ステップ 1 とステップ 2 を繰り返します。 アクティビティが残っていない場合は、ステップ 4 に進みます。

ステップ4） 考慮されたインデックスの和集合を返します。 これらは、スループットを最大化するために使用されるアクティビティ インデックスです。

Archi貪欲なアプローチの構造
Archi貪欲なアプローチの構造

コードの説明

#include<iostream>
#include<stdio.h>
#include<stdlib.h>

#define MAX_ACTIVITIES 12

Archi貪欲なアプローチの構造

コードの説明：

  1. インクルードされるヘッダー ファイル/クラス
  2. ユーザーが提供するアクティビティの最大数。
using namespace std;

class TIME
{
    public:
    int hours;

    public: TIME()
    {
   	 hours = 0;
    }
};

Archi貪欲なアプローチの構造

コードの説明：

  1. ストリーミング操作の名前空間。
  2. TIME のクラス定義
  3. XNUMX 時間のタイムスタンプ。
  4. TIME のデフォルトコンストラクター
  5. 時間変数。
class Activity
{
    public:
    int index;
    TIME start;
    TIME finish;

    public: Activity()
    {
   	 start = finish = TIME();
    }
};

Archi貪欲なアプローチの構造

コードの説明：

  1. アクティビティからのクラス定義
  2. 期間を定義するタイムスタンプ
  3. デフォルトのコンストラクターでは、すべてのタイムスタンプが 0 に初期化されます。
class Scheduler
{
    public:
    int considered_index,init_index;
    Activity *current_activities = new    Activity[MAX_ACTIVITIES];
    Activity *scheduled;

Archi貪欲なアプローチの構造

コードの説明：

  1. スケジューラ クラス定義のパート 1。
  2. 考慮されたインデックスは、スキャンの開始点です。 配列.
  3. 初期化インデックスは、ランダムなタイムスタンプを割り当てるために使用されます。
  4. アクティビティ オブジェクトの配列は、new 演算子を使用して動的に割り当てられます。
  5. スケジュールされたポインタは、貪欲の現在のベース位置を定義します。
Scheduler()
{
   	 considered_index = 0;
   	 scheduled = NULL;
...
...

Archi貪欲なアプローチの構造

コードの説明：

  1. スケジューラ コンストラクター – スケジューラ クラス定義のパート 2。
  2. 考慮されたインデックスは、現在のスキャンの現在の開始を定義します。
  3. 現在のグリーディ エクステントは、最初は未定義です。
for(init_index = 0; init_index < MAX_ACTIVITIES; init_index++)
 {
   		 current_activities[init_index].start.hours =
   			 rand() % 12;

   		 current_activities[init_index].finish.hours =
   			 current_activities[init_index].start.hours +
   				 (rand() % 2);

   		 printf("\nSTART:%d END %d\n",
   		 current_activities[init_index].start.hours
   		 ,current_activities[init_index].finish.hours);
 }
…
…

Archi貪欲なアプローチの構造

コードの説明：

  1. 現在スケジュールされている各アクティビティの開始時間と終了時間を初期化する for ループ。
  2. 開始時刻の初期化。
  3. 終了時間の初期化は常に開始時間後、または開始時間ちょうどに行われます。
  4. 割り当てられた期間を出力するデバッグ ステートメント。
	public:
   		 Activity * activity_select(int);
};

Archi貪欲なアプローチの構造

コードの説明：

  1. パート 4 – スケジューラ クラス定義の最後の部分。
  2. アクティビティ選択関数は、開始点インデックスをベースとして取り、貪欲なクエストを貪欲なサブ問題に分割します。
Activity * Scheduler :: activity_select(int considered_index)
{
    this->considered_index = considered_index;
    int greedy_extent = this->considered_index + 1;
…
…

Archi貪欲なアプローチの構造

  1. スコープ解決演算子 (::) を使用して、関数定義が提供されます。
  2. 考慮されるインデックスは、値によって呼び出されるインデックスです。 greedy_extent は、考慮されたインデックスの直後に初期化されるインデックスです。
Activity * Scheduler :: activity_select(int considered_index)
{
    	while( (greedy_extent < MAX_ACTIVITIES ) &&
   	 ((this->current_activities[greedy_extent]).start.hours <
   		 (this->current_activities[considered_index]).finish.hours ))
    	{
   	 printf("\nSchedule start:%d \nfinish%d\n activity:%d\n",
   	 (this->current_activities[greedy_extent]).start.hours,
   	 (this->current_activities[greedy_extent]).finish.hours,
   	 greedy_extent + 1);
   	 greedy_extent++;
    	}
…
...

Archi貪欲なアプローチの構造

コードの説明：

  1. コア ロジック - 貪欲な範囲はアクティビティの数に制限されます。
  2. 現在のアクティビティの開始時間は、検討中のアクティビティ (検討中のインデックスによって指定) が終了する前にスケジュール可能かどうかがチェックされます。
  3. これが可能な限り、オプションのデバッグ ステートメントが出力されます。
  4. アクティビティ配列の次のインデックスに進みます。
...
if ( greedy_extent <= MAX_ACTIVITIES )
    {

   	 return activity_select(greedy_extent);
    }
    else
    {
   	 return NULL;
    }
}

Archi貪欲なアプローチの構造

コードの説明：

  1. 条件は、すべてのアクティビティがカバーされているかどうかをチェックします。
  2. そうでない場合は、検討中のインデックスを現在のポイントとしてグリーディを再開できます。 これは、問題ステートメントを貪欲に分割する再帰的なステップです。
  3. 「はい」の場合、拡張欲の範囲なしで呼び出し元に戻ります。
int main()
{
    Scheduler *activity_sched = new Scheduler();
    activity_sched->scheduled = activity_sched->activity_select(
   				activity_sched->considered_index);
    return 0;
}

Archi貪欲なアプローチの構造

コードの説明：

  1. スケジューラを呼び出すために使用される main 関数。
  2. 新しいスケジューラがインスタンス化されます。
  3. アクティビティ タイプのポインタを返すアクティビティ選択関数は、貪欲なクエストが終了した後に呼び出し元に戻ります。

出力：

START:7 END 7

START:9 END 10

START:5 END 6

START:10 END 10

START:9 END 10

Schedule start:5 
finish6
 activity:3

Schedule start:9 
finish10
 activity:5

貪欲な手法の限界

並べ替えなど、すべてのサブ問題に対して解決策が必要な貪欲な問題には適していません。

このような Greedy アルゴリズムの練習問題では、Greedy メソッドが間違っている可能性があります。 最悪の場合、最適ではない解決策が導かれることさえあります。

したがって、貪欲アルゴリズムの欠点は、現在の貪欲状態の先に何があるのか​​を知らないことです。

以下は、Greedy メソッドの欠点を示しています。

貪欲な手法の限界

ここでツリーとして示されている貪欲スキャン (値が大きいほど貪欲度が高い) では、値 40 のアルゴリズム状態は、次の値として 29 を取る可能性があります。 さらに、そのクエストは 12 で終了します。これは値 41 に相当します。

ただし、アルゴリズムが次善のパスを選択した場合、または征服戦略を採用した場合。 25 の後に 40 が続き、全体的なコスト改善は 65 となり、これは次善の決定として 24 ポイント高く評価されます。

貪欲の例 Algorithms

ほとんどのネットワーク アルゴリズムは貪欲なアプローチを使用します。貪欲なアルゴリズムの例をいくつか示します。

  • Prim の最小スパニング ツリー アルゴリズム
  • 巡回セールスマン問題
  • グラフ - 地図の色付け
  • Kruskal の最小スパニング ツリー アルゴリズム
  • ダイクストラの最小スパニング ツリー アルゴリズム
  • グラフ – 頂点カバー
  • ナップサック問題
  • ジョブのスケジュールの問題

まとめ

要約すると、この記事では貪欲なパラダイムを定義し、貪欲な最適化と再帰が、ある時点まで最良の解決策を得るのにどのように役立つかを示しました。貪欲アルゴリズムは、貪欲アルゴリズムとして多くの言語で問題解決に広く応用されています。 Python、C、C#、PHP、 Java貪欲アルゴリズムの例のアクティビティ選択は、貪欲アプローチを使用して最大スループットを達成できる戦略的問題として説明されました。最後に、貪欲アプローチの使用のデメリットが説明されました。

よろしければ：