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

Question

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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