56

relaxation of an edgeグラフ理論の文脈で とはどういう意味ですか? ダイクストラの単一ソース最短パスのアルゴリズムを調べているときに、これに出くわしました。

4

6 に答える 6

56

これは、緩和の概念も説明するアルゴリズムの優れた説明です。

「弛緩」の概念は、最短経路の推定値と、圧縮用に設計されていないコイル状引張りばねの長さとの類推から来ています。最初は、最短経路のコストは過大評価されており、引き伸ばされたバネに例えられます。より短いパスが見つかると、推定コストが低くなり、スプリングが緩和されます。最終的に、最短パスが存在する場合はそのパスが検出され、スプリングはその静止長まで緩和されます。

于 2012-10-08T13:23:57.903 に答える
33

ダイクストラのアルゴリズムの緩和プロセスは、頂点 v に接続されたすべての頂点のコストを更新することを指します。これらのコストが、v を介したパスを含めることによって改善される場合です。

于 2012-10-08T13:25:36.893 に答える
11

エッジの緩和 (他の最短経路アルゴリズムにも見られる概念) は、別の頂点を使用して頂点に到達するコストを下げようとしています。

Sなどの開始頂点から他のすべての頂点までの距離を計算しています。ある時点で、中間結果、つまり現在の推定値が得られます。緩和は、いくつかの頂点uおよびvについてチェックするプロセスです。

if directly_connected(v, u)
    if est(S, v) > est(S, u) + dist(u,v)
       est(S, v) = est(S, u) + dist(u, v)

ここest(S,a)で、 は距離の現在の推定値であり、dist(a,b)はグラフ内で隣接する 2 つの頂点間の距離です。

緩和プロセスで基本的にチェックしているのは、a から b への現在の推定値が、 cを通るパスを「迂回」することによって改善される可能性があることです (この「迂回」は、aからcおよびcからbへのパスの長さになります)。）。

于 2012-10-08T13:31:48.923 に答える