这是什么样的算法（稳定的婚姻变异）？

Question

我有一组对象（1到500之间）。每个对象都与来自同一组的某些（零个或多个）其他对象兼容。

任何人都可以给我一些关于如何确定最佳方式来创建对彼此兼容的对象的最佳方式，以便该对象中的大部分都配对？

Answer 1

您正在寻找一般图表中的最大匹配。与您熟悉的稳定婚姻问题相反，在最大匹配问题中，输入图不一定是二分法。没有稳定性的概念（因为顶点不排列它们的兼容选项），并且你正在寻找的是图的边的子集，使得没有两个边共享公共顶点（a.k.a.，匹配）。您正在尝试构建包含最大可能边数的匹配。

幸运的是，发现在一般的图的最大匹配的问题可以使用Edmond's matching algorithm多项式时间（也称为因为它是如何收缩花（奇数周期）插入单个顶点的开花算法）来解决。 Edmond匹配算法的时间复杂度为O（E•V^2）。虽然效率不高，但我相信这对于您正在处理的相对较小的图表来说已经足够好了。您甚至不必从头开始实施它，因为您可以使用开放源代码Java implementation of Edmond's algorithm。但是，如果您对现有技术感兴趣，则可以使用以O（E•sqrt（V））运行的问题所知的most efficient algorithm。

如果输入的顶点兼容性不是二元的（也就是说，每个顶点都有一个排名，用于指定其邻居之间的首选项），则可以将相应的权重添加到边缘以适应首选项配置文件并使用variation of Edmond's algorithm for weighted graphs。