English
!

Доклады

Реализация задачи о максимальном потоке на ЯП Python и ее практическое применение

Кысса А., Лекомцев Д.К., Шек Е.Д.

Российский экономический университет им.Г.В.Плеханова, 177997, г.Москва, Стремянный пер.36, +79774585960, ankyssa7@gmail.com

Задача о максимальном потоке впервые была сформулирована в середине прошлого века и является одной из самых используемых задач в теории оптимизации. Классическая постановка задачи: пусть дан ориентированный граф G, источник s и сток t, при этом s и t принадлежат множеству вершин графа. Необходимо найти такие потоки по дугам, принадлежащим множеству дуг графа, что результирующий поток из s в t будет максимальным. Подсчет максимального потока возможен при наличии сведений о пропускной способности каждой дуги.

Для решения задачи был построен алгоритм, получивший имя его создателей: алгоритм Форда-Фалкерсона. В данной статье мы представляем реализацию этого алгоритма на языке программирования Python и его применение для решения конкретной задачи. Выбор языка обусловлен его гибкостью и быстрым развитием. Вначале мы воспользовались уже готовым модулем NetworkX, который позволяет строить различные виды графов, подсчитывать определенные алгоритмы (напр., максимальный поток, минимальный разрез), выделять необходимые участки рисунка и не только. Разнообразие функций позволяет нам перейти к любой из вариаций графов и пользоваться многообразием представленных действий. Исходя из вышенаписанного, мы считаем, что на данный момент Python является наиболее удобным средством в работе с графами.

Следует акцентировать внимание на практическом применении задачи. Например, она позволяет подсчитать пропускную способность автодорог. Эта тема показалась нам особенно актуальной, так как, живя в Москве, мы нередко наблюдаем огромные пробки. Мы считаем, что нахождение максимального потока автодорог Москвы сможет помочь в оптимизации движения и разгрузки трасс города, а значит облегчит жизнь миллионам людей.

В рамках данной работы мы рассчитываем максимальный поток для автодорог отдельного района Москвы, с учетом и без длины самих дорог. В дальнейших планах использование данного алгоритма с учетом различных факторов: Правила Дорожного Движения, время, затраченное на светофорах. Также мы рассматриваем реализацию загрузки карты, на основе участка которой будет построен граф. Используя данные графа мы будем решать конкретные транспортные задачи определенных макро- и микрорайонов Москвы. Одной из наших целей является усовершенствование алгоритма решения задачи и визуализации задач на ЯП Python.

© 2004 Дизайн Лицея Информационных технологий №1533