Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Поиск кратчайших путей в дорожных сетях: от теории к реализации


Курс даёт уникальную возможность познакомиться с методологией разработки прикладных алгоритмов на конкретной задаче поиска кратчайших путей в дорожных сетях. В ходе курса будут изучаться и реализовываться алгоритмы, используемые миллионами людей в таких сервисах, как Google/Bing/Yandex карты. Предварительный план курса:

  1. Введение в методологию разработки прикладных алгоритмов.
  2. Алгоритм Дейкстры. Двунаправленный алгоритм Дейкстры.
  3. Алгоритм флагов на ребрах.
  4. Алгоритм контракционной иерархии.
  5. Алгоритм меток хабами.
  6. Кратчайшие пуи в условиях динамических изменений графа.
  7. Задача поиска кратчайшего пути от нескольких вершин к нескольким.
Для получения аттестации по курсу необходима реализация графовой структуры данных на языке C++, алгоритма Дейкстры, двунаправленного алгоритма Дейкстры, алгоритма флагов на ребрах и контракционной иерархии.

Прочтения курсов

Семестр
осень 2016