|
Составление расписания
|
|||
---|---|---|---|
#18+
Здравствуйте! Есть такая задачка. Нужно составить расписание для небольшого обучающего клуба. Структура входных условных данныхЕсть n предметов: Предмет_1. 2 раза в неделю (только в будни),через день, по 1 часу Предмет_2. 2 раза в неделю (только в будни), через 2 дня, по 1 часу Предмет_3. 3 раза в неделю (в будни + сб.) ... Предмет_n Есть m залов: Зал_1. Площадь s1 кв. м. Вместимость 30 чел. Зал_2. Площадь s2 кв. м. Вместимость 40 чел Зал_3. Площадь s3 кв. м. Вместимость 20 чел. Присутствует кондионер, равномерно по залу распределяет температуру. ... Зал_m Есть k потребителей: Поребитель_1. Собирается ходить на Предмет_1 (раньше не ходил). Удобно в пн, ср. с 19:00 - 21:00 Поребитель_2. Собирается ходить на Предмет_1 (раньше ходил) и на Предмет_2 (раньше не ходил). Удобно в пн, ср. Поребитель_3. Собирается ходить на Предмет_1 (раньше ходил) и на Предмет_2 (раньше не ходил). На Предмет_1 удобно в пн, ср., а на Предмет2 в вт. и чт. Поребитель_4. Собирается ходить на Предмет_2 (раньше ходил). Удобно в пн, ср. Поребитель_5. Собирается ходить на Предмет_3 (раньше ходил). Удобно в пн, ср. Но в пн. намного удобнее, чем в ср. Поребитель_6. Собирается ходить на Предмет_2 (раньше не ходил). Удобно в в сб и вс. Поребитель_7. Собирается ходить на Предмет_1 (раньше ходил) или на Предмет_2 (раньше не ходил). Удобно в будни. ... Потребитель_k Есть l преподователей: Преподаватель_1. Может вести Предмет_1 и Предмет_2 Преподаватель_2. Может вести Предмет_1, так как опыт большой. И может вести Предмет_3, имеет небольшой пыт. Преподаватель_3. Может вести Предмет_2. Только в сб. ... Преподаватель_l - Смогу; - Скорей всего смогу придти; - И да, и нет (нейтрально, когда как) - Скорее не смогу - Не смогу - Затрудняюсь ответить Шкалу можно растянуть. Вот категория "Затрудняюсь ответить" сложно будет обрабатывать, учитывая что могут быть еще и missing values. Скажите, 1. Правильно понимаю, что это задача решается с помощью нейронных сетей? 2. Для такой задачи какая должна быть структура данных? Что надо еще учесть? Нужна ли шкала Лайкерта? 3. Скиньте, пожалуйста, литературу, где подробно описываются алгоритмы для решения данной задачи. Или ссылки на статьи. 4. Есть ли готовые программы, библиотеки решающие такую задачу? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.09.2019, 14:44 |
|
Составление расписания
|
|||
---|---|---|---|
#18+
ferzmikk, к постановке вопроса. Вообще-то фраза вот такая "удовлетворять пожелания многим клиентам" - требует формализации, коль скоро речь идёт об "оптимальности". Удовлетворять можно по-разному: полностью, частично, .... вааще не - это по линейной шкале. Вообще в жизни всегда есть место зависти, в т.ч. и среди преподов. В условиях этого не предусмотрено, а значит в реале обшая неудовлетворённость может сильно измениться после решения, и зачем тогда мучиться и считать? "многим клиентам" - насколько многим? а остальным? что лучше, 10 счастливых + 10 озлобившихся или 20 одинаково НЕДОудовлетворённых?.. По общей задаче "расписаний", ну нету хорошего решения. Это как есть транспортная задача, и есть задачИ трансп-го типа, и есть на них похожие. Конкретных рекомендаций не даю, т.к. расписаниями не занимался. Однако, что вы все так тянетесь к нервосеткам? чтобы не прогать самому? Конкретно сетки (если в них специально не предусмотрено иного) решают задачу ЛОКАЛЬНОЙ оптимизации. Так что имхо многие методы лок-ной опт-ции способны решать те же задачи. Кроме того, т.н. "шкалу лайкерта" напоминает нечёткую логику, а значит и методы нечёткой логики годятся. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.09.2019, 17:19 |
|
Составление расписания
|
|||
---|---|---|---|
#18+
ferzmikk, По моему задача расписания подходит для решения симплекс методом. Правда ХЗ почему этого так не делают. В универе мы семестр подобного рода задачи решали, нахождение оптимальных решений. Правда очень давно это было. Посмотри в эту сторону, может поможет. Правда теория не сказать что из простых. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.09.2019, 21:19 |
|
Составление расписания
|
|||
---|---|---|---|
#18+
vas0По моему задача расписания подходит для решения симплекс методом. Правда ХЗ почему этого так не делают. Потому что симплекс-метод работает только с плоской целевой функцией и линейными ограничениями. В таких условиях решение всегда лежит в углу, то бишь на пересечении целевой функции и одного-двух ограничений. У расписания целевая функция дискретна, как и ограничения. Так что нормально там способен работать разве что полный перебор. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.09.2019, 13:42 |
|
Составление расписания
|
|||
---|---|---|---|
#18+
exp98к постановке вопроса. Вообще-то фраза вот такая "удовлетворять пожелания многим клиентам" - требует формализации, коль скоро речь идёт об "оптимальности".Имеется ввиду составить такое расписание, чтобы как можно по возможности посещали наибольшее количество клиентов учитывая их пожелания (например, по времени)Удовлетворять можно по-разному: полностью, частично, .... вааще не - это по линейной шкале. Вообще в жизни всегда есть место зависти, в т.ч. и среди преподов. В условиях этого не предусмотрено, а значит в реале обшая неудовлетворённость может сильно измениться после решения, и зачем тогда мучиться и считать? "многим клиентам" - насколько многим? а остальным? что лучше, 10 счастливых + 10 озлобившихся или 20 одинаково НЕДОудовлетворённых?..Какой то малый процент недовольных составленному расписанию останется. Поэтому надо стремится, чтобы расписание составлялось так, чтобы количество клиентов, которые не попадают составленному расписанию, стремилось к нулю. По общей задаче "расписаний", ну нету хорошего решения. Это как есть транспортная задача, и есть задачИ трансп-го типа, и есть на них похожие.Получается, вариант 1 - это использовать транспортную задачу. Транспортная задача учитывает всю заданную структуру данных? Конкретных рекомендаций не даю, т.к. расписаниями не занимался. Однако, что вы все так тянетесь к нервосеткам?Сейчас нейронные сети решают многие задачи.чтобы не прогать самому?Если используешь нейронные сети, то пишешь не мало кода, кроме случаев, когда используешь готовые библиотеки. Конкретно сетки (если в них специально не предусмотрено иного) решают задачу ЛОКАЛЬНОЙ оптимизации. Так что имхо многие методы лок-ной опт-ции способны решать те же задачи. Кроме того, т.н. "шкалу лайкерта" напоминает нечёткую логику, а значит и методы нечёткой логики годятся. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.09.2019, 16:56 |
|
Составление расписания
|
|||
---|---|---|---|
#18+
Тут скорее не нейронками, а MCTS или отжигом/генетическим алгоритмом проще решать. Или взять питоний scipy.optimize (или питоний же hyperopt), определить пространство решений, функцию оценки на нем и перебрать готовые алгоритмы. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.09.2019, 18:54 |
|
Составление расписания
|
|||
---|---|---|---|
#18+
wstMCTSЭто Метод Монте-Карло? ... |
|||
:
Нравится:
Не нравится:
|
|||
19.09.2019, 19:24 |
|
Составление расписания
|
|||
---|---|---|---|
#18+
ferzmikkwstMCTSЭто Метод Монте-Карло?Он самый. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.09.2019, 19:37 |
|
Составление расписания
|
|||
---|---|---|---|
#18+
wstОн самый. Подходит для приближенных вычислений, но не для составления расписания. Прочие методы случайного поиска (или как нынче модно их называть "генетические алгоритмы") требуют гладкую целевую функцию, с дискретными - облом. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.09.2019, 13:41 |
|
Составление расписания
|
|||
---|---|---|---|
#18+
ferzmikk, составь сперва ф-цию, к-рую оптимизировать, потом ограничения. Коль скоро выбран путь задачи оптимизации, она может оказаться решаемой теоретически, хотя бы и очень кропотливо. Однажды давно у меня именно так и вышло. Вопрос устойчивости обычно никого не волнует (из разработчиков). Однако не стоит надеяться, что немножко пошевелив входные данные или условия, получите похожий ответ. Тем более в дискретном случае. В реале это приведёт к ненужности расписания, поскольку (напрмер уволился препод) потом будут перекраивать по типу пасьянса - и это далеко от теоретической оптимальности, в итоге всё сведётся к методу проб и ошибок и последующих аналогий. Иначе бы в МГУ давно расписания считали бы на компах. Впочем, для тренировки - в добрый путь. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.09.2019, 18:54 |
|
|
start [/forum/topic.php?fid=16&fpage=9&tid=1339905]: |
0ms |
get settings: |
9ms |
get forum list: |
13ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
52ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
54ms |
get tp. blocked users: |
2ms |
others: | 231ms |
total: | 385ms |
0 / 0 |