Я полагаю, что то, что вы описываете, является версией проблемы удовлетворения ограничений, которая часто используется для решения проблем распределения ресурсов. Весьма вероятно, что решение будет 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. Но с учетом ограничений фактическое возможное количество типов групп будет меньше. Как оказалось, я думаю, что мы можем безопасно сократить типы групп до четырех, каждый из которых состоит из некоторой комбинации студентов типов:

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

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

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

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

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

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

Ограничения планирования

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

Давайте снова начнем с более простого примера, который мы действительно можем представить в наших головах. Давайте предположим, что есть только четыре курса: Искусство, Музыка, математика и естественные науки, которые будут преподаваться в 2 временных интервалах в 4 классах. У нас будет 8 групп по 2 студента, отмечая, что каждый студент будет в 2 группах, так как каждый студент посещает два из доступных классов. Для простота, давайте предположим, что все учащиеся относятся к одной категории, например, 9N, поэтому их можно без проблем переключать между группами. Учащиеся представлены буквами A-H, а группа представлена двумя буквами, например, группа 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     H     B
Time_3                G     A

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

Быть Разумным В Этом

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

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

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

         Class_1 Class_2
Time_1     AB      CD
Time_2     CD      AB

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

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

Принимая это во внимание, мы могли бы изменить наш приведенный выше алгоритм на следующий:

1. Для каждого студент в ограничительной категории (т.е. тупой/умный)
2. Просмотрите всех других учащихся в этой категории и создайте группы из всех, кто выбрал один и тот же набор классов
3. Если осталась группа с
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, i.e. 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, i.e. 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

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

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