Vertex-Coloring/Assignment, чтобы свести к минимуму количество «пересечений цветов»

Question

Я не уверен, действительно ли это проблема «раскраски», поскольку это проблема назначения/линейного программирования. У меня тоже нет опыта, так что прошу прощения за любую нубость, которая могла бы последовать. Но я чувствую, что эта проблема должна была быть почти окончательно решена/исследована раньше, я просто не смог найти ничего, просмотрев многие алгоритмы графа на http://en.wikipedia.org/wiki/Category:Graph_algorithms. Я надеялся получить некоторые указатели в правильном направлении.

«Проблема-оператор» фактически сводится к:

1. Есть два типа вершин в графе: маршрутизаторы и сердечников.

2. Сердечники подключены к маршрутизаторам ТОЛЬКО. Каждое ядро ​​подключается только к одному маршрутизатору. И каждый имеет введенный пользователем/определенный «цвет». (В моей конкретной проблеме цвет ограничен одним из 4/5 возможных цветов). Их цвет не может быть изменен, это входной параметр. (Ядра являются квадратами на изображении ниже)

3. Маршрутизаторы подключаются к сердечникам, а также к другим маршрутизаторам. У них нет «цвета», назначенного им. Назначение цвета является частью цели программы/алгоритма. (Маршрутизаторы - это круговые вершины на изображении ниже.)

4. Цель программы - назначить цвета для каждого маршрутизатора на графике таким образом, чтобы количество «пересечений»/ребер между вершинами разных цветов минимизировалось ,

(Альтернативный вид:. В сущности, вы получаете график, где некоторые вершины окрашены, а другие не являются Цель состоит в том, чтобы окрасить те, которые не являются такими, что число ребер между вершинами разного цвета сведено к минимуму.)

Я смог сформулировать это (довольно плохо уверен) в качестве Integer-Linear-Program и установить решение/подход, используя LP-Solve. У меня тоже есть эвристика. Я хотел бы знать «правильные»/известные/другие подходы к решению этого ?!

Большое спасибо!

Answer 1

Если количество цветов < = 5 и маршрутизаторы < = 10, то вы можете использовать грубую силу.

Есть гораздо меньше, чем 5^10 параметров, особенно если по умолчанию вы цвет каждого маршрутизатора наиболее распространенный цвет, а затем просто измените цвет некоторых из них, при необходимости отступив назад.

Редактировать: Также есть хороший алгоритм гамильтоновых путей, который вы, возможно, сможете адаптировать к вашим потребностям, если имеется менее 15 маршрутизаторов. What is the dynamic programming algorithm for finding a Hamiltonian cycle in a graph?

Answer 2

Начнем с фокусировки на корпусе с двумя цветами. Мы можем превратить это в случай s-tmin cut. Идея заключается в том, что мы обозначили в сек узла и т узла в виде графа, и что мы хотим разделить оставшиеся узлы в либо сек группы или трут группы , таким образом, что сумма граничные веса между двумя группами минимизированы.Для вашей версии у нас есть главный желтый узел s и главный красный узел t, и мы помещаем высоко взвешенный край, превышающий количество всех ребер в вашем исходном графе между каждым из сердечников и соответствующим им основным узлом цвета, со всеми оригинальными краями, имеющими вес 1 каждый. Высокие ценовые границы гарантируют, что мы никогда не будем незаконно перекрашивать любой из ядер, так как будет дешевле перемещать все маршрутизаторы. Эта проблема может быть решена в полиномиальное время с использованием standard max flow algorithms через Max flow-Min cut theorem. Лучший выбор зависит от вашего края и количества вершин.

В случае нескольких цветов вы пытаетесь решить проблему «многополюсный разрез». Это связано с проблемой minimum k-cut, но стандартной ссылкой для этой проблемы является бумага The Complexity of Multiterminal Cuts (которая косвенно связана с ссылкой на статью k). Для более чем двух цветов, по-видимому, если график плоский, проблема все еще разрешима в полиномиальное время; в противном случае это NP-hard, поэтому вы можете использовать свой решатель целых программ, поскольку это еще одна проблема с NP-трудностью.