本文介绍如何将学生宿舍分配问题建模为带权图上的组合优化任务，利用networkx构建偏好关系图，结合路径权重评估与穷举剪枝策略，在合理规模下求得高满意度的2床/3床房间分配方案。
在组织班级集体出行（如研学、实训或夏令营）时，常需将学生分入固定数量的多人房间（例如本例中的14间三人间 + 6间双人间，共54人），同时尽可能满足学生的室友偏好——即每位学生希望与特定同伴同住。这类问题本质上是一个带约束的多目标组合优化问题：既要覆盖全部学生、严格匹配房间类型与数量，又要最大化群体“满意度”（由双向偏好强度量化）。直接暴力枚举所有分配方案不可行（54!量级），但通过合理建模与剪枝，可在中小规模（≤60人）下获得高质量解。
核心建模思路：将偏好转化为图的边权
我们使用 networkx 构建一个无向完全图 G，节点代表学生，每条边 (u, v) 的权重反映两人同住的适配度：
- 若 u ∈ preferences[v] 且 v ∈ preferences[u]（双向喜欢）→ 权重设为 2（强正向激励）；
- 若仅单向偏好或无明确偏好 → 权重设为 -1（弱惩罚，避免强制拆散）；
- 所有未显式声明的关系默认存在（图是完全图），确保任意两人理论上可同住。
✅ 关键设计：三人间的“房间质量”不等于两两边权之和，而应包含闭环结构。因此定义路径权重函数 path_weight(G, path)，对元组 path = (a,b,c) 计算 G[a][b] + G[b][c] + G[a][c]（即三人两两交互总和），双人间则为 G[a][b]。
算法流程：生成可行解 + 排序择优
预生成所有合法房间单元：
使用 itertools.combinations(students, 2) 和 itertools.combinations(students, 3) 分别生成所有可能的双人组与三人组，并计算其路径权重，存入字典 paths（键为元组，值为得分）。-
构造全局分配候选集：
从所有房间单元中选出恰好 6 个双人组 + 14 个三人组（共20个房间），使其互斥覆盖全部54名学生。这一步通过 itertools.combinations(paths.keys(), 20) 实现，但需严格校验：def is_allowed(combination): all_students = sum(combination, ()) # 展平为学生ID列表 from collections import Counter counts = Counter(all_students) return (len(counts) == 54 and # 全员出现 all(v == 1 for v in counts.values())) # 无人重复⚠️ 注意：原始示例代码中 N_HOTEL_ROOMS=3 是教学简化版，实际需按 6+14=20 个房间构造组合，计算量剧增。生产环境建议改用回溯+剪枝或整数规划（如PuLP） 替代纯穷举。
-
评分与选择最优解：
对每个合法分配方案，累加其包含的所有房间单元得分；最终取总分最高者作为推荐方案：best_assignment = max(allowable_solutions, key=lambda x: sum(paths[r] for r in x))
实用建议与进阶方向
-
性能优化：当学生数 > 40 时，纯组合枚举会超时。推荐改用：
- 混合整数线性规划（MILP）：将每个可能的2/3人组设为二进制变量，添加覆盖约束（每人恰好属于1个房间）、数量约束（6个双人间、14个三人间）、目标函数为加权和；
- 贪心+局部搜索：先按偏好强度排序学生对，优先分配高分双人组；再对剩余学生用启发式聚类补全三人间，最后用交换邻域搜索微调；
- 偏好增强：支持权重分级（如“强烈希望”+3分、“可接受”+1分、“坚决拒绝”-5分），提升模型表达力；
- 公平性考量：在目标函数中加入方差惩罚项，避免部分学生满意度极高而另一些人被严重忽视。
该方法将抽象的社交约束转化为可计算的图结构，兼顾可解释性与实现简洁性，是教育场景下平衡算法深度与工程落地的典型范例。
