c - 如何匹配查找对象类型 A 和对象 B 之间的最大对数？

Question

我有一个对象类型 A 的列表和另一个对象类型 B 的列表。每个 A 类型的对象都有一个 B 对象类型的列表，它可以与之匹配或兼容。 (例如，对象 A3 可以与对象 B1、B5、B7 任意配对)。每个对象 A 可以有一个不同的对象 B 列表，它可以与之兼容(某些对象 A 可以与 B 中的同一对象兼容)。但是每个对象 A 只能与 B 中的一个对象配对。一个对象B只能与一个对象A。

哪种算法有助于找到最大可能的对数？

Answer 1

在不知道问题名称的情况下很难知道如何最好地提出或搜索该问题的答案，但我相信这是二分图最大匹配的一个示例。您可以在维基百科和 Google 上找到示例，例如:

• http://en.wikipedia.org/wiki/Matching_(graph_theory)
• http://www.geeksforgeeks.org/maximum-bipartite-matching/
• http://www.wikihow.com/Use-a-Bipartite-Graph-to-Find-the-Maximal-Matching

我对建议的解决方案的理解如下:

1. 对于每个 A，将其链接到第一个有效的 B。
2. 如果 B 已经链接到另一个 A，则递归检查另一个 A 是否可以链接到另一个 B，排除它通过其余递归搜索链接到的 B。
3. 如果可以，则将其他 A 重新分配给其他 B，否则为该 A 选择下一个 B，并从步骤 2 开始重复(递归)。

在不知道这个解决方案的情况下，我在一两年前实现了自己可能不完美的解决方案，如下所述:

How to prune duplicate associations to yield a unique most-complete set

我在此过程中注意到的一件事可能对您有所帮助:如果您遇到任何只能链接到另一侧的一个节点的 A 或 B，您可能希望自动选择该路径并消除节点的所有其他可能性在两端(重复直到不再被消除)。如果您知道每个节点都应该链接起来，这可能有助于优化您的搜索时间。