1

重み w(e) を持つ重み付き無向グラフ G(v,e) が与えられた場合、頂点の各ペア (u,v)∈G が接続され (つまり、spanning tree)、選択された重みの範囲となるエッジのセットを見つけます。エッジが最小です (または、最小重みと最大重みの差が最小です)。

重みに関してエッジをソートし、ソートされた配列内の連続するエッジ (g[index = current_left],g[index+1 = current_right]) 間の重みの差が最小の 2 つのエッジを選択する貪欲なアプローチを試みました。 (current_left,current_left- j) または (current_right,current_right+ j)の間の最小差に応じて左または右に移動し、j未訪問の頂点が少なくとも 1 つあるエッジが見つかるまでインクリメントされます。

例えば：

ここに画像の説明を入力

ここで取得できる最小範囲は、重みが {2,3,5} のエッジを選択することであり、範囲は 3 です。

提案されたアルゴリズムが失敗するテスト ケースを指摘し、そのようなスパニング ツリーを見つけるためのアルゴリズムを提案してください。

編集：

予想される時間の計算量は O(|E|log|E|) で、|E| は はエッジの数です。

4

2 に答える 2

2

あなたはでそれを行うことができるはずですO(E * (cost of MST computation)):

T = no tree
for all edge weights w_fix sorted in ascending order:
    for all edges e:
        if w(e) >= w_fix:
            set w'(e) = w(e) - w_fix
        else:
            set w'(e) = infinity
    find MST T' according to w'
    if T == no tree or max edge weight(T) > max edge weight(T'):
        set T := T'
print T

考えられるのは、一部のエッジの重みは、最適なスパニング ツリー内のエッジの中で最小のエッジの重みでなければならないということです。したがって、エッジの最小重みを修正し、それより重いエッジのみを含む MST を見つけます。すべての MST は最小のボトルネック スパニング ツリーでもあるため、これは機能します。

これは、対数二乗係数まで最適な改善です。基本的な考え方は変わりません。

sort edge array E[] by increasing weights

low := high := 0
opt_low := opt_high := 0
opt := infinity
connected := false

while (high < E.length - 1) or (connected):

    if not connected:
        high = high + 1
    else:
        low = low + 1

    update(connected)

    if connected:
        if E[high].weight - E[low].weight < opt:
            opt = E[high].weight - E[low].weight
            opt_low = low
            opt_high = high

print(opt, opt_low, opt_high)

アイデアは、端にスライディング ウィンドウを保持し、接続を使用してウィンドウを維持することです。接続情報を維持するには、特別なデータ構造を使用します。エッジの削除と追加の両方の接続情報を維持するための多対数時間コストを考慮したものは数多くあります。これらのデータ構造に関する情報は、これらの MIT 6.851 レクチャー ノート に記載されています。

于 2015-11-09T12:22:30.863 に答える