基于面试官可用时段与候选人偏好生成面试时间表的算法求解

你的问题属于带资源约束的多对多稳定匹配问题，是经典稳定婚姻问题（SM）的扩展，同时结合了覆盖要求（确保候选人匹配到前三偏好面试官）和资源限制（面试官的可用时段）。以下是具体的方向和实现思路：

核心算法方向 #

1. 多对多稳定匹配（Hospital-Resident问题变体）

   • 可将每个面试官的可用时段拆分为独立的“虚拟面试官”节点（比如interviewer1的slot1拆为interviewer1_slot1），把问题转化为标准的Hospital-Resident模型：
     • 候选人的偏好列表仅保留前三排名的面试官，并替换为对应所有虚拟时段节点（保持原偏好顺序）
     • 每个虚拟面试官的配额设为1，直接用Gale-Shapley算法的多对多版本求解，确保每个候选人至少匹配到一个符合要求的虚拟节点
   • 这种方式天然满足“候选人匹配前三偏好面试官”的约束，且适配面试官的时段资源限制。

2. 加权二分图匹配（优化匹配质量）

   • 如果需要最大化整体偏好满意度（比如让候选人尽可能匹配到排名更靠前的面试官），可以用加权二分图最大匹配或最小费用最大流：
     • 构建二分图：左侧为候选人，右侧为“面试官-时段”虚拟节点
     • 边的权重根据候选人对面试官的排名设置（比如第1名权重3、第2名2、第3名1，非前三权重设为0或直接排除）
     • 通过匈牙利算法的加权版本或网络流算法求解，确保每个候选人至少匹配一条边，每个虚拟节点最多匹配一个候选人。

Python实现方案 #

1. 基于Gale-Shapley的多对多实现 #

手动实现适配场景的多对多匹配逻辑，示例如下：

def gale_shapley_multi(candidates_prefs, interviewer_slots):
    # 拆分面试官时段为虚拟节点
    virtual_interviewers = {}
    for interviewer, slots in interviewer_slots.items():
        for slot in slots:
            vid = f"{interviewer}_{slot}"
            virtual_interviewers[vid] = {"current_match": None}
    
    # 过滤候选人偏好为前三，并转换为虚拟节点列表
    cand_filtered_prefs = {}
    for cand, prefs in candidates_prefs.items():
        top3_prefs = prefs[:3]
        cand_virtual_prefs = []
        for interviewer in top3_prefs:
            if interviewer in interviewer_slots:
                cand_virtual_prefs.extend([f"{interviewer}_{s}" for s in interviewer_slots[interviewer]])
        cand_filtered_prefs[cand] = cand_virtual_prefs.copy()
    
    # 初始化匹配状态
    free_candidates = list(cand_filtered_prefs.keys())
    final_matches = {cand: [] for cand in free_candidates}
    
    while free_candidates:
        cand = free_candidates.pop(0)
        if not cand_filtered_prefs[cand]:
            continue  # 无可用偏好，按问题约束应提前避免
        target_vid = cand_filtered_prefs[cand].pop(0)
        current_match = virtual_interviewers[target_vid]["current_match"]
        
        if not current_match:
            # 虚拟节点未匹配，直接绑定
            virtual_interviewers[target_vid]["current_match"] = cand
            final_matches[cand].append(target_vid)
        else:
            # 替换当前匹配，将原候选人放回自由列表
            free_candidates.append(current_match)
            virtual_interviewers[target_vid]["current_match"] = cand
            final_matches[current_match].remove(target_vid)
            final_matches[cand].append(target_vid)
        
        # 若候选人仍无匹配，重新加入自由列表
        if not final_matches[cand]:
            free_candidates.append(cand)
    
    # 转换为易读格式
    formatted_matches = {}
    for cand, vids in final_matches.items():
        formatted_matches[cand] = []
        for vid in vids:
            interviewer, slot = vid.split("_", 1)
            formatted_matches[cand].append({"interviewer": interviewer, "slot": slot})
    return formatted_matches

2. 加权匹配（基于NetworkX的最小费用最大流） #

若需优化匹配质量，用networkx实现最小费用最大流：

import networkx as nx

def weighted_priority_matching(candidates_prefs, interviewer_slots):
    G = nx.DiGraph()
    source = "source"
    sink = "sink"
    G.add_node(source)
    G.add_node(sink)
    
    # 添加候选人节点与源的连接
    candidates = list(candidates_prefs.keys())
    for cand in candidates:
        G.add_edge(source, cand, capacity=1, cost=0)
    
    # 添加面试官-时段节点与汇的连接
    virtual_nodes = []
    for interviewer, slots in interviewer_slots.items():
        for slot in slots:
            vid = f"{interviewer}_{slot}"
            virtual_nodes.append(vid)
            G.add_edge(vid, sink, capacity=1, cost=0)
    
    # 添加候选人到虚拟节点的加权边（负费用对应最大化权重）
    for cand, prefs in candidates_prefs.items():
        top3 = prefs[:3]
        for rank, interviewer in enumerate(top3):
            if interviewer not in interviewer_slots:
                continue
            weight = 3 - rank  # 排名越靠前权重越高
            for slot in interviewer_slots[interviewer]:
                vid = f"{interviewer}_{slot}"
                G.add_edge(cand, vid, capacity=1, cost=-weight)
    
    # 计算最小费用最大流
    _, flow_dict = nx.network_simplex(G, demand={source: -len(candidates), sink: len(candidates)})
    
    # 转换结果格式
    formatted_matches = {cand: [] for cand in candidates}
    for cand, edges in flow_dict.items():
        if cand == source:
            continue
        for vid, flow in edges.items():
            if flow > 0:
                interviewer, slot = vid.split("_", 1)
                formatted_matches[cand].append({"interviewer": interviewer, "slot": slot})
    return formatted_matches

关键注意事项 #

• 若面试官也存在对候选人的偏好，需调整为双向偏好的稳定匹配逻辑，确保匹配不存在“互相偏好超过当前匹配”的不稳定对
• 提前校验候选人前三偏好的面试官是否有可用时段，避免出现无法匹配的极端情况

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