13

我们有 N 对。每对包含两个数字。我们必须找到最大数 K，这样如果我们从给定的 N 对中取出 J (1<=J<=K) 对的任意组合，那么在所有选定的 J 对中我们至少有 J 个不同的数。我们可以有不止一对相同的。

例如，考虑对 (1,2) (1,2) (1,2) (7,8) (9,10) 对于这种情况 K = 2，因为对于 K > 2，如果我们选择三对(1,2)，我们只有两个不同的数字，即 1 和 2。

从一个开始检查每个可能的组合将花费大量时间。什么是解决问题的有效算法？

4

4 回答 4

0

似乎与 MinCut/MaxFlow 有关。这是一个尝试将其减少到 MinCut/MaxFlow：

- Produce one vertex for each number
- Produce one vertex for each pair
- Produce an edge from number i to a pair if the number is present in the pair, weight 1
- Produce a source node and connect it to all numbers, weight 1 for each connection
- Produce a sink node and connect it to all numbers, weight 1 for each connection

在此运行 MaxFlow 应该给你 number K，因为任何三对的集合，总共只包含两个数字，将被来自数字的传出边上的约束“阻塞”。

我不确定这是否是最快的解决方案。我想，那里的某个地方可能还隐藏着一个拟阵。在这种情况下，有一种贪婪的方法。但是我找不到您正在构建的集合的拟阵属性的证据。

于 2012-05-10T14:04:21.323 回答
0

我在这方面取得了一些进展，但还不是一个有效的解决方案。然而，它可能会指明方向。

制作一个点成对的图形，如果它们共享一个数字，则连接任意一对点。那么对于任何子图，其中的数字的数量是顶点的数量减去边的数量。因此，您的问题与定位边数多于顶点数的最小子图（如果有）相同。

具有相同数量的边和顶点的最小子图是一个循环。因此，我们正在寻找的图要么是共享一个或多个顶点的 2 个循环，要么是通过路径连接的 2 个循环。没有其他可能的最小类型。

您可以使用广度优先搜索相当容易地定位和枚举循环。可能有很多，但这是可行的。有了它，您可以查找这些子类型的子图。（枚举最小循环，寻找共享点或连接的对。）但这不能保证是多项式的。我怀疑这将是平均而言相当不错的情况，但最坏的情况是非常糟糕的。但是，这可能比您现在正在做的更有效。

我一直认为某种广度优先搜索可以在多项式时间内找到这些，但我一直无法确切地知道如何做到这一点。

于 2012-05-10T16:44:19.870 回答
0

创建一个图，每个数字有一个顶点，每对有一个边。

如果这个图是一个链或树，我们有“数字”的数量，等于“对”的数量加一，在从这个图中删除任意数量的边之后，我们得到的顶点永远不会少于边。

现在向这个链/树添加一个循环。顶点和边的数量相等。从该图中删除任意数量的边之后，我们再一次得到的顶点永远不会少于边。

现在添加任意数量的断开连接的组件，每个组件不应包含超过一个循环。再一次，在删除任意数量的边之后，我们得到的顶点永远不会少于边。

现在为任何断开的组件添加第二个循环。移除所有其他组件后。最后我们有比顶点更多的边（比数字更多的对）。

所有这些都得出这样的结论，即 K+1 恰好是最小可能子图中的边数，由两个循环组成，可能还有一条连接这些循环的链。

算法：

对于每个连接的组件，使用 Floyd-Warshall 算法找到通过每个节点的最短循环。

然后对于每个不重叠的循环对（在单个组件中），使用 Dijkstra 算法，从一个循环中至少有 3 条边的任何节点开始，找到到另一个循环的最短路径；并计算两个循环的长度之和和一条最短路径，将它们连接起来。对于每对重叠的循环，只需计算它们的边数。

现在找到所有这些子图的最小长度。并减去 1。

如果图中至少有一个双循环分量，则上述算法计算 K。如果没有这样的组件，K = N。

于 2012-05-10T18:24:51.480 回答
0

这相当于在图中找到和最小循环的和弦。一个非常幼稚的算法是：

检查删除一条边是否会导致包含对应于该边的顶点的循环。如果是，则记下最小循环的长度。

于 2012-05-10T21:12:46.760 回答