我在解决以下班级旅行问题时遇到了麻烦：
有54名学生，必须被分成14间3床房和6间2床房。每个人都有一个或多个最喜欢的人，他/她想与他们共享一个房间。
首选项= {'studen1'：[studnet2，student3]，'student2'：[student3，student 1]，...}
我能够计算出每种可能的三重匹配（在 3 个学生组成的小组中，每个人都互相喜欢）和正常匹配（在 2 个学生组成的小组中，每个人都互相喜欢）
我考虑过尝试计算学生的每种可能的组合（或至少是偏好），并尝试通过根据房间的好坏程度提供分数来获得最佳结果： 好的3人间：6分 好2房：4分 平均3人间：5分 平均三床房：4分 中差3房：3分 差3er房间：2分 非常差的三床房：1分 中2房：1分
现在我有点不知所措，不知道如何在不需要使用超级计算机的情况下解决问题；）
我对我的代码非常糟糕感到抱歉；） 这是我计算正常匹配和三重匹配后的代码：
students_with_room = []
real_rooms = []
exit_loop = False
real_rooms = {'2A': [], '2B': [], '2C': [], '2D': [], '2E': [], '2F': [],'3A': [], '3B': [], '3C': [], '3D': [], '3E': [], '3F': [], '3G': [], '3H': [], '3I': [], '3J': [], '3K': [], '3L': [], '3M': [], '3N': [],}
for student in students:
if student not in students_with_room:
if triple_matches[student] == None:
for room in real_rooms:
if real_rooms[room] == [] and '2' in room:
if len(matches[student]) != 0:
for i in range(len(matches[student])):
if len(set([matches[student][i], student]).intersection(students_with_room)) == 0:
real_rooms[room] = [matches[student][i], student]
students_with_room = students_with_room + [matches[student][i]]
students_with_room = students_with_room + [student]
exit_loop = True
break
else:
pass
else:
pass
if exit_loop == True:
break
if real_rooms[room] == [] and '3' in room:
pass
exit_loop = False
else:
for room in real_rooms:
if student not in students_with_room:
if real_rooms[room] == [] and '3' in room:
real_rooms[room] = [triple_matches[student][0], triple_matches[student][1], student]
students_with_room = students_with_room + triple_matches[student]
students_with_room = students_with_room + [student]
else:
pass
for triple_match in triple_matches:
already_done = False
if triple_matches[student] == None:
pass
else:
if student in students_with_room:
already_done = True
if not already_done:
students_with_room.append(triple_matches[student][0])
real_rooms
好吧，这个问题看起来有点有趣，这是一个使用 networkx 的简单但
强力解决方案的示例。请注意，一旦学生数量增加，运行速度就会变慢。我仍然建议将其视为多个背包问题，但希望这足以让您以不同的方式思考该问题。
import networkx as nx
import itertools
from collections import defaultdict
students_to_room = 3
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())
N_HOTEL_ROOMS = 3
student_ids = list(preferences.keys())
for key in student_ids:
for k in student_ids:
if k in preferences[key]:
# arbitrary value, if two students like eachother
G[key][k]['weight'] = 2
else:
# I am lazy
try:
# aribtrary value, if two students don'w seem to like eachother
G[key][k]['weight'] = -1
except:
pass
def path_weight(G, path):
# Function to calculate the weight of a path
weight = 0
for i in range(len(path) - 1):
weight += G[path[i]][path[i + 1]]['weight']
if len(path) > 1:
weight += G[path[0]][path[-1]]['weight']
return weight
def max_path(G, n1, n2, cutoff = students_to_room -1):
# Find the path on G between nodes n1 and n2 of length
# cutoff with the largest edge weight
all_paths = nx.all_simple_paths(G, n1, n2, cutoff= cutoff)
#all_paths = [path for path in all_paths if len(path) == cutoff + 1]
path = max(all_paths, key=lambda path: path_weight(G, path))
return path, path_weight(G, path)
def is_allowed(combination, student_ids = student_ids):
# Function to see if we have any students in multile rooms
#-- if so we can throw away the combination, and we also
# want to make sure all students are accounted for
all_elements = sum(combination, ())
counter = defaultdict(int)
for c in all_elements:
counter[c] += 1
return max(counter.values()) <= 1 and set(all_elements) == set(student_ids)
combos = []
# Find unique pairs of two students, so we can find
# which other students will go with them
room_assignments = [2,3]
for assignment in room_assignments:
for comb in itertools.combinations(keys, assignment):
combos.append(comb)
paths = {}
# Now for each unique pair of students, find a path of length
# sutends_to_room between them and find the weight of the path
# i.e. the "score" of putting those students to a room
for path in combos:
weight = path_weight(G,path)
paths[tuple(path)] = weight
# Get all possible combinations of students between three hotel rooms
allowable = itertools.combinations(paths.keys(), N_HOTEL_ROOMS)
# Only accept solutions where a student isn't between each room,
# and when we have all students
allowable = [a for a in allowable if is_allowed(a)]
max_paths = {}
for path in allowable:
max_paths[path] = sum([paths[a] for a in path])
# # sort the result, and the first entry is our "best" solution
s = dict(sorted(max_paths.items(), key=lambda item: item[1], reverse=True))
room_assignment = list(s.keys())[0]
print("Room assignment", room_assignment, "Happiness score", s[room_assignment])
>>> Room assignment (('A', 'B'), ('C', 'D'), ('E', 'F', 'G')) Happiness score 7
这里，
s编辑：抱歉，我读错了原来的问题，我没有意识到你已经在房间之间设置了学生编号分配，这应该可以解决这个问题。