Optimization Problem - Maximum Search

Question

I have a problem that can be reduced to something like this:

Suppose that in the two-dimensional plane XY there is a bunch of random points, where for each Y there can be several points on X and for each X there can be several points on Y.

Whenever a point (Xi, Yi) is selected, no other point with X = Xi OR Y = Yi can be selected. We must choose the maximum number of points.

Answer 1

This can be reduced to a simple maximum flow problem. If you have a point (xi, yi), in the graph it should be represented by the path from the source S to the point xi, from xi to yi and from yi to the last node (shell) T.

Please note that if we have points (2, 2) and (2, 5), there is only one way left from S to x2. All paths (ribs) have a capacity of 1.

The flow on this network is the answer.

about the general issue
http://en.wikipedia.org/wiki/Max_flow

Update
I do not have a graphical editor right now to visualize the problem, but you can easily draw an example by hand. Let, say, points (3, 3) (3, 5) (2, 5)

Then the edges (paths) will be S → x2, S → x3
y3 → T, y5 → T
x3 → y3, x3 → y5, x2 → y5

: S → x2 → y5 → T S → x3 → y3 → T
"", , 2, .

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow

Answer 2

?

n × n- 0 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 ³) , n - . O (V ³), V - . , n , ; , .

Answer 3

. , , , . , - , X Y, O (NlogN), .

, , , , ( , ). , , X Y, .

, . , (.. len (unique-Xs) > len (unique-Ys), , X). , , , , , . unique-x unique-y , , O (1), - O (1). N O (N), - O (NlogN) (- ).

, :

• , - .
• , , .

, "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:

• " " ( X ), , . , x = 1, x = 10 y = 2, y = 5. x = 1 : . x = 1 → (1,2).
• (10,2).

2:

• : (3, 5); (10, 5); (10, 3)
• 2 X: 3, 10
• Y: 3, 5
• " " (3,5),(10,5),(10,3),(3,3)

2:

• "" , , , . - 4 , . . (10,3).
• (10,5).

3:

• : (3, 5)

3:

• (3,5).

Answer 4

(N), (.. , X Y). N . , .

Answer 5

, . .

Answer 6

XY - . , .

. , node, , , node. - . ( ). , .

Bloom .

Answer 7

IVlad, Hopcroft-Karp. , , . :

:

• . : O (V ³), V - .
• : O (n ³), n -
• Hopcroft-Karp: O (V √2V), V - .

50 × 50 50% :

• . : 1,250 ³= 1,953,125,000
• : 50 ³= 125 000
• Hopcroft-Karp: 1,250 √2,500 = 62,500

1000 × 1000 10 :

• . : 10 ³= 1000
• : 1000 ³= 1,000,000,000
• -: 10 √20 ≅ 44,7

, , .

100 × 100 90% :

• . : 9000 ³= 729 000 000 000
• : 100 ³= 1,000,000
• Hopcroft-Karp: 9 000 √18,000 ≅ 1,207,476.7

Max Flow .

, . :

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)