python - 实际调度问题的 Hopcroft Karp 算法的实现

Question

我们有一个最大的二分匹配问题，需要为 M 人分配 N 个位置，这样每个位置至少有一个人，M 人的一个子集每个人将拥有这 N 个位置中的一个，而其他人将拥有其中 2 个分配给他们的插槽。

例如：8 个插槽，6 人。其中 4 个人只需要每人覆盖 1 个插槽，但其他 2 人将每人覆盖 2 个。因此，将分配所有 8 个插槽 (4*1 + 2*2)。

输入数据将反映 M 人中的哪一个将覆盖 1 个插槽，哪些将每个覆盖 2 个插槽。

到目前为止，我们使用HopCroft Carp进行了以下实现：

from hopcroftkarp import HopcroftKarp
graph = {'john': {12, 3, 5}, 'june': {5, 10, 8}, 'joe': {5, 3}}
HopcroftKarp(graph).maximum_matching(keys_only=True)
>> {'joe': 3, 'june': 5, 'john': 12}

为了使问题进一步复杂化，每个用户都可以指定 3 个选项之一preferred：not preferred but available和conflict (not available)。

我们如何将插槽分配给人们，以便大多数人获得首选插槽，然后是“首选但不可用的插槽”，而没有人获得“不可用”？我们如何调整上述现有信息以考虑人们拥有的这 3 个选择？另外，我们如何进一步反映某些人需要分配2个插槽？

我们已经研究过类似的问题，但是它们只为人们提供 2 个选项available或not available.

标签： pythonalgorithmgraph-algorithmbipartite