1

二部グラフで「最小」「選択」を見つけることができるアルゴリズムを探していると思います。各頂点には、それを選択するための (整数の) コストが関連付けられています。コストではなく、選択したセットの頂点の数を最小限に抑えるアルゴリズムしか見つかりません。以前は「マッチング」が必要だと思っていましたが、実際には、すべてのエッジをカバーする頂点のサブセットが必要なだけです...

貪欲な解決策はうまくいかないと思います。セットが A、B であるとします。

頂点 1、2、3 は A にあり、コストは 1 です。頂点 4 は B にあり、コストは 2 です。

解決策は、最も高価な頂点 4 を削除することです。コストに基づいて選択した貪欲な解決策は失敗します。同様に、B のコストが 10 の場合、最も接続されている頂点を貪欲に選択することはできません。

別の言い回しを考えました:「各頂点にコストが関連付けられている 2 部グラフがある場合、選択したサブセット内の少なくとも 1 つの頂点にすべてのエッジが含まれるように、最小コストの頂点のサブセットを見つけます」。

4

1 に答える 1

3

プライマルLP:

min sum_v c_v x_v
s.t.
forall e=vw. x_v + x_w >= 1
forall v. x_v >= 0

デュアル LP:

max sum_e y_e
s.t.
forall v. sum_{e=vw} y_e <= c_v
forall e. y_e >= 0

  1. エッジが無限の容量を持つ A から B への弧であり、A の頂点がソースであり、B の頂点がシンクであり、すべての頂点の容量がそのコストに等しい最小カットを見つけます。(同様に、A へのアークでスーパーソースを作成し、B からのアークでスーパーシンクを作成します。)

  2. カットの「シンク」側にある A と「ソース」側にある B を取ります。v も w もカバーに属していない場合、vw は残差になるため、すべてのエッジ vw がカバーされます。

Jenő Egerváry さんに敬意を表します。

于 2013-04-06T13:25:08.887 に答える