4

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

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

  • 我相信我正在寻找的是最小生成树，但会修剪所有不以“必需”节点结尾的分支。这是斯坦纳树问题吗？
  • 如果我的图表未加权，Steiner 树和最小生成树的大小是否相同？
  • 如果我能对树的大小说些什么呢？即类似（最小生成树大小的大小=平均最短路径*＃所需节点......我认为这不是真的，但能够根据连通性或其他东西计算平均值会很好）。

几点注意事项：

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

1 回答 1

3

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

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

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

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

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

一种可能的 MST 看起来像/|\或被/\修剪时，但最佳解决方案看起来像_|_.

如果我能对树的大小说些什么呢？

从理论上讲，您可以通过求解 Steiner 树的整数程序的 LP 松弛的对偶来获得下限（实际上使用您正在考虑的大小的图形，如果求解器可以确定，我不会感到惊讶最优的 Steiner 树）。

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

于 2012-04-07T17:06:14.167 回答