К задаче о максимальном потоке найден принципиально новый подход

29.09.2010, СР, 10:10, Мск

Задача о максимальном потоке - одна из основных проблем в теории вычислительных систем. Впервые она была решена при организации Берлинского воздушного моста после Второй мировой войны. Задача является компонентом многих логических задач и главным пунктом курсов введения в теорию алгоритмов. Десятилетиями эта задача занимала ученых, и все новые и новые алгоритмы появлялись один или два раза в год. Однако по мере изучения проблемы их поток начал стихать, и за последние десятилетия эффективных способов решения этой задачи больше не появлялось. Ученым из Массачусетского технологического института совместно с коллегами из Йельского университета и Университета Южной Калифорнии удалось найти алгоритм, существенно повышающий скорость решения задачи о максимальном потоке.

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

Граф - это набор вершин и ребер, их соединящих. На рисунке вершины обычно обозначаются точками, а ребра - линиями.

Задача о максимальном потоке решается при помощи графов. Обычное изображение коммуникационной сети - это граф, так же как и родословное дерево, например. В задаче о максимальном потоке одна из вершин графа назначается истоком - точкой, в которой все объекты начинают свой путь, а другая - стоком - точкой, в которую они все направляются. Пропускная способность каждого ребра ограничена.

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

До сих пор алгоритмы решения этой задачи рассматривали за раз только один способ пройти граф. Если пропускная способность этого пути позволяла, алгоритм просто посылал по нему больше объектов и "смотрел", что получится. Улучшения алгоритма в основном касались изобретения все более "умных" способов перебора возможных путей.

Однако команде ученых из разных научных заведений, состоящей из Джонатана Кельнера (Jonathan Kelner), Александра Мэдри (Aleksander Madry), Поля Кристиано (Paul Christiano), Даниэля Спельмана (Daniel Spielman) и Шангуа Тенга (Shanghua Teng), удалось найти принципиально новый подход к проблеме. Они представили граф в виде матрицы. Каждый узел графа связан с одной строкой и одним столбцом матрицы. Число, находящееся на пересечении строки и столбца, показывает, какое количество объектов может быть переслано между двумя узлами.

В линейной алгебре строка матрицы может быть представлена в виде уравнения, и инструменты этого раздела математики позволяют одновременно решать все уравнения, представленные всеми строками матрицы. Постоянно меняя числа в матрице и заново решая уравнения, исследователи могут эффективно вычислять все значения в графе сразу. Такой подход гораздо эффективнее последовательного перебора путей. Если обозначить количество узлов как N, а количество связей между ними как L, тогда скорость выполнения быстрейшего из предыдущих алгоритмов будет пропорциональна (N + L)^3/2, в то время как новый алгоритм будет выполняться за время, пропорциональное (N + L)^4/3. В действительности ученые еще не написали программу, работающую по этому алгоритму, и на практике его эффективность будет зависеть от эффективности написания кода и управления памятью. Но теоретически в такой сети, как интернет, которая содержит около 100 млрд узлов, новый алгоритм сможет решать задачу о максимальном потоке в 100 раз быстрее, чем его предшественник.

Однако не только очевидная практическая ценность алгоритма впечатлила Джона Хопкрофта (John Hopcroft), профессора прикладной математики Корнельского университета. "Я полагаю, что эта идея может быть применима к широкому кругу других проблем, - комментирует Хопкрофт. - Это принципиально новый подход. Обычно, когда случаются прорывы такого рода, формируется целый подраздел науки, который в 4-5 лет дает целую серию заметных результатов".