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

Question

我确实有一个图(~250个节点）。要连接到一个节点，我必须用points->加权图购买它。有些节点总是被占用（“声明的节点”），我可以从这些节点开始连接到其他节点。此外，我的点数有限。所有节点都可以连接在一起。

有什么方法可以得到一个图，其中所有的节点都必须连接在一起，点最少？如果可能的话，以给定的最大点数。

第二）有没有一种方法可以使它不需要一个完全连通的图？例如：一个“必须有节点”的节点直接连接到一个“声明节点”，所以获得它的最便宜的方法就是只获得必须有的节点，而不将它与剩余的图连接。

编辑（关于前三个问题）：我确实必须购买节点本身，而不是连接。所以，我不计算旅行距离，而是计算节点成本。例如：如果我有一个从A到B、B到C和A到C的图，并且B是一个“必须有节点”，我可以从A“旅行”到B，然后从B到A和从A到C（如果它比B到C短），因为B到A没有额外的成本，因为B已经被要求了。

我想出了这个算法：我做了一个包含所有“必须有节点”的表，并从其中一个节点开始。我要么使用呼吸优先搜索，要么使用深度优先搜索（哪种更好？）让它分支，只要它没有找到一个“必须有节点”，并且将--如果需要的话--更新最短的距离。当它发现一个“必须有节点”时，它结束这个分支并存储它的路径。该距离将登记在表中。只要它发现没有“必须有节点”，它就会运行。当它完成时，我将继续在表中执行下一个“必须有节点”，执行同样的操作并构建表。
当我完成所有节点时，我将在表上运行最小生成树算法，并且应该得到我的最优图。

有人觉得这个有问题吗？

Answer 1

你的问题对应于节点加权Steiner树。
（TinLoaf的链接指向边缘加权版本，这是Steiner树的默认版本。）
节点加权Steiner树->您的问题:
如果S是空的，那么空的子图就是一个解，否则让S的任何一个元素是
唯一声明的节点，让“必须有”的节点是S的其他元素。

您的问题->节点加权Steiner树:
如果您的意思是声明的节点也需要彼此连接，那么这些节点和必须拥有的节点之间没有区别，所以让S是[声明的节点集]
和[必须拥有的节点集]的并集。如果您的意思是每个必有节点只需要连接到至少一个声明节点，那么将声明节点折叠成彼此
并设S是{resulting_node}与[the set of“must have”Nodes]的并集。

注意uni-bonn链接（从本答案开始）
至少有一个关于逼近的错误结果-
实际的主要正结果是“节点加权Steiner树问题可以
逼近到因子1.35(1+epsilon')ln k对于任何epsilon'>0。”
（他们漏掉了1+Epsilon'因子。）

此外，uni-bonn Link的近似硬度参考没有在这方面提出要求，
尽管结果是已知的--它至少像集合覆盖一样难以近似。
当由[解决方案中既没有声明也没有必须声明的节点的数目]html" target="_blank">参数化时，
从集合覆盖的减少仍然适用，因此如果该数目很小，那么
在最坏的情况下，您不太可能比暴力做得更好。
虽然
边加权Steiner树在通过终端数进行参数化时是FPT的，但我还没有从参数化复杂度中找到其他适用的东西。