Vertex-Coloring/Assignment для минимизации количества «пересечений цветов»
Я не уверен, действительно ли это проблема "раскрашивания" в такой же степени, как задача присваивания/линейного программирования. У меня нет никакого опыта ни в том, ни в другом, так что извините за нубство, которое может последовать. Но у меня такое чувство, что эта проблема, должно быть, почти наверняка была решена/исследована раньше, я просто не смог ничего найти после просмотра многих алгоритмов графа на http://en.wikipedia.org/wiki/Category:Graph_algorithms . Я надеялся получить некоторые указатели в правильном направлении.
«Постановка задачи» фактически сводится к следующему:
В графе есть два типа вершин: маршрутизаторы и ядра.
Ядра подключаются ТОЛЬКО к маршрутизаторам. Каждое ядро подключено только к ОДНОМУ маршрутизатору. И у каждого есть введенный пользователем/определенный «цвет». (В моей конкретной проблеме цвет ограничен одним из, скажем, 4/5 возможных цветов). Их цвет нельзя изменить, это входной параметр. (Ядра — это квадраты на изображении ниже)
Маршрутизаторы подключены к ядрам так же, как и другие маршрутизаторы. Им не присвоен «цвет». Назначение цвета является частью задачи программы/алгоритма. (Маршрутизаторы — это круглые вершины на изображении ниже.)
Цель программы — назначить цвета каждому маршрутизатору в графе таким образом, чтобы количество «пересечений»/ребер между вершинами разных цветов было минимальным.
(Альтернативный взгляд: по сути, вам дан граф, в котором некоторые вершины окрашены, а другие нет. Цель состоит в том, чтобы раскрасить те вершины, которые не являются такими, чтобы количество ребер между вершинами разного цвета было минимальным.)
Я смог сформулировать это (довольно плохо, я уверен) как целочисленную линейную программу и настроить решение/подход, используя LP-Solve. У меня тоже есть своя эвристика. Я хотел бы знать «правильные»/известные/другие подходы к решению этой проблемы?!
Большое спасибо!
