LINUX.ORG.RU

Система составления учебных расписаний: концепция


0

0

Проблема (всем известная, но никем толком не решенная): автоматизация составления расписаний в уч. заведениях, в т.ч. высших. Это мой диплом, но я независимо от этого факта хочу осчастливить человечество.

Задача сводится к назначению одних объектов (ресурсов - времени, аудиторий) другим (событиям - занятиям, экзаменам) с учетом набора ограничений - жестких (обязательных) и мягких (необязательных, определяющих качество расписания).

Информационная структура может совершенно различаться у разных заведений, поэтому нужен абстрактный подход типа "ресурсы -> события", позволяющий пользователю задавать структуру самому в данных абстрактных терминах.

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

Я пришел к выводу, что для по-настоящему гибкого задания ограничений требуется: 1) полный по Тьюрингу язык, на котором пишутся функции - предикаты ограничений; 2) API, предоставляющее доступ из этих функций к объектам расписания.

В качестве такого языка мне импонирует Lua.

Система должна также уметь работать с неполными и некорректными (нарушающими жесткие ограничения) расписаниями и вносить в расписания динамические изменения в связи с изменением исх. данных и ограничений.

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

Какие у кого мысли насчет концепции системы? Сам думал-думал, много чего надумал, теперь вот решил поинтересоваться.


А зачем делить ограничения на жёсткие и мягкие? Достаточно каждому ограничению присвоить штраф качества расписания.

окно = 10
суббота = 5
первая пара = 20
экзамен раньше последней лекции = 100000

naryl ★★★★★
()

> Есть наука теория удовлетворения ограничений > всем известная, но никем толком не решенная

Не знаю, как насчет науки, но есть тематика комбинаторных задач, как правило, высокой сложности, имеющих и теоретико-множественную семантику, например, так называемые задачи удовлетворения ограничений и обратные им - задачи кластерного анализа. ПО ЗУО наработано довольно много материала. Прежде всего группой Паскаля ван Хентенрика (P. van Hentenryck - можешь погуглить), но не только. Они решали, кстати, и задачи построения оптимальных расписаний для разного рода компаний (например, расписание полетов Люфт Ганза, емнип). Эти же ребята в свое время решили задачу расстановки ферзей для доски, если я не ошибаюсь, 10^5 : 10^5 как задачу удовлетворения ограничений. В общем, говорить, что задача никем толком не решена, не нужно. :) Другое дело, что эффективные решения находились для некоторых частных случаев, для конкретных проблемных областей без обобщений. Но и у тебя это вряд ли получится. :)

А насчет реализации хз. Такие задачи хорошо ложатся в концепцию CLP (Constraint Logic Programming). Можно пытаться делать, например, на Prolog'е. Если реализацию пилить именно в этом направлении, то, видимо, придется создавать (или использовать существующий) язык для описания задач, делать транслятор с него на Prolog и последующее решение прологом. Поскольку последняя часть уже готова, я бы делал именно так. :) Лень рулит. :D

Кстати, когда я доучивался, у нас на факе расписание составлялось уже автоматически посредством соответствующей софтины.

twosev ★★
()

Одно время занимался этой проблемой. Решение строилось с помощью генетических алгоритмов. Вся проблема заключается в том, что учесть все требования очень сложно. Тестовые запуски составляли расписание для 2-3 курсов, но каждый запуск работал по 5 часов. Если универ большой(а таковых хватает), то полностью автоматически построить расписание это уже задача для кандидатской. Легче построить советующую систему, котороая будет лишь помогать строить расписание, но никак не полностью.

lsv
()
Ответ на: комментарий от twosev

> Не знаю, как насчет науки, но есть тематика комбинаторных задач, как правило, высокой сложности, имеющих и теоретико-множественную семантику, например, так называемые задачи удовлетворения ограничений и обратные им - задачи кластерного анализа. ПО ЗУО наработано довольно много материала. Прежде всего группой Паскаля ван Хентенрика (P. van Hentenryck - можешь погуглить), но не только.

Я знаю. Я об этом и говорил.

> В общем, говорить, что задача никем толком не решена, не нужно. :) Другое дело, что эффективные решения находились для некоторых частных случаев, для конкретных проблемных областей без обобщений. Но и у тебя это вряд ли получится. :)

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

Среди существующего ПО попытка сделать что-то более-менее универсальное - Tablix (http://www.tablix.org). Там реализован параллельный распределенный ГА с фитнесс-функцией в виде взвешенной суммы фитнесс-функций, загружаемых из внешних сишных модулей и использующих некоторое API (то, что я подчеркивал). Модель довольно гибкая, но как бы и не очень.

> Такие задачи хорошо ложатся в концепцию CLP (Constraint Logic Programming). Можно пытаться делать, например, на Prolog'е. Если реализацию пилить именно в этом направлении, то, видимо, придется создавать (или использовать существующий) язык для описания задач, делать транслятор с него на Prolog и последующее решение прологом. Поскольку последняя часть уже готова, я бы делал именно так. :) Лень рулит. :D

Ну, CLP - это просто вписывание бэктрекинга для решения CSP в прологовую модель поиска решений. Я, в общем, не боюсь собственноручно реализовывать алгоритмы.

Пока у меня основная задача - продумать во всех аспектах набор абстракций, предоставляемых системой пользователю, в особенности язык описания поблемы.

grusha
() автор топика

>Это мой диплом
В моей группе человек такую систему делал на 3ем курсе как задание на курсовое проектирование :)

anotheranonymous
()

Обсуждалось уже много раз. Все сводится к тому, что есть много факторов, которые учесть сложно, и проще делать руками. А вот тул, который позворлит упростить ркчное раскидываение может быть полезен. Главное не звцикливаться на полной автоматизации.

alexru ★★★★
()

> Я пришел к выводу, что для по-настоящему гибкого задания ограничений требуется: 1) полный по Тьюрингу язык, на котором пишутся функции - предикаты ограничений; 2) API, предоставляющее доступ из этих функций к объектам расписания.

> В качестве такого языка мне импонирует Lua.

Че быдлокодер? GLPK для кого придумали?

tomodachi_ni_narimashou
()
Ответ на: комментарий от tomodachi_ni_narimashou

> > В качестве такого языка мне импонирует Lua.

>Че быдлокодер? GLPK для кого придумали?

А в чем преимущество? Lua, независимо от его популярности, очень нравится мне по целому ряду причин (простота, прозрачность, легкость, гибкость). Вообще, Lua 5.1 - это пример очень хорошей программной архитектуры.

grusha
() автор топика
Ответ на: комментарий от tomodachi_ni_narimashou

> Хотя, по-моему, в этой заджаче тупого жадного алгоритма больше чем достаточно.

Ага, я давно об этом думал. Можно предоставить юзеру 2 варианта решения - переборный, гарантирующий завершение за экспоненциальное время (с возможностью указания таймаутов и др. параметров преждевременного завершения), и жадный, с вытеснениями, не гарантирующий завершения, но быстро находящий частичное решение.

grusha
() автор топика
Ответ на: комментарий от grusha

А не нужно составлять оптимальное расписание, один фиг там столько разных факторов, что ты их никогда не учтёшь, типа, в какой-то аудитории вымыли окна, и теперь в солнечные дни не видно проектора лол. Сначала составить заготовку жадным способом, потом пускай люди сами договариваются, что куда переставить.

tomodachi_ni_narimashou
()
Ответ на: комментарий от tomodachi_ni_narimashou

> А не нужно составлять оптимальное расписание, один фиг там столько разных факторов, что ты их никогда не учтёшь, типа, в какой-то аудитории вымыли окна, и теперь в солнечные дни не видно проектора лол. Сначала составить заготовку жадным способом, потом пускай люди сами договариваются, что куда переставить.

Учту, если у меня будет Тьюринг-полный язык и гибкое API. :) (знаю что это нифига не просто) Участие людей хочется минимизировать. Как-то: система предоставляет набор методов для различных манипуляций с расписанием, в т.ч. автоматической генерации отдельных его кусков, в частном случае - всего расписания.

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

grusha
() автор топика
Ответ на: комментарий от grusha

Я к тому, что нет смысла искать глобальный минимум, потому что он чётко не определён и для каждого студента свой, а расписание одно на всех. Поэтому приближённое решение может быть ничем не хуже "точного".

tomodachi_ni_narimashou
()
Ответ на: комментарий от tomodachi_ni_narimashou

> Я к тому, что нет смысла искать глобальный минимум, потому что он чётко не определён и для каждого студента свой, а расписание одно на всех. Поэтому приближённое решение может быть ничем не хуже "точного".

Ну да. Можно назначить мягким ограничениям веса (приоритеты) и (суб)минимизировать сумму приоритетов неудовлетворенных ограничений.

grusha
() автор топика

Есть fet например.

А на прологе круче :). Если еще и пролог встроенный в Лисп :).

На самом деле важна система публикации расписания. Причём любого, даже не оптимального. И система поставляющая для него данные, через одного оператора нереально просто, данные всегда будут устаревшими и расписание никуда не годным.

Поэтому надо что бы рабочие программы и аудиторный фонд сливался с людскими ресурсами (с ограничениями) автоматом в пакет непротиворечивых актуальных данных.

Потом уже практически все равно: вручную или оптимальным алгоритмом.

psv1967 ★★★★★
()

когда-то, когда я был совсем маленький и учился в школе, я, путен некоторого размышления пришел к выводу, что за это задача np-полна.

Так ли это? думать лень

namezys ★★★★
()
Ответ на: комментарий от namezys

> когда-то, когда я был совсем маленький и учился в школе, я, путен некоторого размышления пришел к выводу, что за это задача np-полна.

> Так ли это? думать лень

Смотря как ее поставить, но скорее всего да, будет NP-полной.

twosev: > нет

Почему?

grusha
() автор топика

Я бы на генетических алгоритмах делал.

Каждое занятие - токен.

Генокод задаёт последовательность токенов.

Критерий отбора - минимизация штрафов за несоответствие основным критериям.

Можно даже многополую систему организовать, м.б. сходимость будет много лучше. Скажем, занятие задаётся сочетанием признаков дня недели и времени, при этом эти два признака задаются разными хромосомами и при скрещивании лучших результатов происходит перемешивание этих признаков.

KRoN73 ★★★★★
()
Ответ на: комментарий от grusha

> почему?

Что-то сплошные "почему".

Я просто ответил в стиле заданного вопроса. Формально задача нахождения оптимального расписания никаким боком не относится не то, что к NP-полным (NP-complete) задачам - она вообще не лежит в классе NP, ибо он образован только задачами распознавания. Повторюсь: это задача оптимизационная, задача поиска. Эту проблему можно было бы попробовать отнести к NP-трудным (NP-hard), но подобного утверждения (и уж тем более его доказательства) мне встречать не доводилось.

twosev ★★
()
Ответ на: комментарий от twosev

> она вообще не лежит в классе NP, ибо он образован только задачами распознавания

Задачи оптимизации сводятся к задачам распознавания бинарным поиском, в предположении, что множество значений целевой функции ограничено (типа до 2^32 или 2^64).

grusha
() автор топика
Ответ на: комментарий от tomodachi_ni_narimashou

>Я к тому, что нет смысла искать глобальный минимум, потому что он чётко не определён и для каждого студента свой, а расписание одно на всех. Поэтому приближённое решение может быть ничем не хуже "точного".

А потом это г--но ставит пары в понедельник в 8:20 и тупые девочки из деканата говорят, что это всё компьютер и они тут совершенно не при чём.

dn2010 ★★★★★
()
Ответ на: комментарий от dn2010

Если что, то это опять Саратовский полутех так отличился, там по слухам такую систему собственной разработки внедрили.

dn2010 ★★★★★
()
Ответ на: комментарий от grusha

> Задачи оптимизации сводятся к задачам распознавания бинарным поиском, в предположении, что множество значений целевой функции ограничено (типа до 2^32 или 2^64).

И?

twosev ★★
()
Ответ на: комментарий от grusha

Про возможную NP-трудность этой задачи я уже сказал. Какие еще вопросы?

twosev ★★
()
Ответ на: комментарий от dn2010

> А потом это г--но ставит пары в понедельник в 8:20 и тупые девочки из деканата говорят, что это всё компьютер и они тут совершенно не при чём.

Я сказал жадный алгоритм, а не вредный, че.

tomodachi_ni_narimashou
()
Ответ на: комментарий от twosev

> > Задачи оптимизации сводятся к задачам распознавания бинарным поиском, в предположении, что множество значений целевой функции ограничено (типа до 2^32 или 2^64).

> И?

Думаю, та длинная фраза является математическим аналогом поговорки "Хоть горшком назови, только в печь не ставь".

dilmah ★★★★★
()
Ответ на: комментарий от twosev

> Посмотрел точную информацию: данная задача на самом деле NP-трудна.

Ага. (Все же - о какой постановке задачи идет речь? Weighted CSP?) А я посмотрел, чем NP-трудные задачи отличаются от NP-полных (по определению): они не обязательно сами лежат в классе NP. В любом случае всюду речь идет о задачах распознавания.

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

grusha
() автор топика
Ответ на: комментарий от grusha

> В любом случае всюду речь идет о задачах распознавания.

Кхм, вовсе нет. Не буду флудить не по теме. Поэтому, если что, можешь для справки стучать в джаббер.

twosev ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.