У меня есть несколько точек в 100-мерном пространстве, и я хочу найти минимальный путь, который включает n промежуточные шаги для соединения точки A с точкой B.Подвох в том, что от A до B можно добраться только, посетив другие точки в пространстве (каждую из которых можно посетить только один раз), и нужно пройти ровно n точек в пути от Aна B.
В настоящее время я рассматриваю вычисление расстояний между каждой парой точек, затем обрабатываю пространство как граф и использую алгоритм Дейкстры, чтобы найти минимальный путь от A до B.
Прежде чем реализовать это, я хотел спросить: есть ли подход к этой задаче, который не требует вычисления полной матрицы попарных расстояний?
Существует более миллиона узлов,таким образом, сложность подхода Дейкстры была бы огромной .Приблизительное решение, которое не достигает глобальной оптимальности, но минимизирует стоимость / пройденное расстояние, является приемлемым.Будем весьма благодарны за любые предложения другие могут возникнуть по этому вопросу.