Сортировка многомерных векторов

Question

Если у меня есть набор k векторов n измерений, как я могу их сортировать так, чтобы расстояние между каждой последовательной парой векторов было минимальным? Расстояние можно рассчитать, используя эвклидово расстояние, но как «сортировка» затем реализована эффективно?

Я думаю, что одним из подходов было бы выбрать вектор случайным образом, рассчитать расстояние до всех других векторов, выбрать вектор, который минимизирует расстояние в качестве следующего вектора и повторить до тех пор, пока все векторы не будут «отсортированы». Однако этот жадный поиск, вероятно, принесет разные результаты в зависимости от того, с какого вектора я начинаю.

Любые идеи о том, как это сделать?

Answer 1

Если вы действительно хотите просто «чтобы расстояние между каждой последовательной парой векторов было минимально возможным» без случайности, вы можете сначала найти 2 ближайших точки (по O (n log n) algo, например this) - допустим, p и q, тогда найдите ближайшие точки для p (скажем, r) и q (скажем, s), затем сравните расстояние (p, r) и (q, s), а если первое меньше, начните с q , p, r и используйте ваш жадный алгоритм (в другом случае, очевидно, начинайте с p, q, s).

Однако, если ваша цель состоит в том, чтобы организовать точки так, чтобы сумма всех парных расстояний была наименьшей, вы должны выбрать любое приблизительное решение для Travelling salesman problem. Примечание this trick, чтобы уменьшить вашу задачу до TSP.