Ответ 1

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

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

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

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

Скажем, что есть 2 комнаты и 3 часа: 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 - это совпадение курса): Столовая:

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% -ное решение, поэтому она нуждается в работе, прежде чем вы сможете ее использовать.....

Ответ 2

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

Две проблемы

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

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

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

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

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

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

rooms * hours * students/room / hours/student

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

100 * 5 * 8 / 5 = 800 students

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

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

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

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

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

• Уровень умения: тупой, нормальный, умный (D, N, C)
• Уровень оценки: 9, 10, 11, 12

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

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

• 9D, 9N, 10D, 10N
• 9N, 9C, 10N, 10C
• 11D, 11N, 12D, 12N
• 11N, 11C, 12N, 12C

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

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

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

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

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

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

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

Давайте снова начнем с более простого примера, который мы можем представить себе в наших головах. Предположим, что есть только четыре курса: искусство, музыка, математика и наука, которые будут преподаваться в 2 временных слотах в 4 классах. У нас будет 8 групп из 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

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

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

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

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

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

         Class_1 Class_2
Time_1     AB      CD
Time_2     CD      AB

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

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

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

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

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

Что дальше?

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

• Повторите описанную выше стратегию, но группируйте учащихся с 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

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

Ответ 3

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

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

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

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