4

私はこのようなものに減らすことができる手元に問題があります:

2 次元平面 XY に多数のランダムな点があり、Y ごとに X に複数の点があり、X ごとに Y に複数の点があるとします。

点 (Xi,Yi) が選択されるときはいつでも、X = Xi または Y = Yi を持つ他の点を選択することはできません。ポイントの最大数を選択する必要があります。

4

7 に答える 7

11

これは、単純な最大流量問題に還元できます。ポイント (xi, yi) がある場合、グラフでは、ソース S からポイント xi、xi から yi、yi から最後のノード (シンク) T へのパスで表す必要があります。

ポイント (2, 2) と (2, 5) がある場合、S から x2 へのパスは 1 つしかないことに注意してください。すべてのパス (エッジ) の容量は 1 です。

このネットワークの流れが答えです。

一般的な問題について
http://en.wikipedia.org/wiki/Max_flow

更新
問題を視覚化するためのグラフィックエディターは現在ありませんが、手で簡単に例を描くことができます。ポイントは (3, 3) (3, 5) (2, 5) としましょう

その場合、エッジ (パス) は
S -> x2、S -> x3
y3 -> T、y5 -> T
x3 -> y3、x3 -> y5、x2 -> y5 になります。

フロー: S -> x2 -> y5 -> T および S -> x3 -> y3 -> T
ソースからシンクへの「水」の量は 2 であり、答えも 2 です。

また、最大フロー アルゴリズムに関するチュートリアルもあります
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow

于 2010-07-21T18:58:41.277 に答える
3

これはハンガリーのアルゴリズムだけではありませんか?

マークされた頂点を 0、マークされていない頂点を 1 とするn×n行列を作成します。アルゴリズムは、行と列ごとに 1 つずつ、合計を最小化するn個の頂点を選択します。0 に等しいすべての選択された頂点を数えるだけで、答えが得られます。

from munkres import Munkres

matrix = [[0, 0, 1],
          [0, 1, 1],
          [1, 0, 0]]

m = Munkres()
total = 0
for row, column in m.compute(matrix):
    if matrix[row][column] == 0:
        print '(%i, %i)' % (row, column)
        total += 1

print 'Total: %i' % total

これは、O(n 3 ) 時間で実行されます。ここで、nは行列の行数です。最大流解は O(V 3 ) で実行されます。ここで、Vは頂点の数です。選択された交点がn 個より多い限り、これはより高速に実行されます。実際、選択された頂点の数が増えるにつれて、桁違いに速く実行されます。

于 2010-07-21T18:48:19.903 に答える
2

別の解決策。多くの対称性があることが判明し、答えは当初考えていたよりもずっと単純です。できることの最大数は、一意の X と一意の Y の最小値であり、結果だけが必要な場合は O(NlogN) です。

他のすべての形状は、ポイントを含む四角形と同等です。四角形の中心からいくつのポイントを引き出すかは問題ではないため、順序は重要ではありません (以下のように処理された場合)。長方形のように、点を抜き取った形状は、X と Y がそれぞれ 1 つずつ異なります。

したがって、最適解は接続性とは何の関係もありません。最小次元の端にある任意の点を選択します(つまり、len(unique-Xs)>len(unique-Ys) の場合、最大または最小 X を持つ任意の点を選択します)。それがいくつの接続を持っているかは関係ありません。どのディメンションが最大であるかだけで、上で作成された並べ替えられた一意のリストを見ながら簡単に実行できます。リストのその要素内のすべての一意のノードを削除するときに一意の x および一意の y カウンターを保持し、それらをデクリメントすると、各削除は O(1) になり、長さの再計算は O(1) になります。したがって、これを N 回繰り返すと、最悪の場合 O(N) になり、最終的な複雑さは O(NlogN) になります (並べ替えのみによる)。

次の理由により、最短エッジに沿って任意の点を選択できます。

  • その端に1つしかない場合は、今それを選択するか、他の何かがそれを排除します
  • その端に複数いる場合は、誰が気にしても、ピックでそれらすべてを排除します

基本的に、各ポイントで「max(uniqX,uniqY)」を最大化しています。

更新: IVladが特殊なケースをキャッチしました:

次元が等しい場合は、ポイントが最も少ないエッジを取得します。それらが等しくない場合でも、削除する一意のスタックの一番上または一番下のポイントを取得します。

適例：

ターン 1:

  • ポイント:(1, 2); (3, 5); (10, 5); (10, 2); (10, 3)
  • 3 つの固有の X があります。1, 3, 10
  • 3 つの一意の Y があります。2, 3, 5
  • 「バウンディングボックス」は(1,5),(10,5),(10,2),(1,2)

反応 1:

  • 最小のポイントを持つ「外側のエッジ」(ポイントの最も外側の uniqueX または uniqueY リスト) が左です。基本的に、x=1,x=10 と y=2,y=5 の点の集合を見てください。x=1 の集合は最小で、1 点です。x=1 -> の唯一の点をピックし(1,2)ます。
  • それも排除し(10,2)ます。

ターン 2:

  • ポイント:(3, 5); (10, 5); (10, 3)
  • 2 つの固有の X があります。3, 10
  • 2 つの一意の Y があります。3, 5
  • 「バウンディングボックス」は(3,5),(10,5),(10,3),(3,3)

反応 2:

  • 最小の境界ボックスの「端」は、下または左のいずれかです。些細なケースに到達しました - 4 ポイントは、すべてのエッジが外側のエッジであることを意味します。1つ削除します。と言う(10,3)。
  • それも排除し(10,5)ます。

ターン 3:

  • ポイント:(3, 5)

反応 3:

  • 削除し(3,5)ます。
于 2010-07-21T20:31:33.860 に答える
0

これは、動的計画法で解決できる問題のように見えます。最長の一般的な部分文字列、またはナップサック問題のアルゴリズムを調べます。

于 2010-07-21T19:00:11.147 に答える
0

各ポイントについて、そのポイントの選択によって失格となる他のポイントの数 (N) を特定します (つまり、同じ X または Y 値を持つポイント)。次に、N 個の不適格なポイントの数が増える順に、不適格でないポイントを繰り返し処理します。終了すると、ポイントの最大数が削除されます。

于 2010-07-21T18:53:09.063 に答える
0

XY 平面は厄介者です。それぞれが相互に排他的な要素のセットを持つ一連の要素として表現します。

その後、アルゴリズムは深さ優先検索になります。各レベルで、候補ノードごとに、除外された要素のセット、つまり現在除外されている要素と候補ノードによって除外されている要素の結合を計算します。除外される要素が少ないものから多いものの順に候補ノードを試してください。これまでの最良のソリューション (除外されたノードが最も少ない) を追跡します。現在の最良のものよりも悪いサブツリーを剪定します。

見逃される可能性のあるソリューションを犠牲にして、わずかな改善として、除外されたセットを追跡するためにブルーム フィルターを使用できます。

于 2010-07-21T19:06:46.377 に答える
-1

IVladからの推奨に基づいて、ホップクロフト-カープアルゴリズムを調べました。この問題については、最大フローアルゴリズムとハンガリーアルゴリズムの両方よりも一般的に優れており、多くの場合大幅に優れています。いくつかの比較：

一般的に：

  • 最大フロー：O（V 3）ここで、Vは頂点の数です。
  • ハンガリー語：O（n 3）ここで、nは行列の行数です
  • Hopcroft-Karp：O（V√2V）ここで、Vは頂点の数です。

50％が選択された頂点を持つ50×50マトリックスの場合：

  • 最大フロー：1,250 3 = 1,953,125,000
  • ハンガリー語：50 3 = 125,000
  • ホップクロフト-カープ：1,250√2,500= 62,500

1000×1000の行列の場合、10個の頂点が選択されます。

  • 最大フロー：10 3 = 1,000
  • ハンガリー語：1000 3 = 1,000,000,000
  • ホップクロフト-カープ：10√20≅44.7

ハンガリーのアルゴリズムが優れているのは、選択されたポイントの割合が非常に高い場合だけです。

100×100の行列の場合、90％の頂点が選択されます。

  • 最大フロー：9,000 3 = 729,000,000,000
  • ハンガリー語：100 3 = 1,000,000
  • ホップクロフト-カープ：9,000√18,000≅1,207,476.7

最大フローアルゴリズムは決して優れていません。

実際には、これも非常に簡単です。このコードは、DavidEppsteinによる実装を使用しています。

points = {
    0 : [0, 1],
    1 : [0],
    2 : [1, 2],
}

selected = bipartiteMatch(points)[0]

for x, y in selected.iteritems():
    print '(%i, %i)' % (x, y)

print 'Total: %i' % len(selected)
于 2010-07-25T17:58:13.583 に答える