23

我有一个未加权的连接图。我想找到一个连接的子图,它肯定包含一组特定的节点,并且尽可能少的额外节点。这怎么可能实现?

以防万一,我将使用更精确的语言重申这个问题。令 G(V,E) 是一个未加权、无向、连通图。让 N 是 V 的某个子集。找到 G(V,E) 的最小连通子图 G'(V',E') 以使 N 是 V' 的子集的最佳方法是什么?

近似值很好。

4

4 回答 4

12

这正是著名的 NP-hard Steiner Tree问题。如果没有关于您的实例是什么样子的更多详细信息,就很难就适当的算法提供建议。

于 2010-10-20T13:00:49.397 回答
6

我想不出一种有效的算法来找到最佳解决方案,但假设您的输入图是密集的,以下可能工作得很好:

  1. 将输入图转换G(V, E)为加权图G'(N, D),其中N是您要覆盖的顶点子集,D是原始图中相应顶点之间的距离(路径长度)。这会将您不需要的所有顶点“折叠”成边缘。

  2. 计算 的最小生成树G'

  3. 通过以下过程“扩展”最小生成树:对于d最小生成树中的每条边,取图中对应的路径,G并将路径上的所有顶点(包括端点)添加到结果集V',并将路径中的所有边添加到结果集E'

这个算法很容易出错,给出次优的解决方案。示例:等边三角形,在角处、边中点和三角形中间有顶点,边沿边和从角到三角形的中间。为了覆盖角落,选择三角形的单个中间点就足够了,但是这个算法可能会选择边。尽管如此,如果图形很密集,它应该可以正常工作。

于 2010-10-20T08:25:01.353 回答
5

最简单的解决方案如下:

a) 基于 mst: - 最初,V 的所有节点都在 V' 中 - 构建图 G(V,E) 的最小生成树 - 将其称为 T。
- 循环:对于 T 中不在的每个叶子 v N,从 V' 中删除 v。
- 重复循环,直到 T 中的所有叶子都在 N 中。

b)另一种解决方案如下 - 基于最短路径树。
- 选择 N 中的任何节点,称其为 v,令 v 为树 T = {v} 的根。- 从 N 中删除 v。

  • 循环:1)从T中的任何节点和N中的任何节点中选择最短路径。最短路径p:{v,...,u}其中v在T中,u在N中。2)p中的每个节点被添加到 V'。3) p 和 N 中的每个节点都从 N 中删除。 --- 重复循环,直到 N 为空。

在算法开始时:使用任何已知的有效算法计算 G 中的所有最短路径。

就个人而言,我在我的一篇论文中使用了这个算法,但它更适合分布式环境。让 N 是我们需要互连的节点集。我们想要构建图 G 的最小连通支配集,并且我们想要优先考虑 N 中的节点。我们给每个节点 ua 唯一标识符 id(u)。如果 u 在 N 中,我们让 w(u) = 0,否则 w(1)。我们为每个节点 u 创建对 (w(u), id(u))。

  • 每个节点 u 构建一个多集中继节点。也就是说,一组 M(u) 的 1 跳邻居使得每个 2 跳邻居都是 M(u) 中至少一个节点的邻居。[最小的M(u),更好的解决方案]。

  • u 在 V' 中当且仅当: u 在其所有邻居中具有最小的对 (w(u), id(u))。或者 u 在 M(v) 中被选中,其中 v 是 u 的 1-hop 邻居,具有最小的 (w(u),id(u))。

-- 以集中方式执行此算法的技巧是高效计算 2 跳邻居。我可以从 O(n^3) 得到的最好的结果是通过矩阵乘法得到 O(n^2.37)。

- 我真的很想知道最后一个解决方案的近似比率是多少。

我喜欢斯坦纳树启发式的参考:斯坦纳树问题,黄弗兰克;理查兹·达纳 1955- 温特·帕维尔 1952

于 2012-09-04T02:44:00.573 回答
2

您可以尝试执行以下操作:

  1. 为所需节点创建最小顶点覆盖N

  2. 将这些可能未连接的子图折叠成“大”节点。也就是说,对于每个子图,将其从图中移除,并用新节点替换它。调用这组节点N'

  3. 对 中的节点进行最小顶点覆盖N'

  4. “解包” 中的节点N'

不确定它是否为您提供了某个特定范围内的近似值。你甚至可以欺骗算法做出一些非常愚蠢的决定。

于 2010-10-20T07:58:02.667 回答