Распределенный алгоритм раскраски вершин: различия между версиями

Перейти к навигации Перейти к поиску
Строка 18: Строка 18:


== Открытые вопросы ==
== Открытые вопросы ==
Экспериментальный анализ убедительно и несколько неожиданно показывает, что самая простая и тривиальная версия алгоритма на деле оказывается и самой эффективной! В частности, она значительно превосходит эффективностью другие тщательно проанализированные алгоритмы. Финокки, Панконези и Сильвестри предложили эвристические рекуррентности, объясняющие высокую эффективность тривиального алгоритма. Строгое обоснование этих рекуррентностей остается сложным и интересным открытым вопросом. Могут быть полезны альтернативные и менее привлекательные строгие аргументы, доказывающие, что тривиальный алгоритм превосходит эффективностью алгоритмы, проанализированные Лаби и Джоханссоном. Другие вопросы касательно того, как локальная структура графа влияет на эффективность таких алгоритмов (отчасти затронутые выше), заслуживают дальнейшего экспериментального и теоретического анализа.
== Экспериментальные результаты ==
Все проанализированные алгоритмы начинают работу с присвоения исходной палитры цветов каждой вершине и последующего повторения простого раунда итерации:
1. Проснись!: каждая вершина независимо от остальных просыпается с определенной вероятностью участия в раскраске на этом раунде.
2. Попытайся!: каждая вершина независимо от остальных выбирает предварительный цвет из палитры, доступной на этом раунде.
3. Устрани конфликты!: если ни она из соседних вершин не выбрала тот же предварительный цвет, то он становится окончательным. Такая вершина завершает работу алгоритма, остальные вершины соответствующим образом корректируют свои палитры. Если возникает конфликт, он разрешается одним из двух способов: либо все конфликтующие вершины признаются неуспешными и переходят на следующий раунд, либо с помощью так называемой венгерской эвристики среди всех вершин, выбравших один и тот же цвет, вычисляется независимое множество. Вершины независимого множества получают окончательные цвета и выбывают из рассмотрения. Венгерская эвристика для независимого множества рассматривает вершины в произвольном порядке, удаляя всех соседей встретившейся вершины, которая, в свою очередь, добавляется к независимому множеству. См. в [1, p. 91] подробный анализ этой эвристики для доказательства теоремы Турана.
4. Накорми голодных!: если в палитре вершины заканчиваются цвета, ей присваиваются новые свежие цвета.
В этой базовой схеме могут вариьроваться несколько параметров, самыми значимыми из которых являются вероятность пробуждения, способы разрешения конфликтов и размер исходной палитры.
В алгоритме (A + 1)-раскраски исходная палитра для вершины v задается множеством [A] := f1 ; • • ,A + 1g (глобальная настройка) или [d(v) + 1] (где d(v) – степень вершины v) (локальная настройка). Экспериментальные результаты свидетельствуют о том, что (a) наилучшая вероятность пробуждения равна 1, (b) во время выполнения локальная версия палитры оказывается не хуже глобальной, но может обеспечить значительную экономию цветов, (c) венгерская эвристика, применяемая не к случайным числам, а к идентификаторам вершин, дает хорошие результаты.
В раскраске Брукса-Визинга исходная палитра задается значением [d(v)/s], где s – коэффициент стягивания. Экспериментальные результаты свидетельствуют о том, что оптимальную равномерную эффективность демонстрирует алгоритм, у которого вероятность пробуждения равна 1, а конфликты разрешаются при помощи венгерской эвристики. Это касается как времени выполнения, так и числа использованных цветов. Реалистически полезные значения s относятся к диапазону от 4 до 6, что приводит к Л/s-раскраске. Эффективность согласно критерию времени выполнения превосходна; даже графы с тысячами вершин удается раскрасить за 20-30 раундов. По сравнению с последовательными алгоритмами такие алгоритмы используют в 2-3 раза больше цветов, но работают намного быстрее.
== Наборы данных ==
При тестировании использовались как синтетически сгенерированные при помощи различных моделей случайных графов данные, так и эталонные тестовые множества реальных данных из второго конкурса DIMACS по реализации алгоритмов [3] и с сайта Джо Калберсона [ ].
== См. также ==
* [[Раскраска графа]]
* [[Рандомизация в распределенных вычислениях]]
* [[Рандомизированный мгновенный обмен сообщениями в радиосетях]]
== Литература ==
1. Alon, N., Spencer, J.: The Probabilistic Method. Wiley (2000)
2. Culberson,    J.C.:    http://web.cs.ualberta.ca/~joe/Coloring/index.html
3. Ftp site of DIMACS implementation challenges, ftp://dimacs.rutgers.edu/pub/challenge/
4. Finocchi, I., Panconesi, A., Silvestri, R.: An experimental Analysis of Simple Distributed Vertex Coloring Algorithms. Algorithmica 41,1-23 (2004)
5. Garey, M., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman (1979)
6. Grable, D.A., Panconesi, A.: Fast distributed algorithms for Brooks-Vizing colorings. J. Algorithms 37,85-120 (2000)
7. Johansson, O.: Simple distributed {A + 1)-coloring of graphs. Inf. Process. Lett. 70,229-232 (1999)
8. Kim, J.-H.: On Brook's Theorem for sparse graphs. Combin. Probab. Comput. 4,97-132 (1995)
9. Luby, M.: Removing randomness in parallel without processor penalty. J. Comput. Syst. Sci. 47(2), 250-286 (1993)
10. Molly, M., Reed, B.: Graph Coloring and the Probabilistic method. Springer (2002)
11. Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. In: SIAM Monographs on Discrete Mathematics and Applications 5 (2000)
12. Trick, M.: Michael Trick's coloring page: http://mat.gsia.cmu.ed u/COLOR/color.htm l
Источник — http://pco.iis.nsk.su/wega/index.php/Распределенный_алгоритм_раскраски_вершин