我正在尝试解决以下图形练习:
在无向加权图中，有 V 个顶点和 E 个边。从标记为 0 的顶点开始，找到访问 T(T<=V) 个顶点所需的最小权重。此外，如果两个访问的顶点之间存在边，则其权重设置为 0。
这不是一个典型的旅行商问题，因为附加条件是，如果访问两个顶点，它们之间的边的权重将减少到 0。
如果 T == V，则使用 Prim 的最小生成树算法解决该问题，但由于您不必访问所有顶点，因此这并不总是返回最小权重。
我考虑过找到最小生成树，然后切割不会妨碍我到达所有“目标”顶点的能力的每条边，但这似乎有点过分，而且可能不正确。
有什么想法吗？
编辑: 我给你举个例子。假设我们有一个图，有 4 个顶点，标记为 0、1、2 和 3。我们有以下边(从、到、权重): (0,1,1) (0,2,2) (1,3,4) (2,3,1) 最小生成树将包含边:(0,1,1)、(0,2,2) 和(2,3,1)。有了它，每个顶点都可以从 0 开始到达。但是，练习的目标是到达 T 个顶点。话虽如此，例如，我们可能只需要到达顶点 2 和 3，从而不需要边 (0,1,1)，因此到达目标顶点所需的总权重是 2+1，而不是 1 +2+1。
最佳答案
看来您的问题本质上是 Steiner tree problem ，已知这是 NP 困难的。
确实，您有一个无向加权图(V，E)。 给定 T(V 的子集)，您希望找到一棵总权重最小且覆盖 T 的所有顶点的树。
这是一个例子，其中最明显的贪婪想法不起作用。
假设我们的图是一个不规则四面体的顶点和边ABCD哪里AB=BC=CA=5和AD=BD=CD=3 。
如果我们想将 A、B 和 C 连接在一起，我们能做的最好的就是使用边 AD , BD和CD总重量为9 。
如果我们决定不使用D ，我们必须取长度为 5 的两条边。相反，总重量为 10 。
然而，集合 ABC 的每个两顶点子集使用权重的一个直接边缘 5 ( AB 、 BC 或 CA )并且没有到顶点 D 的边的最优解。
(哎呀!在三维欧几里得几何中不可能有精确的长度。不过，它可以作为一个例子。)
关于algorithm - 旅行商最小生成树变体，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29288591/