algorithm - 给定一个一对多的地图，一种算法，告诉地图的一对一“子集”是否可以覆盖所有项目

Question

我不确定要搜索的正确术语是什么（我搜索了“映射算法”和“一对一算法”），而且我想不出更简单（更规范）的公式。

我有两套，说

A B C D E

和

L M N O P

我得到一张一对多的地图，例如

A --> L, M, N, P
B --> M
C --> M, N, O
D --> N
E --> O, L

判断地图的一对一“子集”是否可以覆盖所有项目的最简单和/或最快的算法是什么？例如，上面确实存在这样一个“子集”：

A --> P
B --> M
C --> O
D --> N
E --> L

我不需要知道子集图本身，只需要知道是否存在。

“蛮力”算法是显而易见的——一个轻微的改进是深度优先，只要没有项目满足必要的映射就回溯——另一个改进可能是按照映射的升序进行，例如first B --> M，D --> N然后是 secondE --> O, L等。

但所有这些似乎都是蛮力搜索的原始变体。有更好的算法吗？我对使用线性系统解决此类问题有一个模糊的记忆，例如将地图转换为矩阵并进行某种确定答案的归约，但我必须重新学习线性代数才能解决这个问题——也许SO可以更快地帮助我。

谢谢！

score 2 · Accepted Answer

假设这 2 个集合完全不相交，您正在解决的问题可以简化为二分最大基数匹配问题。如果可以进行的最大匹配数等于第一组的基数，则存在覆盖所有项目的映射子集。

除了将 Bipartite Matching 问题转换为流问题之外，TopCoder 上的这个主题还提到了使用 Kuhn 算法解决问题的更快方法。

score 1 · Accepted Answer

您正在寻找的术语是“二分匹配”。解决这个问题的最简单方法是将其转换为流问题。制作一个来源，将其连接到您的第一组的每个元素。将第一组的每个元素连接到第二组的一个或多个元素（建立一对一映射中的那些连接）。现在将第二组中的每个元素连接到单个接收器。所有这些连接的权重都应该是 1。

您可以使用任何最大流量求解算法（有关想法，请参见http://en.wikipedia.org/wiki/Maximum_flow_problem）来检查最大流量。如果最大流量恰好等于每个集合中的元素数，那么就会存在您正在搜索的映射。

2 回答 2