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

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

Это то, что я сделаю:

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

Что затем выглядит так, например, например:

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

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

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

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

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

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

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

, смотрите эту ссылку http://www.codeproject.com/KB/recipes/GaClassSchedule.aspx

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

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

Таким образом, java.lang. Последовательность расширяет java.lang.Object , поэтому любой Последовательность также является объектом . В данном примере объявляется, что выражение s должно рассматриваться как Объект , а не как Последовательности . Поскольку нет ограничений, препятствующих этому, и требуемый тип является одним из типов s является , он работает.

Почему вы этого хотите? Примите во внимание следующее:

scala> val s = "Dave"
s: java.lang.String = Dave

scala> val p = s: Object
p: java.lang.Object = Dave

scala> val ss = scala.collection.mutable.Set(s)
ss: scala.collection.mutable.Set[java.lang.String] = Set(Dave)

scala> val ps = scala.collection.mutable.Set(p)
ps: scala.collection.mutable.Set[java.lang.Object] = Set(Dave)

scala> ss += Nil
<console>:7: error: type mismatch;
 found   : scala.collection.immutable.Nil.type (with underlying type object Nil)
 required: java.lang.String
       ss += Nil
             ^

scala> ps += Nil
res3: ps.type = Set(List(), Dave)

Это можно было бы также исправить, введя s в объявлении ss , или объявить тип ss как Наборы [AnyRef] .

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

def prefixesOf(s: String) = s.foldLeft(Nil) { 
  case (head :: tail, char) => (head + char) :: head :: tail
  case (lst, char) => char.toString :: lst
}

Но это так:

def prefixesOf(s: String) = s.foldLeft(Nil: List[String]) { 
  case (head :: tail, char) => (head + char) :: head :: tail
  case (lst, char) => char.toString :: lst
}

Было бы глупо использовать здесь идентификатор вместо Nil . И хотя вместо этого я могу написать List [String] () , это не всегда вариант. Рассмотрим, например, следующее:

def firstVowel(s: String) = s.foldLeft(None: Option[Char]) { 
  case (None, char) => if ("aeiou" contains char.toLower) Some(char) else None
  case (vowel, _) => vowel
}

Для справки, это то, что Scala 2,7 spec (march 15, 2009 draft) говорит о описании типа:

Expr1 ::= ...
        | PostfixExpr Ascription

Ascription ::= ‘:’ InfixType
             | ‘:’ Annotation {Annotation}
             | ‘:’ ‘_’ ‘*’

Есть 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)

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

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

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

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

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

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

Вы можете создать булевый массив, в котором будет храниться информация о том, есть ли в этой минуте класс одного из учеников в группе. У вас также есть второй массив. Этот массив хранит количество открытых пробелов в этом блоке и слева. Таким образом, вы можете обойти булевый массив справа налево, и если в блоке есть класс, то вы делаете число 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];

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

EDIT:

Вот алгоритм в питоне:

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)