优化问题 - 寻找最大 [英] Optimization problem - finding a maximum

问题描述

我手边有一个问题，它可以简化为这样的事情：

I have a problem at hand which can be reduced to something like this :

假设一束随机点在两维平面XY其中对于每个Y，有可能是在X和对于每个X多个点，可能会有在Y。多个点

Assume a bunch of random points in a two-dimension plane X-Y where for each Y, there could be multiple points on X and for each X, there could be multiple points on Y.

每当一个点（xi，彝族）被选择，没有其他的点与X = XI或Y =轶可选用。我们要选择的点的最大数目。

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

推荐答案

这可以简化为简单的最大流问题。如果你有一个点（xi，yi）时，在图中应该重新psented与路径从源S指向喜，由喜到义和义的最后一个节点（片）T $ P $。

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

请注意，如果我们有个（2,2）和（2,5），但仍然只有一条路径从S到X2。所有路径（边）有能力1。

Note, if we have points (2, 2) and (2, 5), there's still only one path from S to x2. All paths (edges) have capacity 1.

在此网络中的流量就是答案。

The flow in this network is the answer.

有关一般问题
http://en.wikipedia.org/wiki/Max_flow

about general problem
http://en.wikipedia.org/wiki/Max_flow

更新
我没有图形编辑器现在以可视化的问题，但你可以很容易地画出例如手。比方说，点是（3,3）（3,5）（2,5）

update
I don't have graphic editor right now to visualise problem, but you can easily draw example by hand. Let's say, points are (3, 3) (3, 5) (2, 5)

然后边（路径）将
的S - > X2，S - > X3
Y3 - > T，Y5 - > T
X3 - > Y3，X3 - > Y5，X2 - > Y5

Then edges (paths) would be
S -> x2, S -> x3
y3 -> T, y5 -> T
x3 -> y3, x3 -> y5, x2 -> y5

流量：S - > X2 - > Y5 - > T和S - > X3 - > Y3 - > T
水，从源头去下沉量为2，所以是答案。

Flow: S -> x2 -> y5 -> T and S -> x3 -> y3 -> T
The amount of 'water' going from source to sink is 2 and so is the answer.

也有一个关于最大流算法教程
HTTP：//www.top$c$cr .COM / TC模块=静态和放大器; D1 =教程和放大器; D2 = maxFlow

Also there's a tutorial about max flow algorithms
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow

这篇关于优化问题 - 寻找最大的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！