Наименьшее расстояние пути между точками в виде координат X-Y
В настоящее время я работаю над проектом, в котором есть вектор, содержащий координаты X и Y, приблизительно для 800 точек. Эти точки представляют собой электрическую сеть линий.
Моя цель — вычислить кратчайший путь Path между точкой A и точкой B, который может быть или не быть расположен вдоль пути, заданного векторами, содержащими координаты X-Y электрических линий.
Я читал об алгоритме Дейкстры, но так как я не очень хорошо знаком с ним, я не уверен, стоит ли мне идти в этом направлении. Я буду очень благодарен, если смогу получить какие-либо отзывы или комментарии от вас, которые могут направить меня к решению этого вопроса.
Решение
Любой алгоритм поиска пути зависит от пути, точки просто бессмысленны. Теперь у вас есть список «путевых точек». Однако вы не объяснили, как эти точки соединяются. Например, если любая точка соединена с другой точкой, кратчайшее расстояние будет просто пифагоральным расстоянием между & Б. — Я также не уверен, что вы подразумеваете под X-Y координатами электрических линий, такая «линия» всегда будет иметь начало & конечная позиция?
Поэтому первым шагом является добавление к каждой точке не только координат x, y, но и списка подключаемых точек.
После того, как вы это сделаете, вы можете начать использовать алгоритм поиска пути (в этом случае A * покажется лучше, чем у Дейкстры). Это была бы просто стандартная реализация с каждой «стоимостью» фактического расстояния между точками. (А для A * эвристика будет пифагоральным расстоянием до конечной точки).
Для хорошего урока об A * (и других алгоритмах) вы должны проверить Страницы Амит
РЕДАКТИРОВАТЬ, в ответ на комментарии.
Кажется, первым шагом является преобразование набора отрезков в «точки». Я бы прошел через это:
collection AllPoints {containing Location & LinksToOtherPoints}
for each Segment
get start/end Point of Segment
if Point.Location is not in allPoints
add Point to AllPoints
add the other Point of Segment to LinksToOtherPoints
Тогда у вас есть просто список со всеми точками & связи между ними. Поскольку вы должны постоянно искать в коллекции allPoints, я предлагаю сохранить это в бинарной древовидной структуре (множествах?).
Другие решения
Для вычисления кратчайшего пути Диякстра подойдет.
Вы можете получить более быстрые результаты от использования A *, который использует наилучшее предположение о расстоянии, чтобы сфокусировать его поиск в правильном направлении, тем самым добираясь туда быстрее.
Если вы неоднократно запрашиваете один и тот же набор данных, то мемоизации Это хорошо.
Те люди, которые рекомендуют алгоритм грубой силы, — дураки — стоит потратить немного времени, чтобы научиться программировать эффективное решение. Но вы можете рассчитать кратчайший путь между всеми точками, используя Алгоритм Флойда-Варшалла. К сожалению, это не скажет вам, какой кратчайший путь является просто сколько это.
Просто рассчитайте расстояние для всех возможных путей и выберите самый короткий.
800 дорожек — ничто для современного ПК. Вы даже не заметите этого.