Построение проблемы с расписанием с большим количеством переменных - PullRequest
Новая
       48

Построение проблемы с расписанием с большим количеством переменных

3 голосов
/ 07 мая 2011

У меня есть классическая проблема с расписанием, состоящая из классов переменных (~ 100), комнат (20), терминов (8) и дней недели (5).

Чтобы упростить задачу, ниже приведены сокращенныеограничения.

День составляет 9 часов.

Некоторые уроки являются обязательными для студентов, а уроки обязательными с условиями 1,3,5,7 (и для 2,4,6,8) не должны накладываться друг на друга.

Классы имеют разный вес в часах, некоторые - 2 часа, некоторые - 3.

Некоторые занятия должны проводиться в определенных комнатах.

Не может быть двух лекций в одном классе одновременно.

Я собираюсь использовать модуль ограничений python logilabs.И я знаю, что разумный выбор переменных и доменов приведет к меньшему времени для решения проблемы.Проблема в том, что я никогда раньше не занимался программированием с ограничениями, и мне было трудно создать проблему, чтобы выяснить, с чего и с чего начать.Например:

Я могу установить ограничение, например «нет двух классов с одной комнатой, один и тот же день может перекрывать временной интервал друг друга».Или начните с того, что «ни в одной комнате не может быть зарезервировано более 9 часов в один и тот же день», а затем переходите к сокращенной области решения.Я оцениваю (не пытался), что первое ограничение займет гораздо больше времени, чем другое.Но это также требует (я предполагаю) изменения переменных и областей решения или перестройки меньшей проблемы.Я уже немного потерян в переменных, доменах, интервалах, реализациях и т. Д.

Короче говоря, мне нужны некоторые указатели для построения проблемы, области решения, выбора переменных и т. Д.

Спасибо

ОБНОВЛЕНИЕ

Используя пакет logilab-ограничений, я сделал базовое приложение и загрузил его в github

Ответы [ 2 ]

1 голос
/ 08 мая 2011

Взгляните на пример кода учебного плана из Планировщик слюн .Это в основном то же самое, но терминология немного отличается: каждый курс (= класс) имеет несколько лекций, которые должны быть запланированы в комнату (= комната) и период (= каждый термин в каждом дне недели является периодом).

Хитрость заключается в том, чтобы поддерживать чистую модель предметной области и отделять ее от правил ограничения.Поскольку у ваших классов разный вес в часах, я предлагаю, чтобы Lecture был назначен только startingPeriod, поэтому не так много кода, чтобы переместить Лекцию в другой набор Периода (просто переназначить первый Период).

0 голосов
/ 11 мая 2011

Я получил решение, которое объединяет «мудрый выбор переменных» и «сокращение доменов при выборе».Ниже приведены фрагменты из приложения для создания временных диаграмм на основе Django, которое я делаю: 

class Course(models.Model):
    name = models.CharField(max_length=255, null=False, blank=False)
    duration = models.PositiveSmallIntegerField(blank=False)
    type = models.ForeignKey(CourseType, blank=False, null=False)
    mandatory = models.BooleanField(default=False)
    '''
        following are the basic constraints  
    '''
    days = models.ManyToManyField(Day, blank=True, null=True)
    terms = models.ManyToManyField(Term)
    rooms = models.ManyToManyField('ClassRoom', blank=True, null=True)


    def __unicode__(self):
        return u'%s' % self.name

Я включил основные ограничения в классы, такие как «этот курс может быть в понедельник или вторник, в терминах 1или 2 или 3 в комнатах 1 или 2 или 3 или 4 или 5 ", что позволяет мне непосредственно применять эти основные ограничения в начале при выборе курсов из базы данных.

Общие ограничения, такие как «два курса не могут находиться в одной и той же комнате в одно и то же время в один и тот же день», применяются к сокращенным переменным доменам, полученным в результате выбора, сделанного в базе данных.

Кажется, сейчас работает.

...