Мини-курс "Алгоритмические аспекты моделирования транспортных потоков"

Настоящий курс посвящен алгоритмическим аспектам задач моделирования и анализа транспортных потоков. Вводная часть курса посвящена описанию постановок различных задач транспортного моделирования на языке теории графов и комбинаторной оптимизации. В основной части курса приводятся современные алгоритмы и методы решения задач указанного типа. Особое внимание уделяется вопросам вычислительной эффективности известных методов, в том числе для графов специальных типов возникающих в задачах транспортного планирования. Важную часть курса составляют онлайн-алгоритмы решения задачах на графах и вопросы их эффективной реализации. Заключительная часть посвящена методам приближенного решения трудных графовых задач, в том числе эвристическим алгоритмам, а также методам машинного обучения в задачах на графах.
1. Задачи на графах. Кратчайший путь. Максимальный поток. Транспортная задача. Некоторые релаксации. 2. Динамическое программирование для задач на графах. Классификация графов с точки зрения динамического программирования. Специальные классы графов. 3. Основные структуры данных поиска и их свойства. Введение в анализ сложности алгоритмов. 4. Задачи поиска на графах. Поиск в глубину, в ширину, двунаправленный поиск. 5. Алгоритмы поиска кратчайших путей в графах. Алгоритмы Беллмана — Форда, Левита, Дейкстры и А*. 6. Алгоритмы поиска всех кратчайших путей в графе. Алгоритм Флойда-Воршелла. 7. Онлайн-алгоритмы. Роль предобработки данных в задачах комбинаторной оптимизации. 8. Потоковые задачи на графах. Эффективные алгоритмы поиска максимального потока. Алгоритм Голдберга-Тарьяна. Алгоритм Голдберга-Рао. Алгоритм Орлина. Алгоритмы поиска максимального потока для графов специальных типов. 9. Точные и приближенные алгоритмы. Понятие сложности задач комбинаторной оптимизации. Непрерывные релаксации дискретных экстремальных задач на графах. 10. Задача Штейнера. Приближенные алгоритмы. Задача Монжа. Подход Л.В. Канторовича. 11. Эвристические алгоритмы и алгоритмы локального поиска в задачах на графах. Алгоритм Вернека быстрого локального поиска для задачи Штейнера. 12. Алгоритмы на графах и машинное обучение.
Литература 1. Введение в математическое моделирование транспортных потоков. Под ред. А.В. Гасникова. М.: МЦНМО, 2013. 427 стр., 2-е изд. http://www.mou.mipt.ru/gasnikov1129.pdf 2. Ahuja R.K., Magnati T.L., Orlin J.B. Network flows: Theory, algorithms and applications. Prentice Hall, 1993. 3. Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ = Introduction to Algorithms. — 1-е. — М.: МЦНМО, 2000. — 960 с 4. J. Kleinberg, E. Tardos. Algorithm design. Addison-Wesley, 2005. 864 p. 5. D.C. Kozen. The design and analysis of algorithms. Springer, 1992. 322 p. 6. Mehlhorn K. Algorithms and Data Structures. Springer, 2008. 300 p. 7. J. Matousek, J. Nesetril. An Invitation to Discrete Mathematics. Oxford University Press; 2 edition, 2008. 464 p. 8. F. Fomin, D. Kratsch. Exact Exponential Algorithms. Springer; 2010. 206 p. 9. Vijay V. Vazirani. Approximation Algorithms. Springer, 2004. 380 p. 10. D. P. Williamson, D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press; 2011. 516 p.