圖中有多個「必須有」節點的最短路徑

Question

我確實有一個圖（〜250個節點）。要連接到節點，我必須用點 - >加權圖購買它。 有總是被採取的節點（「被要求的節點」），並且那些我能開始連接到其他節點。此外，我確實擁有有限的積分。所有節點可以連接在一起。

有什麼方法可以得到一個圖，所有必須有節點連接在一起，用最少的點？如果可能的話給定最大點數。

2nd）有沒有辦法不需要一個完全連接的Graph？例如：一個「必須擁有節點」的節點直接連接到一個「被聲明的節點」，因此獲得它的最便宜的方法就是獲得必須擁有的節點，而不是將其與剩餘的圖形連接起來。

編輯（關於前三個問題）：我必須購買節點本身，而不是連接。所以，我不計算行程距離，而是計算節點成本。例如：如果我有一個從A到B的圖形，B到C和A到C和B是一個「必須有節點」，我可以從A到B然後從B到A和從A到C（如果它比B到C短），因爲從B到A沒有額外的成本，因爲B已經被要求。

我想出了這個算法： 我做了一個表，所有的「必須有節點」，並從其中一個開始。我使用呼吸優先搜索或深度優先搜索（什麼會更好？），並讓它分支，只要它沒有找到「必須有節點」，並且將在必要時更新最短距離。當它找到「必須有節點」時，它結束該分支並存儲它的路徑。距離將被登記在表中。它會運行，只要它發現沒有「必須有節點」。完成後，我將在表格中繼續前進，並採取下一個「必須有節點」，執行相同的操作並構建表格。
當我完成所有的節點時，我將在表格上運行最小生成樹算法，並且應該得到我的最優圖。

任何人都會發現此問題？

Answer 1

這看起來像一個Steiner樹問題[0]，它是NP-hard，但可以解決250個節點。我認爲你可以將它像這樣：

• 插入一個虛擬根頂點
• 將它連接到每一個體重0通過邊緣「聲稱頂點」 - 現在所有的「爆料頂點」可以連接到樹（即將構建）與重量0
• 解決「廣義斯坦納樹問題」[0]，其中「必須有節點」的集合形成維基百科描述中的集合S.

如果你能接受近似的解決方案：steiner樹問題有一些近似值（維基百科的文章也應該提到）。

[0] https://en.wikipedia.org/wiki/Steiner_tree_problem#Generalization_of_minimum_Steiner_tree

Answer 2

您的問題對應於Node Weighted Steiner Tree。
（tinLoaf的鏈接是邊緣加權版本，這是Steiner樹的默認版本。）


節點加權Steiner樹 - >您的問題：
如果S爲空，則空子是一個解決方案，否則讓S的任何一個要素是
獨特要求和節點讓「必須有」的節點是S.

你的問題的其他元素 - >節點加權Steiner樹：
如果你的意思是要求保護的節點還需要彼此相連，然後那些和必須有的節點之間沒有區別，所以讓S是單一的[要求的節點集合]
與[必須具有的節點集合]。如果您的意思是每個必備節點只需要連接到至少一個聲明的節點，那麼collapse將聲稱的節點彼此分開
並且讓S是{results_node}與[must有「節點」。

注意the uni-bonn link（從這個答案的開始）
已約近似至少一個錯誤的結果 -
實際主要陽性結果是「The node weighted Steiner tree problem can
be approximated to a factor of ​ 1.35 (1+epsilon') ln k ​ for any ​ epsilon' > 0 .「。
（它們留出了1個+小量」因子。）

另外，單向性波恩鏈路的參考換的逼近硬度使得在該方面不要求，
雖然結果是已知的 - 至少as hard to約as set cover。


當parameterized由[既不是要求也不是必須具備的溶液中節點數量]，
對集合覆蓋的減少仍然適用，因此，如果這個數字是很小那麼你
你」在最糟糕的情況下，不太可能比暴力更好。
我還沒有發現任何其他適用適用於從參數複雜，雖然
邊緣加權Steiner樹is known to是FPT當終端數量的參數。