本文介绍如何将学生宿舍分配问题建模为加权图上的组合优化任务，利用 `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 名学生恰好出现一次；
• 没有任何学生被重复分配或遗漏。

由于全量枚举不可行，我们采用分阶段构造策略：

1. 预生成所有高潜力房间候选集（仅保留得分 ≥ 阈值的 pair/triple）；
2. 随机采样或启发式选取若干候选房间组合，再验证是否覆盖全部学生且不重叠；
3. 使用回溯+剪枝（如按学生优先级逐一分配，提前终止低分分支）提升效率。

以下为轻量级可行实现（适用于 ≤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/启发式），即可在现实时限内交付高实用性解决方案。