* * (Звездный) алгоритм поиска кратчайшего пути

Question

В основном у меня есть наборы узлов, содержащие GPS-координаты. Как реализовать поиск A * таким образом, чтобы я мог использовать эти геопоинты, чтобы сравнить их друг с другом и найти кратчайший путь, назначив расстояние от одного указать на другое.

Обновление: 01/11/12

Я пытаюсь нарисовать маршрут кратчайшего пути, достигая его путем прохождения каждого узла по указанному алгоритму и сравнения расстояний пройденных узлов, чтобы найти кратчайший путь. Другая проблема заключается в том, что я не могу найти правильную реализацию поиска A * в Android / Java. Моя проблема сейчас:

1. Так как я буду сохранять геопункт (узлы) каждого пересечения дорог, как я должен хранить его в массиве или списке ссылок?

2. Прямо сейчас мы смогли вычислить расстояние каждого узла, но не динамически. Что я должен сделать, чтобы использовать это при расчете кратчайшего маршрута с помощью поиска A *.

Answer 1

Евклидово расстояние (т. Е. Расстояние по прямой) между двумя точками может быть хорошей эвристической функцией.

Найти подробности об A * поиск в Википедия .

Поиск * на самом деле является модификацией алгоритма Дейкстры для поиска кратчайшего пути из одного источника .Единственное отличие состоит в том, что поиск * использует эвристическую функцию, которая направляет поиск, убирая ненужные ветви дерева поиска.Хорошая эвристическая функция должна быть разработана таким образом, чтобы ее значение становилось монотонным на любом пути поиска.Он не должен переоценивать фактическое расстояние между двумя состояниями.Поскольку евклидово расстояние - это наименьшее возможное расстояние между двумя точками, вероятность переоценки расстояния между двумя точками отсутствует.

Подробнее о евклидовом расстоянии см. здесь .Для применения его к гео-координатам см. здесь .

Answer 2

Здесь - это эффективная память, хорошо протестированная, с открытым исходным кодом, реальная реализация A *, которая также может использоваться на Android .Расчет расстояния можно легко заменить (по умолчанию используется быстрое использование haversine)

Answer 3

Что именно вы пытаетесь достичь? A * - это эвристический алгоритм поиска, например используется в игре, чтобы найти следующий «лучший» ход. Пытаетесь найти кратчайший путь, соединяющий все эти узлы? В этом случае ищите / google для «проблемы коммивояжера».