多人宿舍分配问题需要同时考虑学生的居住偏好、房间的容量限制、性别分区等多重约束，传统的随机分配或简单排序分配很难满足大部分学生的需求，基于图论与组合搜索的方法可以将这类问题转化为可计算的模型，进而找到更优的分配结果。
问题建模基础
首先需要将宿舍分配问题中的各类元素抽象为图结构中的节点与边。学生作为一类节点，房间作为另一类节点，学生之间的偏好关系可以转化为学生节点之间的边权重，学生与房间之间的适配度可以转化为二分图的边权重。
常见的偏好关系包括：学生希望和特定同学同住、不希望和特定同学同住、对房间朝向楼层的要求等。我们可以将这些偏好量化为不同的分数，正向偏好赋予正分，负向偏好赋予负分，最终目标是最大化所有分配结果的总偏好分数。
图结构定义
整个分配场景可以抽象为三个核心图结构：
- 学生关系图：节点为学生，边表示两个学生之间的同住偏好，权重为偏好强度
- 房间属性图：节点为房间，属性包含容量、楼层、朝向等信息
- 学生房间二分图：左部为学生节点，右部为房间节点，边权重为学生对该房间的适配分数
组合搜索算法设计
组合搜索的核心是在所有可能的分配组合中找到总偏好分数最高的方案，由于房间容量限制，每个学生节点最终需要匹配到唯一的房间节点，且每个房间匹配的学生数量不能超过其容量。
搜索约束条件
搜索过程需要满足以下基础约束：
- 每个学生只能被分配到一个房间
- 每个房间分配的学生数量不超过其最大容量
- 同房间学生的负向偏好总和不超过阈值
剪枝优化策略
全量组合搜索的时间复杂度会随着学生数量增长呈指数级上升，因此需要加入剪枝策略提升效率：
- 当当前部分分配的总分数已经低于当前已知最优分数时，停止当前分支搜索
- 优先分配偏好约束更严格的学生，减少后续搜索的分支数量
- 预计算每个学生可选的最高分数房间，提前排除不可能产生最优解的选项
代码实现示例
以下是基于Python实现的简化版宿舍分配优化代码，包含图结构定义与组合搜索核心逻辑：
class Student:
def __init__(self, student_id, prefer_room_ids=None, prefer_partners=None, avoid_partners=None):
self.student_id = student_id
# 偏好的房间ID列表，元素为(房间ID, 分数)
self.prefer_room_ids = prefer_room_ids if prefer_room_ids else []
# 希望同住的同学ID列表，元素为(同学ID, 分数)
self.prefer_partners = prefer_partners if prefer_partners else []
# 不希望同住的同学ID列表，元素为(同学ID, 分数)
self.avoid_partners = avoid_partners if avoid_partners else []
class Room:
def __init__(self, room_id, capacity, floor=None, direction=None):
self.room_id = room_id
self.capacity = capacity
self.floor = floor
self.direction = direction
self.assigned_students = []
def calculate_pair_score(student1, student2, all_students):
# 计算两个学生同住的偏好分数
score = 0
# 检查student1是否偏好student2
for s_id, s_score in student1.prefer_partners:
if s_id == student2.student_id:
score += s_score
# 检查student1是否排斥student2
for s_id, s_score in student1.avoid_partners:
if s_id == student2.student_id:
score += s_score
# 反向检查student2的偏好
for s_id, s_score in student2.prefer_partners:
if s_id == student1.student_id:
score += s_score
for s_id, s_score in student2.avoid_partners:
if s_id == student1.student_id:
score += s_score
return score
def backtrack_search(students, rooms, current_idx, current_score, best_score, best_assignment, room_student_map):
# 所有学生都已分配完成，更新最优结果
if current_idx == len(students):
if current_score > best_score[0]:
best_score[0] = current_score
best_assignment.clear()
for room_id, s_list in room_student_map.items():
best_assignment[room_id] = [s.student_id for s in s_list]
return
current_student = students[current_idx]
# 遍历所有可选房间
for room in rooms:
# 房间已满则跳过
if len(room_student_map[room.room_id]) >= room.capacity:
continue
# 计算将该学生分配到当前房间的分数
add_score = 0
# 房间偏好分数
for r_id, r_score in current_student.prefer_room_ids:
if r_id == room.room_id:
add_score += r_score
# 同房间已有学生的配对分数
for exist_student in room_student_map[room.room_id]:
add_score += calculate_pair_score(current_student, exist_student, students)
# 剪枝：当前总分数已经低于最优分数则跳过
if current_score + add_score < best_score[0]:
continue
# 分配学生到房间
room_student_map[room.room_id].append(current_student)
# 递归搜索下一个学生
backtrack_search(students, rooms, current_idx + 1, current_score + add_score, best_score, best_assignment, room_student_map)
# 回溯，移除分配
room_student_map[room.room_id].pop()
def allocate_dormitory(students, rooms):
best_score = [-float('inf')]
best_assignment = {}
room_student_map = {room.room_id: [] for room in rooms}
backtrack_search(students, rooms, 0, 0, best_score, best_assignment, room_student_map)
return best_assignment, best_score[0]
# 测试示例
if __name__ == '__main__':
# 初始化学生数据
student1 = Student(1, prefer_room_ids=[(101, 5), (102, 3)], prefer_partners=[(2, 4)], avoid_partners=[(3, -10)])
student2 = Student(2, prefer_room_ids=[(101, 4)], prefer_partners=[(1, 4)], avoid_partners=[(3, -8)])
student3 = Student(3, prefer_room_ids=[(102, 5)], avoid_partners=[(1, -10), (2, -8)])
student4 = Student(4, prefer_room_ids=[(101, 3), (102, 4)])
students = [student1, student2, student3, student4]
# 初始化房间数据
room101 = Room(101, 2, floor=1, direction='南')
room102 = Room(102, 2, floor=2, direction='北')
rooms = [room101, room102]
# 执行分配
assignment, total_score = allocate_dormitory(students, rooms)
print('最优分配方案:', assignment)
print('总偏好分数:', total_score)
结果验证与优化
上述代码实现了基础的组合搜索分配逻辑，在测试场景中可以得到满足约束的分配结果。实际应用时可以根据需求扩展更多约束条件，比如性别分区、专业聚类等，只需要在分数计算与剪枝逻辑中加入对应的判断规则即可。
当学生数量较多时，基础的组合搜索可能会出现性能瓶颈，此时可以结合启发式搜索算法，比如模拟退火、遗传算法等，在可接受的时间内得到近似最优解，平衡分配效果与计算效率。