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

Question

我正试图确定最佳搜索情况以与我写的搜索算法进行比较。我有一组标记为“必需”的节点和一个标记为“开始”的节点，其余标记为“可选”。我想找到我需要扩展的节点的最佳数量，以便发现所有必需的节点，因为我的第一个扩展是“开始”节点。

• 我相信我正在寻找的是最小生成树，但修剪了所有不以“必需”节点结尾的分支。这是Steiner tree problem？
• 如果我的图未加权，那么Steiner树的大小和最小生成树的大小是否一样？
• 如果有什么话我可以说关于树的大小？即类似的东西（最小生成树大小的大小=平均最短路径*＃所需节点...我不认为这是真的，但它能很好地计算基于连通性或某物的平均值）。

的几个注意事项：

1. 这不是旅行的销售问题，因为我并不需要一个路径 每个需要的节点之间存在，我只是想探索每个 需要的节点。
2. 我是无向图和加权（或相等地加权为此事）
3. My图表具有约100所需的节点的平均值，并且甚至数千可选节点

Answer 1

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

如果扩展一个节点的成本可以是任意的，则这是该节点加权斯坦纳树的问题，这，一个合理的复杂性理论的假设下，没有多项式时间近似算法具有比这ö （log n）。

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

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

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

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

如果我能说什么关于树的大小怎么办？

从理论上说，你可以得到一个较低的通过与你正在考虑大小的图形解决双整数规划的LP松弛的Steiner树（实际上的约束，也不会感到惊讶如果一个求解器可以直接确定最优的斯坦纳树）。

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