開始位置和一組所需節點之間的最小生成樹

Question

我正試圖確定最佳搜索情況以與我寫的搜索算法進行比較。我有一組標記爲「必需」的節點和一個標記爲「開始」的節點，其餘標記爲「可選」。我想找到我需要擴展的節點的最佳數量，以便發現所有必需的節點，因爲我的第一個擴展是「開始」節點。

• 我相信我正在尋找的是最小生成樹，但修剪了所有不以「必需」節點結尾的分支。這是Steiner tree problem？
• 如果我的圖未加權，那麼Steiner樹的大小和最小生成樹的大小是否一樣？
• 如果有什麼話我可以說關於樹的大小？即類似的東西（最小生成樹大小的大小=平均最短路徑*＃所需節點...我不認爲這是真的，但它能很好地計算基於連通性或某物的平均值）。

的幾個注意事項：

1. 這不是旅行的銷售問題，因爲我並不需要一個路徑 每個需要的節點之間存在，我只是想探索每個 需要的節點。
2. 我是無向圖和加權（或相等地加權爲此事）
3. My圖表具有約100所需的節點的平均值，並且甚至數千可選節點

Answer 1

的我有一組的標記爲「必需」的節點和標記爲「開始」的節點，其餘的標記爲「可選」。我想找到最佳的節點數量 我需要擴展才能發現所有必需的節點，我給出的第一個擴展是「開始」節點 。

如果擴展一個節點的成本可以是任意的，則這是該節點加權斯坦納樹的問題，這，一個合理的複雜性理論的假設下，沒有多項式時間近似算法具有比這ö （log n）。

我相信我正在尋找的是最小生成樹，但是所有分支的 都不會在「必需」節點中結束。

不，這通常不是最優的。例如，用圖形

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

一個可能的MST看起來像/|\或/\時修剪，但最佳的解決方案看起來像_|_。

如果我能說什麼關於樹的大小怎麼辦？

從理論上說，你可以得到一個較低的通過與你正在考慮大小的圖形解決雙整數規劃的LP鬆弛的Steiner樹（實際上的約束，也不會感到驚訝如果一個求解器可以直接確定最優的斯坦納樹）。

然而，實際上，這不是人們評估搜索算法的方式。