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

Question

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

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

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

  c = pairCost (i, j)

• Общая стоимость затем вычисляется как

  totalCost = 1/2 sum_ {i = 1: N} (pairCost (i, pair (i)))

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

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

Некоторые дальнейшие заметки:

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

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

Answer 1

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

Answer 2

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

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