Знакомьтесь, М*
Алгоритм поиска кратчайшего пути, через весь мир, на смартфоне
Борис Муратшин Dump
Скрыть видео
  • Каждый знает алгоритм Дейкстры.
  • Многие знают алгоритм А*, который является обобщением алгоритма Дейкстры.
  • В А* для точки периметра (кроме стоимости пройденной части) используется «наивная» оценка оставшегося пути — расстояние по прямой. Это позволяет сильно сократить просмотренную часть графа, т.к. стимулирует распространение «волны» по направлению к цели.
  • Однако, когда периметр наталкивается на препятствие, например, море, такая «наивная» оценка, наоборот, начинает усугублять ситуацию.
  • Предложена более умная, но всё ещё дешёвая эвристика оценки оставшейся части пути. Мы назвали её М* («М» значит «морковка»), что, как нам кажется, очень точно описывает суть происходящего.
Борис Муратшин

Программист в команде Navi

В IT-индустрии Борис уже 25 лет, 6 из них — в 2ГИС, в команде Navi. Команда делает навигатор и транспортные сценарии. Борис создал алг...

Биография докладчика
Dump

14 апреля 2017

Конференция уральских разработчиков

Сайт конференции

Похожие доклады

Разработка развесистого API
на Yii-фреймворке

Приёмы разработки сложных API на фреймворке Yii.

Сергей Коржнев
Архитектура Справочного API 2ГИС

Особенности архитектуры справочного API 2ГИС: балансировка, мониторинг, оптимизация.

Сергей Коржнев
Дорожная сеть в графовой базе данных Neo4j

Проверка связности графа дорожной сети на Neo4J .

Вадим Шашенко

Будь в курсе

  • Участвуй в конференциях, учись новому
  • Узнавай от 2ГИС самое интересное из мира технологий
  • Читай новости, смотри выступления опытных экспертов