ほとんどの場合、混乱を招く事実は、問題を解決するために徹底的な検索 (動的プログラミングまたはバック トラッキングまたはブルート フォース) を使用するか、貪欲なアプローチを使用するかです。
私は貪欲を使用して可能な限り最善の解決策を決定することについて話しているのではなく、貪欲なアルゴリズムを使用して「解決策」を見つけることについて話しているのです。問題が貪欲なアプローチで解決できるかどうかを検証できる標準的な方法をいくつか取得しようとしています。最適部分構造と同様に、動的計画法の暗記。そして、特定の問題に関連していません。
貪欲なアプローチが常に最良の解決策を生み出すかどうかを判断するために私ができる誘導の証拠はありますか?
貪欲なアルゴリズムを使用して最適化問題を解決できることを証明するには、問題に次の要素があることを証明する必要があります。
最適な部分構造のプロパティ: 最適なグローバル ソリューションには、すべての部分問題の最適なソリューションが含まれます。
貪欲な選択性：局所的に最適な選択肢を貪欲に選択することで、大域的な最適解が得られる。
古典的な活動選択問題を考えてみましょう。n 個の活動の集合Sがあり、それぞれに開始時刻と終了時刻があります。選択によって重複しないイベントの数が最大になるように、S のサブセットを選択します。
s[i]e[i]
この問題は貪欲なアルゴリズムを使用して解決できますが、それをどのように証明できますか?
それが示すことを示す必要があります:
大域的最適解に含まれる一般的な活動aを考えてみましょう。S = {A', a, A''}SA'A''
問題に部分構造の最適なプロパティがある場合、部分問題の最適解はグローバル最適解に含まれる必要がありA'ますA''S。
これは本当ですが、なぜですか？
部分問題の最適解A'が にないとしSます。A'次に、最適な を に、たとえばS'に置き換えて、Aよりも優れた新しいグローバル最適解を得ることができSます。しかしS、グローバルな最適解でした! 矛盾。
貪欲な選択 (最初に終了するアクティビティを選択する) が正しいことを証明する必要があります。
B部分問題としましょう。最初に終了する部分問題のアクティビティを b とすると、bは(最初の) 貪欲な選択です。の最適解にbが含まれていることを証明する必要があります。BB
Xを部分問題 の最適解としますB。最初に終了するアクティビティを x とします。X
b = xの場合、bは にXあり、 の最適解でBあり、貪欲な選択が最適解に含まれることを示しました。
b != xの場合、確かにそれがありend_time[b] < end_time[x]ます。
bは私たちの貪欲な選択 (すなわち、部分問題 で最初に終了するアクティビティ) であったため、別の最適解を取得するためにb inにB置き換えることができます。のアクティビティの数が同じであるため最適であり、最適でした。この場合、bは にあり、 の最適解です。xXX' = (X \ {x}) U {b}X'XXX'B
したがって、私たちの貪欲な選択bは、いずれかの場合の最適解に含まれBます。
さらに、場合によっては、特定の問題が貪欲なアプローチで解決できることを機械的に証明するために使用できる強力な数学的理論があります。
簡単に言うと:
matroidという名前の特定の組み合わせ構造を定義できます。
一部の賢い人は、これらのマトロイドが最適部分構造プロパティと貪欲な選択プロパティを持っていることを過去に証明しました。
これは、最適化問題に対して貪欲なアルゴリズムを実行できることを意味し、最適解を見つけます。問題がマトロイドのような構造で定義されていることを確認するだけで済みます。
詳細については、こちらを参照してください。