動的プログラミングは、ほぼ定義上、暗黙的な DAG で最短/最長のパスを見つけることです。すべての DP アルゴリズムはこれを行うだけです。
ホログラフィック アルゴリズムは、暗黙的な平面グラフの完全な一致をカウントするものとして大まかに説明できます。
だから、私の質問は、かなりのスピードアップを達成するために暗黙的なグラフでよく知られているアルゴリズムを使用するアルゴリズムの他のファミリーはありますか?
2 に答える
3
貪欲なアルゴリズムが常に最適解を与える最適化問題は、マトロイド構造を持っています。マトロイドは集合システムであるため、グラフ (サブセット (エッジと呼ばれる) がすべて正確に 2 つの要素を持つ集合システム) よりも一般的ですが、それでも興味があるかもしれません。
ホログラフィック アルゴリズムは非常に興味深いようで、これまで聞いたことがありませんでした。ぜひ見てみましょう。
于 2010-04-22T03:18:00.517 に答える
3
頭に浮かぶ別のアイデアは、多面体最適化です。基本的に、線形計画法は、線形不等式と連続変数を含む最適化問題を解決する効率的な方法ですが、変数を整数に制限すると、一般に NP 困難な最適化問題が発生します。非常に多様な問題が整数計画問題として表現できるため、これは残念なことです。
通常のアプローチは、可能性のあるすべてのソリューションを徹底的に列挙し、最善のソリューションを選択することでした。おそらくブランチとバインドを使用して、最適化できない検索空間の部分を削除します。それがうまく機能する場合もありますが、新しい多面体アプローチの方が劇的に優れていることがよくあります。
私が最もよく理解している方法は、切断面法です。この方法では、問題の線形緩和が解決されます (シンプレックス アルゴリズムなどを使用)。解がたまたま整数である場合、問題の整数制限に対する答えも得られます。そうでない場合は、見つかった非整数解を整数解の実行可能領域から分離する平面が求められます。次に、この平面が制約として問題に追加され、線形計画法を使用して新しい問題が再び解決されます。これは、積分解が生成されるまで続きます。
明らかに、そのような平面が存在する必要があります。さらに、それらを見つけるための汎用アルゴリズムが存在します (ただし、そのパフォーマンスは通常非常に弱いものです)。研究者は、特定の問題タイプについて、この「分離問題」を解決するためのより優れたアルゴリズムを見つけることに多くの時間を費やしてきました。最も有名な例は巡回セールスマン問題で、計算上実行可能な問題のサイズの増加は驚異的です。
切断面アプローチは、考慮中の拘束の数を同時に制限することにより、より優れたパフォーマンスを達成します。別のアプローチは列生成で、同時に最適化される変数の数が制限されます。
これが暗黙のグラフアルゴリズムの基準に本当に合っているかどうかはわかりませんが、確かに魅力的で非自明なアプローチだと思います!
于 2010-04-22T08:07:18.273 に答える