基于Hopcroft-Karp算法的带偏好多槽位人员排班匹配适配问询

我来给你梳理下这个带优先级和多分配需求的二分匹配问题怎么解决——咱们可以把问题拆解成「优先满足偏好槽位」+「处理剩余可接受槽位」两个阶段，同时通过虚拟节点把需要2个槽位的人员转化为标准的1对1匹配场景，完美适配Hopcroft-Karp算法。下面是具体的思路和代码实现：

要适配现有的Hopcroft-Karp实现，我们需要把原问题转化为标准二分图匹配问题：

• 对需要分配2个槽位的人员，拆成两个虚拟个体（比如alice_1和alice_2），让每个虚拟个体只需要匹配1个槽位，把多分配需求转化为1对1匹配。
• 把槽位按优先级分层：先最大化偏好槽位的匹配，再处理剩余的可接受槽位（包括未被占用的偏好槽位），冲突槽位直接排除在所有匹配图外。

1. 预处理：拆分多分配人员 #

先遍历所有人员，将需要2个槽位的个体拆分为两个虚拟节点，保留他们的偏好/可接受槽位信息：

def preprocess_people(people_info):
    processed = {}
    for person, data in people_info.items():
        slots_needed = data['slots_needed']
        preferred = data['preferred']
        available = data['available']
        
        if slots_needed == 1:
            processed[person] = {
                'preferred': preferred.copy(),
                'available': available.copy()
            }
        elif slots_needed == 2:
            # 拆成两个虚拟节点，继承原人员的槽位选项
            processed[f"{person}_1"] = {
                'preferred': preferred.copy(),
                'available': available.copy()
            }
            processed[f"{person}_2"] = {
                'preferred': preferred.copy(),
                'available': available.copy()
            }
    return processed

2. 第一阶段：最大化偏好槽位匹配 #

构建仅包含偏好槽位的二分图，用Hopcroft-Karp算法做最大匹配，优先满足人员的偏好需求：

from hopcroftkarp import HopcroftKarp

def build_preference_graph(processed_people):
    graph = {}
    for person, data in processed_people.items():
        if data['preferred']:
            graph[person] = data['preferred']
    return graph

# 示例输入
people_info = {
    'john': {'slots_needed':1, 'preferred':{12,3}, 'available':{5}, 'conflict':{7}},
    'june': {'slots_needed':2, 'preferred':{5,10}, 'available':{8}, 'conflict':{12}},
    'joe': {'slots_needed':1, 'preferred':{3}, 'available':{5}, 'conflict':{10}}
}

processed = preprocess_people(people_info)
preference_graph = build_preference_graph(processed)
preference_matching = HopcroftKarp(preference_graph).maximum_matching(keys_only=True)

3. 第二阶段：处理剩余可接受槽位匹配 #

整理第一阶段后剩余的人员和槽位，构建包含可接受槽位（+未被占用的偏好槽位）的二分图，再次执行匹配：

def get_remaining_resources(processed_people, preference_matching, people_info):
    # 提取第一阶段已匹配的人员和槽位
    matched_people = set(preference_matching.keys())
    matched_slots = set(preference_matching.values())
    
    # 收集所有冲突槽位，后续排除
    all_conflict_slots = set().union(*[p['conflict'] for p in people_info.values()])
    
    # 整理剩余可参与匹配的人员（未匹配的虚拟/原人员）
    remaining_people = {}
    for person, data in processed_people.items():
        if person not in matched_people:
            # 可选择的槽位：可接受槽位 + 未被匹配的偏好槽位（排除冲突）
            available_slots = data['available'].union(data['preferred'] - matched_slots) - all_conflict_slots
            if available_slots:
                remaining_people[person] = available_slots
    
    return remaining_people

# 获取剩余人员，构建第二阶段匹配图
remaining_people = get_remaining_resources(processed, preference_matching, people_info)
remaining_graph = {p: slots for p, slots in remaining_people.items()}
remaining_matching = HopcroftKarp(remaining_graph).maximum_matching(keys_only=True)

4. 结果合并与还原 #

把两个阶段的匹配结果合并，将虚拟节点还原为原人员，得到最终分配方案：

def merge_and_restore(preference_matching, remaining_matching):
    final_assignment = {}
    # 合并两阶段匹配结果
    all_matches = {**preference_matching, **remaining_matching}
    
    for virtual_person, slot in all_matches.items():
        if '_1' in virtual_person or '_2' in virtual_person:
            # 还原虚拟节点为原人员
            real_person = virtual_person.rsplit('_', 1)[0]
            if real_person not in final_assignment:
                final_assignment[real_person] = []
            final_assignment[real_person].append(slot)
        else:
            final_assignment[virtual_person] = [slot]
    
    return final_assignment

# 生成最终结果
final_result = merge_and_restore(preference_matching, remaining_matching)
print(final_result)

示例输入的输出可能为：

{'john': [12], 'june': [5, 10], 'joe': [3]}

如果偏好槽位不足，june的第二个槽位会自动从可接受的8中选取。

• 槽位唯一性：Hopcroft-Karp算法本身保证了1对1匹配，所以每个槽位只会被分配一次。
• 优先级保障：先做偏好槽位的最大匹配，再处理可接受槽位，完全符合「尽可能多的人员获得偏好槽位」的要求。
• 冲突规避：所有阶段都直接排除冲突槽位，确保不会出现无效分配。

内容的提问来源于stack exchange，提问作者learnerX