优化问题 - 寻找最大值

Question

我手头有一个问题，可以简化为以下内容：

假设在一个二维平面 X-Y 上有一堆随机点。对于每个 Y 值，可能有多个点在 X 轴上；对于每个 X 值，可能有多个点在 Y 轴上。

每当选择一个点 (Xi,Yi) 时，不能选择 X = Xi 或 Y = Yi 的任何其他点。我们必须选择最大数量的点。

- user352952

---

糟糕的问题标题。我对图形不够了解，无法生成更好的标题 - 有什么建议吗？ - jball

图形可能会让人感到困惑，因为有些图形在X-Y坐标系中，而其他图形则具有顶点和边缘，并且这两种方法都可以根据问题的看法来应用。 - JB King

Answer 1

这可以简化为最大流问题。如果有一个点（xi，yi），在图中应该用从源S到点xi的路径表示，在从xi到yi和从yi到最后一个节点（汇点）的路径中也应该如此。

请注意，如果我们有点（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

- Nikita Rybak

---

这看起来既优雅又简单。我尝试了贪心启发式算法，正如下面的回复中建议的那样，在一个样本数据集上，结果并不是最好的。非常感谢大家的回复。 - user352952

我想听听您对我解决这个问题的算法的看法。我发布了与之前不同的算法。 - eruciform

可能直接运行最大匹配算法比最大流算法更快、更简单。 - Aryabhatta

这是一个非常出色的见解。我喜欢像等价同构这样的东西。 :) - Nick Johnson

@Moron 我猜是这样，但实际上我从未看到过最大匹配和最大流算法在速度或简单性方面有太大的差异。事实上，我知道的所有最大匹配算法都有点“过于复杂”来实现。 - Nikita Rybak

@Nikita: 最大匹配除了更快之外还有另一个优点...假设我给这些点分配了权重，并且希望得到权重最大的一组。现在你可能需要最大权重匹配，而最大流可能不适用。至于“复杂性”，即使是最大流也很复杂！幸运的是，我们可能都有可用的库。 - Aryabhatta

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 个，该算法就会运行得更快；事实上，随着选择的顶点数量增加，它的运行速度会以数量级的方式提高。

- Chris B.

---

可能是这样，但我认为这并不是显而易见的。你会如何构建图形？你确定它是一个二分图吗？ - IVlad

@ivlad：我想听听你对我的新解决方案的看法。经过更深入的思考，我发现有一个更好的启发式方法。 - eruciform

同意IVlad的观点，你打算如何将这些点映射到矩阵中？ - Aryabhatta

这些点已经是一个矩阵。在每个选择的交叉点上放置0，在其余所有位置上放置1。 - Chris B.

@Chris：那么你并没有比Nikita更快地解决它...实际上，你让它变成了指数级！Nikita的解决方案运行时间为O(n^3)（可以做得更好，但只是说明一个上限），其中n是点的数量。在退化情况下，n=2。因此，你的算法实际上要糟糕得多。 - Aryabhatta

Answer 3

不同的解决方案。事实证明，存在很多对称性，答案比我最初想象的要简单得多。你所能做的最多的事情是唯一的X和唯一的Y的最小值，如果你只想要结果，那么它是O(NlogN)。

每个其他形状都等同于包含这些点的矩形，因为从矩形中心拉出多少个点都没有关系，顺序永远不会有影响（如果按照下面的方式处理）。现在从任何形状中取出一个点都会使其具有一个较少的唯一X和一个较少的唯一Y，就像一个矩形一样。

因此，最优解与连通性无关。选择位于最小维度边缘上的任何一点（即如果len(unique-Xs)>len(unique-Ys)，则选择任何具有最大或最小X的点）。它拥有多少连接并不重要，只要选择最大的维度即可，在上面创建的排序唯一列表中很容易做到这一点。如果您保持唯一的x和唯一的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：

• 拥有最少点数的“外边缘”（最外层的uniqueX或uniqueY点列表）是左边。基本上，看看x=1、x=10和y=2、y=5的点集。 x = 1的集合最小：一个点。选择x = 1的唯一点 -> （1,2）。
• 这也消除了（10,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个点意味着所有边都是外边缘。去掉一个。假设是(10,3)。
• 这也消除了(10,5)。

第三轮：

• 点：(3, 5)

反应3：

• 移除(3,5)。

- eruciform

---

你能否在一个例子上运行它，我不确定我理解了。比如这个输入：(1, 2); (3, 5); (10, 5); (10, 2); (10, 3)。 - IVlad

@eruciform：这基本上是二分图中的最大匹配问题重新表述。事实上，二分图中的最大匹配可以在O（V+E）时间内归约为此问题。我相信（不完全确定）目前已知的二分图匹配算法比O（VlogV）更差，而你似乎已经做到了...所以如果正确的话，你可能想要发表它 :-) - Aryabhatta

@moron：谢谢！这个问题确实激起了我的兴趣。我正在考虑用Python解决它，并使用该算法和暴力方法运行几千个随机点簇，以查看暴力方法是否会更好。这不是证明，但它将是有力的证据。如果我这样做了，我会在这里发布它。 - eruciform

你能澄清一下第二段中的“形状”是什么吗？谢谢！而第一段提出的贪心方法存在一个问题：尝试使用点（0，0）（0，1）（0，2）（10，10）（11，10）（12，10）。有4个唯一的X坐标，Y坐标也是如此。但答案是2。 - Nikita Rybak

@nikita：所谓“形状”，我指的是任何一组点。对于你刚才说的，我的算法会选择(12,10),(0,0)，这是正确的：2个点。第一段只是提到了“最大允许值”——答案可能会更少，但不会更多。 - eruciform

我知道这已经有些老了，但是这个答案非常优雅，快速且易于理解。与邻接矩阵相比，在最大匹配方面表现出色。这是已知算法的一部分吗？ - Pearl

Answer 4

对于每个点，确定选择该点会使多少其他点（N）被淘汰（即与其具有相同的X或Y值的点）。然后，按照被淘汰点数递增的顺序迭代非淘汰点。完成后，将删除最大数量的点。

- btreat

---

你如何确保早期淘汰少量不合格者不会导致最终选择数量略有不同？它肯定会得到一个近似值，但是你能确定它是真正的最大值而不尝试所有可能吗？ - eruciform

很正确。在这种情况下，贪婪算法无法保证最优性。 - btreat

这就是为什么你必须进行完整的树搜索，但你可以修剪许多子树。 - Kennet Belenky

Answer 5

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

- Teddy

---

动态规划肯定不是可行的解决方案。 - user352952

Answer 6

XY平面是一个误导。将其表述为一组元素，每个元素都有一组互斥的元素。

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

为了稍微提高效率，可以使用Bloom过滤器来跟踪被排除的集合，但可能会错过一些解决方案。

- Kennet Belenky

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³ = 1,000
• 匈牙利算法：1000³ = 1,000,000,000
• Hopcroft-Karp算法：10 √20 ≅ 44.7

只有在选择的点占比显著较高的情况下，匈牙利算法才更好。

对于一个100×100的矩阵，选择90％的顶点：:

• 最大流量：9,000³ = 729,000,000,000
• 匈牙利算法：100³ = 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)

- Chris B.

---

我认为那不正确。我相当确定你可以在O(n^3)的时间复杂度内使用邻接矩阵实现Edmonds-Karp算法。你的测试归结为邻接表与邻接矩阵之间的区别。只是匈牙利算法绝对需要一个矩阵，但其他算法并不绝对需要邻接表（尽管我个人从未见过Hopcroft-Karp算法使用矩阵实现，但我相信它是可以的）。 - IVlad

原问题中没有矩阵，只有点。如果从输入创建一个人工大型矩阵，则其大小可能与输入的大小没有实际关系。当然，除非您仅为存在点的那些“行”和“列”创建矩阵，在这种情况下，它是一个mxn矩阵，其中m≤V，n≤V。 - ShreevatsaR