据我了解，只要图表完整，SMP 总会有一个稳定的解决方案。换句话说，每个男性都可以娶每个女性，反之亦然。
但是，如果这不成立呢？可以说，有些男性有一份在任何情况下都不能结婚的女性名单。
这是另一个问题还是存在解决这个问题的好算法。这个问题不应该总是有我认为的解决方案，但我想得到一个尽可能好的解决方案。
问问题
157 次
1 回答
0
不知道你需要它有多高效，但我的标准匹配算法只是制作一个二分图并在其上运行最大流量。这可以在这里找到匹配项，甚至可以在某些节点是孤立的并且无法与任何人匹配的情况下工作。
现在要找到一个有效的好解决方案，您可以使用 min-cost max-flow。在构建图时，第一组是男性都连接到源，成本为 0，容量为 1。然后另一组是连接到接收器的女性，成本为 0，容量为 1。现在将每个男性/女性对与一条边连接容量为 1，成本是衡量匹配程度的某种指标（可能是它们在彼此的偏好列表中的索引之和，或者是总和的平方？）。现在，您的匹配将根据您选择的任何指标最小化。
不完全是最佳的，但可能会有一个很好的解决方案，您可以根据您的数据对其进行调整。
于 2014-06-05T02:14:14.873 回答