Реализация алгоритма звезды

Question

Может ли алгоритм «звезда» реализован с использованием HashMaps вместо ArrayLists?

Answer 1

Прежде всего, звезда не связана с какой-либо конкретной структурой данных.Я реализовал это, используя Array list и Sorted List (для хранения открытых узлов в отсортированном порядке).Вы можете реализовать его в соответствии с вашими потребностями

Answer 2

Я думаю, что вы говорите о куче или, скажем, приоритетной очереди.Подход с поиском по принципу «лучший первый» требует выбора узла из открытого набора с наименьшей стоимостью.Куча позволяет выполнить O (log N) вставку и найти текущий лучший узел в O (1).