OSM и A * Algorithm

Question

Я пытаюсь написать программу, которая вычисляет кратчайший путь (алгоритм A *) от A до B, используя данные OSM в качестве входных данных. Программа должна работать в Android Java. Я использую данные из OSM и конвертирую их с osm_2po (это приложение, которое преобразует файлы OSM xml в файл sql OSM2PO), чтобы поместить данные в мою базу данных PostGIS. В моей базе данных есть следующие записи, и насколько я понял это правильно, мне нужны следующие переменные: source_id, target_id, x1, y1, x2, y2, стоимость и обратная стоимость. Где source_id - это идентификатор исходного узла на основе данных OSM. (long) Где target_id - идентификатор целевого узла на основе данных OSM. (long) Где x1, y1 - координаты исходного узла (широта и долгота). (float) Где x2, y2 - координаты целевого узла (широта и долгота). (float) Где стоимость - это сгенерированные затраты от источника к цели. (float) Где обратная стоимость - это сгенерированные затраты от целевого источника (float). В моей программе Java у меня есть класс данных Node, который хранит мои узлы в следующей структуре для хранения записей в моей базе данных: источник, цель, стоимость, x, y, x2, y2 Сам узел класса данных может хранить x1 , y1, x2, y2, bool visited, sourcenode, targetnode, cost, g, h и f. Это будет храниться два раза. Один раз для src -> target и наоборот. Вход имеет следующую структуру: Начальный узел: источник = 0, target = выбранная начальная точка, все остальные переменные установлены на 0. Destination Node: source = выбранная точка назначения, а все остальные переменные установлены на 0.

У меня есть только тот узел, где пользователь хочет начать и ничего больше. Алгоритм должен выяснить, что является следующим узлом и развернуть их, соответственно. Псевдокод, который я использовал для реализации, находится в немецкой Википедии Wikipedia. Открытый список - это приоритет, а закрытый список - ArrayList. В алгоритме я использую Манхэттенское расстояние для расчета H.

Мои вопросы/проблемы: Является ли моя структура данных правильной для такой реализации? Или мне нужно использовать структуру, которая хранит для узла все предшественники и преемники? Должен ли я устанавливать h, получая данные из моей базы данных? Если да, как я могу вычислить h? Это стоимость вершин от предшественника до следующего узла?

Answer 1

Если я правильно понимаю, каждая запись в базе данных является краем графика - она ​​имеет исходную точку и точку назначения. Я не знаю, что представляет собой «h».

Рассмотрите возможность переименования вашего класса Node в «Edge», поскольку он представляет собой путь между двумя узлами, а не одним узлом. Вы можете использовать целое число для направления со значениями -1, 0, 1 вместо boolean. Но ваша структура данных в порядке.