4

ここに物品税があります：

重み付き連結グラフGからエッジの最小重み連結サブセットTを見つける問題を考えてみましょう。Tの重みはTのすべてのエッジ重みの合計です。最小重み連結サブセットTを計算するための効率的なアルゴリズムを提供します。

これが私が持っているものです：

  1. 重みが正と負の両方で混合されていると仮定する必要があります。この物品税には、両方の種類の重量の組み合わせのみが意味をなします。

  2. 最初にエッジを並べ替えるので、負のエッジが最初に来ます。

  3. クラスカルのアルゴリズムを利用することを検討しますが、いくつかの変更を加える必要があります

  4. ネガティブエッジを歓迎するので、できるだけ多くのネガティブエッジを追加しようと思います。

  5. さらに、すべての負のエッジが接続されていない場合に備えて、いくつかの正のエッジを追加することができ、ブリッジとしていくつかの正のエッジが必要になる場合があります。

わかりました、上記は私の考えです。でも手を汚そうとすると行き詰まってしまいます。

可能な最小ウェイトセットを常に記録するにはどうすればよいですか？

例えば、

{0、1}の重みは-20です

{2、3}は重み-10です

{1、3}の重みが11の場合、もちろん{1、3}は必要ありません。

または、{1、3}の重みが9の場合、

どのようなデータ構造で、常に最小の重みとその重みの頂点を維持できますか？

この物品税が目的とするサブセットであることに注意する価値がありedgesます。

重み付き連結グラフGからエッジの最小重み連結サブセットTを見つける問題を考えてみましょう。

これは、すべての頂点を含める必要があることを意味します。

また、それはMST以上のものです。頂点に2つのエッジがある場合、1つは-1で、もう1つは-2であると考えてください。通常のMSTアルゴリズムでは、-2のエッジのみが取得されます。ただし、この物品税では、全体の重量をさらに減らすために、-1と-2の両方を使用する必要があります。

4

1 に答える 1

7

あなたのアルゴリズムはすでにほとんど正しいと思いますが、わずかな変更を加えるだけで簡単に実装できます。

まず、結果として生じる重量を最小限に抑えるために、すべての負のエッジを含める必要があります。次に、連結成分の数を計算しますc。の場合c=1、完了です。c-1それ以外の場合は、余分なポジティブエッジが必要です。

ここで、負のエッジを追加しているときに、これをクラスカルのアルゴリズムプロセスと見なします。すべての負のエッジは、クラスカルの森のいくつかの木を結合する可能性があります。ただし、その端がクラスカルのフォレスト内の同じツリーに属している場合でも、負のエッジを追加します。これは、2つの異なるツリーを結合するエッジのみを追加する通常のクラスカルのアルゴリズムとは異なります。

このフェーズの後、接続されたコンポーネントのグラフが残りcます（それらはもはやツリーではない可能性があります）。ここで、通常どおりクラスカルのアルゴリズムを続行します。ポジティブエッジで作成したユニオンの数を追跡しながら、ポジティブエッジを昇順で処理します。この数がに達するとc-1、完了です。

ちなみに、フォレストを素集合データ構造として表現すれば、クラスカルのアルゴリズムのすべてのプロセスを簡単に実装できます。書くのにほんの数行のコードが必要であり、その後、作成されたユニオンの数を追跡するのは簡単です。

いくつかの擬似コードは次のとおりです。

sort(edges);
c := n;
for edge in edges:
    if edge.weight < 0:
        if find(edge.firstEnd) != find(edge.secondEnd):
            --c;
        unite(edge.firstEnd, edge.secondEnd);
    else:
        if c == 1: break;
        if find(edge.firstEnd) != find(edge.secondEnd):
            unite(edge.firstEnd, edge.secondEnd);
            --c;

ここuniteにfind、素集合データ構造の関数があります。

于 2012-05-02T22:38:27.037 に答える