Алгоритмы планирования курса: почему не рекомендуется использовать DFS или раскраску графика?

Мне нужно разработать программное обеспечение для составления расписания курсов, которое могло бы эффективно распределять временные интервалы и комнаты. Это рутина, основанная на учебной программе, а не на пост-регистрации. И эффективно означает, что классам назначаются временные интервалы в соответствии с временными предпочтениями персонала, а также необходимо свести к минимуму совпадение классов 1-го и 2-го курсов, чтобы студенты 2-го курса могли повторно пройти курсы, которые они не смогли пройти (а также для пары 3-4 года) .

Сначала я думал, что это будет простая задача, но теперь все кажется другим. Большинство статей, которые я просматривал, используют генетический алгоритм/PSO/Simulated Annealing или алгоритмы такого типа. И я все еще не могу интерпретировать проблему как проблему GA. что меня смущает, так это то, почему почти никто из них не предлагает алгоритм DFS или Graph-coloring?

Может ли кто-нибудь объяснить сценарий, если используется DFS/раскраска графика? Или почему их не предлагают и не пробуют.


algorithm combinatorics mathematical-optimization genetic-algorithm evolutionary-algorithm
person King Julien    schedule 12.11.2012    source источник
comment
В зависимости от деталей ваша проблема, вероятно, NP-Complete. Если это так, то для всех известных точных алгоритмов время экспоненциально увеличивается с размером задачи. Для всего, кроме очень маленьких задач, вам придется использовать какую-то приблизительную эвристику, а не точный алгоритм. Общая раскраска графа заведомо NP-полная.   -  person Patricia Shanahan    schedule 12.11.2012
comment
Чтобы немного расширить, любая часто встречающаяся сложная проблема известна хорошей эвристикой, которая обеспечивает разумное сочетание точности и производительности для этой проблемы. Если бы я не приступал к крупному исследовательскому проекту, я бы выбрал один из обычно рекомендуемых методов.   -  person Patricia Shanahan    schedule 12.11.2012
comment
Проблемы с планированием заданий или составлением расписаний имеют тенденцию быть NP-полными, если вводятся несколько реальных ограничений. С большим упрощением они могут быть в P-времени. Таким образом, поиск в формате DFS является вариантом, но не предпочтительным методом. Просто несколько других методов оптимизации (которые вы нашли) больше подходят для этого класса задач.   -  person Ram Narasimhan    schedule 13.11.2012
comment
Слишком быстрый вызов NP-complete — проклятие разумных обсуждений алгоритмов планирования. Многие реальные проблемы могут быть решены за P, пропорциональное допустимой ошибке. Алгоритмы приближения Вазирани должны быть на книжной полке для тех, кто занимается этим типом работы: amazon.com/Approximation-Algorithms-Vijay-V-Vazirani/dp/   -  person Larry OBrien    schedule 17.11.2012
comment
Если размер проблемы достаточно мал, я бы предложил грубую силу (например, DFS), поскольку это гарантированно найдет оптимальное решение, но как только размер проблемы станет слишком большим, грубая сила займет слишком много времени.   -  person Bernhard Barker    schedule 06.01.2013

Ответы (2)


arrow_upward
2
arrow_downward

Мой опыт решения этой проблемы для сложного факультета показывает, что жесткие ограничения (такие как отсутствие перекрытия курсов, которые посещает одно и то же население, и жесткие ограничения учителей) довольно легко решаются точными методами. Я смоделировал проблему с помощью целочисленного линейного программирования 0-1 и решил ее с помощью инструмента на основе SAT под названием minisat+. Конкурирующие коммерческие инструменты, такие как cplex, также могут решить эту проблему. Таким образом, с современными инструментами нет необходимости аппроксимировать, как было предложено выше, даже если входные данные довольно велики. Теперь оптимизация решения — это отдельная история. Может быть много (взвешенных) целей, и найти решение, сводящее цель к минимуму, действительно очень сложно с вычислительной точки зрения (ни один инструмент, который я пробовал, не может решить его за 24 часа), но они достигают почти оптимального значения за несколько часов (я знаю это близко к оптимальному, потому что я могу вычислить теоретическую оценку решения).

person Ofer strichman    schedule 06.07.2013
comment
Это зависит от размера проблемы, но именно так я бы начал. Нет причин писать алгоритм, если вы можете сначала ударить по нему молотком MIP и посмотреть, достаточно ли он хорош. Написание модели также имеет очень полезное дополнительное преимущество, поскольку заставляет вас задуматься о проблеме и убедиться, что у вас есть правильные ограничения и цели. - person user327301; 07.07.2013

arrow_upward
0
arrow_downward

В этом документе описывается применение подхода ГА к составлению расписаний университетов, поэтому он должен быть непосредственно применим к вашим требованиям: Использование ГА для решения расписания в университете

person Jool    schedule 06.12.2012
comment
Я обновил ссылку - не уверен, что произошло, но я, должно быть, неправильно извлек URL-адрес. Извини. - person Jool; 10.12.2012