本文介绍如何将学生宿舍分配问题建模为加权图上的组合优化任务，利用 `networkx` 构建偏好图、定义房间兼容性得分，并通过有限枚举+约束过滤寻找高满意度的可行分配方案。
在组织集体出行（如班级研学）时，将 54 名学生合理分配至 14 间三人间和 6 间双人间，同时尽可能满足其住宿偏好（例如“希望与 A、B 同住”），是一个典型的带约束的多目标匹配问题。直接穷举所有分配方案（约 $ \frac{54!}{(3!)^{14}(2!)^6 \cdot 14! \cdot 6!} $ 种）显然不可行；但借助图建模与智能剪枝，我们可在小规模到中等规模（如 ≤30 人）下获得高质量近似解——本文即围绕这一思路展开。
核心思想：将“偏好”转化为图边权重
我们将每位学生视为图的一个节点，若学生 A 将 B 列入偏好列表，则在 A→B 之间添加一条有向边；若偏好是双向的（即 A 喜欢 B 且 B 喜欢 A），则可视为无向边并赋予正向权重（如 +2）；否则设为较低分（如 -1）。最终构建一个完全图（所有学生两两相连），每条边携带反映“配对意愿强度”的权重：
import networkx as nx
import itertools
from collections import defaultdict
preferences = {
"A": ["B", "C", "F"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["C", "B"],
"E": ["F", "G"],
"F": ["G", "A"],
"G": ["F", "D"]
}
# 构建无向完全图（所有学生均为节点）
G = nx.complete_graph(preferences.keys())
# 设置边权重：双向偏好 → +2；单向或无偏好 → -1
for u in preferences:
for v in preferences[u]:
if v in G.nodes() and u in preferences.get(v, []):
G[u][v]['weight'] = 2 # 互喜，强兼容
else:
G[u][v]['weight'] = -1 # 单向/无偏好，弱兼容✅ 注意：实际应用中应确保偏好数据清洗完整（如统一 ID、去重、补全缺失项），避免键错误导致 KeyError。
房间得分函数：量化“一间房的和谐度”
对任意房间组合（如三元组 (A,B,C) 或二元组 (D,E)），其整体适配度不应仅是两两边权之和，还应包含闭环一致性——即三人同住时，A↔B、B↔C、C↔A 三对关系均需被评估。因此定义路径权重函数如下：
def room_score(G, group):
"""计算一组学生（2人或3人）组成的房间总得分"""
score = 0
n = len(group)
# 累加所有两两之间的边权（无序对）
for i in range(n):
for j in range(i + 1, n):
score += G[group[i]][group[j]]['weight']
# 若为3人房，额外鼓励三角闭环（非必需，可选增强）
if n == 3:
score += G[group[0]][group[2]]['weight'] # 补全 A-C 边（已在上层循环计入，此处仅为示意逻辑）
return score该函数使互惠型小团体（如 A-B-C 彼此喜欢）自动获得更高分，而存在冲突或冷淡关系的组合得分偏低，自然被后续筛选机制淘汰。
构造合法分配：组合生成 + 约束验证
我们需要从全部可能的双人/三人子集中，选出恰好 6 个大小为 2 的组合与 14 个大小为 3 的组合，使得：
- 所有 54 名学生恰好出现一次；
- 没有任何学生被重复分配或遗漏。
由于全量枚举不可行，我们采用分阶段构造策略：
- 预生成所有高潜力房间候选集（仅保留得分 ≥ 阈值的 pair/triple）；
- 随机采样或启发式选取若干候选房间组合，再验证是否覆盖全部学生且不重叠；
- 使用回溯+剪枝（如按学生优先级逐一分配，提前终止低分分支）提升效率。
以下为轻量级可行实现（适用于 ≤25 人场景）：
# Step 1: 生成所有合法双人/三人房间候选（按得分排序）
candidates_2 = []
candidates_3 = []
students = list(preferences.keys())
for pair in itertools.combinations(students, 2):
s = room_score(G, pair)
if s >= 0: # 过滤明显不合适的pair
candidates_2.append((pair, s))
for triple in itertools.combinations(students, 3):
s = room_score(G, triple)
if s >= 2: # 更严格门槛（三人房要求更高一致性）
candidates_3.append((triple, s))
# Step 2: 枚举满足数量约束的组合（示例：仅选3个房间用于演示）
N_2, N_3 = 2, 1 # 小规模测试：2间双人房 + 1间三人房
best_score = float('-inf')
best_assignment = None
# 枚举：选 N_2 个双人房 + N_3 个三人房
for c2 in itertools.combinations(candidates_2, N_2):
for c3 in itertools.combinations(candidates_3, N_3):
rooms = [t[0] for t in c2] + [t[0] for t in c3]
all_people = set(sum(rooms, ()))
if len(all_people) == 2*N_2 + 3*N_3 and len(all_people) == len(sum(rooms, ())):
total_score = sum(t[1] for t in c2) + sum(t[1] for t in c3)
if total_score > best_score:
best_score = total_score
best_assignment = rooms
if best_assignment:
print("✅ 最优分配（得分=", best_score, "）:")
for i, r in enumerate(best_assignment):
room_type = "双人房" if len(r) == 2 else "三人房"
print(f" {room_type} {i+1}: {r}")
else:
print("⚠️ 未找到满足约束的可行解，请放宽得分阈值或检查偏好数据完整性。")实践建议与进阶方向
- 性能优化：当学生数 >30，建议改用整数线性规划（ILP），以 x_{i,j,k} 表示学生 i 是否与 j,k 同住于某三人间，配合 PuLP 或 OR-Tools 求解；
- 偏好扩展：支持“黑名单”（禁止同住）、权重分级（“非常希望” vs “可以接受”）、房间类型偏好（靠窗/安静区）等；
- 公平性增强：除最大化总分外，可引入最小个体满意度约束（max-min fairness），避免个别学生被强行塞入低分房间；
- 部署友好：封装为 CLI 工具或简易 Web 表单（Flask + Bootstrap），供教师上传 CSV 偏好表并一键导出分配结果。
总之，本问题本质是约束满足 + 多目标优化的融合体。虽无银弹算法，但通过合理建模（图+权重）、可控搜索（剪枝枚举）与渐进增强（ILP/启发式），即可在现实时限内交付高实用性解决方案。
