close

Вход

Забыли?

вход по аккаунту

?

Модифиципованный алгоритм раскраски графа.

код для вставкиСкачать
Тезисы докладов
УДК
Конференция
«Интеллектуальные САПР»
628.3
Л.А. Стасенко
МОДИФИЦИПОВАННЫЙ АЛГОРИТМ РАСКРАСКИ ГРАФА
Раскраской вершин графа G=(X,U) называется разбиение множества вершин
X на L непересекающихся классов (подмножеств) таких, что внутри каждого подмножества Xi не должно содержаться смежных вершин. Если каждому подмножеству Xi поставить в соответствие определенный цвет, то вершины внутри этого
подмножества можно окрасить в один цвет, а вершины другого подмножества Xj в другой цвет, и так далее, до раскраски всех подмножеств.
Основной стратегией для задач раскраски графа являются последовательные и
жадные эвристики, которые дают с первой попытки результаты с локальным оптимумом.
Последовательная эвристика заключается в следующем. Сначала составляется
упорядоченный в порядке убывания степеней вершин список. Первая вершина
удаляется из списка и окрашивается в цвет 1. Просматривая список, в цвет 1 раскрашиваются и удаляются из него все вершины, несмежные с первой выбранной и
между собой. Далее выбирается вторая вершина из списка, она окрашивается в
цвет 2 и удаляется. Процесс продолжается аналогично, пока не будут окрашены
все вершины.
Так как жадная и последовательная эвристики раскраски графа достаточно
быстрые, то предлагается совместить их с генетическим поиском (ГП). Стратегия
совмещения предполагает, что используется новое кодирование алгоритма. Основная идея алгоритма следующая.
1. Построение заданной популяции альтернативных решений.
2. Кодирование альтернативных решений или их частей.
3. Определение целевой функции (ЦФ).
4. Согласно ЦФ выбираем первую вершину и присваиваем ей первый реальный цвет, если это возможно. Каждая альтернатива учитывает предыдущие использованные цвета.
5. Перестановка списка вершин получается в результате упорядочивания
элементов в списке (тривиальная перестановка просто оставляет предыдущий порядок).
6. Жадная, последовательная или комбинированная эвристика сортирует
список вершин и передает результат в эвристику декодирования.
7. Декодирование.
8. Замена инициализации на случайную или основанную на знаниях о решаемой задачи перестановку списка вершин.
9. Конец работы алгоритма.
В результате изменений порядка вершин в упорядоченном списке получим
измененный список вершин графа. Для выхода из локальных оптимумов используются процедуры, реализуемые в блоках предпроцессор и постпроцессор в архитектуре ГП. Алгоритм отличается от известных возможностью получения набора
альтернативных решений за полиномиальное время. Алгоритм имеет временную
сложность
≈O(n2).
313
Документ
Категория
Без категории
Просмотров
5
Размер файла
88 Кб
Теги
алгоритм, раскраска, модифиципованный, граф
1/--страниц
Пожаловаться на содержимое документа