#algorithm #graph #labels #approximation
#алгоритм #График #метка #аппроксимация
Вопрос:
Я пытаюсь реализовать алгоритм 0-расширения.
Он используется для раскрашивания графика несколькими цветами, где некоторым узлам уже присвоен цвет и где каждое ребро имеет расстояние. Алгоритм вычисляет назначение цветов таким образом, чтобы соседние узлы с одинаковым цветом имели как можно большее расстояние между собой.
Я нашел эту статью, объясняющую алгоритм: http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=1FBA2D22588CABDAA8ECF73B41BD3D72?doi=10.1.1.100.8049amp;rep=rep1amp;type=pdf но я не вижу, как мне нужно это реализовать.
Я уже задавал этот вопрос на сайте «теоретическая информатика», но в середине обсуждения мы вышли за рамки сайта: https://cstheory.stackexchange.com/questions/6163/explain-0-extension-algorithm
Кто-нибудь может объяснить этот алгоритм в терминах непрофессионала? Я планирую сделать окончательный код с открытым исходным кодом в пакете jgrapht.
Ответ №1:
Цель 0-расширения — минимизировать общую взвешенную стоимость ребер с разными цветовыми конечными точками, а не максимизировать ее, поэтому 0-расширение на самом деле является проблемой кластеризации, а не проблемой раскраски. Я вообще скептически отношусь к тому, что использование алгоритма кластеризации для раскрашивания даст хорошие результаты. Если вы хотите что-то с теоретической гарантией, вы могли бы изучить приближения к задаче MAXCUT (действительно обобщение, если имеется более двух цветов), но я подозреваю, что алгоритм локального поиска будет работать лучше на практике.
Комментарии:
1. я думал, что алгоритм MAXCUT не может обрабатывать предварительно окрашенные узлы, или для этого просто нужна более общая версия алгоритма? моя текущая реализация в brute fore (оптимизированная с ограничением ветвей) вычисляет 35 узлов с 3 цветами за 12 минут, мне нужно выделить 64 узла за 10 минут
2. Для двух цветов вам просто нужно применить ограничение, согласно которому векторы, соответствующие предварительно окрашенным узлам, имеют скалярное произведение -1. В общем случае, при k цветах требуется значение -1 / (k-1), но округление становится сложнее. Я бы попробовал ceil (lg k) случайные гиперплоскости, которые разделяют предварительно окрашенные узлы.