17370845950

本文介绍如何将54名学生按偏好（互选关系）分配到14间3人房和6间2人房中，通过构建加权图、枚举合法房间组合并评分排序，实现可解释、可扩展的近似最优分配方案。

这是一个典型的带偏好约束的组合分配问题，本质是将学生划分为固定大小（2人或3人）且互不重叠的子集，同时最大化群体满意度。由于硬性约束明确（恰好6个双人间 + 14个三人间 = 54人），而偏好具有对称性（如A喜欢B且B喜欢A才构成有效匹配），我们可将其建模为加权超图划分问题，并采用“生成-过滤-评分”三步策略高效求解。

核心思路：图建模 + 合法组合生成 + 加权评估

1. 构建无向加权图
   每位学生为一个节点；若两人互为偏好（即 B in preferences[A] and A in preferences[B]），则在它们之间添加一条权重为 +2 的边；否则设为 -1（表示低兼容性）。注意：必须验证双向偏好，单向喜欢不能保证共住意愿。

2. 生成所有合法房间候选

   • 所有满足互惠偏好的2人组合 → 双人间候选集 pairs
   • 所有满足两两互惠的3人组合（即三角形子图）→ 三人间候选集 triples
     使用 itertools.combinations(students, 2) 和 itertools.combinations(students, 3) 枚举，并用集合交集快速验证：

def is_valid_pair(a, b, prefs):
    return b in prefs.get(a, []) and a in prefs.get(b, [])

def is_valid_triple(a, b, c, prefs):
    return (is_valid_pair(a, b, prefs) and 
            is_valid_pair(b, c, prefs) and 
            is_valid_pair(a, c, prefs))

3. 构造全局分配方案并过滤合法性
   直接枚举所有从 pairs ∪ triples 中选出6个pair + 14个triple的组合，计算量爆炸（不可行）。更优策略是：
   ✅ 先生成所有可能的 单个房间（pair/triple）及其得分；
   ✅ 再使用回溯或约束编程（如 python-constraint 或 ortools）进行精确匹配；
   ⚠️ 若规模可控（如 ≤30人），可改用 itertools.product 分层采样 + is_allowed() 过滤（见原答案中 defaultdict 计数逻辑）。

以下为轻量级可行实现（适配原题54人场景，含剪枝）：

from itertools import combinations, product
from collections import Counter

# 假设已预计算好 valid_pairs 和 valid_triples 列表，每个元素为 tuple + score
# e.g., valid_pairs = [(('A','B'), 4), (('C','D'), 3), ...]
#       valid_triples = [(('A','B','C'), 9), ...]

def score_room(group, prefs):
    s = 0
    for a, b in combinations(group, 2):
        s += 2 if (b in prefs.get(a, []) and a in prefs.get(b, [])) else -1
    return s

# 预生成（建议用多进程加速）
valid_pairs = [
    (pair, score_room(pair, preferences)) 
    for pair in combinations(students, 2) 
    if is_valid_pair(*pair, preferences)
]
valid_triples = [
    (triple, score_room(triple, preferences)) 
    for triple in combinations(students, 3) 
    if is_valid_triple(*triple, preferences)
]

# 关键剪枝：仅保留高分候选（如 top 500 pairs & top 1000 triples）
valid_pairs = sorted(valid_pairs, key=lambda x: x[1], reverse=True)[:500]
valid_triples = sorted(valid_triples, key=lambda x: x[1], reverse=True)[:1000]

# 枚举分配：选择6个pair + 14个triple，覆盖全部54人且无重复
best_score, best_assignment = -float('inf'), None
for pairs_combo in combinations(valid_pairs, 6):
    used = set()
    for p, _ in pairs_combo:
        used.update(p)
    if len(used) != 12: continue  # 必须恰好12人

    remaining = set(students) - used
    for triples_combo in combinations(valid_triples, 14):
        all_in_triples = set()
        for t, _ in triples_combo:
            all_in_triples.update(t)
        if all_in_triples == remaining:
            total_score = sum(s for _, s in pairs_combo) + sum(s for _, s in triples_combo)
            if total_score > best_score:
                best_score = total_score
                best_assignment = (pairs_combo, triples_combo)

print("✅ Optimal assignment found!")
print("2-bed rooms:", [p for p, _ in best_assignment[0]])
print("3-bed rooms:", [t for t, _ in best_assignment[1]])
print("Total happiness score:", best_score)

注意事项与进阶建议

• 时间复杂度警示：纯暴力枚举在54人下不可行（C(54,2)≈1400对，C(54,3)≈24k个三人组），务必配合预筛选 + 分数阈值剪枝 + 启发式采样；
• 偏好数据清洗：原始 preferences 字典需统一键名、去重、补全空列表，避免 KeyError；
• 替代方案推荐：
  • ✅ 整数规划（IP）：用 ortools.linear_solver 建模为0-1变量（x_ij=1 表示i,j同房），添加容量与覆盖约束；
  • ✅ 图聚类启发式：将学生视为节点，偏好强度为边权，用 networkx.algorithms.community.greedy_modularity_communities 初步分组，再按大小调整；
  • ✅ 模拟退火 / 遗传算法：定义邻域操作（如交换两人房间、拆分重组三元组），以总分作为适应度函数；
• 公平性补充：可在目标函数中加入方差惩罚项，避免出现“全高分房+全低分房”的极端分配。

最终，该问题不是单纯算法题，而是建模能力 + 工程权衡 + 领域理解的综合体现——优先保证约束满足（人数/房间数/互惠性），再追求满意度最大化。