Я-реализация алгоритма A-star объяснил - PullRequest
Новая
       13

Я-реализация алгоритма A-star объяснил

0 голосов
/ 29 апреля 2018

Недавно у меня была курсовая работа по реализации алгоритма 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);

Но когда я запускаю алгоритм, я получаю максимально длинный путь. Легенда для обоих изображений: путь оранжевый, источник розовый, пункт назначения фиолетовый.

image of incorrect path

Когда я изучал реализации Java для этого алгоритма для входных данных на основе сетки, если используется приоритетная очередь, они всегда отдают более высокий приоритет узлам с более высокой конечной стоимостью. Я попробовал этот метод, изменив компаратор на этот 

PriorityQueue<GridPiece> unvisitedNodes = new PriorityQueue<>(10,
            (gridPie1, gridPie2) -> ((GridPiece) gridPie1).getFinalCost() < 
((GridPiece) gridPie2).getFinalCost()? -1
                    : ((GridPiece) gridPie1).getFinalCost() > ((GridPiece) 
gridPie2).getFinalCost() ? 1 : 0);

Тогда я получу лучший путь;

image of correct path

Мой простой запрос - краткое объяснение того, почему алгоритм не ведет себя так, как ожидалось, когда реализация в точности придерживается псевдокода, и почему нужно переключать приоритет узлов (более высокая конечная стоимость передается первой) для алгоритм работы в реализации Java?

Полный код проекта можно найти здесь .

1 Ответ

0 голосов
/ 29 апреля 2018

Заголовок приоритетной очереди является наименьшим элементом по отношению к данному порядку. Ваш компаратор возвращает -1, когда стоимость первого элемента больше, чем стоимость второго элемента. Другими словами, вы ставите самый высокий элемент затрат на первое место. Вот почему в голове вашей очереди есть круговая сетка с наибольшей стоимостью.

Во второй реализации компаратор возвращает -1, когда стоимость первого элемента меньше стоимости второго элемента, а это то, что вам нужно.

Если вы просто сортируете по стоимости (предположительно int?), Тогда вы можете просто сделать: 

new PriorityQueue<GridPiece>(Comparator.comparingInt(GridPiece::getFinalCost));

Редко указывается начальная емкость. Для такой маленькой сетки, как ваша, просто используйте емкость по умолчанию, чтобы все было просто.

...