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