人员与可用预约最优匹配算法实现方案咨询

问题建模 #

你的需求可以直接抽象为带权二分图最小权完美匹配问题：

• 二分图左侧顶点集为所有预约人员，共N个（示例中N=6）
• 二分图右侧顶点集为所有可用预约时段，共M个（示例中M=7）
• 边权重规则：
  • 人员i对时段j的偏好为0：边权重设为0（优先匹配，代价最低）
  • 人员i对时段j的偏好为1：边权重设为1（次优先匹配，代价次之）
  • 人员i对时段j的偏好为2：不连边，或权重设为极大值（例如10000，代表不可匹配）
• 最终目标：找到匹配方案，满足每个人员匹配唯一的时段、每个时段最多分配给1人，且所有边的权重总和最小，即为全局最优的匹配结果。

算法选择 #

你提到的数十量级的人员和时段规模，直接使用**匈牙利算法（Kuhn-Munkres算法）**即可，该算法在N<100的场景下计算速度极快，完全满足性能要求。
如果时段数M大于人员数N，只需要在左侧补充(M-N)个虚拟人员，虚拟人员和所有时段的边权重都设为0，算法运行后忽略虚拟人员的匹配结果即可。

代码实现参考（Python） #

不需要手写匈牙利算法，直接调用scipy库封装好的线性和分配函数即可：

import numpy as np
from scipy.optimize import linear_sum_assignment

def solve_appointment(n_people, n_slots, preference_matrix):
    # 构建权重矩阵，不可匹配的2替换为极大值
    INF = 10 ** 6
    cost_matrix = np.array(preference_matrix, dtype=np.float64)
    cost_matrix[cost_matrix == 2] = INF
    # 时段数大于人数时补全虚拟人员
    if n_slots > n_people:
        dummy = np.zeros((n_slots - n_people, n_slots), dtype=np.float64)
        cost_matrix = np.vstack([cost_matrix, dummy])
    # 运行匈牙利算法
    row_ind, col_ind = linear_sum_assignment(cost_matrix)
    # 提取真实人员的匹配结果
    result = {}
    total_cost = 0
    for i in range(n_people):
        person_id = i + 1 # 转1-based编号方便查看
        slot_id = col_ind[i] + 1
        result[person_id] = slot_id
        total_cost += cost_matrix[i][col_ind[i]]
    return result, total_cost, total_cost >= INF

# 示例输入测试
if __name__ == "__main__":
    n_people = 6
    n_slots = 7
    pref_matrix = [
        [0,0,0,0,0,0,0],
        [1,0,0,1,1,0,0],
        [2,2,2,1,2,2,2],
        [2,1,1,1,2,1,2],
        [0,1,2,2,1,0,0],
        [1,2,1,2,0,1,1]
    ]
    match_res, total_cost, is_invalid = solve_appointment(n_people, n_slots, pref_matrix)
    if is_invalid:
        print("当前偏好无法生成合法匹配方案")
    else:
        print("人员-时段匹配结果：")
        for person, slot in match_res.items():
            print(f"人员{person} → 时段{slot}")
        print(f"全局匹配总代价：{total_cost}")

边界情况处理 #

• 若存在人员所有时段偏好都是2、或总可用可匹配时段数小于人数的情况，返回的is_invalid会为True，可直接提示用户当前偏好无法生成合法匹配。
• 若存在多个总代价相同的最优解，算法会返回任意一个，若需要额外优先级规则（比如优先分配更早的时段），可以调整权重设置，比如给更早的时段加0.001级别的极小权重偏移即可。

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