2

最短経路に関連する次の問題の解決策を探しています。

有向グラフ G = (V,E)、ソース s、ターゲット t1、t2、...、tk が与えられ、移動エッジ {i,j} のコストは cij です。s から t1, ..., tk までの最短経路を知りたいです。ただし、頂点 v i (ソースまたはターゲットではない) が使用される場合、C の追加コストが発生します。2 つのパスが同じ頂点 vi を使用する場合、コスト C は 1 回だけ支払われることに注意してください。

4

3 に答える 3

1

最短パスを探していて、c を使用すると各パスにペナルティが課される場合:

変更された加重関数を作成します。

w'(u,v) = w(u,v) + C    if v == c
w'(u,v) = w(u,v)        otherwise

ダイクストラのアルゴリズムまたはBellman Fordを実行している場合、 を使用するw'すべてのパスがc正確Cにペナルティを受けることは簡単にわかりcます。最短パスで 1 回]、もちろん、このパスで を使用しなくてもペナルティはありません。Ccc

編集： @SaeedAmiriが言及していることが正しい場合、およびペナルティを1回だけ与えたい場合[そしてt1、...、tkへのパスの合計を最小限に抑える]場合、私が正しく理解したかどうかはわかりません。次に、使用する必要があります別の解決策 - 同様のアイデアで:

次のような重み付け関数 w' を作成します。

w'(u,v) = w(u,v) + C + epsilon    if v == c
w'(u,v) = w(u,v)                  otherwise

イプシロンは w' でのみ達成できる小さなサイズであり、可能な限り小さいサイズであることが重要であることに注意してください。

  1. でグラフ上で dijkstra または BF を実行しますw。重みを次のように表します。 W1
  2. グラフで dijkstra または BF を実行しw'、重みをW2
  3. 各 ti ∈ { t1, ..., tk } の場合W1[ti] == W2[ti]- 最短パスでは必要なくc、合計結果はSUM(W1[ti])
  4. それ以外の場合 - 結果は min { SUM(W1[ti]) + C , SUM(W2[ti])` です

ステップ 4 の背後にある考え方は、次の 2 つの可能性があるということです。

  • c を使用せずに t1, ... , tk のすべてにアクセスできます。c を使用してパスを使用するよりもコストがかからないため、W2 の合計を返します。
  • または、無視する場合c- より拡張的になります - したがって、自由に使用し [そして W1 の合計を返します]、ペナルティを 1 回だけ追加します。
于 2012-04-17T07:49:09.790 に答える
0

あなたはまだ問題が何であるかを正確に教えてくれませんでしたが、セットカバーからの目的を維持する削減を認める明確な断片があります。

セットカバーの任意のインスタンスについて、ソース、各セットの頂点、および各要素の頂点を使用してグラフを設定します。端子t1、...、tkは要素頂点です。各セット頂点には、ソースとその要素に対応する頂点に対して重みがゼロのエッジがあります。このグラフでは、ソースから端末に到達するためにセットカバーを購入する必要があり、すべてのセットカバーで十分です。

インスタンスについて何か教えていただけない限り、多項式時間アルゴリズムの近似比はTheta（log n）よりも優れているわけではないので、整数計画法をお勧めします。

于 2012-04-17T13:00:06.643 に答える
0

標準の O(n^3) 動的計画法ソリューション...

http://en.wikipedia.org/wiki/Dijkstras_algorithm

...まだ動作しますが、わずかな調整のみです:

直接コストの隣接行列を計算してから、ショートカットを検討することを繰り返しますが、ショートカットアドオンのコストを計算するときは vi.

于 2012-04-17T07:21:00.027 に答える