最大最小重みを持つパスを見つける

https://stackoverflow.com/questions/873126

22-08-2019
|

質問

有向グラフ全体のパスを見つけるアルゴリズムを考え出そうとしています。これは従来の方法ではなく、同様のことが既に行われているという情報は見つかりません。

最大最小重みを持つパスを見つけたいです。

つまり、重み 10->1->10 および 2->2->2 を持つ 2 つのパスがある場合、最小重み (2) が最初の最小重み (1) より大きいため、2 番目のパスが最初のパスよりも優れていると見なされます。）。

誰かがこれを行う方法を見つけ出すことができれば、または参考資料の方向性を私に教えてくれれば、それは非常に便利です:)

編集：：特定の頂点から別の特定の頂点に到達しようとしているということを忘れていたようです。非常に重要な点があります:/

編集2::以下の誰かが指摘したように、エッジの重みは負ではないことを強調しておきます。

解決

//en.wikipedia：

プリムののか<のhref = "HTTPのいずれかを使用します。 ORG /ウィキ/クラスカルの％の27s_algorithm」のrel = "nofollowをnoreferrer">クラスカルののアルゴリズム。彼らはあなたが尋ねる頂点が接続されていることを見つけたとき、彼らは停止するので、ちょうどそれらを変更します。

EDIT：あなたは、最大最小を求めるが、あなたが最小、最大をしたいようなあなたの例が見えます。最大最小の場合、クラスカルのアルゴリズムは動作しません。

EDIT：例は大丈夫です、私のミス。のみプリム法は、動作します。

他のヒント

コピーしていますこれ答えと、アルゴリズムの正しさの証明も追加します。

私はいくつかのバリエーションを使用しますディクストラの. 。以下の疑似コードを Wikipedia から直接取得し、5 つの小さな点だけを変更しました。

名前変更 dist に width (3行目以降)
それぞれ初期化しました width に -infinity (3行目)
ソースの幅を初期化しました infinity (8行目)
終了基準を次のように設定します -infinity (14行目)
更新関数と署名を変更(20行目+21行目)

1  function Dijkstra(Graph, source):
2      for each vertex v in Graph:                                 // Initializations
3          width[v] := -infinity  ;                                // Unknown width function from 
4                                                                  // source to v
5          previous[v] := undefined ;                              // Previous node in optimal path
6      end for                                                     // from source
7      
8      width[source] := infinity ;                                 // Width from source to source
9      Q := the set of all nodes in Graph ;                        // All nodes in the graph are
10                                                                 // unoptimized – thus are in Q
11      while Q is not empty:                                      // The main loop
12          u := vertex in Q with largest width in width[] ;       // Source node in first case
13          remove u from Q ;
14          if width[u] = -infinity:
15              break ;                                            // all remaining vertices are
16          end if                                                 // inaccessible from source
17          
18          for each neighbor v of u:                              // where v has not yet been 
19                                                                 // removed from Q.
20              alt := max(width[v], min(width[u], width_between(u, v))) ;
21              if alt > width[v]:                                 // Relax (u,v,a)
22                  width[v] := alt ;
23                  previous[v] := u ;
24                  decrease-key v in Q;                           // Reorder v in the Queue
25              end if
26          end for
27      end while
28      return width;
29  endfunction

これが機能する理由を (手振りで) 説明します。ソースから始めます。そこから、あなたはそれ自体に無限の能力を持ちます。次に、ソースの近隣すべてをチェックします。エッジがすべて同じ容量ではないと仮定します (例では、 (s, a) = 300）。そうすれば、これ以上に到達する方法はありません b その後経由 (s, b), 、これで、最適なケース容量がわかります。 b. 。すべての頂点に到達するまで、既知の頂点セットの最良近傍に進み続けます。

アルゴリズムの正しさの証明:

アルゴリズムのどの時点でも、 頂点 A と B の 2 セット. 。A の頂点は、正しい最大最小容量パスが見つかった頂点になります。そして集合 B には答えが見つかっていない頂点があります。

帰納的仮説:どのステップでも、セット A 内のすべての頂点は、それらへの最大最小容量パスの正しい値を持ちます。つまり、以前の反復はすべて正しいです。

基本ケースの正確性:集合 A が頂点 S のみを持つ場合。したがって、S の値は無限大であり、これは正しいです。

現在の反復では、次のように設定します。

val[W] = max(val[W], min(val[V], width_between(V-W)))

帰納的ステップ:W が最大の val[W] を持つ集合 B の頂点であると仮定します。そして、W がキューからデキューされ、W には応答 val[W] が設定されます。

ここで、他のすべての南西方向のパスの幅が val[W] 以下であることを示す必要があります。W に到達する他のすべての方法は集合 B 内の他の頂点 (X とします) を経由するため、これは常に true になります。

セット B 内の他のすべての頂点 X については、val[X] <= val[W]

したがって、W への他のパスは val[X] によって制約され、val[W] より大きくなることはありません。

したがって、val[W] の現在の推定値は最適であるため、アルゴリズムはすべての頂点に対して正しい値を計算します。

また、「バイナリ検索の答えの」パラダイムを使用することができます。もしwより大きい重量のエッジのみを使用して、グラフ内のパスを見つけることができるかどうかwすなわち、各重みについて試験重みでバイナリ検索を実行している。

あなたは（バイナリ検索さ）ができているため、最大wは答えを与えます。あなたが唯一のパスが存在するかどうかを確認する必要があることに注意してください、これだけO（| E |）幅優先/深さ優先探索ではなく、最短パス。だから、ダイクストラ/クラスカル/プリムのO(|E|*log(max W))に匹敵するすべてでO(|E|log |V|)、（と私はすぐに、あまりにも、それらの証拠を見ることはできません）です。

これは BFS スタイルのアルゴリズムを使用して解決できますが、次の 2 つのバリエーションが必要です。

各ノードを「訪問済み」としてマークするのではなく、そのノードに到達するまでにたどったパスに沿った最小の重みでノードをマークします。

たとえば、I と J が隣接しており、I の値が w1 で、それらの間のエッジの重みが w2 である場合、J=min(w1, w2) となります。

値 w1 でマークされたノードに到達した場合、新しい値 w2 (および w2>w1) を割り当てる場合は、そのノードをリマークして再処理する必要がある場合があります。これは、すべての最小値のうち最大値を確実に取得するために必要です。

たとえば、I と J が近傍であり、I の値は w1、J の値は w2 で、それらの間のエッジの重みが w3 である場合、min(w2, w3) > w1 の場合、J をマークしてその近傍をすべて処理する必要があります。また。

私はプリムがここに動作することを確認していません。この反例を取ります：

V = {1, 2, 3, 4}

E = {(1, 2), (2, 3), (1, 4), (4, 2)}

weight function w:
  w((1,2)) = .1, 
  w((2,3)) = .3
  w((1,4)) = .2
  w((4,2)) = .25

MAXMIN距離が4を経由するパスのために達成されている間、

あなたは1から始まり、1から3までMAXMINパスを見つけることがプリム適用する場合は、1 --> 2 --> 3パスを選択します。

[OK]を、ちょうど試してみて、私はここに投稿する前に働いた暫定的な解決策に与えたフィードバックのビットを取得するために、ここで自分の質問に答えるます：

各ノードは、「パス断片」を記憶し、これはこれまでのところ、それ自体のパス全体である。

0）を出発頂点
に現在の頂点を設定します 1）この頂点からのすべてのパスの断片を生成し、プライオリティキューに追加します
2）上から優先キュー断片を外し、そのパスの終了頂点に現在の頂点を設定
現在の頂点が目標頂点である場合3）、次にパスを返す
4）後藤1

私はこれはしかし、最適なパスを見つけると確信してないんだけど、私はステップ3で終了条件が少し野心的だと思います。このアルゴリズムは、ダイクストラのようにすべての頂点が閉じられるまであなただけ待つことができないではないに近い頂点（それが好きとして頂点として多くのパス断片で参照することができます）（のために行いますので、私は、しかし、より良い終了条件を考えることはできません例）

あなたはまだダイクストラを使用することができます！

の代わりに+を使用する、分（）演算子を使用する。
また、あなたは最大のものが上になるようにヒープ/ PRIORITY_QUEUEを向けることになるでしょう。

このような何か作業をする必要があります：（私はおそらくいくつかの実装の詳細を見逃している）

let pq = priority queue of <node, minimum edge>, sorted by min. edge descending
push (start, infinity) on queue
mark start as visited
while !queue.empty:
   current = pq.top()
   pq.pop()
   for all neighbors of current.node:
      if neighbor has not been visited
          pq.decrease_key(neighbor, min(current.weight, edge.weight))

これは、（あなたが高い順に、すべての可能性を見つけるために、あなたは、エッジを追加して、パスを改善することはできません）あなたがノードに到達するたびに、最適な経路をたどっていることが保証されます。

の時間境界は、ダイクストラのと同じである - O（動画ブログ（E））

編集：ああ待って、これはあなたが投稿何を基本的にあります。 LOLます。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow