В МТИ оптимизировали алгоритм выбора кратчайшего маршрута
В МТИ оптимизировали алгоритм выбора кратчайшего маршрута




09:45 17.01.2014

|   698 прочтений



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

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

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

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

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


Теги: