Реализация алгоритма A Star (A*) в Java

Отказ от ответственности: у меня мало опыта работы с Java, так как я преимущественно разработчик C#.

Хотелось бы иметь реализацию алгоритма A* в Java.
Да, я видел много версий одного и того же в Интернете и не могу выбрать между ними.

Я ищу реализацию алгоритма A *, которая использует все новые функции java, которые делают алгоритм быстрее (даже если немного). Причина в том, что мы реализуем это для поиска пути в MMO, поэтому производительность является главным приоритетом.

Любые указатели (по крайней мере, где искать)?


java algorithm path-finding a-star
person naveen    schedule 07.01.2011    source источник
comment
Можете ли вы дать нам ссылки на версии, которые вы уже нашли? И, кстати, использование новых возможностей Java не сделает алгоритм быстрее.   -  person darioo    schedule 07.01.2011
comment
Срок действия ссылки снова истек, вот самое новое для тех, кто, как и я, найдет это: github.com/graphhopper/graphhopper/blob/master/core/src/main/   -  person    schedule 12.05.2013
comment
@BattleBarnes включенный двунаправленный A * еще быстрее   -  person Karussell    schedule 23.01.2015

Ответы (2)


arrow_upward
23
arrow_downward

Попробуйте несколько, измерьте, выберите самый быстрый, адаптируйтесь к вашим потребностям. Производительность в основном определяется выбором эвристической функции, которая не зависит от собственно A*.

Если эвристика исправлена, реализация приоритетной очереди, вероятно, станет узким местом, поэтому попробуйте сопряжение кучи< /а>. Это одни из самых быстрых структур данных кучи на практике, и они имеют то преимущество перед двоичными кучами, что они допускают время вставки O(1) + амортизированное O(log n) всплывающих минут. Это важно в ожидаемом случае многих циклов A*, когда очередь заполняется, но никогда полностью не очищается, т. е. количество вставок намного превышает количество всплывающих окон.

Если память становится проблемой, переключитесь на итеративное углубление A* (IDA*) или рекурсивный поиск по первому наилучшему (RBFS).

Если ничего не работает, рассмотрите возможность использования приближенного алгоритма (жадный поиск). Простая оптимизация прилично написанного цикла A* не даст вам огромного ускорения.

См. Рассела и Норвига для получения информации об алгоритмах и хорошего обсуждения проблем.

person Fred Foo    schedule 07.01.2011
comment
какую структуру данных следует использовать для closedList? - person st0le; 07.01.2011
comment
Хэш-таблица. Или красно-черное дерево. Или раскидистое дерево. Или то, что окажется быстрее. @ st0le, вы правы, это важно, но по моему опыту, быстрые наборы найти легче, чем очереди с быстрым приоритетом. - person Fred Foo; 07.01.2011
comment
@ sk0le: если вообще нужен закрытый набор, то есть. - person Fred Foo; 07.01.2011
comment
@ Роберт, спасибо. Как реализовать A * время от времени появляется на SO, и чтение R&N почти всегда является ответом;) - person Fred Foo; 07.01.2011

arrow_upward
10
arrow_downward

Если производительность является вашим главным приоритетом, A *, вероятно, не лучший выбор. A* предоставляет точное решение и в результате не будет выполнять обработку, пока не найдет правильный ответ. Существуют и другие легкие решения, которые дают достаточно хорошие решения за гораздо более короткое время: например, принудительное восхождение на холм или поиск лучшего, даже простой поиск в глубину.

person Robert    schedule 07.01.2011
comment
+1. Оптимизация кода A * не принесет ОП награду за производительность. - person Fred Foo; 07.01.2011
comment
-0, так как да, A *, вероятно, не так эффективен, но альтернативы, которые вам нужны, - это методы ускорения, характерные для поиска пути, такие как иерархии сжатия и тому подобное. - person Karussell; 10.08.2014
comment
Ради точности A* не всегда дает оптимальный ответ. Это происходит только в том случае, если эвристика допустима. - person Pierre-Antoine; 06.02.2019