오늘의 실습 코드
# ------------------ Day10(25.06.16) ------------------
# 교사 이동 최소화
teacher_moves = []
for teacher in teachers:
for t in range(1, len(time_slots)):
for room1 in rooms:
for room2 in rooms:
if room1 != room2:
for c in classes:
for s in teacher_subjects[teacher]:
prev = x.get((c, time_slots[t - 1], s, teacher, room1), None)
curr = x.get((c, time_slots[t], s, teacher, room1), None)
if prev is not None and curr is not None:
move_var = model.NewBoolVar(f'move_{teacher}_{t}_{room1}_{room2}')
model.AddBoolAnd([prev, curr]).OnlyEnforceIf(move_var)
model.AddBoolOr([prev.Not(), curr.Not()]).OnlyEnforceIf(move_var.Not())
teacher_moves.append(move_var)
# model.Minimize(sum(teacher_moves))
# 특정 교사 특정 시간대 선호 반영
bonus = []
for c in classes:
for t in [1, 2]: # 1~2교시
for s in teacher_subjects['T1']:
for room in rooms:
var = x.get((c, t, s, 'T1', room), None)
if var is not None:
bonus.append(var)
model.Maximize(10 * sum(bonus) - sum(teacher_moves))
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print(f'목적함수 값: {solver.ObjectiveValue()}')
print(f'이동 횟수: {sum(solver.Value(m) for m in teacher_moves)}')
print(f'T1 선호 시간대 수업: {sum(solver.Value(b) for b in bonus )}')
for c in classes:
print(f'\n{c} 시간표:')
schedule = {}
for t in time_slots:
for s in subjects:
for teacher in teachers:
if s in teacher_subjects[teacher]:
for room in rooms:
if solver.Value(x[c, t, s, teacher, room]):
print(f' {t}교시: {s} ({teacher}, {room})')
schedule[t] = (s, teacher, room)
# 시간표 정렬 출력
print(f'\n{c} 정렬된 시간표:')
for t in sorted(schedule.keys()):
s, teacher, room = schedule[t]
print(f' {t}교시: {s} ({teacher}, {room})')
else:
print('해를 찾을 수 없습니다.')
'''
목적함수 값: 20.0
이동 횟수: 0
T1 선호 시간대 수업: 2
1A 시간표:
1교시: Math (T1, R1)
2교시: Science (T3, R1)
3교시: Math (T1, R1)
4교시: English (T2, R2)
5교시: English (T2, R1)
1A 정렬된 시간표:
1교시: Math (T1, R1)
2교시: Science (T3, R1)
3교시: Math (T1, R1)
4교시: English (T2, R2)
5교시: English (T2, R1)
1B 시간표:
1교시: Science (T3, R2)
2교시: Math (T1, R2)
3교시: English (T2, R2)
4교시: Math (T1, R1)
5교시: Science (T3, R2)
1B 정렬된 시간표:
1교시: Science (T3, R2)
2교시: Math (T1, R2)
3교시: English (T2, R2)
4교시: Math (T1, R1)
5교시: Science (T3, R2)
'''코드 전체
------------------ Day8(25.06.15) ------------------
'''
간단한 시간표 문제를 해결하기 위한 예시 데이터
'''
# 교사 목록
teachers = ['T1', 'T2', 'T3']
# 과목 목록
subjects = ['Math', 'English', 'Science']
# 학급 목록
classes = ['1A', '1B']
# 교실 목록
rooms = ['R1', 'R2']
# 시간 슬롯(교시)
time_slots = [1, 2, 3, 4, 5]
# 각 반의 시수
class_subject_requirements = {
'1A': {'Math': 2, 'English': 2, 'Science': 1},
'1B': {'Math': 2, 'English': 1, 'Science': 2}
}
# 교사별 담당 과목
teacher_subjects = {
'T1': ['Math'],
'T2': ['English'],
'T3': ['Science']
}
from ortools.sat.python import cp_model
model = cp_model.CpModel()
x = {}
for c in classes:
for t in time_slots:
for s in subjects:
for teacher in teachers:
if s in teacher_subjects[teacher]: # 교사가 해당 과목을 가르칠 수 있을 때만
for room in rooms:
x[c, t, s, teacher, room] = model.NewBoolVar(f'x_{c}_{t}_{s}_{teacher}_{room}')
# 한 반은 한 시간에 한 과목
for c in classes:
for t in time_slots:
model.Add(sum(x[c, t, s, teacher, room]
for s in subjects
for teacher in teachers if s in teacher_subjects[teacher]
for room in rooms
) <= 1
)
# 반별 시수
for c in classes:
for s in subjects:
model.Add(sum(x[c, t, s, teacher, room]
for t in time_slots
for teacher in teachers if s in teacher_subjects[teacher]
for room in rooms
) == class_subject_requirements[c][s]
)
# 한 교사는 한 시간에 한 반만 가르칠 수 있다.
for teacher in teachers:
for t in time_slots:
model.Add(sum(x[c, t, s, teacher, room]
for c in classes
for s in subjects if s in teacher_subjects[teacher]
for room in rooms
) <= 1
)
# 한 교실은 한 시간에 한 반만 사용
for room in rooms:
for t in time_slots:
model.Add(sum(x[c, t, s, teacher, room]
for c in classes
for s in subjects
for teacher in teachers if s in teacher_subjects[teacher]
) <= 1
)
# solver = cp_model.CpSolver()
# status = solver.Solve(model)
# if status == cp_model.FEASIBLE or status == cp_model.OPTIMAL:
# for c in classes:
# print(f'\n{c} 시간표:')
# for t in time_slots:
# for s in subjects:
# for teacher in teachers:
# if s in teacher_subjects[teacher]:
# for room in rooms:
# if solver.Value(x[c, t, s, teacher, room]):
# print(f' {t}교시: {s} ({teacher}, {room})')
# else:
# print('해를 찾을 수 없습니다.')
# ------------------ Day9(25.06.15) ------------------
# # 1. 시간표 출력 가독성 높이기(해당 시간 수업 없는 경우)
# for c in classes:
# print(f'\n{c} 시간표:')
# for t in time_slots:
# found = False
# for s in subjects:
# for teacher in teachers:
# if s in teacher_subjects[teacher]:
# for room in rooms:
# if solver.Value(x[c, t, s, teacher, room]):
# print(f' {t}교시: {s} ({teacher}, {room})')
# found = True
# if not found:
# print(f' {t}교시: 수업 없음')
'''
1A 시간표:
1교시: Science (T3, R1)
2교시: Math (T1, R2)
3교시: Math (T1, R2)
4교시: English (T2, R1)
5교시: English (T2, R2)
1B 시간표:
1교시: Math (T1, R2)
2교시: English (T2, R1)
3교시: Science (T3, R1)
4교시: Science (T3, R2)
5교시: Math (T1, R1)
'''
# 2. 여러 해 탐색
# class SolutionPrinter(cp_model.CpSolverSolutionCallback):
# def __init__(self, x, classes, time_slots, subjects, teachers, rooms, teacher_subjects, limit=5):
# cp_model.CpSolverSolutionCallback.__init__(self)
# self.x = x
# self.classes = classes
# self.time_slots = time_slots
# self.subjects = subjects
# self.teachers = teachers
# self.rooms = rooms
# self.teacher_subjects = teacher_subjects
# self.solution_count = 0
# self.limit = limit
#
# def on_solution_callback(self):
# self.solution_count += 1
# print(f'\n=== Solution {self.solution_count} ===')
# for c in self.classes:
# print(f'\n{c} 시간표:')
# for t in self.time_slots:
# found = False
# for s in self.subjects:
# for teacher in self.teachers:
# if s in self.teacher_subjects[teacher]:
# for room in self.rooms:
# if self.Value(self.x[c, t, s, teacher, room]):
# print(f' {t}교시: {s} ({teacher}, {room})')
# found = True
# if not found:
# print(f' {t}교시: 수업 없음')
# if self.solution_count >= self.limit:
# print(f'--- {self.limit}개 해까지만 출력합니다 ---')
# self.StopSearch()
#
# solver = cp_model.CpSolver()
# solution_printer = SolutionPrinter(x, classes, time_slots, subjects, teachers, rooms, teacher_subjects, limit=3)
# solver.SearchForAllSolutions(model, solution_printer)
'''
=== Solution 1 ===
1A 시간표:
1교시: Math (T1, R2)
2교시: English (T2, R1)
3교시: English (T2, R2)
4교시: Science (T3, R2)
5교시: Math (T1, R2)
1B 시간표:
1교시: Science (T3, R1)
2교시: Science (T3, R2)
3교시: Math (T1, R1)
4교시: Math (T1, R1)
5교시: English (T2, R1)
=== Solution 2 ===
1A 시간표:
1교시: Science (T3, R1)
2교시: Math (T1, R1)
3교시: English (T2, R2)
4교시: English (T2, R1)
5교시: Math (T1, R2)
1B 시간표:
1교시: Math (T1, R2)
2교시: Science (T3, R2)
3교시: Science (T3, R1)
4교시: Math (T1, R2)
5교시: English (T2, R1)
=== Solution 3 ===
1A 시간표:
1교시: Science (T3, R1)
2교시: English (T2, R2)
3교시: English (T2, R2)
4교시: Math (T1, R2)
5교시: Math (T1, R2)
1B 시간표:
1교시: Math (T1, R2)
2교시: Science (T3, R1)
3교시: Math (T1, R1)
4교시: Science (T3, R1)
5교시: English (T2, R1)
--- 3개 해까지만 출력합니다 ---
'''
# 3. 해가 없을 때(UNSATISFIABLE) 원인 분석 및 대처
# if status == cp_model.INFEASIBLE:
# print('해를 찾을 수 없습니다.')
'''
원인:
제약조건이 너무 빡빡하거나,
데이터(수업시수, 교실/교사 수, 시간 수 등)가 현실적으로 불가능한 경우
대처법:
제약조건을 하나씩 풀어보며 원인 찾기
(예: 과목별 수업시수를 줄이거나, 교사/교실 수를 늘려보기)
충돌이 많은 제약조건에 대해 로그 출력
(예: 어떤 반이 어떤 시간에 수업이 배정되지 못하는지 확인)
OR-Tools의 model.Validate() 사용
(명시적으로 오류를 알려주진 않지만, 제약조건 오류를 미리 점검 가능)
'''
# ------------------ Day10(25.06.16) ------------------
# 교사 이동 최소화
teacher_moves = []
for teacher in teachers:
for t in range(1, len(time_slots)):
for room1 in rooms:
for room2 in rooms:
if room1 != room2:
for c in classes:
for s in teacher_subjects[teacher]:
prev = x.get((c, time_slots[t - 1], s, teacher, room1), None)
curr = x.get((c, time_slots[t], s, teacher, room1), None)
if prev is not None and curr is not None:
move_var = model.NewBoolVar(f'move_{teacher}_{t}_{room1}_{room2}')
model.AddBoolAnd([prev, curr]).OnlyEnforceIf(move_var)
model.AddBoolOr([prev.Not(), curr.Not()]).OnlyEnforceIf(move_var.Not())
teacher_moves.append(move_var)
# model.Minimize(sum(teacher_moves))
# 특정 교사 특정 시간대 선호 반영
bonus = []
for c in classes:
for t in [1, 2]: # 1~2교시
for s in teacher_subjects['T1']:
for room in rooms:
var = x.get((c, t, s, 'T1', room), None)
if var is not None:
bonus.append(var)
model.Maximize(10 * sum(bonus) - sum(teacher_moves))
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print(f'목적함수 값: {solver.ObjectiveValue()}')
print(f'이동 횟수: {sum(solver.Value(m) for m in teacher_moves)}')
print(f'T1 선호 시간대 수업: {sum(solver.Value(b) for b in bonus )}')
for c in classes:
print(f'\n{c} 시간표:')
schedule = {}
for t in time_slots:
for s in subjects:
for teacher in teachers:
if s in teacher_subjects[teacher]:
for room in rooms:
if solver.Value(x[c, t, s, teacher, room]):
print(f' {t}교시: {s} ({teacher}, {room})')
schedule[t] = (s, teacher, room)
# 시간표 정렬 출력
print(f'\n{c} 정렬된 시간표:')
for t in sorted(schedule.keys()):
s, teacher, room = schedule[t]
print(f' {t}교시: {s} ({teacher}, {room})')
else:
print('해를 찾을 수 없습니다.')
'''
목적함수 값: 20.0
이동 횟수: 0
T1 선호 시간대 수업: 2
1A 시간표:
1교시: Math (T1, R1)
2교시: Science (T3, R1)
3교시: Math (T1, R1)
4교시: English (T2, R2)
5교시: English (T2, R1)
1A 정렬된 시간표:
1교시: Math (T1, R1)
2교시: Science (T3, R1)
3교시: Math (T1, R1)
4교시: English (T2, R2)
5교시: English (T2, R1)
1B 시간표:
1교시: Science (T3, R2)
2교시: Math (T1, R2)
3교시: English (T2, R2)
4교시: Math (T1, R1)
5교시: Science (T3, R2)
1B 정렬된 시간표:
1교시: Science (T3, R2)
2교시: Math (T1, R2)
3교시: English (T2, R2)
4교시: Math (T1, R1)
5교시: Science (T3, R2)
'''
개발 공부하는 30대 비전공자 직장인