算法发现选择顶点最小生成树 [英] Algorithm to find minimum spanning tree of chosen vertices

问题描述

一个可以使用的Prim算法或Kruskal算法寻找顶点/节点和边缘/链路集合的最小生成树/图。我想要的虽然是一种算法，找到这个集合的最小生成图形，但所得到的曲线图需要包括仅任意选择的节点，而不是所有的节点。这没关系，如果生成的图形包括的不仅仅是那些需要更多的节点。

One can use Prim's algorithm or Kruskal's algorithm to find the minimum spanning tree/graph of a collection of vertices/nodes and edges/links. What I want though, is an algorithm that finds the minimum spanning graph of this collection, but the resulting graph needs to include only arbitrarily chosen nodes, instead of all nodes. It's okay if the resulting graph includes more nodes than just those needed.

有没有这样的算法存在吗？或许，人们可以只使用普里姆（或Kruskal的）算法修改图形只包括所需的节点后？但是，我不知道如何修改图这样做，同时保持其连通性。

Does such an algorithm exist? Perhaps one could just use Prim's (or Kruskal's) algorithm after modifying the graph to include only the needed nodes? But, I'm not sure how to modify the graph to do so while maintaining its connectedness.

举例来说，假设我们有形出发（随链接在括号费用）金刚石：

For example, say we have a diamond shaped starting graph (with costs of links in brackets):

    A
(2)/ \(1)
  B   C
(2)\ /(5)
    D

现在，我们随意决定，只有节点A和D是必要的。如果我们开始在A，我们还是希望它走左边的路，因为：（（2 + 2）≤（1 + 5））。

Now, we arbitrarily decide that only nodes A and D are needed. If we started at A, we'd still want it to take the left path, because ((2 + 2) < (1 + 5)).

假设我们稍微修改图：

    A
(2)/ \(1) (2)
  B   C ------E
(2)\ /(5)
    D

如果我们决定，只有节点A，D和E都需要，我们认识到，以最小的成本的路径不一定是一个具有最少链路。以A - B - D和A - C - ê成本7，但是A - C - D和C - E费用8

If we decide that only nodes A, D, and E are needed, we realize that the path with the minimum cost is not necessarily the one with the fewest links. Taking A--B--D and A--C--E costs 7, but A--C--D and C--E costs 8.

推荐答案

你想找到什么是离散 Steine​​r树。当图中的不是所有的顶点是强制性的，但树被允许分割在可选顶点，问题是NP难题。

What you want to find is a discrete Steiner tree. When not all vertices in the graph are mandatory but the tree is allowed to split at the optional vertices, the problem is NP-hard.

维基说（上面链接）：据认为任意好的近似比例不能在一般在多项式时间内实现的。有一个多项式时间算法，找到一个因素1.39逼近最低斯坦纳树。的

Wikipedia says (linked above) of this problem: it is believed that arbitrarily good approximation ratios cannot in general be achieved in polynomial time. There is a polynomial-time algorithm that finds a factor 1.39 approximation of a minimum Steiner tree.

这篇关于算法发现选择顶点最小生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！