Подтвердить что ты не робот

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

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

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

Я идентифицирую позицию A с помощью 24-uple = (xA1, xA2..., xA24), и если я хочу присвоить A node номер 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

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

Я определяю график, определяя отношение соседей каждого node, скажем, node 8 имеет соседей node 7 и node 10

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

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 =...

...

Х = (0,0,..., 1,..., 0)

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

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

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

L (A) = [B, B, C, E, G...]//список neigbors of A (может повторяться)

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), я в L (A))

...

N (X) =...

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

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

Объективная функция

min (Sum (N (Z), Z = A до X)

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

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

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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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