Подтвердить что ты не робот

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

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

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

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

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

Ответ 1

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

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

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

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

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

Ответ 2

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