节点加权图的最小生成树变化

Question

我正在尝试解决最小生成树问题的变体；我有一个图表，其中有某些关键节点和可选节点。每个可选节点都有一个权重，我们需要找到跨越所有关键节点的节点子集，同时最小化可选节点的总权重。由于关键节点是强制性的，因此它们没有权重。边也没有权重，一旦选择了它连接的两个节点，它们就在意义上是自由的。我做了一个例子，关键节点标记为红色，解决方案（我认为）标记为绿色。

编辑： 虽然我认为这可能会简化为 MST，但我认为这实际上可能是斯坦纳树问题，因此是 NP 难问题。该用例适用于视频游戏，因此更优选快速（且简单）的近似解决方案。

Answer 1

这是最大权连通子图问题的特例。它是 NP 困难的，但实际上即使对于具有数万个节点的图也可以有效地解决。解决这个问题的最佳软件：https://scipjack.zib.de/（免责声明，我是开发人员之一）