8

最近、私はいくつかの欲張りアルゴリズムの問​​題を見てきました。私は局所的に最適であると混乱しています。ご存知のように、欲張りアルゴリズムは局所的に最適な選択肢で構成されています。しかし、局所的に最適な決定を組み合わせることは、必ずしも全体的に最適であることを意味するわけではありませんよね？

例として変更を加えます。15¢を作るために最小数のコインを使用します。10¢、5¢、および1¢のコインがある場合、1つの10¢と1つの5¢でこれを達成できます。しかし、12¢コインを追加すると、（1×12¢+ 3×1¢）は（1×10¢+ 1×5¢）よりも多くのコインを使用するため、欲張りアルゴリズムは失敗します。

Huffman、Dijkstraなどの古典的な欲張りアルゴリズムを考えてみましょう。私の意見では、これらのアルゴリズムは縮退したケースがないため成功しています。つまり、局所的に最適なステップの組み合わせは常にグローバルな最適と等しくなります。分かりますか？

私の理解が正しければ、欲張りアルゴリズムが最適かどうかを確認するための一般的な方法はありますか？

サイトの他の場所で欲張りアルゴリズムの議論を見つけました。ただし、問題の詳細についてはあまり詳しく説明しません。

4

4 に答える 4

4

一般的に言えば、問題が凸であるときはいつでも、局所的に最適な解は常に全体的に最適です。これには線形計画法が含まれます。明確な目的を持った二次計画法。凸目的関数を使用した非線形計画法。（ただし、NLP問題は非凸目的関数を持つ傾向があります。）

ヒューリスティック検索では、ヒューリスティック関数に特定のプロパティがある場合、ローカルで最適な決定を行うグローバルな最適化が提供されます。詳細については、AIブックを参照してください。

しかし、一般的に、問題が凸状でない場合、局所的に最適な解の全体的な最適性を証明する方法はわかりません。

于 2011-06-29T01:13:42.983 に答える
2

貪欲なアルゴリズムがマトロイド (greedoids とも呼ばれる) の観点から最適である問題を表す定理がいくつかあります。詳細については、このウィキペディアのセクションを参照してください。

于 2011-06-29T10:11:35.920 に答える
1

欲張りアルゴリズムは、最適なソリューションを見つけることに成功することはほとんどありません。その場合、これは問題自体に大きく依存します。Ted Hoppが説明したように、凸曲線では、もちろん目的関数の最大値を見つけることを前提として、グローバル最適化を見つけることができます（逆に、最小化する場合は凹曲線も機能します）。そうでなければ、ほぼ確実に局所最適点で立ち往生するでしょう。これは、目的関数をすでに知っていることを前提としています。

私が考えることができるもう一つの要因は、近傍関数です。特定の近隣は、十分に大きい場合、グローバル最大値とローカル最大値の両方を含むため、ローカル最大値を回避できます。ただし、近隣を大きくしすぎると、検索が遅くなります。

言い換えると、欲張りアルゴリズムでグローバル最適を見つけるかどうかは問題固有ですが、ほとんどの場合、グローバル最適を見つけることはできません。

于 2011-06-29T02:38:12.260 に答える
0

アルゴリズムがグローバルなものであるという前提が失敗する証人の例を設計する必要があります。アルゴリズムと問題に従って設計してください。

あなたのコイン交換の例は有効なものではありませんでした。コインは、すべての組み合わせを可能にするように意図的に設計されていますが、混乱を招くことはありません。12cの追加は保証されておらず、追加料金がかかります。

加えて、問題はコインの変更ではなく、別の問題です（主題がコインであっても、例を好きなように変更できます）。このために、あなた自身が証人の例を挙げて、この問題の欲張りアルゴリズムが極大値でスタックすることを示しました。

于 2011-06-29T00:55:47.743 に答える