2

偶数の頂点を持つ完全な重み付きグラフで、次のプロパティを持つエッジのセットを見つけるための効率的なアルゴリズムはありますか？

  • セットには、他の可能な基準を満たしたセットの最小、最大のエッジウェイトがあります
  • すべての頂点は、セット内の1つのエッジに接続されています

すべての重みは正です

dブルートフォースよりも優れたものは考えられませんが、NP困難とは認識していません。

4

2 に答える 2

2

多項式時間でこの問題を解決する1つの方法は、次のとおりです。

  1. エッジの重みをO（E log E）時間で並べ替えます
  2. エッジごとに、〜O（E）時間で疑似重みE'= 2^{順序付けの位置}を割り当てます
  3. O（V ^ 3）時間のようなもので、疑似重み間の最小重みの完全一致を見つけます（選択したアルゴリズムに応じて、遅くなることも速くなることもあります）

これにより、完全一致に含まれる最大のエッジが最小化されます。これは、O（V ^ 3）時間のようなものでまさに探しているものです。

パート3の実行方法のソースは、以下に示されています
[1] http://www2.isye.gatech.edu/~wcook/papers/match_ijoc.pdf
[2] http://www.cs.illinois.edu/class/ sp10 / cs598csc / Lectures / Lecture11.pdf
[3] http://www.cs.ucl.ac.uk/staff/V.Kolmogorov/papers/blossom5.ps

http://ciju.wordpress.com/2008/08/10/min-cost-perfect-matching/で入手可能なサンプルC++ソースを使用

于 2010-10-31T14:51:15.460 に答える
0

これを試してみてください（私はこれを考えたので、それが最適な答えを与えるという証拠も、すべての場合に解決策を生み出すかどうかもわかりません）：

  1. 最も重い頂点を検索するV（A、B）
  2. グラフから頂点Vを削除します
  3. Aが他の単一の頂点T（A、C）にのみ接続されている場合は、Cに接続されている他のすべてのエッジを削除し、それらのエッジでも手順3を繰り返します。
  4. Bが他の単一の頂点S（B、D）にのみ接続されている場合は、Dに接続されている他のすべてのエッジを削除し、それらのエッジでも手順4を繰り返します。
  5. 手順1から繰り返します
于 2010-10-31T14:38:33.577 に答える