欲張りアルゴリズムの最適性

Question

最適な解決策を得るために欲張りなアルゴリズムを設計し、アルゴリズムは異なる値の組み合わせを生成することができるがそれでも、これらの組み合わせのいずれかが最適解です。どのようにそれが最適性であることを証明するか？

たとえば、数字のセットがあります。 $ \ mathcal {m}={1,2,3,4 \} $ 、デザインしたいです。合計5を取得するために必要な整数の最小数を取得するためのアルゴリズム5.この場合、 $ 1,4 $ または $ 2、3 $ は5を生成でき、どちらも必要な最小数が2つであるため、最適な解決策です。

アルゴリズムの最適性を証明する方法？

矛盾することで試してみたが、最適な解決策 $ P ^ * $ と私のアルゴリズムは最適な解決策 $ p $ so $ p \ neq p ^ * $ 。しかし、私は議論を続ける方法を知っています。

Answer 1

これは 作成問題 です。いくつかの宗派のいくつかのセット（例えば、いくつかの基本 $ B $ 、米国コイン、またはほとんどすべてのコインシステムの電力）のために、貪欲なアルゴリズムは最小限の数を与えますコイン一般的なケースはNP完成です、実用的な解決策は動的なプログラミングを必要とする（好きなウィキペディアの記事を参照）。所与の分母が貪欲アルゴリズムを最適にするかどうかを確認する多項式時間アルゴリズムは、 Pearson（1994）＆quot;変化問題の多項式-Timeアルゴリズム" 、DOI 10.1.1.57.3243。

Answer 2

貪欲なアルゴリズムが常に最適ではない場合、Chenterexampleはこれの十分な証明です。

この場合は、 $ \ mathcal {m}={1,2,4,5,6 \} $ です。その後、 $ 9 $ の合計の場合、貪欲なアルゴリズムは $ 6 + 2 + 1 $ を生成しますが、これは最適ではありません $ 5 + 4 $ なので、サマンドが少なくなります。

Answer 3

貪欲アルゴリズムは通常一連の選択を含み、選択が行われたら、次のステップでそれを元に戻すことはできません。だから彼ら（貪欲なアルゴリズム）が間違えなかったことは重要です。局所最適解は、可能な限り最良の解決策を意味します。

SET $ S $ は、いくつかの問題に対する最適な解決策であり、私たちの貪欲アルゴリズムはset $ p $ < /スパン>。 $ p $ と $ s $ の両方が同じ場合は同じです。両方の $ p $ と $ s $ が異なると仮定します。最適な最適ではない中間ステップ（ローカルソリューション）の要素は、 $ p $ ではなく、最適なset $ s $ < /スパン>。しかし、貪欲なアルゴリズムによると、私たちは常に地域の最適解を選びます。したがって、議論は矛盾による証明によって証明されます。