无向图转化为路径最小代价的并集

Question

我需要为一个加权无向图创建一个解决方案，穿过所有节点，使总成本最小化。多条路径，没有定义的起点，应该以一个交叉节点终止并相遇。路径数量和路径包含的节点数量没有预先确定。可以多次通过节点。

我所处理的问题属于哪种类型？可能的算法解决方案是什么？ 我认为这应该是最小生成树的变体（意味着使用交叉节点作为路径的起点而不是终点）。

- DelicateBehemoth

---

嗯，我没听懂你的意思。这个问题到底给出了什么还不清楚。 - dreamzor

给定一个节点图。要求通过所有节点，使得通过的总成本最小。从图的“外围”任意节点开始路径，到达图中心的某个确定（给定）节点。可以多次访问节点，因此路径可以去访问一个节点，然后在继续时返回先前经过的节点（如果这满足最小成本条件）。 - DelicateBehemoth

另一种解决方案是从相反的方向开始 - 而不是从起始节点到达中心节点，而是从中心节点开始并将路线扩展到“外围”节点。这就是为什么我提到了生成树，但分支应该是路由。 - DelicateBehemoth

Answer 1

这个问题被称为最小成本哈密顿回路问题。

在这里你可以阅读更多相关信息。

- dreamzor

---

谢谢您的回答，但是这个结构不是电路。它应该呈星形，汇聚在一个预定的节点上，有未知数量的哈密顿路径。 - DelicateBehemoth

Answer 2

你正在寻找一棵树，问题是最小生成树（MST）：构建一棵跨越图中所有节点的树，并且树上边缘的成本尽可能地最小。这是一个多项式问题。Prim和Kruskal各自都有着众所周知的算法来解决这个问题。 请参见http://en.wikipedia.org/wiki/Kruskal的Kruskal算法。

注意：当树应该跨越给定节点的适当子集而不是图中的所有节点时，该问题是NP完全的。这时它被称为Steiner Minimal Tree问题。

- ashley

---

谢谢您的回复，但实际上它可能应该是MST的一个变体，它可以给出一棵树，其中有几条路径，每条路径只需从中心节点到外围节点的一个分支/路径，沿途经过节点，而不是跨越多个分支。 - DelicateBehemoth

也许你应该更清晰地阐述你的问题。对我来说，它仍然看起来像是MST或最短路径树。 - ashley

正如我所说，它是MST的一种变体，不同之处在于它是在无向图上进行有向路径搜索（从“外围”节点开始，并沿途按顺序访问节点以到达给定节点），并且可能会多次访问某些节点/边。 - DelicateBehemoth

例如，为了使问题更清晰，我们可以将其视为在一个区域内让多辆汽车通过所有城市并到达“中心”节点的问题，不考虑有多少辆汽车，只是尽可能降低总成本。如果我们有一个生成树，则几辆汽车会开始旅行，但它们会在某个点相遇，并在到达“中心”节点时重复一部分路线，这将增加总成本。这在经典的最小生成树问题公式中没有考虑到。 - DelicateBehemoth