проблема удовлетворения ограничений отсутствует одно ограничение
Я преподаватель лабораторной практики в университете, основываясь на прошлогодних комментариях студентов, мы хотели, чтобы мы с моим начальником обратились к ним. Мой босс решил написать сценарий C, а я выбрал python (ограничение python), чтобы попытаться решить нашу проблему.
Информация
- Всего 6 сеансов
- Есть 4 роли
- Есть 6 практик
- Всего 32 студента
- В команде 4 студента
Проблема:
Распределите каждого ученика по 4 ролям по 4 практики в 4 разных занятиях.
Ограничения:
- Студенты должны разыграть роль
- Студенты должны выполнить 4 различных практики из 6
- Студенты должны выполнять только одну практику за занятие.
- Студент должен встретиться с одним и тем же партнером только один раз
Шаблоны:
Вот шаблон, который я чувствую со студентами, где каждая команда состоит из 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]]]
Другими словами:
Это сеанс:
[[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, я смог проверить первые три ограничения:
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. Например, за один сеанс я делаю:
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])
Я не могу найти способ ограничить команду, моя последняя попытка на всем semester было это:
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 товарищей каждому ученику, и каждый из них встретится с одним и тем же товарищем только один раз.
- Из-за ограничений команды я пропустил более производительный алгоритм?
- Любой пистолет, за которым я могу следить?
2 ответа
На главный вопрос можно было бы ответить примерно так...
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))
Добавлено редактирование
Вчера я еще раз взглянул на вашу проблему (правда, недолго, так как у меня сейчас много работы), и...
Прежде всего, я вижу, что ваша сущность "команда" - это в значительной степени то, что я назвал сущностью "действия", и, оглядываясь назад, я думаю, что "команда" (или "группа") было более подходящим словом для этого.
Если вам все еще трудно найти ограничения, я предлагаю вам устранить их и поработать над ними индивидуально - особенно ограничения команды / человека / сеанса, за которыми следуют ограничения роли / задачи.
/ Добавлено редактирование
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
В любом случае, проблема не слишком сложна, поэтому, возможно, использование решателя будет для вас излишним.
Аналогичным образом, для такого рода проблем может быть лучше использовать dict с ключом кортежа для хранения ваших переменных, а не вложенные списки:
{Команда, Сеанс, Человек: 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
Просто идея алгоритма перестановки, для каждой итерации можно сосредоточить внимание на одном из каждого ученика или на одном из каждого сеанса:
Session 1:
Roles
1,2,3,4
Students
1,2,3,4
(Note is 1st permutation 1234)
Sess 2 for student 1
Roles 1234
Students 5,1,7,6
Здесь студент 2 занимает место студента 1 на занятии 1 и продолжает это так
Roles 1234
St 2,5,6,7
Продолжить с учеником 1 S3 R 1234 St 10,9,1,8
S4
R 1234
St 11,12,13,1
В конце вы удаляете взаимодействия для ученика 1, как и при перестановках для следующей итерации, которую вы удаляете текущую.
Это как кубик рубика.
Если вам удастся закодировать это или узнать какой-то код с этим алгоритмом, дайте мне знать.
Может быть, с перестановками itertools
Сессии,> чем практики, я считаю, не так актуальны, как их количество. Просто немного пула, чтобы взять больше, когда у вас закончится, или больше места для ротации. Может быть, можно было бы упростить задачу сначала нацеливаясь на 4 занятия = практики?