algorithm - 「貪欲な」アルゴリズムを見つける方法は?

Question

「貪欲な」アルゴリズムに関するチュートリアルを読んでいますが、実際の「トップコーダー」の問題を解決するのに苦労しています。

与えられた問題が「貪欲な」アルゴリズムで解決できることがわかっている場合、解決策をコーディングするのは非常に簡単です。ただし、この問題が「貪欲」であると言われなければ、それを見つけることはできません。

「貪欲な」アルゴリズムで解決される問題の一般的な特性とパターンは何ですか? それらを既知の「貪欲な」問題 (MST など) の 1 つに減らすことはできますか?

Answer 1

正式には、もちろんマトロイド プロパティを証明する必要があります。ただし、トップコーダーに関しては、問題に貪欲にアプローチできるかどうかをすばやく調べたいと考えています。

その場合、最も重要なポイントは、最適な部分構造のプロパティです。このためには、問題が部分問題に分解できること、およびそれらの最適解が問題全体の最適解の一部であることを確認できなければなりません。

もちろん、貪欲な問題は多種多様であるため、質問に対して一般的な正解を提供することはほぼ不可能です。したがって、私の最善のアドバイスは、これらの線に沿ってどこかで考えることです。

• ある時点で、さまざまな選択肢から選択できますか?
• この選択により、個別に解決できるサブ問題が発生しますか?
• サブ問題の解決策を使用して、問題全体の解決策を導き出すことができますか?

たくさんの経験 (これも言わなければなりませんでした) と合わせて、これは貪欲な問題を素早く見つけるのに役立つはずです。もちろん、最終的に問題を貪欲に分類することもできますが、そうではありません。その場合、コードに長時間取り組む前に、それを実現することを願うだけです。

(繰り返しになりますが、参考までに、トップコーダーのコンテキストを想定しています。より現実的で実用的な結果を得るには、貪欲なアルゴリズムを選択する前に、マトロイド構造を実際に検証することを強くお勧めします。)

Answer 2

あなたの問題の一部は、「貪欲な問題」を考えることによって引き起こされている可能性があります。貪欲なアルゴリズムと、貪欲なアルゴリズムが存在する場合の問題があり、最適なソリューションにつながります。貪欲なアルゴリズムでも解決できる難しい問題は他にもありますが、結果は必ずしも最適ではありません。

たとえば、ビンパッキング問題の場合、指数アルゴリズムよりもはるかに複雑な貪欲なアルゴリズムがいくつかありますが、最適解と比較して特定のしきい値を下回る解が得られることは確実です。 .

貪欲なアルゴリズムが最適な解決策につながる問題に関してのみ、帰納的正当性の証明は完全に自然で簡単に感じると思います。あなたの貪欲なステップの一つ一つについて、これが最善の策だったことは明らかです。

通常、最適で貪欲な解を伴う問題はとにかく簡単ですが、他の問題では、複雑さの制限により、貪欲なヒューリスティックを考え出す必要があります。通常、意味のある削減は、問題が実際には少なくとも NP 困難であることを示しているため、ヒューリスティックを見つける必要があることがわかっています。これらの問題については、私は試してみるのが大好きです。アルゴリズムを実装し、ソリューションが「かなり良い」かどうかを調べてみてください (結果を比較できる遅いが正しいアルゴリズムもある場合は理想的です。そうでない場合は、手動で作成されたグラウンド トゥルースが必要になる可能性があります)。うまく機能するものがある場合にのみ、その理由を考えてみてください。境界の証明を考え出すことさえできます。機能するかもしれませんが、機能せず、改良が必要な境界ケースを見つけるかもしれません。

Answer 3

「アルゴリズムのファミリーを説明するために使用される用語。ほとんどのアルゴリズムは、いくつかの初期構成からいくつかの「良い」構成に到達しようとし、正当な動きのみを行います。多くの場合、ソリューションの「良さ」の尺度があります (1 つが見つかったと仮定します)。貪欲なアルゴリズムは、常に最善の正当な動きを実行しようとします. この基準は局所的であることに注意してください: 貪欲なアルゴリズムは「先を考える」ことはなく、平凡に見える動きを今実行することに同意し、後でより良い動きを可能にします.

たとえば、エジプト分数の貪欲なアルゴリズムは、分母が小さい表現を見つけようとします。最後の分母が小さい表現を探す代わりに、各ステップで最小の正当な分母を取ります。一般に、これにより後のステップで分母が非常に大きくなります。

貪欲なアルゴリズムの主な利点は、通常、分析が単純なことです。通常、プログラミングも非常に簡単です。残念ながら、最適ではないことがよくあります。" --- ariels (http://www.everything2.com/title/greedy+algorithm?searchy=search)