.gif)
Исследователи из Массачусетского технологического института предложили новый алгоритм решения задачи максимального потока, более эффективный чем существующие, поскольку его быстродействие уменьшается в обратной пропорции к сложности задачи.
В числе возможных применений алгоритма разработчики называют оптимизацию планирования расписаний работы летных экипажей и выбор самого быстрого пути передачи данных по сети с высоким трафиком. Алгоритм еще не получил официального наименования, пока что его называют KLOS по фамилиям разработчиков: Джонатан Келнер, Инь Тат Ли, Лоренцо Орекиа и Аарон Сидфорд.
Алгоритмы нахождения максимального потока действуют путем построения графа, вершины которого представляют конечные точки маршрутов, а ребра — связи между ними; затем выбирается оптимальный путь с учетом предельной пропускной способности каждой вершины. Обычно ребра при этом насыщаются по одному, и при большом их количестве время выполнения алгоритма и затрачиваемые ресурсы могут вырасти настолько, что эффективность сводится на нет. Новый алгоритм, по словам ученых, проверяет все возможные пути одновременно и при этом распознает узкие места сети.
Как отмечают исследователи, пока разработана лишь теоретическая основа алгоритма, а на его реализацию может уйти еще некоторое время.