Недавно у меня была курсовая работа по реализации алгоритма A star на Java, где входные данные представлены в виде сетки 20 * 20.
В соответствии с псевдокодом алгоритма «звезда», в качестве текущего узла выбирается узел с наименьшей конечной стоимостью в открытом списке.
Прежде чем на самом деле реализовать алгоритм в Java, я прошел через множество различных реализаций на других языках, таких как ruby, python и c ++.
В реализации на других языках характерно то, что он придерживается метода алгоритмов перехода к узлу с наименьшей конечной стоимостью в качестве нового текущего узла при обходе пути.
Я использовал очередь приоритетов для реализации открытого списка для этого алгоритма, добавив приведенный ниже компаратор, который дает более высокий приоритет узлу с более низкой конечной стоимостью
PriorityQueue<GridPiece> unvisitedNodes = new PriorityQueue<>(10,
(gridPie1, gridPie2) -> ((GridPiece) gridPie1).getFinalCost() >
((GridPiece) gridPie2).getFinalCost()? -1
: ((GridPiece) gridPie1).getFinalCost() < ((GridPiece)
gridPie2).getFinalCost() ? 1 : 0);
Но когда я запускаю алгоритм, я получаю максимально длинный путь.
Легенда для обоих изображений: путь оранжевый, источник розовый, пункт назначения фиолетовый.
Когда я изучал реализации Java для этого алгоритма для входных данных на основе сетки, если используется приоритетная очередь, они всегда отдают более высокий приоритет узлам с более высокой конечной стоимостью. Я попробовал этот метод, изменив компаратор на этот
PriorityQueue<GridPiece> unvisitedNodes = new PriorityQueue<>(10,
(gridPie1, gridPie2) -> ((GridPiece) gridPie1).getFinalCost() <
((GridPiece) gridPie2).getFinalCost()? -1
: ((GridPiece) gridPie1).getFinalCost() > ((GridPiece)
gridPie2).getFinalCost() ? 1 : 0);
Тогда я получу лучший путь;
Мой простой запрос - краткое объяснение того, почему алгоритм не ведет себя так, как ожидалось, когда реализация в точности придерживается псевдокода, и почему нужно переключать приоритет узлов (более высокая конечная стоимость передается первой) для алгоритм работы в реализации Java?
Полный код проекта можно найти здесь .