Алгоритм календарного планировщика

Ответ 1

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

no.:  id: [ start  -   end  ] type
---------------------------------------------------------
 0:  234: [08:00AM - 09:00AM] Breakfast With Mindy
 1:  400: [09:00AM - 07:00PM] Check out stackoverflow.com
 2:  219: [11:40AM - 12:40PM] Go to Gym
 3:   79: [12:00PM - 01:00PM] Lunch With Steve
 4:  189: [12:40PM - 01:20PM] Lunch With Steve
 5:  270: [01:00PM - 05:00PM] Go to Tennis
 6:  300: [06:40PM - 07:20PM] Dinner With Family
 7:  250: [07:20PM - 08:00PM] Check out stackoverflow.com

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

 0 |  1 |  2 |  3 |  4 |  5 |  6 |  7
 1 |  7 |  4 |  5 |  6 |  6 |  7 | -1

С этим списком можно создать направленный ациклический график. Каждая вершина имеет соединение с вершинами, начиная со следующего элемента. Но для вершин, где уже есть вершины, они не имеют края. Я попытаюсь объяснить на примере. Для вершины 0 следующий элемент равен 1. Таким образом, край делается 0 → 1. Следующий элемент из 1 равен 7, это означает, что диапазон для вершин, которые связаны с вершиной 0, теперь находится от 1 to (7-1). Поскольку вершина 2 находится в диапазоне от 1 до 6, выполняется другое ребро 0 → 2, и диапазон изменяется до 1 to (4-1) (поскольку 4 является следующим элементом из 2). Поскольку вершина 3 находится в диапазоне от 1 до 3, производится еще одно ребро 0 → 3. Это было последнее ребро для вершины 0. Это должно быть продолжено со всеми вершинами, ведущими к такому графику:

До сих пор мы находимся в O (n ²). После этого все пути можно найти с помощью глубины первого поиска-подобного алгоритма, а затем устранения дублированных типов с каждого пути. Для этого примера существует 4 решения, но ни один из них не имеет всех типов, потому что это невозможно для примера Go to Gym, Lunch With Steve и Go to Tennis.

Также этот поиск для всех путей имеет худшую сложность O (2 ⁿ). Например, следующий график имеет 2 ^n/2 возможных путей от начальной вершины до конечной вершины.

пример graph2 http://web.archive.org/web/20120103133636/http://img295.imageshack.us/img295/2848/cal.gif

Можно было бы сделать еще некоторую оптимизацию, например, слияние некоторых вершин, прежде чем искать все пути. Но это невозможно. В первом примере вершина 3 и 4 не может быть объединена, хотя они имеют один и тот же тип. Но в последнем примере вершины 4 и 5 могут быть объединены, если они одного типа. Это означает, что не имеет значения, какую деятельность вы выберете, оба действительны. Это может значительно ускорить вычисление всех путей.

Возможно, есть и умный способ рассмотреть повторяющиеся типы раньше, чтобы устранить их, но в худшем случае все еще O (2 ⁿ), если вы хотите все возможные пути.

EDIT1:

Можно определить, существуют ли множества, которые содержат все типы, и получить по меньшей мере одно такое решение в полиномиальное время. Я нашел алгоритм с наихудшим временным временем O (n ⁴) и O (n ²). Я возьму новый пример, который имеет решение со всеми типами, но более сложным.

no.:  id: [ start  -   end  ] type
---------------------------------------------------------
 0:  234: [08:00AM - 09:00AM] A
 1:  400: [10:00AM - 11:00AM] B
 2:  219: [10:20AM - 11:20AM] C
 3:   79: [10:40AM - 11:40AM] D
 4:  189: [11:30AM - 12:30PM] D
 5:  270: [12:00PM - 06:00PM] B
 6:  300: [02:00PM - 03:00PM] E
 7:  250: [02:20PM - 03:20PM] B
 8:  325: [02:40PM - 03:40PM] F
 9:  150: [03:30PM - 04:30PM] F
10:  175: [05:40PM - 06:40PM] E
11:  275: [07:00PM - 08:00PM] G

1.) Подсчитайте разные типы в наборе элементов. Это возможно в O (nlogn). Для этого примера 7.

2.) Создайте n * n-матрицу, которая представляет, какие узлы могут достичь фактического node и которые могут быть достигнуты из фактического node. Например, если для позиции (2,4) установлено значение 1, это означает, что на графике есть путь от node 2 до node 4, а (4,2) тоже установлен на 1, поскольку node 4 может быть достигнуто от node 2. Это возможно в O (n ²). Для примера матрица будет выглядеть так:

111111111111
110011111111
101011111111
100101111111
111010111111
111101000001
111110100111
111110010111
111110001011
111110110111
111110111111
111111111111

3.) Теперь мы имеем в каждой строке, к каким узлам можно дойти. Мы также можем отметить каждую node в строке, которая еще не отмечена, если она имеет тот же тип, что и node. Мы устанавливаем эти позиции матрицы от 0 до 2. Это возможно в O (n ³). В этом примере нет пути от node 1 до node 3, но node 4 имеет тот же тип D, что и node 3, и есть путь от node 1 до node 4. Итак мы получим эту матрицу:

111111111111
110211111111
121211111111
120121111111
111212111111
111121020001
111112122111
111112212111
111112221211
111112112111
111112111111
111111111111

4.) Узлы, которые все еще содержат 0 (в соответствующих строках), не могут быть частью решения, и мы можем удалить их из графика. Если было удалено хотя бы один node, мы начнем снова на шаге 2.) с меньшим графиком. Поскольку мы удалили хотя бы один node, мы должны вернуться к шагу 2.) не более n раз, но чаще всего это произойдет только несколько раз. Если в матрице осталось 0, мы можем продолжить с шага 5.). Это возможно в O (n ²). В качестве примера невозможно построить путь с node 1, который также содержит node с типом C. Поэтому он содержит 0 и удаляется как node 3 и node 5. В следующем цикле с меньшим графом node 6 и node 8 будет удалено.

5.) Подсчитайте разные типы в остаточном наборе элементов/узлов. Если он меньше первого счета, не существует решения, которое может представлять все типы. Поэтому мы должны найти другой способ получить хорошее решение. Если это то же самое, что и первый счет, мы теперь имеем меньший граф, который все еще содержит все возможные решения. O (NlogN)

6.) Чтобы получить одно решение, мы выбираем начало node (неважно, потому что все узлы, оставшиеся на графике, являются частью решения). O (1)

7.) Мы удаляем каждый node, который не может быть достигнут из выбранного node. О (п)

8.) Мы создаем матрицу, как на шаге 2.) и 3.) для этого графика, и удалим узлы, которые не могут достигать узлов любого типа, как на шаге 4.). О (п ³)

9.) Мы выбираем один из следующих узлов из node, который мы выбираем раньше и продолжаем с 7.), пока мы не закончим node, и график имеет только один путь слева.

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

Ответ 2

Хммм, это напоминает мне задачу в университете, я опишу, что я могу запомнить Время выполнения - O (n * logn), что довольно хорошо.

Это жадный подход... я уточню ваш запрос abit, скажите, если я ошибаюсь.. Algorithem должен возвращать MAX-подмножество не сталкивающихся задач (с точки зрения общей длины или количества действий? я guess Общая длина)

Я бы сначала заказал список по времени окончания (первое минимальное время окончания, последний максимум) = O (nlogn)

Find_set(A):
  G<-Empty set;
  S<-A
  f<-0
  while S!='Empty set' do
    i<-index of activity with earliest finish time(**O(1)**)
    if S(i).finish_time>=f
      G.insert(S(i)) \\add this to result set
      f=S(i).finish_time
    S.removeAt(i) \\remove the activity from the original set
  od
  return G

Анализ времени выполнения: начальный порядок: nlogn каждая итерация O (1) * n = O (n)

Total O (nlogn) + O (n) ~ O (nlogn) (ну, учитывая слабость нотации O, чтобы представить реальную сложность на малых числах... но по мере увеличения масштаба это хороший алгоритм)

Enjoy.

Update:

Хорошо, похоже, что я неправильно прочитал сообщение, вы можете использовать динамическое программирование для сокращения времени выполнения, есть решение в текст ссылки стр. 7-19.

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

Ответ 3

Я использовал бы Дерево интервала для этого.

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

Ответ 4

Да, исчерпывающий поиск может быть вариантом:

инициализировать частичные графики с самыми ранними задачами, которые перекрываются (например, 9-9.30 и 9.15-9.45)

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

повторяется с новыми частичными расписаниями

В вашем случае initlialisation будет производить только (8-9 breakfast)

После первой итерации: (8-9 brekkie, 11.40-12.40 gym) (без связей)

После второй итерации: (8-9 brekkie, 11.40-12.40 gym, 12.40-1.20 lunch) (опять нет связей)

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

Ответ 5

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

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

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

• Отбросьте первые n элементов одного типа и поместите их в список.

• Для каждого элемента в списке добавьте этот элемент в список расписаний.

• Отбросьте следующие n элементов одного и того же типа.

• Для каждого элемента, который начинается после завершения первого элемента, набирайте список. (Если нет, сбой)

• Продолжайте, пока не закончите.

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