Исследователи представили алгоритм SSLD для оптимизации раскраски графов

Исследователи представили SSLD (Semidefinite Spectral Learning with DSATUR) — новый метод предварительной обработки данных, который повышает эффективность классического эвристического алгоритма DSATUR для решения задачи раскраски графов (GCP).

Метод основан на использовании семиопределенного программирования (SDP) для выбора первого класса цветов перед запуском основного алгоритма. В отличие от стандартного подхода, SSLD фиксирует начальный набор вершин, что позволяет значительно улучшить качество итоговой раскраски графа, минимизируя общее количество используемых цветов.

Эффективность алгоритма была протестирована на более чем 1600 бенчмарках, включая графы Эрдёша — Реньи, Ваттса — Строгаца и Барабаши — Альберт, а также на задачах назначения частот и планирования производства. Результаты показывают, что SSLD либо превосходит, либо соответствует показателям стандартного DSATUR во всех протестированных случаях.

Основным ограничением метода является вычислительная сложность: процесс предварительной обработки делает выполнение алгоритма примерно в 195 раз медленнее, чем у оригинального DSATUR. Тем не менее, авторы подтвердили, что использование SDP-направляемого выбора первого класса цветов является перспективным направлением для дальнейшей оптимизации NP-трудных задач.

Данная работа, опубликованная под лицензией arXiv, демонстрирует потенциал гибридных подходов, сочетающих классические эвристики с методами математического программирования для решения сложных комбинаторных проблем.