0

次の問題があります。すべてのエッジ {i,j} 間のエッジ コスト cij を持つ有向グラフ G=(V,E) が与えられます。s1,...,sk などの複数のソースと、t などの 1 つのターゲットがあります。問題は、s1,...sk から t までの最小の合計コストを見つけることです。ここで、すべての異なるパスによって訪問された頂点の合計量は M です (ソースとターゲットは訪問された頂点としてカウントされず、0 <= M <= |V|-k+1 であるため、M = 0 の場合、すべてのパスはソースからターゲットに直接行きます。)

私は次のことを思いつきましたが、まだ解決策を見つけていません。

  1. この問題は、複数のターゲット (t1、...、tk) と 1 つのソースに似ています。すべてのエッジを逆にして、ソースをターゲットにし、ターゲット ソースを作成するだけです。たとえば、Dijkstra はグラフ内の 1 つのソースから他のすべての頂点への最短パスを計算するので、これは便利だと思いました。

  2. 1 つのターゲットと 1 つのソースだけで、最大で最短パスを見つけることができます。Bellman Ford アルゴリズムで訪問した頂点 M の量。これは、訪問した頂点の数を繰り返し増やすことによって行われます。

  3. 頂点 v1,...,vk を訪問する必要があるときに、1 つのソースから 1 つのターゲットへの最短パスを見つける問題は、k が小さい場合、次のように解決できます。i) すべての頂点間の最短パスを計算します。ii) k のどれをチェックしてください! 順列は最短です。これは、1) で調整した問題を、あるソースから 1 つの「スーパーターゲット」に移動し、「古い」ターゲット t1=v1,...,tk=vk を強制的に訪問するという問題に変換する場合に役立つと考えました。

残念ながら、1、2、3 を組み合わせても解決にはなりませんが、役立つ場合があります。誰かが解決策を知っていますか？これは効率的に解決できますか？

4

1 に答える 1

1

s ごとに個別の Dijkstra を実行し、後でコストを合計してみませんか?

何かのようなもの：

float totalCost;
for (int i=0; i<k; i++)
  totalCost += Dijkstra(myGraph,s[i],t);

質問を正しく理解できたと思います。

于 2011-12-05T06:39:18.473 に答える