寻找最长的匹配设备链

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 ∈ V，A 中有一个设备（称为 d _i）。
• 对于每条边 {vi _, v _j } ∈ V，B 中都有一个设备（称为 e _{i, j}）。
• 对于每个节点 v _i和边 {vi _, v _j }，设备 d _{i与设备 e i, j}兼容。

这种减少具有多项式大小，因为生成的设备总数大小为 |V| + |E| 连接数为2|E|。此外，我们可以看到，图 G 中存在一条从 vi 到 v j 的长度为 k 的路径，_当且_仅当从di到 d _j存在长度为 2k + 1 的设备链。具体来说，if ((vi _{1 , vi 2 ) , ( vi 2 , vi 3 ), ..., (vi k - 1 , vi k ) ) 是从vi到 v j的简单路径，则链 di 1 → e i 1 , i 2 → di 2 → e i 2 , i 3 → di 3 → ... → e i k - 1 , i k → d i k，反之亦然。因此，我们从无向最长路径到问题的多项式时间减少如下：}

• 作为无向最长路径问题的 输入 (G, v _i , v _j , k)给出：
  • 如上构造集合 A 和 B，并具有如上的兼容性 C。
  • _{检查从 d i}到 d _j是否存在长度为 2k + 1 的设备链。
  • 如果是，则输出“yes”
  • 如果不是，则输出“否”。

这种减少使用问题的求解器解决了非确定性多项式时间内的无向最长路径问题，因此您的问题是 NP 困难的。因此，您不应期望为您的问题找到多项式时间算法；除非 P = NP，否则找到准确答案可能需要指数时间。

很抱歉给出否定的答案，但希望这对您有所帮助！