algorithm - 多对一匹配算法

Question

如果这是重复的，我很抱歉。我缺乏计算机科学知识，不知道要正确搜索什么。

我需要找到一个匹配算法。我有一系列房间，以及一系列内容换房间。内容物有一个最小尺寸的房间可以容纳——所以有些人很乐意放在任何房间里，有些人只能放在一两个房间里。我还将为某些房间设置最大尺寸，但我认为这仅在我确定房间是否合适时才会生效。

假设（虽然 - 这在我的实际使用中不能保证）有一个潜在的解决方案，我如何找到最佳分配，使得每个房间只使用一次并且没有一个内容缺少房间？

Answer 1

您的问题似乎是最大二分匹配问题。您可以将您的问题视为无向图G(V,E)，其中顶点V是房间和内容，边E是房间和内容之间的可能连接：

1. 该图是二分图。如果我们将顶点分成两个集合，房间和内容，每个集合中都没有内部边。
2. 如果房间足够大以容纳内容contents(i)，则图表中存在一条边。room(j)

最大匹配产生两个集合（即房间和内容）中顶点之间的最大配对数，确保每个顶点只使用一次。如果所有顶点都匹配，则称匹配是“完美的”。有许多算法可用于此类问题，可能最快的是Hopcroft-Karp方法。

您还可以考虑进一步优化您的问题，尝试将房间中浪费的总空间最小化。在这种情况下，“权重”将根据内容区域和房间区域之间的差异与上面定义的边缘相关联。然后，您将寻求最大权重最大匹配。

Answer 2

您可以将其解决为http://en.wikipedia.org/wiki/Assignment_problem。您没有匹配数量的要匹配的东西，但您可以为先不足的一方补上东西。如果您为每个可能的匹配设置相同的组合事物的成本，则具有组合事物的解决方案的最小成本答案也将是仅产生部分匹配的没有组合事物的解决方案的最小成本答案，因为编造的东西对成本的贡献无论如何分配都是一样的。

（当然，可能有一种更快的方法来解决您的特定问题 - 例如，如果您在一侧只有一件事要匹配，只需在每个可能的位置尝试）。