algorithm - 起始位置和一组所需节点之间的最小生成树

Question

我正在尝试确定最佳搜索案例，以便与我编写的搜索算法进行比较。

我有一组标记为“必需”的节点和一个标记为“开始”的节点，其余标记为“可选”。我想找到我需要扩展的最佳节点数以发现所有需要的节点，因为我的第一个扩展是“开始”节点。

• 我相信我正在寻找的是最小生成树，但修剪掉了所有不以“必需”节点结尾的分支。这是Steiner tree problem吗？
• 如果我的图没有加权，Steiner 树的大小和 最小生成树是否相同？
• 关于这棵树的大小，我能说些什么吗？即类似于(最小生成树大小的大小 = 平均最短路径 * # 所需的节点......我不认为这是真的，但能够根据连通性或其他东西计算平均值会很好)。

一些注意事项:

1. 这不是旅行销售问题，因为我不需要路径 存在于每个必需的节点之间，我只想发现每个 所需节点。
2. 我的图表是无向且未加权的(或就此而言具有同等权重)
3. 我的图表平均有大约 100 个必需节点，可能还有数千个可选节点

Answer 1

I have a set of nodes marked "required" and a node marked "start", the rest are marked "optional". I want to find the optimal number of nodes I would need to expand to discover all of the required nodes given that I my first expand is the "start" node.

如果扩展节点的成本可以是任意的，那么这就是节点加权斯坦纳树问题，在合理的复杂性理论假设下，没有多项式时间近似算法，其比率为 o(log n ).

I believe what I am looking for is the minimum spanning tree, but pruned of all branches that do not end in a "required" node.

不，这通常不是最优的。例如，用图

       s
      /|\
     / | \
    *  |  *
   /   |   \
  /    |    \
 r1----*----r2,

一个可能的 MST 在修剪后看起来像 /|\ 或 /\，但最佳解决方案看起来像 _|_。

What if anything can I say about the size of the tree?

从理论上讲，您可以通过求解 Steiner 树整数程序的 LP 松弛的对偶来获得下界(实际上使用您正在考虑的大小的图，如果 a求解器可以直接确定最优的 Steiner 树)。

然而，实际上，这并不是人们评价搜索算法的方式。