Рекурсивный алгоритм наибольшего первого числа

Алгоритм Recursive Largest First ( RLF ) — это эвристика для решения NP-сложной задачи раскраски графов . Первоначально он был предложен Фрэнком Лейтоном в 1979 году. ^[1]

Алгоритм RLF присваивает цвета вершинам графа, создавая каждый цветовой класс по одному. Для этого он идентифицирует максимальный независимый набор вершин в графе, присваивает им один и тот же цвет, а затем удаляет эти вершины из графа. Эти действия повторяются с оставшимся подграфом до тех пор, пока не останется вершин.

Для формирования высококачественных решений (решений с использованием небольшого количества цветов) алгоритм RLF использует специализированные эвристические правила, чтобы попытаться идентифицировать независимые множества «хорошего качества». Эти эвристики делают алгоритм RLF точным для двудольных , циклических и колесных графов . ^[2] графа Однако в целом алгоритм является приблизительным и вполне может возвращать решения, в которых используется больше цветов, чем хроматическое число .

Описание

Алгоритм можно описать следующими тремя шагами. В конце этого процесса ${\mathcal {S}}$ дает разбиение вершин, представляющих допустимое $|{\mathcal {S}}|$ - раскраска графика $G$ .

Позволять ${\mathcal {S}}=\emptyset$ быть пустым решением. Кроме того, пусть $G=(V,E)$ это граф, который мы хотим раскрасить, содержащий набор вершин $V$ и набор кромок $E$ .
Определите максимальный независимый набор $S\subseteq V$ $S\subseteq V$ . Для этого:
1. Первая вершина, добавленная к $S$ должна быть вершиной в $G$ у которого наибольшее число соседей.
2. Последующие вершины добавлены в $S$ следует выбирать те, которые (а) в данный момент не смежны ни с одной вершиной в $S$ и (б) имеют максимальное число соседей, смежных с вершинами в $S$ . Связи в условии (б) можно разорвать, выбрав вершину с минимальным числом соседей, не входящих в $S$ . Вершины добавляются в $S$ таким образом до тех пор, пока невозможно будет добавить дополнительные вершины.
Теперь установите ${\mathcal {S}}={\mathcal {S}}\cup \{S\}$ и удаляем вершины $S$ от $G$ . Если $G$ все еще содержит вершины, то вернитесь к шагу 2; иначе конец.

Пример

Рассмотрим график $G=(V,E)$ показано справа. Это круговой граф , поэтому его оптимально раскрасить с помощью RLF. В результате выполнения алгоритма вершины выбираются и раскрашиваются в следующем порядке:

Вертекс $g$ (цвет 1)
Вертекс $a$ , $c$ , а потом $e$ (цвет 2)
Вертекс $b$ , $d$ , а потом $f$ (цвет 3)

Это дает окончательное трехцветное решение. ${\mathcal {S}}=\{\{g\},\{a,c,e\},\{b,d,f\}\}$ .

Производительность

Позволять $n$ — количество вершин в графе и пусть $m$ быть числом ребер. Используя обозначение большого О , в своей оригинальной публикации Лейтон утверждает, что сложность RLF должна быть ${\mathcal {O}}(n^{3})$ ; однако это можно улучшить. Большая часть затрат на этот алгоритм приходится на шаг 2, на котором выбор вершин производится в соответствии с эвристическими правилами, изложенными выше. Действительно, каждый раз, когда вершина выбирается для добавления в независимое множество $S$ , информацию о соседях необходимо пересчитывать для каждой неокрашенной вершины. Эти расчеты можно выполнить в ${\mathcal {O}}(m)$ время, а это означает, что общая сложность RLF ${\mathcal {O}}(mn)$ . ^[2]

Если эвристику шага 2 заменить случайным выбором, то сложность этого алгоритма сводится к ${\mathcal {O}}(n+m)$ ; однако результирующий алгоритм обычно возвращает решения более низкого качества по сравнению с решениями RLF. ^[2] Теперь оно также будет неточным для двудольных , циклических и колесных графов .

В ходе эмпирического сравнения, проведенного Льюисом в 2021 году, было показано, что RLF дает значительно лучшую раскраску вершин, чем альтернативные эвристики, такие как ${\mathcal {O}}(n+m)$ жадный алгоритм и ${\mathcal {O}}((n+m)\lg n)$ DSatur Алгоритм на случайных графах . Однако время выполнения RLF также оказалось выше, чем у этих альтернатив, из-за его более высокой общей сложности. ^[2]

Ссылки

^ Лейтон, Ф. (1979). «Алгоритм раскраски графов для больших задач планирования» . Журнал исследований Национального бюро стандартов . 84 (6): 489–503. дои : 10.6028/jres.084.024 . ПМК 6756213 . ПМИД 34880531 .
^ Jump up to: ^а ^б ^с ^д Льюис, Р. (2021). Руководство по раскраске графов: алгоритмы и приложения . Тексты по информатике. Спрингер. дои : 10.1007/978-3-030-81054-2 . ISBN 978-3-030-81053-5 . S2CID 57188465 .

Внешние ссылки

Высокопроизводительные алгоритмы раскраски графов Набор алгоритмов раскраски графов (реализованных на C++), используемых в книге «Руководство по раскраске графов: алгоритмы и приложения» (Springer International Publishers, 2021).

[:0-1] Лейтон, Ф. (1979). «Алгоритм раскраски графов для больших задач планирования» . Журнал исследований Национального бюро стандартов . 84 (6): 489–503. дои : 10.6028/jres.084.024 . ПМК 6756213 . ПМИД 34880531 .

[:1-2] Jump up to: ^а ^б ^с ^д Льюис, Р. (2021). Руководство по раскраске графов: алгоритмы и приложения . Тексты по информатике. Спрингер. дои : 10.1007/978-3-030-81054-2 . ISBN 978-3-030-81053-5 . S2CID 57188465 .

[1]

[2]