图中有多个“必须有”节点的最短路径

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当终端数量的参数。