Участник:Lizord/Алгоритм Джонса Плассмана: различия между версиями
Lizord (обсуждение | вклад) Добавлено общее описание алгоритма |
Lizord (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
'''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, основанная на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Алгоритм выделения этого подмножества был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref> | '''Алгоритм Джонса-Плассмана''' - параллельная версия жадного алгоритма для раскраски графа, основанная на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Алгоритм выделения этого подмножества был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. <ref name="jp">M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993</ref> | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
Исходные данные: граф <math>G = G(V, E)</math>, где <math>V</math> - множество вершин, а <math>E</math> - множество ребёр.<br> | |||
Вычисляемые данные: вектор цветов <math>c = \{c_i\}</math> размерности <math>|V|</math> | |||
Для раскраски графа, необходимо проделать следующие шаги: | |||
# Обозначим множество нераскрашенных вершин как <math>V' = V</math>.<br> | |||
# На каждой итерации будем выделять максимальное независимое подмножество вершин <math>I \subset V'</math>, которое раскрашивается параллельно.<br> | |||
# После этого полагаем <math>V' = V'\;\backslash\;I</math>. Алгоритм работает, пока <math>V' \neq \emptyset</math>. | |||
Подмножество независимых вершин <math>I</math> выделяется следующим образом <ref>M. Luby, A simple paral lel algorithm for the maximal independent set problem, SIAM | |||
Journal on Computing, 4 (1986), pp. 10</ref>:<br> | |||
Положим <math>I = \emptyset, V' = V, G' = G</math>. Повторяем следующие шаги, пока <math>G' \neq \emptyset </math>: | |||
# <math>I = I \cup I'</math> | |||
# <math>X = I' \cup N(I')</math> | |||
# <math>V' = V' \;\backslash\; X</math> | |||
# <math>G' = G(V')</math> | |||
Для раскраски вершины <math>v_i \in I</math> необходимо назначить ей цвет <math>c_i</math> такой, что <math>c_i \notin N_c(v_i)</math>, где <math>N_c(v_i)</math> - цвета вершин, соседних для <math>v_i</math>. Это можно сделать последовательным перебором, это займёт в худшем случае <math>deg(v_i)</math> итераций.<br> | |||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
Версия от 12:25, 16 октября 2025
| Файл:Warning sign font awesome.svg | Данная страница в настоящее время активно редактируется участником Lizord (обсуждение). Пожалуйста, не вносите в неё никаких изменений до тех пор, пока не исчезнет это объявление. В противном случае могут возникнуть конфликты редактирования. |
Основные авторы описания: Демаков М. А.
| Алгоритм Джонса-Плассмана | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(V + E) }[/math] |
| Объём входных данных | [math]\displaystyle{ 8|E| }[/math] |
| Объём выходных данных | [math]\displaystyle{ V }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ O(\frac{log(V)}{log log(V)}) }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ O(log(V)) }[/math] |
Свойства и структура алгоритмов
Общее описание алгоритма
Алгоритм Джонса-Плассмана - параллельная версия жадного алгоритма для раскраски графа, основанная на выделении из графа максимального независимого подмножества вершин и параллельной его раскраске. Алгоритм выделения этого подмножества был предложен Луби, он заключается в назначении вершинам уникальных меток, и последующего выбора ранее не выбранных вершин с максимальной меткой среди своих соседей. [1]
Математическое описание алгоритма
Исходные данные: граф [math]\displaystyle{ G = G(V, E) }[/math], где [math]\displaystyle{ V }[/math] - множество вершин, а [math]\displaystyle{ E }[/math] - множество ребёр.
Вычисляемые данные: вектор цветов [math]\displaystyle{ c = \{c_i\} }[/math] размерности [math]\displaystyle{ |V| }[/math]
Для раскраски графа, необходимо проделать следующие шаги:
- Обозначим множество нераскрашенных вершин как [math]\displaystyle{ V' = V }[/math].
- На каждой итерации будем выделять максимальное независимое подмножество вершин [math]\displaystyle{ I \subset V' }[/math], которое раскрашивается параллельно.
- После этого полагаем [math]\displaystyle{ V' = V'\;\backslash\;I }[/math]. Алгоритм работает, пока [math]\displaystyle{ V' \neq \emptyset }[/math].
Подмножество независимых вершин [math]\displaystyle{ I }[/math] выделяется следующим образом [2]:
Положим [math]\displaystyle{ I = \emptyset, V' = V, G' = G }[/math]. Повторяем следующие шаги, пока [math]\displaystyle{ G' \neq \emptyset }[/math]:
- [math]\displaystyle{ I = I \cup I' }[/math]
- [math]\displaystyle{ X = I' \cup N(I') }[/math]
- [math]\displaystyle{ V' = V' \;\backslash\; X }[/math]
- [math]\displaystyle{ G' = G(V') }[/math]
Для раскраски вершины [math]\displaystyle{ v_i \in I }[/math] необходимо назначить ей цвет [math]\displaystyle{ c_i }[/math] такой, что [math]\displaystyle{ c_i \notin N_c(v_i) }[/math], где [math]\displaystyle{ N_c(v_i) }[/math] - цвета вершин, соседних для [math]\displaystyle{ v_i }[/math]. Это можно сделать последовательным перебором, это займёт в худшем случае [math]\displaystyle{ deg(v_i) }[/math] итераций.
Вычислительное ядро алгоритма
Макроструктура алгоритма
Схема реализации последовательного алгоритма
Последовательная сложность алгоритма
Информационный граф
Ресурс параллелизма алгоритма
Входные и выходные данные алгоритма
Свойства алгоритма
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
Возможные способы и особенности параллельной реализации алгоритма
Результаты прогонов
Выводы для классов архитектур
Литература
Test2 [3]
- ↑ M.T.Jones, P.E.Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, vol. 14, no. 3, pp. 654–669, 1993
- ↑ M. Luby, A simple paral lel algorithm for the maximal independent set problem, SIAM Journal on Computing, 4 (1986), pp. 10
- ↑ Maciej Besta, Armon Carigiet et. al. High-Performance Parallel Graph Coloring with Strong Guarantees on Work, Depth, and Quality. // ACM/IEEE Supercomputing Conference, 2020