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

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

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

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

Описание

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

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

Пример

Граф-колесо с семью вершинами

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

  1. Вершина (цвет 1) г {\displaystyle г}
  2. Вершина , , а затем (цвет 2) а {\displaystyle а} с {\displaystyle с} е {\displaystyle е}
  3. Вершина , , а затем (цвет 3) б {\displaystyle б} г {\displaystyle д} ф {\displaystyle f}

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

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

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

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

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

Ссылки

  1. ^ Лейтон, Ф. (1979). «Алгоритм раскраски графов для больших задач планирования». Журнал исследований Национального бюро стандартов . 84 (6): 489–503. doi :10.6028/jres.084.024. PMC  6756213. PMID  34880531 .
  2. ^ abcd Льюис, Р. (2021). Руководство по раскраске графов: алгоритмы и приложения . Тексты по информатике. Springer. doi :10.1007/978-3-030-81054-2. ISBN 978-3-030-81053-5. S2CID  57188465.
  • Высокопроизводительные алгоритмы раскраски графов Набор алгоритмов раскраски графов (реализованных на языке C++), использованных в книге «Руководство по раскраске графов: алгоритмы и приложения» (Springer International Publishers, 2021).
Получено с "https://en.wikipedia.org/w/index.php?title=Рекурсивный_самый_большой_первый_алгоритм&oldid=1250833901"