4446
правок
Распределенный алгоритм раскраски вершин: различия между версиями
Материал из WEGA
Распределенный алгоритм раскраски вершин (посмотреть исходный код)
Версия от 22:27, 16 сентября 2019
, 16 сентября 2019→Экспериментальные результаты
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 21: | Строка 21: | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
Все проанализированные алгоритмы начинают работу с присвоения исходной палитры цветов каждой вершине и последующего повторения простого раунда итерации: | Все проанализированные алгоритмы начинают работу с присвоения исходной ''палитры'' цветов каждой вершине и последующего повторения простого раунда итерации: | ||
1. ''Проснись!'': каждая вершина независимо от остальных просыпается с определенной вероятностью участия в раскраске на этом раунде. | |||
2. ''Попытайся!'': каждая вершина независимо от остальных выбирает предварительный цвет из палитры, доступной на этом раунде. | |||
3. ''Устрани конфликты!'': если ни одна из соседних вершин не выбрала тот же предварительный цвет, то он становится окончательным. Такая вершина более не рассматривается алгоритмом, остальные вершины соответствующим образом корректируют свои палитры. Если возникает конфликт, он разрешается одним из двух способов: либо все конфликтующие вершины признаются неуспешными и переходят на следующий раунд, либо с помощью так называемой венгерской эвристики среди всех вершин, выбравших один и тот же цвет, вычисляется независимое множество. Вершины независимого множества получают окончательные цвета и выбывают из рассмотрения. Венгерская эвристика для независимого множества рассматривает вершины в произвольном порядке, удаляя всех соседей встретившейся вершины, которая, в свою очередь, добавляется к независимому множеству. См. в [1, p. 91] подробный анализ этой эвристики для доказательства теоремы Турана. | |||
4. ''Накорми голодных!'': если в палитре вершины заканчиваются цвета, ей присваиваются новые свежие цвета. | |||
4. Накорми голодных!: если в палитре вершины заканчиваются цвета, ей присваиваются новые свежие цвета. | |||
| Строка 36: | Строка 35: | ||
В алгоритме <math>(\Delta + 1)</math>-раскраски исходная палитра для вершины v задается множеством <math>[\Delta] := \{ 1, ..., \Delta + 1 \}</math> (глобальная настройка) или [d(v) + 1] | В алгоритме <math>(\Delta + 1)</math>-раскраски исходная палитра для вершины v задается множеством <math>[\Delta] := \{ 1, ..., \Delta + 1 \}</math> (глобальная настройка) или [d(v) + 1], где d(v) – степень вершины v (локальная настройка). Экспериментальные результаты свидетельствуют о том, что (1) наилучшая вероятность пробуждения равна 1, (2) во время выполнения локальная версия палитры оказывается не хуже глобальной, но может обеспечить значительную экономию цветов, (3) венгерская эвристика, применяемая не к случайным числам, а к идентификаторам вершин, дает хорошие результаты. | ||
