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 回答