1

V の頂点と E のエッジを持つ有向加重グラフ G があります。グラフに 2 つのノード (A と B としましょう) があり、w(A, B) として示されるエッジ AB の重みが与えられると、ノード C を見つけて max(w(A, C), w (B, C)) はすべての可能性の中で最小です。可能性とは、C が取り得るすべての値を意味します。完全に明確かどうかはわかりません。そうでない場合は、より正確にしようと思います。

4

2 に答える 2

2

w(A, C) が本当にエッジの重みだけを意味している場合は、A に直接接続されているすべてのノードを順番にチェックしてください。最悪の場合、グラフのサイズの総コストは、期待できるほど良好です。 、常にグラフを読み取る必要があると仮定します。

w(A, C) で A から C への最小コスト パスのコストを意味する場合、http://en.wikipedia.org/wiki/Dijkstra%27s_algorithmのようなほとんどのパス検索アルゴリズムは、実際にはA から他のすべてのノードへの最小コスト パスのコスト。A から各ノードに到達するコストと、各ノードから B に到達するコストの両方がある場合、各ノードを順番に調べることで問題を解決できます。

したがって、1 回実行して A から他のすべてのノードへのコストを計算し、次にノードのエッジを逆にして、別の実行を実行して、逆グラフの B から他のすべてのノードへの最小コスト パスを計算します。次に、各ノードについて、最小コスト w(A, C) と最小コスト w(C, B) のコストがあるので、各ノードを順番にチェックして、どれが最適かを確認できます。

グラフにサイクルが含まれている場合は、http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithmのようなものが必要です。負のサイクルがある場合、問題が発生します。

于 2012-11-13T04:56:45.397 に答える
0

あなたが求めていることはあまり明確ではありませんが、重み付けされた距離の1つの方法は次のとおりです.R ^ nの距離問題のように扱います。ここで、任意の次元のCからの実際の直線距離に、パスのその次元の重みを掛けて取得します加重距離。式全体を加重距離の合計にし、この式の最大化に 2 次導関数検定を使用します。

乾杯、アンドリュー

于 2012-11-13T04:52:32.210 に答える