календарный алгоритм планировщика
Я ищу алгоритм, которые, учитывая ряд объектов, содержащих время начала, время окончания, вводят, и идентификатор, он возвратит ряд всех наборов объектов, которые совмещаются (никакие перекрывающиеся времена, и все типы представлены в наборе).
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)]]
Спасибо!
5 ответов
Это можно решить, используя теорию графов . Я бы создал массив, содержащий элементы, отсортированные по времени начала и окончания для равного времени начала: (добавил еще несколько элементов в пример):
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
С помощью этого списка можно сгенерировать ориентированный ациклический граф . Каждая вершина соединяется с вершинами, начиная со следующего элемента. Но для вершин, между которыми уже есть вершина, ребро не делается. Попробую пояснить на примере. Для вершины 0 следующий элемент равен 1. Таким образом, создается ребро 0 -> 1. Следующим элементом из 1 является 7, это означает, что диапазон для вершин, которые соединяются из вершины 0, теперь составляет от 1 до ( 7-1) . Поскольку вершина 2 находится в диапазоне от 1 до 6, создается еще одно ребро 0 -> 2, и диапазон обновляется с 1 до (4-1) (поскольку 4 является следующим элементом 2). Поскольку вершина 3 находится в диапазоне от 1 до 3, создается еще одно ребро 0 -> 3. Это было последнее ребро для вершины 0. Это должно быть продолжено со всеми вершинами, ведущими к такому графу:
До сих пор мы находимся в O (n 2 ). После этого все пути могут быть найдены с использованием алгоритма, подобного поиску в глубину , с последующим удалением повторяющихся типов из каждого пути.
Для этого примера есть 4 решения, но ни одно из них не имеет всех типов, потому что в примере невозможно выполнить Перейти в спортзал , Обед со Стивом и Перейти к Теннис .
Также этот поиск для всех путей имеет сложность наихудшего случая O (2 n ). Например, следующий граф имеет 2 n / 2 возможных путей от начальной вершины до конечной вершины.
(источник: archive.org )
Можно было бы провести дополнительную оптимизацию, например, объединить некоторые вершины перед поиском всех путей. Но это невозможно. В первом примере вершины 3 и 4 нельзя объединить, даже если они одного типа. Но в последнем примере вершины 4 и 5 могут быть объединены, если они одного типа. Это означает, что неважно, какое действие вы выберете, оба действительны. Это может значительно ускорить расчет всех путей.
Может быть, есть еще один умный способ учесть повторяющиеся типы раньше, чтобы устранить их, но в худшем случае все равно остается O (2 n ), если вам нужны все возможные пути.
РЕДАКТИРОВАТЬ1:
Можно определить, существуют ли наборы, содержащие все типы, и получить хотя бы одно такое решение за полиномиальное время. Я нашел алгоритм с временем наихудшего случая O (n 4 ) и O (n 2 ) пространства. Я возьму новый пример, в котором есть решения со всеми типами, но он более сложный.
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-матрицу, которая представляет, какие узлы могут достигать фактического узла, а какие могут быть достигнуты из фактического узла. Например, если позиция (2,4) установлена в 1, это означает, что существует путь от узла 2 к узлу 4 в графе, и (4,2) также установлен в 1, потому что узел 4 может быть достигнут из узла 2. .Это возможно за O (n 2 ). Для примера матрица будет выглядеть так:
111111111111
110011111111
101011111111
100101111111
111010111111
111101000001
111110100111
111110010111
111110001011
111110110111
111110111111
111111111111
3.) Теперь у нас есть в каждой строке, какие узлы могут быть достигнуты. Мы также можем пометить каждый узел в строке, который еще не отмечен, если он того же типа, что и узел, к которому можно добраться. Мы устанавливаем эти позиции матрицы от 0 до 2. Это возможно за O (n 3 ). В примере нет пути от узла 1 к узлу 3, но узел 4 имеет тот же тип D, что и узел 3, и есть путь от узла 1 к узлу 4. Итак, мы получаем эту матрицу:
111111111111
110211111111
121211111111
120121111111
111212111111
111121020001
111112122111
111112212111
111112221211
111112112111
111112111111
111111111111
4.) узлы, которые все еще содержат 0 (в соответствующих строках), не могут быть частью решения, и мы можем удалить их из графа. Если нужно было удалить хотя бы один узел, мы снова начнем с шага 2.) с меньшим графом. Поскольку мы удалили по крайней мере один узел, мы должны вернуться к шагу 2.) не более n раз, но чаще всего это происходит всего несколько раз. Если в матрице не осталось 0, мы можем продолжить с шага 5.). Это возможно за O (n 2 ). В этом примере невозможно построить путь с узлом 1, который также содержит узел с типом C. Поэтому он содержит 0 и удаляется, как узел 3 и узел 5. В следующем цикле с узлом 6 и узлом меньшего графа 8 будет удалено.
5.) Подсчитайте различные типы в оставшемся наборе элементов / узлов. Если оно меньше первого числа, не существует решения, которое могло бы представить все типы. Поэтому нам нужно найти другой способ получить хорошее решение. Если это то же самое, что и в первом подсчете, теперь у нас есть меньший граф, который по-прежнему содержит все возможные решения. O (nlogn)
6.) Чтобы получить одно решение, мы выбираем начальный узел (неважно, какой, потому что все узлы, оставшиеся в графе, являются частью решения). O (1)
7.)Мы удаляем каждый узел, к которому невозможно добраться из выбранного узла. O (n)
8.) Мы создаем матрицу, как на шаге 2.) и 3.) для этого графа, и удаляем узлы, которые не могут достичь узлов любого типа, как на шаге 4.). O (n 3 )
9.) Мы выбираем один из следующих узлов из узла, который мы выбрали ранее, и продолжаем с 7.) до тех пор, пока мы не достигнем конечного узла, а в графе будет только один путь налево.
Таким образом также можно получить все пути, но их количество по-прежнему может быть экспоненциальным. В конце концов, это должно быть быстрее, чем поиск решений в исходном графике.
Я бы использовал для этого Дерево интервалов .
После построения структуры данных вы можете перебрать каждое событие и выполнить запрос пересечения. Если никаких перекрестков не найдено, оно добавляется в ваше расписание.
Поскольку вы ищете все возможные расписания, я думаю, что лучшим решением, которое вы найдете, будет простой исчерпывающий поиск.
Единственное, что я могу сказать алгоритмически, это то, что ваша структура данных списков строк довольно ужасна.
Реализация сильно зависит от языка, поэтому я даже не думаю, что псевдокод имеет смысл, но я попытаюсь дать шаги для основного алгоритма.
Вытащите первые n элементов одного типа и поместите их в список.
Для каждого элемента в списке добавьте этот элемент в набор расписания.
Удалить из списка следующие n элементов того же типа.
Для каждого элемента, который начинается после окончания первого элемента, занести в список. (Если нет, неудача)
Продолжайте, пока не будете готовы.
Самая сложная часть - это решить, как именно построить списки / рекурсию, чтобы это было наиболее элегантно.
Да исчерпывающий поиск может быть вариантом:
инициализируйте частичные расписания с самыми ранними задачами, которые перекрываются (например, 9-9.30 и 9.15-9.45)
для каждого частичного расписания, созданного до сих пор, создайте список новых частичных расписаний, добавляя к каждому частичному расписанию самую раннюю задачу, которая не пересекается (создайте несколько в случае равенства)
повторяйте с новыми частичными расписаниями
В вашем случае инициализация даст только (8-9 завтрак)
После первой итерации: (8-9 завтрак, 11.40-12.40 спортзал) (без связей)
После второй итерации: (8-9 завтрак, 11.40-12.40 спортзал, 12.40-1.20 обед) (снова нет связей)
Это поиск по дереву, но он жадный. Он не учитывает такие возможности, как пропуск спортзала и ранний обед.
Хммм, это напоминает мне задание в университете, я опишу то, что вспомнил Время выполнения - O (n * logn), что неплохо.
Это жадный подход .. доработаю Ваш запрос abit, скажите, если я ошибаюсь .. Алгоритм должен возвращать МАКСИМАЛЬНОЕ подмножество не конфликтующих задач (с точки зрения общей длины? Или количества действий? Я предполагаю, что общая длина)
Я бы сначала упорядочил список по времени завершения (первое минимальное время завершения, последнее максимальное время ) = 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.
вам нужно немного подправить алгоритм, сначала вы должны построить таблицу, а затем вы можете довольно легко получить все ее вариации.