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

Ответ 1

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

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

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

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

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

Ответ 2

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