Поиск самых длинных цепочек подходящих устройств

Question

Set A имеет n устройств.Набор B имеет m устройств.Некоторые устройства в A совместимы с устройствами в B, а некоторые устройства в B совместимы с устройствами в A.

Я хочу подключить как можно больше совместимых устройств друг к другу.(Необязательно, чтобы устройства a в A и b в B были взаимно совместимы.)

Правка для ясности : любое устройство может быть связано с 0, 1 или 2 другими устройствами, но не сам по себе.

В конечном итоге все устройства (или все, кроме двух, если «концы» не встречаются) должны быть связаны друг с другом 1 на 1. Можно связать любое одно устройство с любым другим устройством.Но ни одно устройство в A не совместимо с каким-либо устройством в A (но они связываются ), и то же самое относится и к устройствам в B.

If I have A = {a1,a2,a3}, B = {b1,b2,b3} and n=m=3

a1 is compatible with b1,b2
a2 is compatible with b1
a3 is compatible with b1
b1 is compatible with a1,a3
b2 is compatible with a1
b3 is compatible with a1

Тогда график G

a1 <-> b2 <-> a2 <-> b1 <-> a3 <-> b3 <-> a1

- оптимальный график.

G не обязательно должен быть циклическим, но это может быть.

Есть ли какие-нибудь умные способы приблизиться к этому?

Answer 1

Я полагаю, что эта проблема является NP-трудной из-за сокращения от проблемы ненаправленного длинного пути, которая, как известно, является NP-трудной из-за сокращения от проблемы ненаправленной гамильтоновой траектории (см. Sipser: Введение в теорию вычислений , чтобы узнать, почему).

В задаче с неориентированным длинным путем в качестве входных данных нам дается неориентированный граф G = (V, E) вместе с парой узлов u и v и некоторым числом k, и мы хотим определить, существует ли простой (ни один узел не появляется дважды) путь от u до v длиной не менее k. Мы можем преобразовать это в вашу проблему, используя сокращение полиномиального времени следующим образом:

• Для каждого узла v _i & in; V, есть устройство в A (назовите его d _i ).
• Для каждого ребра {v _i , v _j } & in; V, в B есть устройство (назовите его e _{i, j} ).
• Для каждого узла v _i и ребра {v _i , v _j } устройство d _i совместимо с устройством e _{i, j} .

Это уменьшение имеет полиномиальный размер, так как общее количество генерируемых устройств имеет размер | V | + | E | и количество соединений составляет 2 | E |. Кроме того, мы можем видеть, что существует путь длины k от v _i до v _j в графе G, если существует цепочка устройств длины 2k + 1 от d _i до d _j . В частности, если ((v _{i 1} , v _{i 2} ), (v _{i 2} , v _{i 3} ), ..., (v _{i k - 1} , v _{i k} )) - это простой путь от v _i до v _j , затем цепочка d _{i 1} & rarr; e _{i 1 , i 2} & rarr; d _{i 2} & rarr; e _{i 2 , i 3} & rarr; d _{i 3} & rarr; ... & rarr; e _{i k - 1 , i k} & rarr; d _{i k} и наоборот. Таким образом, мы имеем полиномиальное сокращение времени от ненаправленной самой длинной проблемы к вам следующим образом:

• В качестве входных данных (G, v _i , v _j , k) для задачи с ненаправленным длинным путем:
  • Создайте множества A и B, как указано выше, с совместимостью C, как указано выше.
  • Проверьте, существует ли цепочка устройств длиной 2k + 1 от d _i до d _j .
  • Если это так, выведите «yes»
  • Если нет, выведите «no».

Это сокращение решает проблему ненаправленного длинного пути в недетерминированный полиномиальный момент времени с использованием решателя для вашей задачи, поэтому ваша задача NP-трудна. В результате вы не должны ожидать, что найдете алгоритм с полиномиальным временем для вашей задачи; поиск точного ответа может занять экспоненциальное время, если P = NP.

Извините, что дал отрицательный ответ, но я надеюсь, что это поможет!

Answer 2

Это сложно, но я думаю, что аппроксимации задачи покрытия максимального цикла могут вам помочь (в каждой группе устройства связи с ребром размера 0), также вы можете добавить дополнительный узел, который подключен ко всем остальным узлам весом 0)Например, эта статья: Вам поможет аппроксимация обложек циклов максимального веса на ориентированных графиках с нулевыми и равными весами *. 1002 *.