我有一个图表，其中每个节点都是一个 3D 点，边表示 3D 空间中这些点之间的距离。该图未完全连接。这意味着在 A 点和 B 点之间，可能有一条直达路径或多阶段路径(例如 A->C->D->E->B)。
我想找到通过一组给定点的最短闭合路径(所有点都应位于路径上)。
Boost Graph 库中是否有现成的实现？
附言路径应该从同一个顶点开始和结束(Cycle)
最佳答案
这是 NP 难的旅行商问题。
BGL中有一种最优解的近似算法:https://www.boost.org/doc/libs/1_71_0/libs/graph/doc/metric_tsp_approx.html
它假设距离有一些 metric properties :
A very natural restriction of the TSP is to require that the distances between cities form a metric to satisfy the triangle inequality; that is the direct connection from A to B is never farther than the route via intermediate C:
这适合您的问题，因为您的图形模型指向 3D 空间
关于c++ - boost 图 : Shortest path that pass through a set of points，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58748521/