我有一个权重未知、连通的图。我想找到一个包括特定节点集合的连通子图，且尽可能少地包含其他节点。如何实现呢？
为了更准确地表达问题，设G(V,E)为一张权重未知、无向、连通的图，N是V的某个子集。如何找到G(V,E)的最小连通子图G'(V',E')，使得N是V'的子集？
逼近解也是可以的。
为了更准确地表达问题，设G(V,E)为一张权重未知、无向、连通的图，N是V的某个子集。如何找到G(V,E)的最小连通子图G'(V',E')，使得N是V'的子集？
逼近解也是可以的。
5个回答
14
这正是众所周知的NP-hard 斯坦纳树问题。如果没有更多关于您实例的详细信息，很难就适当的算法给出建议。
- Falk Hüffner
6
我之前没有听说过斯泰纳树，但我已经查看了维基百科关于k-最小生成树的页面，我认为这与斯泰纳树的MST版本是相同的。 - hyluka
我认为这并不完全是斯坦纳树问题。首先，被优化的值是顶点数量而不是边长，其次，您不能添加任意顶点。不过，您是正确的，这个问题很接近，研究它的解决方案可能会对手头的问题有所启示。 - Gintautas Miliauskas
4如果将边的长度设置为1，则边的数量将最小化，由于结果子图必须是一棵树，树的边数比顶点少一个，因此这等同于最小化顶点数量。我不明白你所说的“无法添加任意顶点”的意思。 - Falk Hüffner
“任意顶点”是指“欧几里得斯坦纳树”问题，根据维基百科的说法，这是斯坦纳树的原始形式。http://en.wikipedia.org/wiki/Steiner_tree - hyluka
2我明白了，维基百科页面确实有点混淆。我指的是通用的斯坦纳树问题，也称为“图中的斯坦纳树”。 - Falk Hüffner
你好，我有一个非常类似的问题，并在这里发布了一个问题：http://stackoverflow.com/questions/38543608/find-the-minimal-subgraph-that-connects-the-root-node-and-several-special-nod。你能帮忙解决一下吗？谢谢！ - lllllllllllll
6
我想不出一种有效的算法来找到最优解，但是假设您的输入图形是密集的，以下算法可能足够好：
1. 将输入图形 G(V, E) 转换为加权图 G'(N, D)，其中 N 是您想要覆盖的顶点子集，D 是原始图形中相应顶点之间的距离（路径长度）。这将“折叠”所有不需要的顶点到边缘。
2. 计算 G' 的最小生成树。
3. “扩展”最小生成树的方法如下：对于最小生成树中的每条边 d，在图形 G 中取相应路径，并将路径上的所有顶点（包括端点）添加到结果集 V' 中，将路径上的所有边添加到结果集 E' 中。
该算法易于出现次优解。例如，等边三角形具有在角落、边中点和三角形中心的顶点，以及沿边缘和从角落到三角形中心的边缘。要覆盖角落，只需选择三角形的单个中心点即可，但此算法可能会选择边缘。尽管如此，如果图形是密集的，则应该可以正常工作。
1. 将输入图形 G(V, E) 转换为加权图 G'(N, D)，其中 N 是您想要覆盖的顶点子集，D 是原始图形中相应顶点之间的距离（路径长度）。这将“折叠”所有不需要的顶点到边缘。
2. 计算 G' 的最小生成树。
3. “扩展”最小生成树的方法如下：对于最小生成树中的每条边 d，在图形 G 中取相应路径，并将路径上的所有顶点（包括端点）添加到结果集 V' 中，将路径上的所有边添加到结果集 E' 中。
该算法易于出现次优解。例如，等边三角形具有在角落、边中点和三角形中心的顶点，以及沿边缘和从角落到三角形中心的边缘。要覆盖角落，只需选择三角形的单个中心点即可，但此算法可能会选择边缘。尽管如此，如果图形是密集的，则应该可以正常工作。
- Gintautas Miliauskas
5
最简单的解决方案如下：
a) 基于 mst： - 首先，所有节点都在 V' 中 - 构建图 G(V,E) 的最小生成树 - 称为 T。 - 循环：对于 T 中未在 N 中的每个叶节点 v，请从 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）从 N 中删除 p 中的每个节点和 N 中的节点。 --- 重复循环，直到 N 为空。
在算法开始时：使用任何已知的有效算法计算 G 中的所有最短路径。
个人而言，在我的一篇论文中使用了此算法，但它更适用于分布式环境。 假设 N 是我们需要相互连接的节点集。 我们想要构建图 G 的最小连接支配集，并且我们想要为 N 中的节点提供优先级。 我们为每个节点 u 分配唯一的标识符 id(u)。 我们让 w(u) = 0，如果 u 在 N 中，否则为 w(1)。 我们为每个节点 u 创建一对 (w(u)，id(u))。
每个节点 u 构建一个多重继电器节点。也就是说，一个 1-hop 邻居集合 M(u)，使得每个 2-hop 邻居都是至少与 M(u) 中的一个节点相邻的邻居。[M（u）越小，解决方案越好]。 当且仅当： - u 具有所有邻居中最小的一对 (w(u), id(u))，或者 - u 被选择为 M(v) 的一部分，其中 v 是 u 的 1-hop 邻居，其具有最小的 (w(u), id(u))。
-- 当您以集中方式执行此算法时的技巧在于高效计算 2-hop 邻居。我从 O(n^3) 中得到的最佳结果为通过矩阵乘法将其降低到 O(n^2.37)。
-- 我真的很想知道这个最后一个解决方案的近似比率是多少。 我喜欢这个 Steiner 树启发式的参考文献：The Steiner tree problem, Hwang Frank ; Richards Dana 1955- Winter Pawel 1952
a) 基于 mst： - 首先，所有节点都在 V' 中 - 构建图 G(V,E) 的最小生成树 - 称为 T。 - 循环：对于 T 中未在 N 中的每个叶节点 v，请从 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）从 N 中删除 p 中的每个节点和 N 中的节点。 --- 重复循环，直到 N 为空。
在算法开始时：使用任何已知的有效算法计算 G 中的所有最短路径。
个人而言，在我的一篇论文中使用了此算法，但它更适用于分布式环境。 假设 N 是我们需要相互连接的节点集。 我们想要构建图 G 的最小连接支配集，并且我们想要为 N 中的节点提供优先级。 我们为每个节点 u 分配唯一的标识符 id(u)。 我们让 w(u) = 0，如果 u 在 N 中，否则为 w(1)。 我们为每个节点 u 创建一对 (w(u)，id(u))。
每个节点 u 构建一个多重继电器节点。也就是说，一个 1-hop 邻居集合 M(u)，使得每个 2-hop 邻居都是至少与 M(u) 中的一个节点相邻的邻居。[M（u）越小，解决方案越好]。 当且仅当： - u 具有所有邻居中最小的一对 (w(u), id(u))，或者 - u 被选择为 M(v) 的一部分，其中 v 是 u 的 1-hop 邻居，其具有最小的 (w(u), id(u))。
-- 当您以集中方式执行此算法时的技巧在于高效计算 2-hop 邻居。我从 O(n^3) 中得到的最佳结果为通过矩阵乘法将其降低到 O(n^2.37)。
-- 我真的很想知道这个最后一个解决方案的近似比率是多少。 我喜欢这个 Steiner 树启发式的参考文献：The Steiner tree problem, Hwang Frank ; Richards Dana 1955- Winter Pawel 1952
- AJed
1
虽然我最喜欢这种方法，但两者都是启发式算法，对吗？A）显然因为MST在子图中可能会选择随机边，而这些边在子图中可能不是连通的，B）因为随机起点可能导致不同的遍历。但是对我来说，b）似乎是一种更可靠的启发式算法 - 是吗？有没有办法选择一个“好”的起点？最后，如果有情况下a）更好，是否有一种方法可以估计哪种启发式算法更糟糕，给定已知的图形？ - fnl
2
你可以尝试以下方法：
为所需的节点
N创建一个minimal vertex-cover。将这些可能不相连的子图合并成“大”节点。也就是说，对于每个子图，从图中删除它，并用一个新节点替换它。将这组节点称为
N'。对
N'中的节点进行最小顶点覆盖。“解压缩”
N'中的节点。
- aioobe
0
正如已经指出的那样，这是图中的斯坦纳树问题。然而，一个重要的细节是所有边的权重都应该为1。因为对于任何斯坦纳树（V'，E'），|V'| = |E'| + 1，这正好实现了你想要的目标。 为了解决这个问题，我建议使用以下斯坦纳树求解器（透明度：我是其中之一的开发人员）：
对于具有数千条边的图形，通常可以在不到0.1秒的时间内获得最优解。
- daniel
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接