例で説明された欲張りアルゴリズム

欲張りアルゴリズムとは何ですか?

ここの記事のいくつかをふるいにかけている間、あなたは多くのアルゴリズム設計技術について聞いたことがあるかもしれません。それらのいくつかは次のとおりです。

  • 強引な
  • 分割統治
  • 欲張りプログラミング
  • いくつか例を挙げると、動的計画法。この記事では、欲張りアルゴリズムとは何か、そしてこの手法を使用して、他の方法では簡単ではないように思われる多くのプログラミング問題を解決する方法について学習します。

あなたがハイキングに行くと想像してください、そしてあなたの目標は可能な限り最高のピークに到達することです。開始する前にすでにマップがありますが、マップには何千もの可能なパスが表示されています。あなたは怠惰すぎて、それぞれを評価する時間がありません。地図をねじ込みます!あなたは単純な戦略でハイキングを始めました–貪欲で近視眼的です。最も上向きに傾斜している道を進むだけです。これはハイキングのための良い戦略のようです。しかし、それは常に最高ですか?

旅行が終わり、全身が痛くて疲れた後、初めてハイキングマップを見る。何てことだ!上向きに歩き続けるのではなく、渡るべきだった泥だらけの川があります。これは、欲張りアルゴリズムが最良の即時選択を選択し、その選択を再検討しないことを意味します。ソリューションの最適化に関しては、これは単に、欲張りソリューションがローカルの最適ソリューションを見つけようとすることを意味します。これは多くの場合があり、グローバルな最適ソリューションを見逃す可能性があります。

正式な定義

特定のポイントで最適化(最大化または最小化)する必要のある目的関数があると仮定します。欲張りアルゴリズムは、目的関数が最適化されるように、各ステップで貪欲な選択を行います。欲張りアルゴリズムは、最適解を計算するためのショットが1つしかないため、二度と戻って決定を覆すことはありません。

欲張りアルゴリズムには、いくつかの長所と短所があります。

  • 問題に対して欲張りアルゴリズム(または複数の欲張りアルゴリズム)を思い付くのは非常に簡単です。欲張りアルゴリズムの実行時間の分析は、通常、他の手法(分割統治法など)よりもはるかに簡単です。分割統治法の場合、その法が速いか遅いかは明確ではありません。これは、再帰の各レベルでのサイズが小さくなり、サブ問題の数が増えるためです。
  • 難しいのは、欲張りアルゴリズムの場合、正確性の問題を理解するためにもっと一生懸命働かなければならないということです。正しいアルゴリズムを使用しても、なぜそれが正しいのかを証明するのは困難です。欲張りアルゴリズムが正しいことを証明することは、科学というよりは芸術です。それは多くの創造性を伴います。通常、アルゴリズムを考え出すのは簡単に思えるかもしれませんが、それが実際に正しいことを証明することは、まったく別の問題です。

間隔スケジューリングの問題

ほぼすべての業界またはあらゆる分野で遭遇する可能性のある興味深い問題に飛び込みましょう。問題のいくつかの例は次のとおりです。

  • 大学での1日の講義のNスケジュールのセットが与えられます。特定の講義のスケジュールは(s時間、f時間)の形式であり、s時間はその講義の開始時間を表し、同様にf時間は終了時間を表します。 Nの講義スケジュールのリストを前提として、どの講義も互いに重複しないように、日中に開催される講義の最大セットを選択する必要があります。  つまり、講義LiとLjが選択に含まれている場合、jの開始時刻> = iの終了時間またはその逆
  • あなたの友人はキャンプカウンセラーとして働いており、彼は一連のキャンパーのための活動を組織することを担当しています。彼の計画の1つは、次のミニトライアスロンエクササイズです。各競技者は、プールを20周泳ぎ、10マイルを自転車で走り、3マイル走る必要があります。
  • 計画では、次のルールに従って、競技者を千鳥状に送り出します。競技者は一度に1つずつプールを使用する必要があります。つまり、最初の1人の競技者は、20周を泳ぎ、出て、自転車に乗り始めます。
  • この一人称がプールから出るとすぐに、2人目の競技者が20周を泳ぎ始めます。外出して自転車に乗り始めるとすぐに、3人目の競技者が水泳を始めます。
  • 各競技者には、予想される水泳時間、予想される自転車時間、および予想される実行時間があります。あなたの友人は、トライアスロンのスケジュール、つまり競技者のスタートを順番に並べる順序を決めたいと思っています。
  • スケジュールの完了時間は、時間の予測が正確であると仮定して、すべての競技者がトライアスロンの3つのレッグすべてで終了する最も早い時間であるとしましょう。競争全体をできるだけ早く終わらせたいのであれば、人々を送り出すための最良の順序は何ですか?より正確には、完了時間が可能な限り短いスケジュールを生成する効率的なアルゴリズムを提供します

講義スケジューリング問題

この問題を解決するためのさまざまなアプローチを見てみましょう。

最も早い開始時刻最初、  つまり、最も早い開始時刻を持つ間隔を選択します。このソリューションを破る次の例を見てください。非常に早く開始する間隔が非常に長い可能性があるため、このソリューションは失敗しました。これは、私たちが試すことができる次の戦略は、最初に小さな間隔を調べることであることを意味します。

最初の最も早い開始時間

最小間隔最初、  つまり、全体的な間隔の順に講義を選択することになります。これは、講義に他なりません  finish time - start time。繰り返しますが、この解決策は正しくありません。次の場合を見てください。

最初の最短間隔

最短間隔の講義が真ん中の講義であることがはっきりとわかりますが、それはここでは最適な解決策ではありません。このソリューションから洞察を得て、この問題のさらに別のソリューションを見てみましょう。

Least Conflicting Interval First  i.e. you should look at intervals that cause the least number of conflicts. Yet again we have an example where this approach fails to find an optimal solution.

競合の少ない間隔を最初に

The diagram shows us that the least confliciting interval is the one in the middle with just 2 conflicts. After that we can only pick the two intervals at the very ends with conflicts 3 each. But the optimal solution is to pick the 4 intervals on the topmost level.

Earliest Finishing time first. This is the approach that always gives us the most optimal solution to this problem. We derived a lot of insights from previous approaches and finally came upon this approach. We sort the intervals according to increasing order of their finishing times and then we start selecting intervals from the very beginning. Look at the following pseudo code for more clarity.

function interval_scheduling_problem(requests) schedule \gets \{\} while requests is not yet empty choose a request i_r \in requests that has the lowest finishing time schedule \gets schedule \cup \{i_r\} delete all requests in requests that are not compatible with i_r end return schedule end 

When do we use Greedy Algorithms

Greedy Algorithms can help you find solutions to a lot of seemingly tough problems. The only problem with them is that you might come up with the correct solution but you might not be able to verify if its the correct one. All the greedy problems share a common property that a local optima can eventually lead to a global minima without reconsidering the set of choices already considered.

欲張りアルゴリズムは、次のようなさまざまな種類の問題を解決するのに役立ちます。

最短経路問題:

グラフの最小全域木問題

ハフマン符号化の問題

Kセンターの問題