Ограничение, делающее ваше расписание FET невозможным
Одно неверное ограничение может сделать файл FET нерешаемым, а поиск — длиться часами — проверьте файл заранее, это бесплатно и занимает секунды.
Вы заканчиваете ввод данных. Вы нажимаете Сгенерировать в FET. Затем вы ждёте.
Проходит десять минут. Проходит час. Количество размещённых занятий так и не достигает общего числа. В конце концов, вы останавливаете генерацию, и у вас нет расписания. Хуже того, вы не знаете почему.
Проблема часто заключается в одном ограничении
Школьное расписание содержит сотни ограничений. Большинство из них верны. Одно из них — нет, и вы не можете его увидеть.
Например:
- Класс из 31 студента может использовать только аудитории на 30 мест.
- У преподавателя 26 часов занятий, но он доступен только в течение 24 временных интервалов.
- Правило оставляет занятие без возможного времени начала в течение недели.
- Четыре занятия должны проходить в разные дни, но группа студентов учится только три дня в неделю.
Каждый из этих случаев делает расписание невозможным. Никакое расположение не может ему удовлетворить. Но файл выглядит нормально. FET открывает его и начинает поиск.
Почему поиск не даёт ответа
FET очень хорошо справляется со своей задачей. Он ищет такое расположение, которое соблюдает все ограничения. Некоторые файлы FET отклоняет сразу. Для многих других проблем он начинает поиск, который не может увенчаться успехом.
Неудачный поиск говорит вам только одно: этот поиск не нашёл расположения. Он не может отличить «ваши ограничения делают это невозможным» от «в этот раз я не нашёл». Поэтому вы меняете вес, пробуете снова и снова ждёте.
Вот куда уходят часы. Время уходит на поиск, который никогда не мог увенчаться успехом, а не на решение задачи.
Сначала посчитать, потом искать
Есть более быстрый вопрос, который стоит задать перед генерацией: возможно ли это расписание в принципе?
Этот вопрос не требует поиска. Он требует арифметики. Проверка считывает ваши ограничения и подсчитывает оставшиеся возможности:
- количество часов, которые должен провести преподаватель, в сравнении с количеством доступных временных интервалов
- возможное время начала занятия после применения всех правил
- не попадают ли два обязательных занятия в один и тот же временной интервал
- не требует ли группа занятий больше дней, чем есть в неделе
Когда один из этих счётчиков достигает нуля, расписание становится невозможным. Это не предположение о сложности. Это доказательство, и проверка предоставляет его за секунды.
Она указывает на правило
Доказательство полезно только тогда, когда на его основе можно действовать. Каждый результат проверки простыми словами говорит, что не так, и указывает на задействованные правила.
В приведённом выше примере в классе Математика · 9А 31 студент. Самая большая аудитория, которую разрешает ограничение Предпочтительная аудитория для занятия, вмещает 30 человек. Решение очевидно: разрешить аудиторию большего размера или разделить класс.
Результаты проверки сгруппированы. Группа Доказано невозможно содержит проблемы, которые не может обойти ни один решатель. Другие группы содержат вероятные ошибки и то, что усложняет файл. Подробнее читайте в статье Четыре вида результатов проверки.
Два способа использования
Без учётной записи: помощник FET. Перейдите на fetviewer.com/check и выберите свой файл .fet. Это бесплатно, и количество повторных проверок не ограничено. Ваш файл остаётся на вашем компьютере. Ваш браузер отправляет на наш сервер только сводку, и эта сводка не содержит имён: преподаватели, аудитории и группы студентов передаются в виде чисел. Мы ничего не храним. См. Проверка файла без учётной записи.
В вашей учётной записи: Предполётная проверка. Когда вы импортируете своё расписание, страница Предполётная проверка находится рядом с ограничениями на экране данных. В каждом разделе ограничений вверху также отображается однострочная сводка. Измените ограничение и проверьте снова прямо во время работы. См. Что делает предполётная проверка.
Чего она не может вам сказать
Проверка доказывает невозможность в определённых случаях. Она не может доказать, что файл будет решён, и не может сказать, сколько времени займёт работа FET. Успешная проверка устраняет одну из причин неудачи. Поиск по-прежнему остаётся задачей FET.
Поэтому используйте оба инструмента в таком порядке:
- Проверьте файл.
- Исправьте то, что доказывает проверка.
- Затем позвольте FET выполнить поиск.
Полное сравнение читайте в статье Чем проверка отличается от решения с помощью FET.
Перед следующим долгим ожиданием
В следующий раз, когда генерация будет длиться слишком долго, остановите её. Сначала проверьте файл. Если какое-либо ограничение делает расписание невозможным, вы узнаете об этом за секунды и увидите, какое именно.