Специалисты по информатике теперь могут решить проблему, которой уже несколько десятилетий, практически за то же время, что и её запись. Сохранить статью Прочитать позже
Введение
Группа учёных-компьютерщиков разработала значительно более быстрый алгоритм для одной из старейших задач в информатике: максимального потока. Задача заключается в том, какой объём материала может передаваться по сети от источника к приемнику, если пропускная способность звеньев сети ограничена.
Новый алгоритм «невероятно быстр», — заявил Дэниел Спилман из Йельского университета. «Я был склонен полагать… алгоритмов, настолько хороших для решения этой задачи, не существует».
Задача о максимальном потоке изучается с 1950-х годов, когда она была сформулирована для изучения советской железнодорожной системы. «Она, пожалуй, старше, чем теория информатики», — сказала Эдит Коэн из исследовательского центра Google в Маунтин-Вью, Калифорния. У этой задачи множество приложений: потоки данных в интернете, составление расписаний авиарейсов и даже поиск соискателей на вакансии. В новой статье рассматриваются как задача о максимальном потоке, так и более общая версия задачи, в которой также требуется минимизировать затраты. За прошедшие годы эти две задачи вдохновили многие из крупнейших достижений в области алгоритмических технологий. «Они, пожалуй, и есть причина, по которой у нас есть область алгоритмов», — сказал Спилман.
Новый алгоритм решает эти две задачи практически за линейное время, то есть время выполнения алгоритма примерно пропорционально времени, необходимому для записи информации о сети. Ни один другой алгоритм для решения этих задач не может сравниться с такой скоростью для всех возможных сетей. Результат заставил его «подпрыгнуть от восторга», — сказал Сатиш Рао из Калифорнийского университета в Беркли. «Это потрясающе».
Пока это в первую очередь теоретический прогресс, поскольку повышение скорости заметно только в сетях, значительно превышающих те, что встречаются в реальном мире, где задачи максимального потока уже решаются довольно быстро (по крайней мере, если они не требуют минимизации затрат). Но, по прогнозам Ричарда Пэна из Университета Ватерлоо в Канаде, одного из шести создателей алгоритма, отдельные фрагменты нового алгоритма могут найти практическое применение уже через год. Исследователи утверждают, что в ближайшие годы специалисты по информатике, вероятно, найдут способы сделать его более практичным и, возможно, даже немного быстрее.
Однако даже если улучшения действительно появятся, эта новая статья — настоящий прорыв, считает Александр Модри из Массачусетского технологического института. «По сути, это лучшее из возможного», — добавил он.
Один путь за раз
По словам Пэна, так много специалистов по информатике изучали задачу максимального потока, что доклады о прошлых работах на конференциях выглядят как титры после фильма. Однако большинство людей датируют первый формальный алгоритм 1956 годом, когда Лестер Форд и Делберт Фулкерсон решили задачу максимального потока, используя так называемый «жадный» подход, который на каждом этапе использует наиболее доступные объекты.
Чтобы понять этот подход, представьте себе сеть автомагистралей, по которой вы хотите отправить как можно больше грузовиков доставки из Лос-Анджелеса в Нью-Йорк за заданное время. Алгоритм Форда и Фулкерсона начинается с выбора одного пути из Лос-Анджелеса в Нью-Йорк и направления по нему как можно большего количества грузовиков. Обычно это не позволяет использовать всю пропускную способность всех дорог на этом пути: если один из участков вашего пути представляет собой пятиполосное шоссе, но ведёт к двухполосному мосту, вы можете одновременно запустить только два грузовика.
Затем алгоритм пересматривает пропускную способность этих участков, учитывая, что вы уже использовали часть их пропускной способности: он вычитает количество отправленных вами грузовиков из пропускной способности участков, поэтому пропускная способность пятиполосного шоссе теперь составляет всего 3, а двухполосного моста — 0. Одновременно алгоритм добавляет 2 к пропускной способности этих же участков в обратном направлении, чтобы мы могли отменить часть этого потока позже, если захотим.
Затем алгоритм находит новый путь из Лос-Анджелеса в Нью-Йорк, на котором достаточно места для нескольких грузовиков, отправляет по нему максимально возможное количество грузовиков и снова обновляет пропускную способность. После конечного числа таких шагов не останется ни одного пути из Лос-Анджелеса в Нью-Йорк, по которому можно было бы пропустить больше грузовиков, и на этом всё — мы просто объединяем все построенные нами потоки и получаем максимально возможный поток через сеть.
Алгоритм Форда и Фулкерсона не пытается делать разумный выбор по ходу дела. Если он выбирает путь, который отсекает другие полезные маршруты, это просто проблема, которую он решает позже. В течение десятилетий после публикации алгоритма исследователи пытались ускорить его выполнение, заставляя алгоритм делать более разумный выбор — например, всегда использовать кратчайший доступный путь или путь с наибольшей доступной пропускной способностью.
В 1970 году Ефим Диниц нашёл эффективный способ использовать все кратчайшие пути в сети за один шаг. Это привело к созданию алгоритма, время выполнения которого в сетях с низкой ёмкостью, как показали Шимон Эвен и Роберт Тарьян, кратно m1,5, где m — количество связей в сети. (Для сравнения, алгоритм Форда-Фалкерсона в сетях с низкой ёмкостью требует шагов, кратных m2.) Почти 30 лет спустя Рао и Эндрю Голдберг, который сейчас работает в Amazon, получили аналогичные результаты для сетей с высокой ёмкостью. Но никто не смог превзойти показатель 1,5. «К началу 2000-х годов… этот барьер в m1,5 укрепился», — сказал Сушант Сачдева из Университета Торонто, один из авторов новой статьи.
Чтобы добиться прогресса, специалистам по информатике придется использовать совершенно иной подход.
От комбинаций к исчислению
До сих пор все эти алгоритмы использовали комбинаторные подходы, которые на каждом этапе ищут определённую структуру и используют её для обновления потока. Но в 2003 году Спилман и Шан-Хуа Тэн из Университета Южной Калифорнии открыли путь к радикально иному подходу к «оптимизации», в котором для нахождения оптимального решения используются методы математического анализа.
Спилман и Тэн разработали быстрый алгоритм оптимизации, который решает не задачу максимального потока, а тесно связанную с ней задачу поиска электрического потока с наименьшей энергией через сеть проводов, каждый из которых имеет заданное сопротивление. По словам Сачдева, достижение Спилмана и Тэна стало «ключевым моментом».
Команда, создавшая сверхбыстрый алгоритм, способный определить максимальный поток и минимальную стоимость сети: (по часовой стрелке сверху слева) Ян Лю, Ли Чен, Расмус Кинг, Максимилиан Пробст Гутенберг, Ричард Пэн и Сушант Сачдева.
Вскоре исследователи начали изучать, как применить это достижение к задаче о максимальном потоке. Идея заключается в том, чтобы представить нашу сеть автомагистралей как сеть проводов и увеличить сопротивление на магистралях с недостаточной пропускной способностью, чтобы воспрепятствовать движению электронов по ним. Благодаря Шпильману и Тенгу мы можем быстро рассчитать поток электричества по этим проводам, и он будет иметь приблизительные характеристики максимального потока автомобилей по магистралям. (Они не будут полностью совпадать, поскольку задача о потоке электричества не накладывает жестких ограничений на пропускную способность проводов.)
Затем, создав этот начальный поток, вы перестраиваете ёмкости, как в комбинаторных алгоритмах Форда и Фулкерсона. Затем вы переустанавливаете сопротивление каждого провода, чтобы отразить изменившиеся ёмкости, и решаете новую электрическую задачу, и так далее.
В отличие от комбинаторных подходов, которые изменяют только один участок сети за раз, оптимизационный подход Спилмана и Тенга охватывает всю сеть сразу. Это делает каждый шаг более эффективным, поэтому для достижения максимума требуется меньше шагов. В 2008 году Сэмюэл Дейч из Google и Спилман использовали этот подход, чтобы фактически достичь предыдущего предела m1.5 для максимального потока. Затем, в 2013 году, Модри развил этот подход дальше, преодолев барьер m1.5 для сетей с низкой пропускной способностью, увеличив время выполнения примерно до m1.43. «Это было потрясающе», — сказал Рао.
В последующие годы исследователи расширили этот подход, но застряли на значении m1,33. Они начали задаваться вопросом, не является ли этот показатель степени фундаментальным пределом.
Максимально возможное время выполнения алгоритма максимального потока было бы кратно m (то есть m1.0), поскольку для записи сети требуется несколько шагов, кратных m. Это называется линейным временем. Но многим исследователям такой молниеносный алгоритм казался немыслимым.
«Не было никаких оснований полагать, что мы сможем это сделать», — сказал Шпильман.
Сокращение, повторное использование, переработка
Однако авторы новой статьи посчитали, что из подхода Дейча и Спилмана можно выжать больше. Модри использовал его для сокращения количества шагов, необходимых для решения задачи максимального потока, но это сокращение имело свою цену: на каждом этапе приходилось переписывать всю сеть и решать её электрический поток с нуля.
Этот метод рассматривал алгоритм Шпильмана и Тэна как «чёрный ящик» — неважно, что именно алгоритм делает внутри. Шесть исследователей решили вместо этого разобраться в сути алгоритма и адаптировать его различные компоненты к задаче максимального потока. Они подозревали, что эти компоненты могут даже позволить им решить более сложную задачу «минимальной стоимости», в которой требуется найти самый дешёвый способ переправить заданное количество материала. Специалистам по информатике давно известно, что любой алгоритм минимальной стоимости также может решить задачу максимального потока.
Как и в случае с другими подходами к оптимизации, исследователи предложили понятие «энергии» потока — функции, учитывающей стоимость и пропускную способность звеньев. Перемещение потока с дорогостоящего маломощного звена на дешёвое высокопроизводительное звено снижает общую энергию системы.
Чтобы понять, как быстро перевести поток в состояние с низкой энергией, исследователи объединили этот подход к оптимизации со старым комбинаторным подходом. Последний, изменяющий только часть сети за раз, открывает возможность повторного использования части результатов работы, проделанной на предыдущих этапах.
На каждом этапе алгоритм ищет цикл — путь, начинающийся и заканчивающийся в одной точке, — который может снизить энергозатраты. Основная идея проста: представьте, что вы создали поток, направляющий грузовики из Чикаго в Нью-Йорк по платной дороге, но затем обнаруживаете, что есть более дешёвая автомагистраль. Добавление цикла, начинающегося в Нью-Йорке, следующего в Чикаго по дорогой дороге и возвращающегося по более дешёвому маршруту, фактически отменяет дорогой путь и заменяет его более дешёвым, снижая общую стоимость потока.
Этот подход использует гораздо больше шагов, чем электрический, поэтому на первый взгляд он «звучит как регресс», — говорит Валери Кинг из Университета Виктории в Канаде. Чтобы компенсировать это, на каждом этапе алгоритм должен невероятно быстро находить подходящий цикл — быстрее, чем требуется для простого осмотра всей сети.
Именно здесь вступает в действие внутренняя работа алгоритма Шпильмана и Тенга. Их алгоритм предлагает новый способ использования «низкоэластичного остовного дерева» — своего рода внутренней основы, охватывающей многие из наиболее важных особенностей сети. При наличии такого дерева всегда есть как минимум один хороший цикл, который можно построить, добавив одно звено извне. Таким образом, наличие низкоэластичного остовного дерева значительно сокращает количество циклов, которые необходимо учитывать.
Даже в этом случае, для обеспечения быстрой работы алгоритма, команда не могла позволить себе строить совершенно новое остовное дерево на каждом этапе. Вместо этого им нужно было гарантировать, что каждый новый цикл вызывал лишь незначительные резонансные эффекты в остовных деревьях, чтобы можно было повторно использовать большую часть предыдущих вычислений. Достижение такого уровня контроля было «главной сложностью», — сказал Ян Лю, аспирант Стэнфордского университета и один из авторов статьи.
В конце концов, исследователи создали алгоритм, работающий «почти линейно» по времени, то есть по мере роста сетей до всё большего размера время его работы приближается к числу, кратному m. Это настоящий «прорыв», сказал Модри.
Алгоритм использует многие идеи из работы Шпильмана и Тэна, но объединяет их в нечто совершенно новое. По словам Шпильмана, смотреть на алгоритм — всё равно что смотреть на автомобиль, если вы видели только конные экипажи. «Я вижу, что у него есть место для сидения, я вижу, что у него есть колёса, я вижу, что у него есть что-то, что приводит его в движение. Но они заменили лошадь двигателем».
Рао предсказал, что анализ, проводимый группой, будет долгим и сложным, но вскоре другие исследователи займутся его упрощением. «Мне кажется, что в ближайшие несколько лет всё станет чище и лучше», — сказал он.
По словам Спилмана, как только алгоритм будет оптимизирован, специалисты по информатике, вероятно, начнут использовать его в качестве подпрограммы в алгоритмах решения различных задач. «Теперь, когда мы знаем, что можем делать это очень быстро, люди найдут для него множество применений, о которых раньше и не думали».
Это головокружительное ускорение решения задачи на максимальный поток заставило Спилмана задуматься о других центральных проблемах теории алгоритмов. «Что ещё мы могли бы сделать?»
Источник: www.quantamagazine.org
