Этот ответ просто предназначен как направление решения для части расписания, а не 100% -ное решение:

То, что вы создали, требует, чтобы циклы были в состоянии удовлетворить все условия.

Чтобы этот случай был решен быстрее, может оказаться целесообразным работать в векторах, в которых в векторе все позиции представлены 0 (доступно) и 1 (взято).

Таким образом, проблема ученика / математики-1:

Скажем, есть 2 комнаты и 3 часа: Math-1 вектор на номер тогда:

 Room 1: [0 0 0] Room 2: [0 0 0] 

По существу (я, по крайней мере) не заботятся о том, доступна ли определенная комната, если доступна 1: поэтому И для каждого индекса может быть ответом в этом случае на наличие (помните: 0 доступно):

Номер 1: [1 0 0] Комната 2: [0 0 0] Результат комнаты: [1 0 0] И [0 0 0] = [0 0 0]

Таким образом, И может определить, доступен ли первый час.

Если теперь вы комбинируете это со студентом с доступными часами (также для этого примера всего 3):

Студент A: [0 0 1] Результат комнаты: [0 0 0] Студенческие совпадения с комнатой с использованием OR для этой операции: [0 0 1] ИЛИ [0 0 0] = [0 0 1]

Таким образом, ученик A будет соответствовать результату комнаты.

В SQL: модель данных (часть: Missing – это совпадение курса): Table room:

 CREATE TABLE room( room_id INT, space TINYINT DEFAULT 0, hour INT DEFAULT 1 ); CREATE TABLE student( student_id INT, space TINYINT DEFAULT 0, hour INT DEFAULT 1 ) 

Все данные были полностью вставлены в таблицы: в этом случае доступно 1 комната, 3 часа и 3 места.

 INSERT INTO room VALUES (1,0,1); INSERT INTO room VALUES (1,0,1); INSERT INTO room VALUES (1,0,1); INSERT INTO room VALUES (1,0,2); INSERT INTO room VALUES (1,0,2); INSERT INTO room VALUES (1,0,2); INSERT INTO room VALUES (1,0,3); INSERT INTO room VALUES (1,0,3); INSERT INTO room VALUES (1,0,3); 

Студент имеет:

 INSERT INTO student VALUES(1,0,1); INSERT INTO student VALUES(1,0,2); INSERT INTO student VALUES(1,1,3); 

Таким образом, студент доступен только в первые два часа.

Чтобы получить результат из запроса:

 SELECT room_id FROM room a INNER JOIN student b ON a.space=b.space AND a.hour=b.hour; 

Этот результат нужно разделить на группы максимум 8, в которых это конец части SQL и время для другого языка программирования.

Эта модель может быть расширена с датой, однако она лучше всего работает при использовании только часов и рабочих дней (доступ в будние дни снова 0 или 1).

Как я уже сказал, это концепция / идея, а не 100% -ное решение, поэтому она нуждается в работе, прежде чем вы сможете ее использовать …..

Я считаю, что то, что вы описываете, является версией проблемы ограничения ограничений , которая часто используется для решения проблем с распределением ресурсов. Весьма вероятно, что решение будет NP-полным , или, другими словами, время, необходимое для решения проблемы, будет расти экспоненциально, поскольку размер проблемы (в этом случае число студентов / классов / комнат) растет , Это одна из классических выдающихся проблем в информатике. Неизвестного идеального решения нет, но это не означает, что в вашей ситуации не будет ничего полезного. Я попытаюсь описать вашу проблему немного более подробно, прежде чем предлагать путь к решению.

Две проблемы

У вас есть как минимум две проблемы, которые вы пытаетесь решить:

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

Во-первых, очень вероятно, что нет возможных комбинаций , которые удовлетворяли бы вашим ограничениям. Чтобы продемонстрировать это, представьте, что у вас есть только два ученика и только один класс, который доступен всего на один час. Если два ученика могут быть помещены в одну группу, тогда их можно планировать одновременно в одном классе. Однако, если два студента не могут быть сгруппированы, например, один «немой», а один «умный», то нет никакой комбинации ресурсов, которые удовлетворят ваши ограничения.

Хотя легко определить, существует ли решение в очень простом случае, как я описал, очень сложно определить, существует ли решение даже для произвольно большого набора учеников / классов / комнат.

Установка разумных пределов

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

rooms * hours * students/room / hours/student

Например, если у вас есть 100 номеров в течение 5 часов каждый, в каждом номере могут разместиться 8 студентов, и каждый студент должен учиться в течение 5 часов:

100 * 5 * 8 / 5 = 800 students

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

Если мы исходим из другого конца спектра, предположим, что у вас есть 500 часов в классе (100 номеров * 5 часов), то вы знаете, что вы всегда можете разместить не менее 100 студентов (1 студент за номер * 5 часов). Хитрость заключается в том, чтобы выяснить разумную верхнюю границу от 100 до 800, что делает эту проблему разрешимой в разумные сроки.

Чтобы сделать разумное предположение о том, какова должна быть эта верхняя граница, представляется разумным рассмотреть ограничения на формирование группы.

Группировка ограничений

Студенты классифицируются в двух измерениях:

1. Уровень Способности: Тупой, Нормальный, Умный (D, N, C)
2. Уровень оценки: 9, 10, 11, 12

Это означает, что у вас есть 12 категорий студентов: 9D, 9N, 9C, 10D, 10N, 10C, …

Только некоторые из этих категорий совместимы друг с другом для группировки, что дает вам конечное число потенциальных типов групп. Предполагая, что у вас было только 12 учеников, по 1 из 12 типов, теоретическое максимальное количество типов групп (при условии, что любой тип ученика может быть сопряжен с любым другим типом), будет 12!/4! = 19,958,400 12!/4! = 19,958,400 . Но с учетом ограничений фактическое возможное количество типов групп будет меньше. Как оказалось, я думаю, что мы сможем безопасно уменьшить типы групп до четырех, каждый из которых состоит из некоторой комбинации студентов типов:

1. 9D, 9N, 10D, 10N
2. 9N, 9C, 10N, 10C
3. 11D, 11N, 12D, 12N
4. 11N, 11C, 12N, 12C

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

Начните с назначения студентов в наиболее ограничительных категориях для групп в первую очередь. Затем добавьте учащихся в менее ограничительные группы.

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

1. Для каждого курса
2. Выберите всех умных / немых студентов в классах 9/10 или 11/12
3. Создайте столько групп из 8, сколько сможете со студентами этой категории
4. Заполните оставшиеся группы пустыми слотами с «нормальными» учениками
5. Группируйте оставшихся «нормальных» учеников в группы по 8

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

Планирование ограничений

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

Давайте снова начнем с более простого примера, который мы можем себе представить в наших головах. Предположим, что есть только четыре курса: искусство, музыка, математика и наука, которые будут преподаваться в 2 временных слотах в 4 классах. У нас будет 8 групп из 2 студентов, отметив, что каждый студент будет в двух группах, поскольку каждый студент принимает два доступных класса. Для простоты предположим, что все учащиеся находятся в одной категории, например 9N, поэтому их можно поменять местами между группами без проблем. Студенты, представленные буквами AH и группой, представлены двумя буквами, например, группа AB содержит учеников A и B. Предположим, что первое расписание, сгенерированное системой, выглядит следующим образом:

  Art Music Math Science Time_1 AB CD EF AH Time_2 CD EF GH GB 

Каждый курс преподается дважды, и мы видим, что все группы состоят из действительного набора студентов, но мы видим, что студенты A и G оба забронированы: A имеет два класса в Time_1, а G имеет два класса в Time_2 , Проще всего сделать, чтобы поменять местами A и G в свое научное время:

  Art Music Math Science Time_1 AB CD EF GH Time_2 CD EF GH AB 

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

  Art Music Math Science Time_1 AC ED GF BH Time_2 BD FC HE AG 

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

Конечно, другим решением было бы просто добавить больше временных интервалов, например:

  Art Music Math Science Time_1 AB CD EF GH Time_2 CD EF HB Time_3 GA 

Вычислительно, это проще и быстрее, но, очевидно, не оптимизирует пространство в классе и время преподавателя, и, конечно, это было бы невозможно, если бы все возможные временные интервалы уже имели классы в них.

Быть разумным об этом

Давайте отступим на секунду и подумаем о том, что мы знаем о всей системе. Вот некоторые вещи, которые мы знаем:

1. Аналогичные ученики, вероятно, будут выбирать аналогичные наборы классов
2. Если у вас есть набор групп студентов, которые все принимают один и тот же набор классов, их просто запланировать

Например, если у нас есть 4 ученика (2 группы из 2), которые все хотят взять один и тот же набор классов, легко просто поместить группы в матрицу:

  Class_1 Class_2 Time_1 AB CD Time_2 CD AB 

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

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

Учитывая это, мы можем изменить наш алгоритм выше на следующее:

1. Для каждого ученика в ограничительной категории (т. Е. Немой / умной)
2. Прокрутите все остальные ученики этой категории и создайте группы из всех тех, кто выбрал один и тот же набор классов
3. Если есть группа, оставшаяся с <8 учениками, заполните эту тему студентами в группе без ограничений (нормальный), которые выбрали тот же набор классов
4. Когда ученики добавляются в группы, удалите их из общего пула
5. Повторите это для всех учащихся в ограничительных категориях
6. Запланируйте всех этих учеников методом сетки
7. Повторите это для оставшихся учеников в нормальной категории

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

Что дальше?

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

• Повторите вышеуказанную стратегию, но группируйте студентов с 4 из 5 классов
• Создайте список курсов, которые необходимо создать на основе запрошенных курсов в оставшемся пуле, затем пройдите через каждый из этих курсов и добавьте столько студентов, сколько сможете, каждый раз, начиная со студентов в более ограничительных категориях и заполняя нормальные студенты
• Если число достаточно мало, просто вручную создайте все оставшиеся курсы

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

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

Примеры кода

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

 // function to determine whether two students have selected the same classes function studentsSelectedSameClasses($s1, $s2) { // returns true if students selected the same set of classes // returns false other wise // this takes into account knowledge_level and will consider // a class the same if the knowledge_levels are compatible } // create arrays of unscheduled students, ie not yet in groups, by grade // 9th/10th and 11th/12th together since they can be in the same classes $unscheduled["9_10"] = Student::find()->whereIn('class', [9,10])->all(); $unscheduled["11_G"] = Student::find()->whereIn('class', [11,G])->all(); // copy this array into another array from which we'll remove // students as they get put into groups $pool = $unscheduled; // loop through unscheduled; try to match on course selections foreach($unscheduled as $grade => $students) { foreach($students as $i => $student) { // make sure they are still in the pool, ie not already in a group if(!in_array($student, $pool[$grade]) continue; // now loop through other students foreach($pool[$grade] as $j => $potential_classmate) { if(studentsSelectedSameClasses($student,$potential_classmate)){ // create new groups for each class if necessary // add both students to the groups if necessary // remove them from the $pool // if the group size reaches 8 go on to the next unscheduled } } } } // At this point $pool may not be empty, but you should have a bunch of // easily scheduled groups and a much smaller pool to resolve 

Спасибо за интересную проблему. Мне понравилось думать об этом и надеяться, что это поможет!

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

Я могу следовать предложенному отсутствию сужения, и это заставило меня думать о линейных задачах / программировании, которым также нужны точные ограничения для расчета оптимального. Но также, что мы можем сократить матричный расчет пополам, сначала разделив его на 2, а затем ищем результат в нижней или верхней половине, поскольку он не может быть в обоих. Но нет ничего, что можно было бы перерезать наполовину, поэтому я подумал, что более разумно предположить, что здесь должна быть реальная жизнь, которая делает что-то вроде этого, или это не сработает или не добавит быстро, – это мой термин для этого: D

Поэтому я теперь предлагаю, чтобы в этом подходе была логика: курсы линейны, начиная с интро-курса и заканчивая экзаменом. Таким образом, ни один студент, который прошел курс интро, не может принять его снова, поскольку это просто глупо (Einstein et al.). Поэтому каждый студент, который посещал математику 1, может быть исключен для этого курса. Поэтому, если мы сделаем постепенный подход с математикой с 1 по 5 и правило, что все курсы должны быть посещены, где уровень курса может не отличаться более чем от уровня ученика, равный курсам, проводимым линейным образом для данного учащегося, тогда все учащиеся, которые посетили курс 1, могут быть исключены для этого класса. Итак, для математики 2 могут присутствовать только студенты с уровнями или посещаемые курсы, 0 и 1. Для математики могут присутствовать 3 ученика уровня 1 или 2. Поэтому, если мы начнем создавать самые большие группы студентов, которые могут посещать любой курс и начать с того, что сделают сокращение умным и глупым сразу, чтобы сэкономить время, анализируя бессмысленные варианты, поскольку студент 4 уровня никогда не может посещать тот же математический класс, что и уровень 0 , 1 студент?

Или что-то типа того. Я работаю над этим графиком для этого, но он больше похож на гараж моих соседей в этот момент, поэтому я не ожидал многого, думаю.