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

Question

Установите A Имеет N -устройства. Набор B имеет M -устройства. Некоторые устройства в A совместимы с устройствами в B, а некоторые устройства в B совместимы с устройствами в A.

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

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

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

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-Hard из-за снижения из-за неопределенной проблемы с самой длинной дорожкой, которая, как известно, является NP-Hard из-за снижения из-за неопределенной проблемы гамильтонианского пути (см. Sipser's Введение в теорию вычислений Для получения подробной информации о том, почему).

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

• Для каждого узла V_я ∈ V, в a есть устройство (Call It D_я).
• Для каждого края {v_я, v_Дж} ∈ V, в B есть устройство (назовите e_{я, j}).
• Для каждого узла V_я и Edge {V_я, v_Дж}, устройство D_я совместим с устройством E_{я, j}.

Это сокращение имеет полиномиальный размер, поскольку общее количество генерируемых устройств имеет размер | V | + | E | и количество соединений составляет 2 | e |. Более того, мы видим, что есть путь длины k от V_я В_Дж На графике g Iff есть цепочка устройств длины 2K + 1 из D_я до д_Дж. Анкет В частности, if ((v_я1, v_я2), (V_я2, v_я3), ..., (v_{яk - 1}, v_яk)) - простой путь от V_я В_Дж, затем цепь D_я1 → E._{я1, я2} → D._я2 → E._{я2, я3} → D._я3 → ... → E_{яk - 1, яk} → D._яk наоборот. Таким образом, у нас есть снижение полиномиального времени от неправомерного длительного пути к вам проблеме следующим образом:

• Дано в качестве входного (g, v_я, v_Дж, k) к неправомерной задаче самого длинного пути:
  • Создайте наборы A и B, как указано выше, с совместимостью C, как указано выше.
  • Проверьте, есть ли цепочка устройств длины 2K + 1 из D_я до д_Дж.
  • Если так, вывод "да"
  • Если нет, вывод "нет".

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

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

Answer 2

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