Алгоритм планирования студенческого времени

Question

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

заранее спасибо

Answer 1

Интересный вопрос.

Вот что я бы сделал:

1. Сначала выровняйте все временные рамки для всех студентов (например, начиная с понедельника, каждый день делится на 24 часа),Вы можете использовать логическое или целое число для каждого периода и сохранять их в массиве.
2. Затем выполнить операцию сложения для всех схем вместе.

, которая затем выглядит следующим образом, дляпример:

Student A: 11100000111111100000
Student B: 00000011111000010001
Student C: 00000000111111110001
_______________________________+
           11100022333222220002
              ^^^          ^^^

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

Answer 2

это проблема соответствия и может быть решена с помощью алгоритма максимального потока

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

см. также Введение в алгоритмы (глава по сетям потоков)

Answer 3

Я бы установил продолжительность встречи и допустимый диапазон времени, когда встреча может состояться, то есть 45 минут, начиная с 8:00 или позже, но не после 9:30. Тогда нужно просто пересечь свободное время члена группы и найти подходящий ему блок. Возможно, вы захотите включить допуски на перекрытие, т. Е. Если 75% группы могут встретиться, то это жизнеспособно.

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

Answer 4

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

Answer 5

Я бы начал с очень простого подхода к этому:

• сортировка всех запланированных временных блоков из всех членов группы в один список, упорядоченный по времени начала блока
• просмотреть список и объединить смежные элементы, если они перекрываются (endTime из n больше времени начала n + 1)

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

Answer 6

Есть 24*60 = 1440 минут в день. Таким образом, вы можете легко перебрать его, так как вам не нужно получать точность с точностью до минуты. Однако я опишу простой DP.

Вы можете создать логический массив, в котором будет храниться информация о том, есть ли в эту минуту класс одного из учеников в группе. У вас также есть второй массив. Этот массив хранит количество открытых пространств в этом блоке и слева. Итак, вы можете пройти через логический массив справа налево, и если в блоке есть класс, вы делаете число 0, в противном случае вы делаете его равным 1 плюс число в предыдущую минуту.

Однако я чувствую, что мое объяснение отсутствует, поэтому вот псевдокод:

blocked = <boolean array>;
numtoleft = <array containing the counts>;
if blocked[0]:
    numtoleft[0] = 0;
else:
    numtoleft[0] = 1;

for i = 1 to 1440-1:
    if blocked[i]:
        numtoleft[i] = 0;
    else:
        numtoleft[i] = numtoleft[i-1];

Тогда вы можете легко найти самый большой открытый слот, найдя максимальное число в массиве 'numtoleft', и вы можете добавить ограничения на время, которое вы смотрите.

EDIT:

Вот алгоритм на python:

def largestslot(blocked, startminute, endminute):
    numtoleft = [0]*1440
    numtoleft[startminute] = 0 if blocked[startminute] else 1
    for i in xrange(startminute+1, endminute+1):
        numtoleft[i] = 0 if blocked[i] else 1
    ansmax = max(numtoleft[startminute:endminute+1)
    ansi = numtoleft.index(ansmax)
    return (ansi-ansmax, ansi)

Answer 7

Насколько я помню, лучшие решения этой проблемы - это решения, генерируемые генетическими алгоритмами

см. Ссылку http://www.codeproject.com/KB/recipes/GaClassSchedule.aspx