4

我手头有一个问题，可以简化为这样的问题：

假设在二维平面 XY 中有一堆随机点，其中对于每个 Y，X 上可能有多个点，对于每个 X，Y 上可能有多个点。

无论何时选择一个点 (Xi,Yi)，都不能选择 X = Xi OR Y = Yi 的其他点。我们必须选择最大的点数。

4

7 回答 7

11

这可以简化为简单的最大流量问题。如果你有一个点 (xi, yi)，在图中它应该用从源 S 到点 xi、从 xi 到 yi 以及从 yi 到最后一个节点 (sink) T 的路径表示。

注意，如果我们有点 (2, 2) 和 (2, 5)，那么从 S 到 x2 的路径仍然只有一条。所有路径（边）的容量为 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，答案也是如此。

还有一个关于最大流量算法的教程
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow

于 2010-07-21T18:58:41.277 回答
3

这不只是匈牙利算法吗？

创建一个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 3 ) 时间内运行，其中n是矩阵中的行数。最大流量解在 O(V 3 ) 中运行，其中V是顶点数。只要选择的交叉点多于n 个，它就运行得更快；事实上，随着所选顶点数量的增加，它的运行速度要快几个数量级。

于 2010-07-21T18:48:19.903 回答
2

不同的解决方案。事实证明有很多对称性，答案比我最初想象的要简单得多。您可以做的最大事情是唯一 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)

反应一：

  • 具有最少点的“外边缘”（最外层的 uniqueX 或 uniqueY 点列表）是左侧。基本上，查看 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
  • 有 2 个独特的 Y：3, 5
  • “边界框”是(3,5),(10,5),(10,3),(3,3)

反应二：

  • 具有最少的边界框的“边缘”是底部或左侧。我们遇到了简单的情况 - 4 分意味着所有边缘都是外边缘。消除一个。说(10,3)。
  • 那也消除了(10,5)。

第三回合：

  • 要点：(3, 5)

反应3：

  • 删除(3,5).
于 2010-07-21T20:31:33.860 回答
0

对于每个点，确定因选择该点而被取消资格的其他点的数量 (N)（即具有相同 X 或 Y 值的点）。然后，按照 N 个不合格点的数量递增的顺序对非不合格点进行迭代。完成后，您将删除最大点数。

于 2010-07-21T18:53:09.063 回答
0

这看起来像是一个可以用动态规划解决的问题。研究最长公共子串或背包问题的算法。

于 2010-07-21T19:00:11.147 回答
0

XY 平面是一条红鲱鱼。将其表述为一组元素，每个元素都有一组互斥的元素。

然后该算法变为深度优先搜索。在每个级别，对于每个候选节点，计算排除元素的集合，当前排除元素与候选节点排除的元素的并集。按排除元素最少到最多的顺序尝试候选节点。跟踪迄今为止的最佳解决方案（排除的节点最少）。修剪任何比当前最好的子树更差的子树。

作为以可能错过解决方案为代价的轻微改进，您可以使用布隆过滤器来跟踪排除集。

于 2010-07-21T19:06:46.377 回答
-1

根据IVlad的推荐，我研究了Hopcroft–Karp 算法。对于这个问题，它通常比最大流量算法和匈牙利算法都要好，通常是显着的。一些比较：

一般来说：

  • 最大流量：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
  • Hopcroft-Karp：9,000 √18,000 ≅ 1,207,476.7

最大流量算法永远不会更好。

在实践中，这也很简单。此代码使用David Eppstein的实现：

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 回答