查找最长的匹配设备链

发布于 2024-12-18 19:00:46 字数 739 浏览 0 评论 0原文

A 组有 n 台设备。 B组有m台设备。 A 中的某些设备与 B 中的设备兼容，B 中的某些设备与 A 中的设备兼容

。我希望尽可能多的兼容设备相互连接。（A 中的设备 a 和 B 中的设备 b 不必相互兼容。）

为清楚起见进行编辑：任何设备都可以链接到 0、1 或 2 个其他设备，但不能链接到其自身。

最终，所有设备（或者除了两个之外的所有设备，如果“末端”不相交）都应该一对一地链接在一起。可以将任何一个设备链接到任何其他设备。但是 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 不一定是循环的，但它可以是。

有什么聪明的方法可以解决这个问题吗？

原文

Set A has n devices. Set B has m devices. Some devices in A are compatible with the devices in B, and some devices in B are compatible with those in A.

I want as many compatible devices connected to each other as possible. (It's not necessary to have the device a in A and b in B to be mutually compatible.)

Edit for clarity: any device can be linked to 0, 1 or 2 other devices, but not itself.

Eventually all devices (or all but two, if the "ends" don't meet) should be linked together 1 on 1. It's possible to link any one device to any other device. But no device in A are compatible with any device in A (but they are linkable), and the same holds true for devices in 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

Then the graph G

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

is an optimal graph.

G doesn't have to be cyclic, but it can be.

Are there any clever ways to approach this?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

浅听莫相离 2024-12-25 19:00:46

我相信这个问题是 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 开始的长度为 2k + 1 的设备链_i 到 d_j。具体来说，如果 ((v_i₁, v_i₂), (v_i₂, v_i₃), ..., (v_{i_{k - 1}}, v_{i_k})) 是一条简单的路径v_i 到 v_j，然后链 d_i₁ → e_i₁，i₂ → d_i₂ → e_{i₂ , i₃} → d_i₃ → ... → 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”
- 如果没有，输出“no”。

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

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

I believe that this problem is NP-hard by a reduction from undirected longest path problem, which is known to be NP-hard by a reduction from the undirected Hamiltonian path problem (see Sipser's Introduction to the Theory of Computation for details on why).

In the undirected longest path problem, we are given as input an undirected graph G = (V, E), along with a pair of nodes u and v and some number k, and want to determine whether or not there is a simple (no node appears twice) path from u to v of length at least k. We can convert this into your problem using a polynomial-time reduction as follows:

For each node v_i ∈ V, there is a device in A (call it d_i).
For each edge {v_i, v_j} ∈ V, there is a device in B (call it e_{i, j}).
For each node v_i and edge {v_i, v_j}, device d_i is compatible with device e_{i, j}.

This reduction has polynomial size, since the total number of devices generated is of size |V| + |E| and the number of connections is 2|E|. Moreover, we can see that there is a path of length k from v_i to v_j in graph G iff there is a chain of devices of length 2k + 1 from d_i to d_j. Specifically, if ((v_i₁, v_i₂), (v_i₂, v_i₃), ..., (v_{i_{k - 1}}, v_{i_k})) is a simple path from v_i to v_j, then the chain d_i₁ → e_{i₁, i₂} → d_i₂ → e_{i₂, i₃} → d_i₃ → ... → e_{i_{k - 1}, i_k} → d_{i_k} and vice-versa. We thus have a polynomial-time reduction from undirected longest path to you problem as follows:

Given as input (G, v_i, v_j, k) to the undirected longest path problem:
- Construct the sets A and B as above, with compatibilities C as above.
- Check whether there is a chain of devices of length 2k + 1 from d_i to d_j.
- If so, output "yes"
- If not, output "no."

This reduction solves the undirected longest path problem in nondeterministic polynomial time using a solver for your problem, and so your problem is NP-hard. As a result, you should not expect to find a polynomial-time algorithm for your problem; finding an exact answer is likely to take exponential time unless P = NP.

Sorry to give a negative answer, but I hope this helps!

回复收藏 0 原文