Алгоритм соединения геометрических линий

Question

у меня n открытых геометрических линий в 3D.которые должны быть объединены в одну линию на основе критериев минимальной длины дополнительных линий между конечными точками линий.Пожалуйста, предложите алгоритм, который имеет минимальную сложность.

Answer 1

Самый известный алгоритм работает за O (2 ⁿ ).Как сказал Эндрю Саид в своем комментарии, это более общая версия проблемы путешествующих продавцов.Если вы найдете лучший алгоритм, вы получите приз в размере 1000000 долларов.

Вместо этого вы должны попробовать приблизительные решения, см. wikipedia .