3622
правки
Изменения
Нет описания правки
Каждое расписание может быть представлено последовательностью работ в порядке, в котором они выполняются. Пусть <tex> \pi </tex> будет оптимальной такой последовательностью со свойством, что количество работ между <tex> i </tex> и <tex> j </tex> равное <tex> l </tex> было бы минимальным. Можно считать, что <tex> l > 0 </tex>. Тогда расписание можно представить следующим образом:
Рассмотрим <tex>2</tex> случая.
Если для получения работы <tex> j </tex> с минимальным значением <tex> q(j) </tex> использовать очередь с приоритетами, а для поиска родителям вершины использовать систему непересекающихся множеств, то время работы алгоритма будет <tex> O(n\log{n}) </tex>.
Проиллюстрируем работу алгоритма на следующем примере. [[Файл:JobsOuttrees.jpg|650px]] Первой выберется работа с номером <tex> 5 </tex>. Она объединиться со своим родителем <tex> 2 </tex> и допишется в конец <tex> \pi_2 </tex>. Потом выберется работа <tex> 4 </tex>, потом <tex> \{2, 5\} </tex> и т. д. Процесс будет продолжаться, пока не останется одна вершина. Ответ {{---}} оптимальная последовательность работ {{---}} содержится в <tex> \pi_1 </TODO: картинка с примеромtex>, который написан внутри последней вершины.
== Доказательство оптимальности алгоритма ==
{{Теорема
