График усиления: кратчайший путь, проходящий через набор точек

Question

У меня есть график, на котором каждый узел является трехмерной точкой, а ребра представляют расстояния между этими точками в трехмерном пространстве. График не полностью связан. Это означает, что между точками A и B может быть один прямой или многоступенчатый путь (например, A->C->D->E->B).

Я хочу найти кратчайший замкнутый путь, который проходит через данный набор точек(все точки должны лежать на пути).

Есть ли готовая реализация для этого в библиотеке Boost Graph?

PS Путь должен начинаться и заканчиваться в одной и той же вершине (цикл)

Answer 1

Это задача коммивояжера, которая NP-сложная.

В BGL существует один алгоритм приближения оптимальных решений: https://www.boost.org/doc/libs/1_71_0/libs/graph/doc/metric_tsp_approx.html

Предполагается, что расстояния имеют некоторые свойства метрики :

Очень естественным ограничением TSP является требование, чтобы расстояния между городами формировали метрику для удовлетворения неравенства треугольника;то есть прямое соединение от А до В никогда не дальше, чем маршрут через промежуточное звено С:

Это соответствует вашей проблеме, потому что ваш графикмодели точек в 3D пространстве