起始位置和一组必须节点之间的最小生成树

Question

起始位置和一组必须节点之间的最小生成树

algorithmsearchgraph-theoryshortest-pathminimum-spanning-tree

4

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

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

我认为我正在寻找的是最小生成树，但修剪了所有不以“必需”节点结尾的分支。这就是斯坦纳树问题吗？
如果我的图形未加权，那么Steiner树和最小生成树的大小是否相同？
关于树的大小，我能说什么呢？例如（最小生成树大小=平均最短路径*＃必需节点...我不认为这是正确的，但基于连通性或其他因素计算平均值将是很好的）。

一些注意事项：

这不是旅行推销问题，因为我不需要每个所需节点之间存在路径，我只想发现每个所需节点。我的图是无向且未加权的（或同样加权）。我的图平均有约100个所需节点，可能有数千个可选节点。

- Ben Holland

根据定义，如果运行您的算法，则最优树将是最小化连接节点的加权路径的树。因此，树上的任何子路径，如果被删除（并且其他路径保持不变），都将是您必须重新创建以重新链接所需元素的最佳路径。 - ninjagecko

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- oldboy · Accepted Answer

我有一组标记为“必需”的节点和一个标记为“起点”的节点，其余节点标记为“可选”。我想找到扩展的最佳节点数，以便在我的第一个扩展是“起点”节点的情况下发现所有必需节点。如果扩展节点的成本可以是任意的，则这是加权Steiner树问题，在合理的复杂性理论假设下，没有多项式时间的近似算法，其比率小于o(log n)。

我相信我正在寻找的是最小生成树，但要修剪所有不以“必需”节点结束的分支。

不，这通常不是最优的。例如，对于以下图形：

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

一个可能的最小生成树看起来像/|\或/\，但是最优解看起来像_|_。

关于树的大小，我能说什么呢？

理论上，您可以通过解决Steiner树整数规划的LP松弛的对偶问题来获得下限（实际上，对于您考虑的这个大小的图形，如果求解器可以直接确定最优的Steiner树，那也不会让人感到惊讶）。

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