Современная метаэвристика окраски графа
У меня есть проблема раскраски графа, которая включает в себя тысячи вершин, каждая из которых имеет от 10 до 50 ребер. Я исследовал многие эвристические схемы окраски графиков (GA, поиск по табу...), но мне трудно их сравнивать и решать, что подойдет мне лучше всего. У кого-нибудь есть опыт крупномасштабной раскраски графиков, чтобы рекомендовать технику или сообщить мне о современных современных или современных алгоритмах в этой области?
Благодарю.
2 ответа
Внедрите его в механизм оптимизации, такой как Drools Planner, и запустите его тест для определения того, какая метаэвристика работает лучше всего.
Особенно, если у вас нет проблемы с чистой раскраской графа (поэтому у вас есть дополнительные ограничения), невозможно заранее определить, какая метаэвристика будет работать лучше всего.
Хорошее решение, о котором я знаю, - это использовать имитационный отжиг с цепями Kempe. По сути, вы используете стандартный имитационный отжиг, а когда вы хотите сделать случайное изменение в решении, вы выбираете два соседних узла и изменяете их цвет в соответствии с правилом цепочек Kempe.