我是大学的实验室实践导师,根据去年学生的评论,我们希望我的老板和我能够解决这些问题。我的老板选择编写 C 脚本,而我选择 python(python-constraint)来尝试解决我们的问题。
信息
- 共有 6 个 session
- 有 4 个角色
- 有 6 种做法
- 共有 32 名学生
- 每队有 4 名学生
问题:
为每个学生分配 4 个角色,在 4 个不同类(class)的 4 次练习中进行。
约束:
- 学生应该扮演一次角色
- 学生应该进行 6 种不同练习中的 4 种
- 学生每节课只能进行一次练习
- 学生只能与同一个伙伴见面一次
模板:
这是我和学生一起感受的模板,每个团队由 4 名学生组成,位置 [0, 1, 2 或 3] 是分配给他们的角色。每个可用位置的编号为 1 到 128
[# Semester
[ # Session
[ # Practice/Team
1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16],
[17, 18, 19, 20],
[21, 22, 23, 24]],
[[25, 26, 27, 28],
[29, 30, 31, 32],
[33, 34, 35, 36],
[37, 38, 39, 40],
[41, 42, 43, 44],
[45, 46, 47, 48]],
[[49, 50, 51, 52],
[53, 54, 55, 56],
[57, 58, 59, 60],
[61, 62, 63, 64],
[65, 66, 67, 68],
[69, 70, 71, 72]],
[[73, 74, 75, 76],
[77, 78, 79, 80],
[81, 82, 83, 84],
[85, 86, 87, 88],
[89, 90, 91, 92],
[93, 94, 95, 96]],
[[97, 98, 99, 100],
[101, 102, 103, 104],
[105, 106, 107, 108],
[109, 110, 111, 112]],
[[113, 114, 115, 116],
[117, 118, 119, 120],
[121, 122, 123, 124],
[125, 126, 127, 128]]]
换句话说:
这是一个 session :
[[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16],
[17, 18, 19, 20],
[21, 22, 23, 24]],
这些团队进行相同的练习:
[
[1, 2, 3, 4],
[25, 26, 27, 28],
[49, 50, 51, 52],
[73, 74, 75, 76],
[97, 98, 99, 100],
[113, 114, 115, 116]
]
这些位置起着相同的作用:
[
1,
5,
9,
13,
17,
21,
25,
...
]
到目前为止我所拥有的:
使用python-constraint我能够验证前三个约束:
Valid solution : False
- sessions : [True, True, True, True, True, True]
- practices : [True, True, True, True, True, True]
- roles : [True, True, True, True]
- teams : [False, False, True, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, True, False, False, False, False, False]
对于那些可能感兴趣的人,我只是这样做:
对于每个条件,我使用 AllDifferentConstraint 。例如,对于一次 session ,我执行以下操作:
problem.addConstraint(AllDifferentConstraint(), [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24])
我找不到限制团队的方法,我整个学期
的最后一次尝试是这样的:
def team_constraint(self, *semester):
students = defaultdict(list)
# get back each teams based on the format [# Semester [ #Session [# Practice/Team ...
teams = [list(semester[i:i+4]) for i in range(0, len(semester), 4)]
# Update Students dict with all mate they work with
for team in teams:
for student in team:
students[student] += [s for s in team if s != student]
# Compute for each student if they meet someone more than once
dupli = []
for student, mate in students.items():
dupli.append(len(mate) - len(set(mate)))
# Loosly constraint, if a student meet somone 0 or one time it's find
if max(dupli) >= 2:
print("Mate encounter more than one time", dupli, min(dupli) ,max(dupli))
return False
pprint(students)
return True
问题:
- 根据团队条件可以做我想做的事吗?我的意思是,我不知道是否可以为每个学生分配 12 个伙伴,并且每个人只遇到同一个伙伴一次。
- 由于团队限制,我是否错过了性能更高的算法?
- 有什么我可以关注的吗?
最佳答案
主要问题可以用...来回答
def person_works_with_different():
# over all the sessions, each person works with each other person no more than once.
# 'works with' means in 'same session team'
for p in all_people:
buddy_constraint = []
for s in all_sessions:
for g in all_teams:
p_list = [pv[k] for k in filter(lambda i: i[P] == p and i[S] == s and i[G] == g, pv)]
for o in all_people:
if o != p: # other is not person
o_list = [self.pv[k] for k in filter(lambda i: i[self.P] == o and i[self.S] == s and i[self.G] == g, self.pv)]
tmp = model.NewBoolVar('')
buddy_constraint.append(tmp)
model.Add(sum(o_list) == sum(p_list)).OnlyEnforceIf(tmp)
# tmp is set only if o and p are in the same session/team
# The number of times a student gets to take part is the number of roles.
# The size of the group controlled by the number of roles
model.Add(sum(buddy_constraint) = all_roles * (all_roles - 1))
添加编辑
昨天我又看了一遍你的问题 - (诚然时间不长,因为我现在有很多工作要做),并且......
首先,我看到你的“团队”实体,几乎就是我所说的“行动”实体,回想起来,我认为“团队”(或“团体”)是一个更好的词。
如果您仍然发现这些约束很难,我建议您将它们分解出来,并单独处理它们 - 特别是团队/人员/ session 约束,然后是角色/任务约束。
/添加编辑
team: a gathering of 4 persons during a session
person (32): a participant of a team
session (6): time: eg, 8am -10am
role (4): what responsibility a person has in an action
task (6): type of action
A person does:
0..1 action per session-group
1 role per action
1 task per action
0..1 of each task
1 of each role in an action
4 persons in an action
A person meets each other person 0..1 times
An action requires exactly 4 people
我最近也遇到了类似的问题,最后转向了OR-tools。 https://developers.google.com/optimization/cp/cp_solver
特别是看一下护士调度问题:https://developers.google.com/optimization/scheduling/employee_scheduling#nurse_scheduling
无论如何,问题并不太复杂,所以使用求解器对你来说可能有点大材小用。
同样,对于此类问题,最好使用元组键控字典来保存变量,而不是嵌套列表:
{ 团队、 session 、人员:BoolVar }
主要原因是您可以通过过滤器应用约束,这比必须执行嵌套列表操作要容易得多,例如,可以在人员/团队之间应用约束(其中人员索引为 2 且团队索引为 0):
for p in all_persons:
for t in all_teams:
stuff = [b_vars[k] for k in filter(lambda i: i[2] == p and i[0] == t, b_vars)]
model.Add(sum(stuff) == 4) # persons per team == 4
关于python - 缺少一个约束的约束满足问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59180598/