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

Question

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

S = [("8:00AM", "9:00AM", "Breakfast With Mindy", 234),
     ("11:40AM", "12:40PM", "Go to Gym", 219),
     ("12:00PM", "1:00PM", "Lunch With Steve", 079),
     ("12:40PM", "1:20PM", "Lunch With Steve", 189)]

Algorithm(S) => [[("8:00AM", "9:00AM", "Breakfast With Mindy", 234),
                  ("11:40AM", "12:40PM", "Go to Gym", 219),
                  ("12:40PM", "1:20PM", "Lunch With Steve", 189)]]

Спасибо!

Answer 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

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

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

С этим списком можно сгенерировать направленный ациклический граф 1010 *.Каждая вершина имеет связь с вершинами, начиная со следующего элемента.Но для вершин, где уже есть вершины, между ними нет ребер.Я постараюсь объяснить на примере.Для вершины 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-матрицу, которая представляет, какие узлы могут достигать фактического узла, а какие - с фактического узла.Например, если для позиции (2,4) задано значение 1, это означает, что в графе есть путь от узла 2 к узлу 4, а для (4,2) также задано значение 1, поскольку узел 4 может быть доступен с узла 2.. Это возможно в O (n ² ).Для примера матрица будет выглядеть так:

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

Сначала я бы упорядочил список по времени окончания (первое минимальное время окончания, последнее-максимальное) = 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)

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

Наслаждайтесь.

Обновление:

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

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

Answer 3

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

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

Answer 4

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

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

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

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

В вашем случае инициализация выдаст только (8-9 breakfast)

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

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

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

Answer 5

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

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

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

1. Вытащите первые n элементов того же типа и поместите их в список.

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

3. Вывести из списка n следующих предметов того же типа.

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

5. Продолжить до завершения.

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