寻找最长匹配设备链

Question

集合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不一定是循环的，但它可以是。

有没有聪明的方法来解决这个问题？

- krgr

---

这里在问什么？难道不只是从输入构建图吗？ - cdeszaq

你只是想寻找代表所有节点的最短路径吗？ - Michael Dorgan

不，实际上我正在尝试找到最长的。我希望尽可能多的设备与兼容设备连接。 - krgr

Answer 1

我认为这个问题是NP难的，通过从无向最长路径问题的约化来证明，而这个问题已经被证明是NP难的，因为它是从无向哈密顿路径问题的约化中得出的（有关详细信息，请参见Sipser的《计算理论导论》）。

在无向最长路径问题中，我们将一个无向图G =（V，E），以及一对节点u和v和某个数字k作为输入，并希望确定是否存在从u到v的长度至少为k的简单（没有节点出现两次）路径。我们可以使用多项式时间约化将其转换为您的问题，如下所示：

- 对于每个节点v _i ∈V，在A中有一个设备（称之为d _i ）。 - 对于每个边{v _i ，v _j }∈V，在B中有一个设备（称之为e _i，j ）。 - 对于每个节点v _i 和边{v _i ，v _j }，设备d _i 与设备e _i，j 兼容。

此约简具有多项式大小，因为生成的设备总数的大小为| V | + | E |，连接数为2 | E |。此外，我们可以看到，如果在图G中存在从v _i 到v _j 的长度为k的路径，则存在从d _i 到d _j 长度为2k + 1的设备链。具体来说，如果（（v _i1 ，v _i2 ），（v _i2 ，v _i3 ），...，（v _{i k-1} ，v _ik ））是从v _i 到v _j 的简单路径，则链d _i1 →e _i1，i2 →d _i2 →e _i2，i3 →d _i3 →...→e _{i k-1，ik} →d _ik ，反之亦然。因此，我们有一个从无向最长路径到您问题的多项式时间约化，如下所示：

• 给定输入(G, v_i, v_j, k)到无向最长路径问题：
  • 按照上述方式构建A和B集合，并使用上述兼容性C。
  • 检查是否存在从d_i到d_j的长度为2k + 1的设备链。
  • 如果是，请输出“yes”
  • 如果不是，请输出“no”。

通过使用您的问题求解器，此约化以非确定性多项式时间解决了无向最长路径问题，因此您的问题是NP难的。 因此，您不应期望找到一个多项式时间算法来解决问题; 要找到确切的答案可能需要指数时间，除非P = NP。

很抱歉给出负面答案，但我希望这有所帮助！

- templatetypedef

---

那个回复速度真是太快了，让我有点害怕！非常感谢。我确实认为这个问题类似于最长路径问题，感谢您清晰地指出了这一点。一个简短的后续问题（如果在这里允许的话）：如果每个设备只能连接到一个设备，那么这个问题是否变成了稳定婚姻问题，并且运行时间为O(n^2)？ - krgr

Answer 2

这是一个 NP-hard 问题，但是我认为最大环覆盖问题的近似算法可以帮助你（在每个组中，连接大小为0的边缘设备），同时你也可以添加一些额外的节点，并将其与所有其他节点连接，权重为0。例如，这篇论文：Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One 将会对你有所帮助。

- Saeed Amiri