Выполнение поиска A *, реализованного в Clojure - PullRequest
Новая
       13

Выполнение поиска A *, реализованного в Clojure

6 голосов
/ 09 сентября 2010

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

Здесь - код.Реализация алгоритма является общей (состояния должны быть только «хэшируемыми» и «сопоставимыми»), но в данном конкретном случае состояния являются парами (векторами) целых чисел [x y], и они представляют одну ячейку в данной карте высот (стоимость ) для перехода к соседней ячейке зависит от разницы высот).

Вопрос в том, можно ли улучшить производительность и как?Может быть, используя некоторые функции из 1.2 или более поздних версий, изменив логику реализации алгоритма (например, используя другой способ сохранения пути) или изменив представление состояния в этом конкретном случае?

Реализация Java запускается мгновенно для этой карты , а реализация Clojure занимает около 40 секунд.Конечно, для этого есть несколько естественных и очевидных причин: динамическая типизация, постоянные структуры данных, ненужный (не) бокс примитивных типов ...

Использование переходных процессов не имело большого значения.

Ответы [ 2 ]

4 голосов
/ 10 сентября 2010

Использование priority-map вместо sorted-set

Сначала я использовал sorted-set для хранения открытых узлов (границы поиска), переключаясь на priority-map повышение производительности: теперь это занимает15-20 секунд для этой карты (до этого прошло 40 секунд).

Это сообщение в блоге было очень полезным.И «моя» новая реализация почти такая же.

Новый поиск * можно найти здесь .

3 голосов
/ 12 сентября 2010

Я не знаю Clojure, но могу дать вам несколько общих советов по улучшению производительности Vanilla A *.

  • Рассмотрите возможность реализации IDA *, который является вариантом A *, который использует меньше памяти, если он подходит для вашего домена.

  • Попробуйте другую эвристику. Хорошая эвристика может оказать значительное влияние на количество требуемых расширений узлов.

  • Используйте кеш, часто называемый " таблица транспонирования " в алгоритмах поиска. Поскольку графы поиска обычно Направленные ациклические графы , а не истинные деревья, вы можете в конечном итоге повторить поиск состояния более одного раза; кэш для запоминания ранее найденных узлов уменьшает количество расширений узлов.

Dr. У Джонатана Шеффера есть несколько слайдов на эту тему:

http://webdocs.cs.ualberta.ca/~jonathan/Courses/657/Notes/10.Single-agentSearch.pdf

http://webdocs.cs.ualberta.ca/~jonathan/Courses/657/Notes/11.Evaluations.pdf

...