Ученые упростили решение задачи о максимальном потоке - Новости

08.01.2014 - «Проблема поиска наиболее эффективного пути в транспортной системе или сетях интернета является наиболее актуальной для математиков и программистов уже на протяжении десятилетий.»

Решение заключалось в использовании так называемых алгоритмов «максимального потока», в которых сеть представлена графом с множеством вершин, соединенных ребрами.

Каждое ребро, которое может представлять собой дорогу или оптоволоконный кабель, имеет определенную пропускную способность. Алгоритмы должны учитывать эти ограничения при поиске наиболее эффективного пути передачи информации или доставки груза. Интернет разросся до небывалых масштабов, делая традиционные методы поиска крайне затратными по времени.

Исследователи из Массачусетского технологического института рассмотрели граф как множество резисторов, соединяющих точки A и B. Пропуская ток через них, электричество протекало не по одному конкретному резистору, а через разные, оставляя им небольшое количество тока, т. е. протекая по всему графу глобально. Такой принцип существенно ускорил решение задачи о максимальном потоке.

Новый алгоритм определяет легкие пути и проблемные маршруты или «узкие места», сосредотачиваясь на структурах высокого уровня, используя время более рационально.

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

Теги: Наука