Boost Graph：通过一组点的最短路径
Boost Graph: Shortest path that pass through a set of points
我有一个图表，其中每个节点都是一个 3D 点，边表示 3D 中这些点之间的距离 space。该图未完全连接。这意味着在 A 点和 B 点之间，可能有单一的直达方式或多阶段方式（例如 A->C->D->E->B）。
我想找到通过一组给定点的最短闭合路径（所有点都应位于路径上）。
Boost Graph 库中是否有现成的实现？
P.S。路径应该从同一个顶点开始和结束（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 space
我有一个图表，其中每个节点都是一个 3D 点，边表示 3D 中这些点之间的距离 space。该图未完全连接。这意味着在 A 点和 B 点之间，可能有单一的直达方式或多阶段方式（例如 A->C->D->E->B）。
我想找到通过一组给定点的最短闭合路径（所有点都应位于路径上）。
Boost Graph 库中是否有现成的实现？
P.S。路径应该从同一个顶点开始和结束（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 space