Планирование маршрута для графа с узлами и максимальным расстоянием "прыжка" между узлами
У меня ~6500 узлов с (x,y,z)-координатами. Для моей задачи мне нужно найти маршрут из Node A в Node Bучитывая, что я могу только двигаться K расстояние между узлами. K изменения между маршрутами (поэтому он постоянен при расчете заданного маршрута, но для нового начального и конечного узла он может отличаться).
Я представлял себе алгоритм A*, но это означало бы, что мне придется вычислять расстояние между каждым "текущим" узлом и всеми другими узлами для каждого прыжка, что невозможно. Я также мог бы предварительно рассчитать график для каждого приращения K (1, 2, 3, 4), но это оставит мне огромное количество данных (максимум K было бы около 15).
Есть ли умный способ, который с некоторыми предварительными вычислениями позволяет мне быстро искать такой маршрут. Ожидается, что набор данных будет немного расти, но, вероятно, никогда не превысит 10.000.