Алгоритм Коффмана – Грэма

Метод разделения частичных заказов на уровни

Алгоритм Коффмана-Грэма — это алгоритм организации элементов частично упорядоченного множества в последовательность уровней. Алгоритм выбирает такое расположение, при котором элемент, следующий за другим в порядке, назначается более низкому уровню и такой, чтобы каждый уровень имел количество элементов, не превышающее фиксированную границу ширины W . Когда W = 2 , он использует минимально возможное количество различных уровней и, как правило, использует не более чем в 2–2/ W раз больше уровней, чем необходимо.

Он назван в честь Эдварда Г. Коффмана-младшего и Рональда Грэма , которые опубликовали его в 1972 году для применения в планировании рабочих мест . В этом приложении упорядочиваемыми элементами являются задания, ограничение W — это количество заданий, которые можно запланировать одновременно, а частичный порядок описывает обязательные отношения между заданиями. Цель состоит в том, чтобы найти расписание, при котором все задания выполняются за минимальное общее время. Впоследствии тот же алгоритм стал использоваться и при рисовании графов как способ размещения вершин ориентированного графа в слоях фиксированной ширины так, чтобы большинство или все ребра были направлены последовательно вниз.

Для частичного упорядочения, заданного его транзитивной редукцией (отношением покрытия), алгоритм Коффмана – Грэма может быть реализован за линейное время , используя структуру данных уточнения разделения в качестве подпрограммы. Если транзитивная редукция не задана, ее построение занимает полиномиальное время .

Постановка задачи и приложения

В версии задачи планирования цеха, решаемой алгоритмом Коффмана–Грэма, дается набор из n заданий J ₁ , J ₂ , ..., J _n вместе с системой ограничений предшествования J _i < J _j требование, чтобы задание J _i было завершено до начала задания J _j . Предполагается, что выполнение каждой работы занимает единицу времени. Задача планирования состоит в том, чтобы назначить каждое из этих заданий временным интервалам в системе из W идентичных процессоров, минимизируя время выполнения назначения (время от начала первого задания до завершения последнего задания). Абстрактно, ограничения приоритета определяют частичный порядок заданий, поэтому проблему можно перефразировать как задачу присвоения элементов этого частичного порядка уровням (временным интервалам) таким образом, чтобы каждый временной интервал содержал не более процессоров (не более W элементов на уровень), соблюдая ограничения приоритета. Это приложение стало первоначальным стимулом для Коффмана и Грэма разработать свой алгоритм. ^{[1] [2]}

В структуре рисования многоуровневых графов , описанной Сугиямой, Тагавой и Тодой (1981) ^[3], входными данными является ориентированный граф , а рисунок графа строится в несколько этапов: ^{[4] [5]}

1. Выбирается набор дуг обратной связи и ребра этого набора меняются местами, чтобы преобразовать входные данные в ориентированный ациклический граф с (если возможно) небольшим количеством перевернутых ребер.
2. Вершинам графа присваиваются целые координаты y таким образом, что для каждого ребра начальная вершина ребра имеет более высокую координату, чем конечная вершина, при этом не более W вершин имеют одну и ту же координату y . Таким образом, все ребра ориентированного ациклического графа и большинство ребер исходного графа будут ориентированы последовательно вниз.
3. Внутри каждого ребра вводятся фиктивные вершины, так что все разделенные ребра соединяют пары вершин, находящихся на соседних уровнях чертежа.
4. Внутри каждой группы вершин с одинаковой координатой y вершины переставляются так, чтобы минимизировать количество пересечений в результирующем рисунке, и вершинам присваиваются координаты x в соответствии с этой перестановкой.
5. Вершины и ребра графа рисуются с присвоенными им координатами.

В этой структуре присвоение координаты y снова включает группировку элементов частично упорядоченного набора (вершины графа с упорядочением достижимости набора вершин) в слои (наборы вершин с одинаковой координатой y ), что задача, решаемая алгоритмом Коффмана–Грэма. ^[4] Хотя существуют альтернативные подходы к этапу наслоения, отличные от алгоритма Коффмана-Грэма, эти альтернативы, как правило, либо не могут включать ограничение на максимальную ширину уровня, либо полагаются на сложные процедуры целочисленного программирования . ^[6]

Более абстрактно, обе эти проблемы можно формализовать как задачу, в которой входные данные состоят из частично упорядоченного набора и целого числа W. Желаемый результат — это присвоение чисел целочисленного уровня элементам частично упорядоченного набора так, что, если x < y является упорядоченной парой связанных элементов частичного порядка, число, присвоенное x , меньше, чем число, присвоенное y. , так что не более чем W элементам присваиваются одинаковые номера, и минимизируется разница между наименьшим и наибольшим присвоенными номерами.

Алгоритм

Алгоритм Коффмана – Грэма выполняет следующие шаги. ^[4]

1. Представьте частичный порядок посредством его транзитивной редукции или отношения покрытия , ориентированного ациклического графа G , который имеет ребро от x до y всякий раз, когда x < y , и не существует третьего элемента z частичного порядка, для которого x < z < y . В приложениях для рисования графов алгоритма Коффмана-Грэма результирующий ориентированный ациклический граф может не совпадать с рисуемым графом, а в приложениях планирования он может не иметь ребра для каждого ограничения приоритета входных данных: в обоих случаях , транзитивная редукция удаляет избыточные ребра, которые не необходимы для определения частичного порядка.
2. Постройте топологическое упорядочение графа G , в котором вершины упорядочены лексикографически по набору позиций их входящих соседей. Для этого добавляйте вершины в порядок по одной, на каждом этапе выбирая добавляемую вершину v так, чтобы все входящие соседи вершины v уже были частью частичного упорядочения, и чтобы последний добавленный входящий сосед вершины v уже был частью частичного упорядочения. v находится раньше, чем самый последний добавленный входящий сосед любой другой вершины, которая может быть добавлена ​​вместо v . Если две вершины имеют одного и того же последнего добавленного входящего соседа, алгоритм разрывает связь в пользу той, у которой второй, последний добавленный входящий сосед, был раньше и т. д.
3. Назначьте вершины G уровням в обратном топологическому порядку, построенному на предыдущем шаге. Для каждой вершины v добавьте v к уровню, который как минимум на один шаг выше, чем самый высокий уровень любого исходящего соседа v , которому еще не назначено W элементов, и который является как можно более низким с учетом этих двух ограничения.

Анализ

Качество вывода

Как первоначально доказали Коффман и Грэм (1972), их алгоритм вычисляет оптимальное назначение для W = 2 ; то есть для задач планирования задач единичной длины на двух процессорах или для задач рисования многослойных графов с не более чем двумя вершинами на слой. ^[1] Близко связанный алгоритм также находит оптимальное решение для планирования заданий различной длины, позволяя вытеснять запланированные задания на двух процессорах. ^[7] Для W > 2 алгоритм Коффмана–Грэма использует несколько уровней (или вычисляет расписание с интервалом выполнения), которое находится в пределах 2–2/ W от оптимального. ^{[8] [9]} Например, для W = 3 это означает, что он использует максимум в 4/3 раза больше уровней, чем оптимально. Когда частичный порядок ограничений предшествования является интервальным порядком или принадлежит нескольким связанным классам частичных порядков, алгоритм Коффмана – Грэма находит решение с минимальным количеством уровней независимо от его границы ширины. ^[10]

Алгоритм Коффмана-Грэма (модифицированный по сравнению с представленной здесь презентацией так, что он топологически упорядочивает обратный граф G и размещает вершины как можно раньше, а не как можно позже) не только позволяет находить расписания с небольшим интервалом выполнения, но и минимизирует общее время потока . двухпроцессорных расписаний — сумма времен завершения отдельных заданий. Соответствующий алгоритм можно использовать для минимизации общего времени потока для версии задачи, в которой разрешено вытеснение заданий. ^[11]

Временная сложность

Коффман и Грэм (1972) и Ленстра и Риннуй Кан (1978) ^[12] утверждают, что временная сложность алгоритма Коффмана-Грэма в частичном порядке из n -элементов равна O ( n ² ) . Однако в этом анализе не учитывается время на построение транзитивной редукции, которая, как известно, невозможна в пределах этой границы. Sethi (1976) показывает, как реализовать стадию топологического упорядочения алгоритма за линейное время , основываясь на идее уточнения разделов . ^[13] Сетхи также показывает, как эффективно реализовать этап назначения уровня алгоритма, используя структуру данных с непересекающимися наборами . В частности, в версии этой структуры, опубликованной позже Габоу и Тарджаном (1985), этот этап также занимает линейное время. ^[14]

Рекомендации

1. Коффман, Э.Г. младший ; Грэм, Р.Л. (1972), «Оптимальное планирование для двухпроцессорных систем» (PDF) , Acta Informatica , 1 (3): 200–213, doi : 10.1007/bf00288685, MR  0334913, S2CID  40603807.
2. Люнг, Джозеф Ю.-Т. (2004), «Некоторые базовые алгоритмы планирования», Справочник по планированию: алгоритмы, модели и анализ производительности , CRC Press, ISBN 978-1-58488-397-5.
3. Сугияма, Кодзо; Тагава, Сёдзиро; Тода, Мицухико (1981), «Методы визуального понимания иерархических системных структур», Транзакции IEEE по системам, человеку и кибернетике , SMC-11 (2): 109–125, doi : 10.1109/TSMC.1981.4308636, MR  0611436, S2CID  8367756.
4. ди Баттиста, Джузеппе; Идс, Питер ; Тамассия, Роберто ; Толлис, Иоаннис Г. (1999), «Глава 9: Многоуровневые рисунки орграфов», Рисование графиков: алгоритмы визуализации графиков , Прентис Холл, стр. 265–302.
5. Бастерт, Оливер; Матушевский, Кристиан (2001), «Многослойные рисунки орграфов», Кауфманн, Майкл; Вагнер, Доротея (ред.), Рисование графиков: методы и модели , Конспекты лекций по информатике, том. 2025, Springer-Verlag, стр. 87–120, номер документа : 10.1007/3-540-44969-8_5.. Бастерт и Матушевски также включают описание алгоритма Коффмана – Грэма; однако они опускают этап транзитивной редукции алгоритма.
6. Хили, Патрик; Николов, Никола С. (2002), «Как расслоить направленный ациклический граф», Рисование графика: 9-й Международный симпозиум, GD 2001, Вена, Австрия, 23–26 сентября 2001 г., Переработанные статьи , Конспекты лекций по информатике, том. 2265, Springer-Verlag, стр. 16–30, номер документа : 10.1007/3-540-45848-4_2 , MR  1962416..
7. Мунц, Р.Р.; Коффман, Э.Г. (1969), «Оптимальное вытесняющее планирование в двухпроцессорных системах», IEEE Transactions on Computers , 18 (11): 1014–1020, doi : 10.1109/TC.1969.222573, S2CID  206617438.
8. Лам, Шуй; Сетхи, Рави (1977), «Анализ наихудшего случая двух алгоритмов планирования», SIAM Journal on Computing , 6 (3): 518–536, doi : 10.1137/0206037, MR  0496614.
9. Браски, Бертран; Тристрам, Денис (1994), «Новый взгляд на алгоритм Коффмана-Грэма», SIAM Journal on Computing , 23 (3): 662–669, doi : 10.1137/S0097539790181889, MR  1274650.
10. Шардон, Марк; Мукрим, Азиз (2005), «Алгоритм Коффмана-Грэма оптимально решает системы задач UET с сверхинтервальными порядками», SIAM Journal on Discrete Mathematics , 19 (1): 109–121, doi : 10.1137/S0895480101394999, MR  2178187.
11. Коффман, Э.Г. младший ; Сетураман, Дж.; Тимковский В.Г. (2003), «Идеальные вытесняющие расписания на двух процессорах», Acta Informatica , 39 (8): 597–612, doi : 10.1007/s00236-003-0119-6, MR  1996238, S2CID  7016804.
12. Ленстра, Дж. К .; Риннуй Кан, AHG (1978), «Сложность планирования в условиях ограничений приоритета», Operations Research , 26 (1): 22–35, doi : 10.1287/opre.26.1.22, hdl : 10338.dmlcz/141477 , JSTOR  169889, МР  0462553.
13. Сетхи, Рави (1976), «Графы планирования на двух процессорах», SIAM Journal on Computing , 5 (1): 73–82, doi : 10.1137/0205005, MR  0398156.
14. Габоу, Гарольд Н .; Тарьян, Роберт Эндре (1985), «Алгоритм линейного времени для особого случая объединения непересекающихся множеств», Journal of Computer and System Sciences , 30 (2): 209–221, doi : 10.1016/0022-0000(85) 90014-5 , МР  0801823.