algorithm - 貪欲なアルゴリズムによる最適化

Question

貪欲な方法を使用して最適化問題を解くことができる場合、すべての最適解には常に最初の選択肢 (つまり、貪欲な選択) が含まれている必要があるというのは本当ですか?

Answer 1

私はあなたの質問を「すべての最適なソリューションのセットには常に最初の選択肢が含まれている必要がある」と解釈しています。そうしないと、ソリューションに別のソリューションが含まれても意味がありません。

当然のことながら、答えは自明です。貪欲なアルゴリズムが問題を解決すると、最適解が生成されます。これは、定義上、最適解のセットに含まれます。

おそらく、「貪欲なアルゴリズムが最適なソリューションを生成する場合がある場合...」という意味だったのかもしれませんが、その場合も答えは簡単です。

「貪欲なアルゴリズムが最適な解を生成する場合がある場合、すべての保証された最適なアルゴリズムもその解を生成するというのは本当ですか?」答えは、問題に固有の最適解があるか複数の解があるかによって異なります。

問題に複数の最適解がある場合、答えは明らかにノーです。

考える良い例は、すべての 1 桁の数字が 2 桁の数字よりも前に来るように、2 桁の数字が 3 桁の数字よりも前に来るように、数字のリストをソートすることです。私はe。99 が 11 の前に来るか、その逆かは気にせず、9 を 25 の前に、33 を 872 の前に、555 を 1234 の前に置きたいだけです。

この例の問題には、複数の最適解があります。怠惰ではあるが貪欲ではないアルゴリズムは、11 が 99 より前に来ることを保証しません。どちらも、互いに異なる最適解を生成します。

これが役に立たない場合、何もしません;-)