Алгоритм поиска оптимальных пар узлов в шестиугольном графе

Я ищу алгоритм для поиска пар соседних узлов на шестиугольном (сотовом) графе, который минимизирует функцию стоимости.

  • каждый узел соединен с тремя соседними узлами
  • каждый узел "i" должен быть связан с ровно одним соседним узлом "j".

  • каждая пара узлов определяет функцию стоимости

    с = цена пары ( я , j )

  • Тогда общая стоимость рассчитывается как

    totalCost = 1/2 sum_{i=1:N} (pairCost(i, пара(i)) )

Где пара(i) возвращает индекс узла, с которым связан "i". (Сумма делится на два, потому что сумма учитывает каждый узел дважды). У меня вопрос: как мне найти пары узлов, которые минимизируют общую стоимость?

Связанное изображение должно прояснить, как будет выглядеть решение (толстая красная линия указывает на пару):

введите здесь описание изображения

Некоторые дополнительные примечания:

  • Меня не волнуют крайние узлы
  • Моя функция стоимости что-то вроде || v(i) - v(j) || (расстояние между векторами, связанными с узлами)
  • Я предполагаю, что проблема может быть NP-сложной, но мне действительно не нужно действительно оптимальное решение, достаточно хорошего.
  • Наивные алгоритмы, как правило, получают узлы, которые «заблокированы», то есть все их соседи заняты.

Примечание: я не знаком с обычной номенклатурой в этой области (это теория графов?). Если бы вы могли помочь с этим, то, возможно, это позволило бы мне найти решение в литературе.


graph algorithm mathematical-optimization graph-algorithm complexity-theory
person svantana    schedule 23.06.2011    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Это пример задачи сопоставления максимального веса на общем графике. конечно, вам придется свести на нет ваши веса, чтобы сделать это проблемой сопоставления минимального веса. алгоритм дорожек, деревьев и цветов Эдмондса (ссылка на Википедию) решит эту проблему за вас (есть также общедоступный Реализация Python). Простая реализация — O(n4) для n вершин, но ее можно уменьшить до O(n1/2m) для n вершин и m ребер с использованием алгоритма Микали и Вазирани (извините, не удалось найти PDF для этого).

person Tamás    schedule 23.06.2011
comment
Спасибо, алгоритм Edmonds' Blossom решает проблему. К сожалению, его сложность больше, чем квадрат числа узлов (для моего случая). Поскольку я рассматриваю довольно большие графики, мне нужно будет найти более быстрый алгоритм. Можно было бы использовать однородную структуру моего графика, а если нет, то, кажется, существует множество эвристик для быстрых приближенных решений. - person svantana; 23.06.2011
comment
Попробуйте найти реализацию алгоритма Микали и Вазирани; поскольку ваш граф шестиугольный, m асимптотически равно 3n, что доводит его сложность до O(n‹sup›3/2‹/sup›). - person Tamás; 23.06.2011

arrow_upward
0
arrow_downward

Похоже, это связано с проблемой минимального покрытия ребер с дополнительным ограничением, что может быть только одно ребро на узел, и что вы пытаетесь минимизировать стоимость, а не количество ребер. Может быть, вы сможете найти некоторые ответы, выполнив поиск по этой фразе.

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

person Aasmund Eldhuset    schedule 23.06.2011