hyl*_*uka 19 algorithm graph-theory graph subgraph graph-algorithm
我有一个未加权的连接图.我想找到一个连接的子图,它肯定包含一组特定的节点,并且尽可能少的附加内容.怎么可以实现呢？
为了以防万一,我将使用更精确的语言重述问题.设G(V,E)为未加权,无向连通图.设N是V的某个子集.找到G(V,E)的最小连通子G'(V',E')的最佳方法是什么,N是V'的子集？
近似没问题.
Fal*_*ner 10
这正是众所周知的NP-hard Steiner Tree问题.如果没有关于实例的详细信息,很难就适当的算法提供建议.
我无法想到找到最佳解决方案的有效算法,但假设您的输入图是密集的,以下可能会运行得很好:
将输入图转换G(V, E)为加权图G'(N, D),其中N是要覆盖的顶点子集,并且D是原始图中相应顶点之间的距离(路径长度).这将"折叠"您不需要的所有顶点到边缘.
计算最小生成树G'.
通过以下过程"展开"最小生成树:对于d最小生成树中的每个边,在图中采用相应的路径,G并将路径上的所有顶点(包括端点)添加到结果集V',并将路径中的所有边添加到结果集E'.
该算法很容易绊倒以提供次优解决方案.示例案例:等边三角形,其中在拐角处,在边的中点和三角形的中间存在顶点,并且沿着边的边缘以及从角的边缘到三角形的中间.为了覆盖角落,它足以选择三角形的单个中点,但是这个算法可能会选择边.尽管如此,如果图表密集,它应该可以正常工作.
最简单的解决方案如下：
a) 基于 mst： - 最初，V 的所有节点都在 V' 中 - 构建图 G(V,E) 的最小生成树 - 称其为 T。
- 循环：对于 T 中不在的每个叶子 v N，从 V' 中删除 v。
- 重复循环直到 T 中的所有叶子都在 N 中。
b）另一种解决方案如下 - 基于最短路径树。
- 选取 N 中的任何节点，称其为 v，让 v 成为树 T = {v} 的根。- 从 N 中删除 v。
在算法开始时：使用任何已知的有效算法计算 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))。或者在 M(v) 中选择 u，其中 v 是 u 的 1 跳邻居，具有最小的 (w(u),id(u))。
-- 以集中方式执行此算法的技巧是高效计算 2 跳邻居。我从 O(n^3) 得到的最好结果是通过矩阵乘法得到 O(n^2.37)。
-- 我真的很想知道这最后一个解决方案的近似比是多少。
我喜欢这个关于 steiner 树启发式的参考：The Steiner tree problem, Hwang Frank；理查兹·达纳 1955-1952 年冬季帕维尔