Алгоритм поиска минимального расстояния между последовательностями точек

Question

У меня есть последовательность точек (длина). Точка - это пара чисел (a, b), таких как координаты x и y. И у меня огромный массив других последовательностей точек, которые имеют случайную длину. И задача - найти m последовательностей из огромного массива, которые имеют минимальное расстояние до последовательности поиска. Расстояние будет минимальным, если сумма ближайших точек минимальна, даже если последовательность поиска больше.

Answer 1

Используйте подход кластеризации на основе k-критерия для минимизации квадратов расстояний между точками для заданного N числа кластеров.

Answer 2

Вы можете смоделировать вопрос в виде взвешенного графа G = (V, E, f), так что узел в графе является точкой, а весовая функция f для каждого ребра между двумя соседними точками - это промежуточное расстояние между этими точки.

Затем вы можете просто запустить Dijkstra's algorithm на графике созданных точек, которые будут вычислять кратчайший путь от стартового узла до любой точки, доступной на графике. Вас интересует кратчайшее дерево путей, так что если вы хотите найти кратчайший путь к определенной точке, вы можете просто получить точку и следовать ее предыдущим указателям, чтобы получить ее кратчайший путь от начальной точки.