Разработка алгоритма назначения узлов графам

Question

У меня есть теоретико-графическая (которая также связана с комбинаторикой) проблема, которая проиллюстрирована ниже, и задаюсь вопросом, каков наилучший подход к разработке алгоритма для ее решения.

Учитывая 4 разных графа из 6 узлов (под разными, я имею в виду разные структуры, например, STAR, LINE, COMPLETE и т. Д.) И 24 уникальных объекта, разработайте алгоритм для назначения этих объектов этим 4 графам 4 раза , так что количество повторяющихся соседей на графиках по 4 присваиваниям равно , сведено к минимуму . Например, если объект A и B являются соседями на 1 из 4 графиков в одном назначении, то в лучшем случае , A и B будут не снова быть соседями в остальных 3 назначения.

Очевидно, степень, в которой может идти такая минимизация, зависит от конкретных приведенных структур графов. Но меня больше интересует общее решение здесь, чтобы при любых 4 графовых структурах такая минимизация гарантировалась как результат алгоритма.

Любое предложение / идея решения этой проблемы приветствуется, и некоторого псевдокода вполне может быть достаточно для иллюстрации проекта. Спасибо.

Answer 1

Представление:

У вас есть 24 элемента, я назову эти элементы от A до X (24 первых буквы). Каждый из этих элементов будет иметь место на одном из 4 графиков. Я назначу число 24 узлам 4 графиков от 1 до 24.

Я буду обозначать позицию A с помощью 24-uple = (xA1, xA2 ..., xA24), и если я хочу назначить A для узла номер 8 для примера, я напишу (xa1, Xa2. .xa24) = (0,0,0,0,0,0,0,1,0,0 ... 0), где 1 находится на позиции 8.

Можно сказать, что A = (xa1, ... xa24)

e1 ... e24 - единичные векторы (от 1,0 ... 0) до (0,0 ... 1)

примечание об операторе '.':

• A.e1 = xa1
• ...
• X.e24 = Xx24

Существуют некоторые ограничения для A, ... X с этими обозначениями:

Xii находится в {0,1} и

Сумма (Xai) = 1 ... Сумма (Xxi) = 1

Сумма (Xa1, xb1, ... Xx1) = 1 ... Сумма (Xa24, Xb24, ... Xx24) = 1

Поскольку один элемент может быть назначен только одному узлу.

Я определю граф, определив отношение соседей каждого узла, допустим, что у узла 8 есть соседний узел 7 и узел 10

, чтобы проверить, что A и B являются соседями на узле 8 для примера I nedd:

A.e8 = 1 и B.e7 или B.e10 = 1, тогда мне просто нужно A.e8 * (B.e7 + B.e10) == 1

в функции isNeighborInGraphs (A, B) я проверяю это для каждого узла и получаю один или ноль в зависимости от окрестности.

нотации:

• 4 графика из 6 узлов, положение каждого элемента определяется целым числом от 1 до 24. (От 1 до 6 для первого графика и т. Д.)
• e1 ... e24 - единичные векторы (от 1,0,0 ... 0) до (0,0 ... 1)
• Пусть A, B ... X - N элементов.

A = (0,0 ..., 1, ..., 0) = (xa1, xa2 ... xa24)

B = ...

...

X = (0,0, ..., 1, ..., 0)

• График описания:

IsNeigborInGraphs (A, B) = A.e1 * B.e2 + ... // если 1 и 2 являются соседями в одном графе для примера

• Состояние системы:

L (A) = [B, B, C, E, G ...] // список соседки А (могут повторяться)

actualise(L(A)):
for element in [B,X]
if IsNeigbotInGraphs(A,Element)
L(A).append(Element)
endIf
endfor

• объективные функции

N (A) = len (L (A)) + Sum (IsneigborInGraph (A, i), i в L (A))

...

N (X) = ...

Описание алгоритма

1. начать с начальной позиции A = e1 ... X = e24
2. Актуализировать L (A), L (B) ... L (X)
3. Решите это (с решателем, усиление для пример будет работать, я думаю, так как это нелинейная оптимизация проблема):

Целевая функция

мин (сумма (N (Z), Z = от А до Х)

Ограничения:

Сумма (Xai) = 1 ... Сумма (Xxi) = 1

Сумма (Xa1, xb1, ... Xx1) = 1 ... Сумма (Xa24, Xb24, ... Xx24) = 1

Вы получите лучшее решение

4. Повторите шаги 2 и 3, еще 3 раза.

Answer 2

Если все четыре графика равны K_6, то лучшее, что вы можете сделать, - это выбрать 4 набора разбиений ваших 24 объектов на 4 набора, каждый из которых имеет мощность 6, так, чтобы у парных пересечений любых двух наборов было максимально 2. это можно сделать, выбрав множество разделов, которые находятся максимально далеко друг от друга на диаграмме Хассе из множества разделов с частичным порядком, заданным уточнением. Общий случай гораздо сложнее, но, возможно, вы все же можете начать с этого грубого приближения решения, а затем понять, какой вершине назначен какой объект в четырех назначениях.

Answer 3

Если это как-то связано с реальным миром, то вряд ли у вас обязательно должно быть решение, которое является истинным минимумом. Близко к минимуму должно быть достаточно хорошо, верно? Если это так, вы можете многократно выполнять 4 назначения случайным образом и проверять результаты, пока у вас не истечет время, или вы не найдете достаточно хорошего решения, или, кажется, не перестаете улучшать свое лучшее решение.

Answer 4

Предполагая, что вы не хотите циклически повторять все комбинации и каждый раз вычислять сумму и выбирать самую низкую, вы можете реализовать минимальную задачу (решаемую в зависимости от ваших ограничений с помощью либо средства линейного программирования, то есть механизмов симплексного алгоритма, либолинейный решатель, гораздо сложнее говорить с точки зрения времени) с ограничениями на ваши переменные (24) в зависимости от формы вашего пути.Вы также можете использовать бесплатное программное обеспечение, такое как LINGO / LINDO, для быстрого создания модели теории решений и проверки ее правильности (хотя вам нужны понятия теории решений)