2

对于作业，我必须创建一个Steiner Tree。然而，这不是典型的施泰纳树，因为我们需要使用的图结构不允许插入新的顶点。相反，测试用例定义了 N 个顶点和 M 个边的图结构，同时专门将 X 个顶点标记为目标节点。这些是我们在使用图中的一些、没有或所有未标记的顶点时必须跨越的节点。

我对这个问题的解决方案是

  1. 实现Dijkstra 算法以找到所有目标顶点之间的最短路径
  2. 对于每条最短路径 1:n
    1. 将所有当前选定的路径顶点提取到一个集合中
    2. 将所有剩余的顶点提取到一个集合中
    3. 对于当前选定路径的所有顶点 1:m
      1. 执行 Dijkstra 以找到当前顶点和其他路径顶点之间的最短路径
      2. 如果这会创建生成树，则将路径和长度保存在按长度值排序的优先级队列中
  3. 弹出优先级队列顶部和返回路径

我的问题是这是一个详尽的搜索，它使用 Dijkstra 的初始应用程序来创建一组可能的起始顶点的缩减集，用于比最小生成树更短的路径。

是否有可以解决此问题的启发式或其他算法？

4

1 回答 1

1

在一些帮助下，我为我遇到的类似问题制定了这个答案。与在空间斯坦纳树问题中添加新顶点不同，该图中的新斯坦纳点是位于标记节点之间的路径上的顶点。对于具有 N 个顶点、M 条边、X 需要顶点和 S 找到顶点（沿我们路径的顶点）的图：

  1. 计算所有对最短路径（Floyd-Warshall、Johnson's 等）
  2. 对于 X 中的 k
    1. 从 X 中删除 k，将 k 插入到 S
    2. for v in (X + S) - 两组
      1. 找到从 k 到 v 的最短距离 - 路径 P
    3. 对于 P 中的 u（路径上的所有顶点）
      1. 将 u 插入 S
      2. 如果 u 存在于 k 中，则将 u 从 k 中删除

现在看一下这个算法的作用。我们在 X 中选择一个顶点 k，然后在目标集 X 或结果集 S 中找到到最近的其他顶点的最小距离，并将其命名为 v。然后我们从 {k,u} 开始跟踪节点的路径，将它们插入我们的结果集中。最后，仔细检查并确保 X 中路径上的所有顶点（不应该发生）都从 X 中删除。

您要添加的任何新顶点 c 将与结果集 S 中已有的某个节点具有最小距离。由于 S 中的节点之间的距离最小，因此 c 将是与任何点的最小距离在 S 到 c。例如，如果您有三个节点，A、B 和 C，如果已经发现 A 和 B 之间的距离最小，则添加 C 满足它与 B 的最小距离和距 B 的最小距离路径的要求A到C经过B。

我对离散施泰纳树问题（就是这样）做了一些研究，这是我发现的最好的蛮力解决方案。主要问题将是完成所有对最短路径所需的 O(n^3) 时间，但是最小树的构建应该简单快捷，因为您只需要查找距离信息。我最终使用的实现在 wikipedia 上有很好的概述。

于 2013-05-02T21:55:40.850 回答