找到最长的匹配设备链

StackOverflow https://stackoverflow.com/questions/8317962

  •  25-10-2019
  •  | 
  •  

题

设置A具有N设备。设置B具有M设备。 A中的某些设备与B中的设备兼容，并且B中的某些设备与A中的设备兼容。

我想要尽可能多的兼容设备相互连接。 （不必在B中的A和B中使用A和B中的设备互相兼容。）

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

最终，所有设备（或除两个设备，如果“端”不符合）应链接在一起1 On 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不一定是循环的，但可以。

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

有帮助吗？

解决方案

我认为，这个问题是通过从无向路径问题中减少的，这是NP的困扰，这是通过从无向的汉密尔顿路径问题中的减少来减少的（参见sipser's 计算理论简介 有关原因的详细信息）。

在无方向的最长路径问题中，我们被以输入为无方向的图G =（v，e），以及一对节点u和v和v和一些k，并希望确定是否有简单（否）节点出现两次）从u到v的路径至少至少k。我们可以使用多项式时间缩短如下：将其转换为您的问题：

  • 对于每个节点V一世 ∈V，A中有一个设备（称为D一世).
  • 对于每个边缘{v一世, ，vj}∈V，b中有一个设备（称其为e我，j).
  • 对于每个节点V一世 和edge {v一世, ，vj}，设备D一世 与设备E兼容我，j.

此减少具有多项式的大小，因为生成的设备总数是大小| v | + | e |连接的数量为2 | e |。此外，我们可以看到V有v的长度k一世 到vj 在Graph G IFF中，有一系列来自D的设备长度为2K + 1一世 到dj. 。具体而言，if（（v一世1, ，v一世2），（v一世2, ，v一世3），...（v一世K -1, ，v一世k））是v的简单路径一世 到vj, ，然后链D一世1 →e一世1, ， 一世2 →d一世2 →e一世2, ， 一世3 →d一世3 →...→E一世K -1, ， 一世k →d一世k 和反之亦然。因此，我们从无方向性的最长途径到您问题的多项式时间减少，如下所示：

  • 作为输入（g，v）给出一世, ，vj, ，k）到无方向的最长路径问题：
    • 如上所述，构造集合A和B如上所述。
    • 检查是否有一系列长度为2k + 1的设备。一世 到dj.
    • 如果是这样，输出“是”
    • 如果没有，输出“否”。

这种还原解决了使用求解器解决问题的非确定多项式时间中无向最长的路径问题，因此您的问题是NP-HARD。结果，您不应该期望为您的问题找到多项式时间算法；除非p = np，否则找到确切的答案可能需要指数时间。

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

其他提示

这是np- hard，但我认为最大循环覆盖问题近似可以帮助您（在每个组链接设备中，尺寸为0），您也可以添加一些额外的节点，这些节点由重量0连接到所有其他节点0）这张纸： 近似于重量为零的有向图中的最大重量循环覆盖物和一个 会帮助你。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top