Алгоритмы вопрос по n * n матрице расстояний

Question

Предположим, у меня есть n * n матрица расстояний между n пользователями. Я хотел бы знать, какой алгоритм использовать, чтобы найти маршрут вокруг группы, начиная с пользователя X и возвращаясь к пользователю X, когда все остальные узлы посещаются один раз, но только один раз, и с использованием как можно более короткого расстояния в каждом прыжке.

Answer 1

Эта проблема называется задачей коммивояжера. На ней есть отличная страница Википедии , которая должна указать вам правильное направление.

Answer 2

Это Задача коммивояжера при условии, что вы хотите минимизировать общую длину тура. NP-Complete, поэтому не существует многочастичного алгоритма, но существуют хорошие методы аппроксимации.