Привет, Друзья!



Я написал библиотеку поисков путей на произвольных графах, и хотел бы поделиться ей с вами:



Пример использования на огромном графе:




Поиграться с демо можно здесь:



В библиотеке используется мало-известный вариант `A*` поиска, который называется [`NBA*`][1]. Это двунаправленный поиск, с расслабленными требованиями к функции-эвристике, и очень агрессивным критерием завершения. Не смотря на свою малоизвестность у алгоритма отличная скорость сходимости к оптимальному решению.



Описание разных вариантов `A*` уже не раз встречалось на хабре. Мне очень понравилось [вот это][2], потому повторяться в этой статье я не буду. Под катом расскажу подробнее почему библиотека работает быстро и о том, как было сделано демо.

[Читать дальше →][3]

[1]: https://repub.eur.nl/pub/16100/ei2009-10.pdf
[2]: https://habrahabr.ru/company/2gis/blog/326638/
[3]: https://habrahabr.ru/post/338440/?utm_source=habrahabr&utm_medium=rss&utm_campaign=feed_posts#habracut