标题：基于偏好关系的宿舍分配优化：用图论与组合搜索求解多人房间匹配问题_技术教程

本文介绍如何将学生宿舍分配问题建模为加权图上的组合优化任务，利用 networkx 构建偏好图、定义路径得分函数，并通过有限枚举+约束过滤策略，在合理规模下找到满足房间容量（14 个三人间 + 6 个双人间）且整体“偏好满意度”最高的分组方案。

在组织班级集体出行时，将 54 名学生合理分配至 14 间三床房和 6 间双床房，并尽可能满足其相互住宿偏好，本质上是一个带容量约束的多组匹配优化问题。直接暴力穷举所有分组方式（如 $ \frac{54!}{(3!)^{14}(2!)^6 \cdot 14! \cdot 6!} $）计算量远超可行范围；但若善用图建模与智能剪枝，可在中小规模（≤60人）下获得高质量近似最优解。

核心思路：将“偏好”转化为图边权重

我们将每位学生视为图节点，若学生 A 与 B 互为偏好（即 B in preferences[A] 且 A in preferences[B]），则在无向图中添加一条权重为 +2 的边；若单向偏好或无偏好，则设为 -1（可依实际需求调整）。这样，一个三人房 {A,B,C} 的“兼容度得分”可定义为三边权重之和：
$$ \text{score}(A,B,C) = w{AB} + w{BC} + w{AC} $$
同理，双人房 {A,B} 得分为 $w{AB}$。该设计天然鼓励“闭环偏好”（如 A↔B↔C↔A），也惩罚孤立或冲突匹配。

实现关键：约束感知的组合生成与评分

由于目标房间结构固定（14×3 + 6×2 = 54），我们不枚举全部划分，而是分两步高效构造合法解：

预生成所有合法子组
使用 itertools.combinations(students, 2) 和 itertools.combinations(students, 3) 分别生成所有可能的双人/三人候选组，并计算其得分：

from itertools import combinations
valid_pairs = []
valid_triples = []
for pair in combinations(students, 2):
    if pair[1] in preferences.get(pair[0], []) and pair[0] in preferences.get(pair[1], []):
        valid_pairs.append((pair, 2))  # 互惠偏好得2分
    else:
        valid_pairs.append((pair, -1))

for triple in combinations(students, 3):
    # 检查三者是否两两互惠（强偏好三角）
    if all(t in preferences.get(s, []) for s, t in [(triple[0], triple[1]), 
                                                   (triple[0], triple[2]), 
                                                   (triple[1], triple[2])]):
        valid_triples.append((triple, 6))  # 3条边×2分
    # 可扩展：支持部分互惠的中间得分（如4分、5分）

构建全局分配并过滤非法解
从 valid_pairs 和 valid_triples 中选取恰好 6 个 pair 和 14 个 triple，确保：
- 所有 54 名学生恰好出现一次（无重复、无遗漏）；
- 使用 collections.Counter 快速验证覆盖性。
  为控制计算量，可加入启发式剪枝：优先尝试高分子组，或使用 heapq 维护候选池。

注意事项与进阶建议

时间复杂度管理：对 54 人，C(54,3)=24804 个三人组 + C(54,2)=1431 个两人组，枚举所有 (14+6) 元组合仍不可行。实践中应：
✅ 限制仅考虑得分 ≥ 阈值（如 ≥4）的子组；
✅ 采用贪心初始化 + 局部搜索（如模拟退火）优化；
❌ 避免无剪枝的全组合 itertools.combinations(all_groups, 20)。
偏好数据清洗：原始 preferences 字典需标准化（统一 ID、处理空列表、补全单向偏好为双向或标记为弱关联）。
扩展性设计：若未来需支持“禁止同住”（如冲突学生）、楼层/性别约束，可在图中添加负无穷权重边，或在 is_allowed() 函数中嵌入额外校验逻辑。

最终，该方法将主观偏好客观量化，以图论为桥梁，把一个看似混乱的社交匹配问题，转化为可编程、可评估、可迭代优化的工程任务——这正是算法思维在真实场景中的有力体现。