7

エッジの重みが正の有向非巡回グラフがあります。単一のソースと一連のターゲット (ソースから最も遠い頂点) があります。ソースから各ターゲットへの最短経路を見つけます。これらのパスの一部は重複しています。私が欲しいのは、すべてのエッジの重みの合計を最小化する最短パス ツリーです。

たとえば、2 つのターゲットを考えてみましょう。すべてのエッジの重みが等しい場合、それらの長さの大部分で 1 つの最短パスを共有する場合、2 つのほとんど重複しない最短パスよりも望ましい方法です (ツリー内のエッジが少ないほど、全体的なコストが低くなります)。

別の例: 2 つのパスは、その長さのごく一部が重複していません。重複していないパスのコストは高くなりますが、長い共有パスのコストは低くなります (結合コストが低い)。一方、2 つのパスはその長さの大部分が重複しておらず、重複していないパスのコストは低くなりますが、短い共有パスのコストは高くなります (合計コストも低くなります)。多くの組み合わせがあります。ソースからターゲットへのすべての最短経路を考慮して、全体のコストが最も低いソリューションを見つけたいと考えています。

言い換えれば、最短、最短パス ツリーが必要です。

これは誰かと何か鐘を鳴らしますか? 関連するアルゴリズムや類似のアプリケーションを教えてもらえますか?

乾杯！

4

2 に答える 2

2

この問題 ( Steiner Tree ) は NP 困難であり、最大 SNP 完全であるため、P = NP でない限り、多項式時間アルゴリズムも PTAS (任意近似近似) もありません。

MST は、グラフの特別な機能 (たとえば、グラフが平面である、または少なくとも重みが三角形の不等式に従うこと) を知らない限り、最適よりも任意に悪い重みを与えることができます。たとえば、K_1,000,000,001 があり、すべてのエッジの重みが 1 でターゲットが 1 つだけの場合、最適解の重みは 1 で、MST の重みは 1,000,000,000 です。

ターゲット間のすべてのエッジ、およびソースと各ターゲット間のすべてのエッジが存在すると仮定した場合でも、任意の係数でオーバーシュートする可能性があります。上記の例を考えてみましょう。ただし、ターゲットとソースの間のエッジの重みを 2,000,000,000,000,000,000 に変更します (最適から 10 億倍もずれています)。

もちろん、グラフをトラバースすることで、時間 O(E) ほど高いエッジの重みを「削除」するようにグラフを変換できます。これにターゲットとソースのセットの MST を加えると、近似比率は 2 になります。

より良い近似比が存在します。Robins & Zelikovsky には、最適よりも 54.94% 以上悪くならない多項式時間アルゴリズムがあります: http://www.cs.virginia.edu/~robins/papers/soda2000_camera.pdf

Chlebik と Chlebikova は、1.05% よりも近い近似は NP 困難であることを示しています: グラフのシュタイナー木問題: 非近似性の結果 (doi 10.1.1.4.1339)

グラフが平面である場合、状況は良好です。Borradaile、Kenyon-Mathieu、および Klein (Erickson、Monma、および Veinott に基づく) により、任意に近い近似を与える高速アルゴリズムがあります 。 4154)

于 2010-05-18T14:51:16.300 に答える
1

正のコストしかなく、最小化する場合は、ダイクストラのアルゴリズムを使用してください。

于 2010-05-17T18:08:38.583 に答える