§3.5. Венгерский метод Куна-Манкреша
В 1955 году Кун разработал новый комбинаторный подход решения задачи о назначениях. Он базируется на работе Егервари от 1931 года, а потому Кун выбрал для него название «Венгерский метод». В 1957 году метод был улучшен Манкрешом (Munkres). Несмотря на то, что в оригинале метод был сформулирован в терминах матриц, он представляет собой комбинаторный подход к решению задачи о назначениях. Оригинальный алгоритм имеет сложность работы O(N^4). В одной из статей Форда и Фалкерсона от 1957 года, в примечании было приведено следующее интересное сравнение: «Для решения задачи об оптимальных назначениях размера 20*20, при использовании симплекс-метода, требовалось около часа вычислений на компьютере. Новый подход Куна позволяет решить эту задачу всего за 30 минут вручную».
В 1970 году Эдмондс и Карп улучшили алгоритм, что позволило достичь времени работы O(N^3). С этих пор задачу о назначениях можно было фактически считать решенной.
Глава 4. Дальнейшие исследования в теории потоков
§4.1. Потоки минимальной стоимости
Аналогично тому, как задача о паросочетании была обобщена на случай ребер с различными весами (задача о назначениях), задача о максимальном потоке может быть обобщена как задача о максимальном потоке минимальной стоимости. Для решения этой задачи также справедлив метод Форда и Фалкерсона, за исключением того, что дополняющий путь нужно выбрать кратчайшим относительно стоимостей ребер сети. Для этой цели можно использовать классический алгоритм Форда-Беллмана нахождения кратчайшего пути. Это позволит достичь оценки времени работы алгоритма для максимального потока минимальной стоимости O(E V^3). Джонсон (Johnson) разработал метод потенциалов, обобщающий классический алгоритм Дейкстры нахождения кратчайшего пути на случай графов с отрицательными ребрами, что позволило улучшить время работы до O(E V^2).
Однако, существуют более эффективные с практической точки зрения алгоритмы решения задачи. Идея состоит в последовательном приближении («алгоритм масштабирования») исходной сети. Соответствующий алгоритм был изложен в 1987-1989 годах Гольдберг (Goldberg) и Тарьян (Tarjan) опубликовали целую серию статей по этой тематике. Другой алгоритм в 1988 году представил Орлин (Orlin) в статье «Быстрый сильно-полиномиальный алгоритм нахождения максимального потока минимальной стоимости».
§4.2. Динамические потоки. Задача транспортировки
Интерес к транспортировке возник в области потоков в сетях в течение 1940-х и 50-х годов. Было опубликовано множество работ в этой области, однако все они содержали одно интересное упущение. Несмотря на естественную связь между потоками в сетях и задачами транспортировки, большинство исследований в области теории потоков игнорировали самый главный вопрос, который задает любой ребенок, сидящий на заднем сиденье автомобиля: «Мы уже приехали?». Родители, вынужденные постоянно выслушивать этот вопрос, несомненно, подумают о времени, прежде чем думать о том, куда и как ехать далее.
Форд и Фалкерсон были хорошо осведомлены о важности времени в транспортировке, и они учли его в их модели сети. Они обобщили стандартное определение сети путем добавления в него транзитных времен между вершинами, получив тем самым динамическую сеть. Каждое ребро yz в динамической сети моделирует трубопровод из вершины y в вершину z. Пропускная способность ребра yz соответствует площади сечения труб, тем самым ограничивая количество потока, которое может быть передано за единицу времени. Транзитные времена соответствуют длине трубопровода; они определяют, сколько времени требуется потоку на прохождения из вершины y в вершину z вдоль ребра yz. Динамический поток перемещается с течением времени в динамической сети. Он является расширением традиционных потоков; отображением пар (ребро, время) в величину потока, а не отображением ребер как это было ранее.
Со времен Форда и Фалкерсона исследования в области динамических потоков направлены как на теоретические исследования математических моделей, так и на практические и алгоритмические аспекты их реализации. В то же время было уделено недостаточно внимания алгоритмической теории. В частности, очень немного было известно о вычислительной сложности задач о динамических потоках. В диссертации Хоупа (Hoppe, 1995) акцент был сделан именно на разработке теоретически эффективных алгоритмов. Эта работа устранила разрыв между изучением потоков в традиционных и динамических сетях.
§4.3. Универсально-максимальные динамические потоки
Форд и Фалкерсон рассматривали простейшую потоковую задачу в динамической сети: задачу о максимальном динамическом потоке. Входом для данной задачи является временной интервал T и динамическая сеть с одним источником и одним стоком; решением является допустимый динамический поток, который пересылает наибольшее возможное количество потока из истока в сток за время T.
Форд и Фалкерсон обнаружили оригинальный полиномиальный алгоритм для данной задачи. Гэйл, Уилкинсон и Миниека рассматривали вариант задачи о максимальном динамическом потоке, в котором сток должен был получить как можно больше потока на каждом промежуточном шаге до T и включительно. Вдобавок к этому поток должен покидать источник как можно позднее. (Факт существования такого потока нетривиален и был установлен Гэйлом). Позже Уилкинсон и Миниека независимо получили псевдополиномиальный алгоритм нахождения такого потока.
Первый полиномиальный алгоритм нахождения значения универсально-максимального динамического потока для любого ребра для каждого отдельного момента времени (т.е. временной разрез полного решения) был предложен Хоупом. Он также предложил первый полиномиальный алгоритм, который приближает универсально-максимальный динамический поток с коэффициентом 1 + eps для любого eps > 0. (Алгоритм работает полиномиальное относительно 1/eps время).
§4.4. Наибыстрейшие потоки
Другой вариант задачи о максимальном динамическом потоке это задача о наибыстрейшем потоке, в которой нам задана величина потока v и
требуется найти допустимый динамический поток, который доставит v единиц потока из источника в сток за наименьшее возможное время. Задача о наибыстрейшем потоке может быть сведена к задаче о максимальном динамическом потоке с помощью двоичного поиска. Баркард (Burkard) и др. изучали эту задачу и описали более эффективную технику ее решения.
Задача эвакуации является обобщением задачи о наибыстрейшем потоке на случай нескольких источников. Для каждого из них нам задан вектор снабжения и требуется найти допустимый динамический поток, который доставляет требуемое количество потока из каждого источника в сток за наименьшее возможное время. В традиционной сети без времен транзита, задача эвакуации тривиально сводится к задаче о максимальном потоке с одним источником (путем добавления "суперисточника"). Однако, в динамическом случае, задача является гораздо более сложной, чем задача о наибыстрейшем потоке. В то же время она полезнее: задача эвакуации была изначально сформулирована в практической модели эвакуации из зданий.
Хоуп (Hoppe) в своей диссертации (1995) представил первый (сильно) полиномиальный алгоритм для задачи о наибыстрейших перевозках - обобщении задачи эвакуации, где в дополнение к нескольким источникам разрешены несколько стоков. Алгоритм Хоупа также для целочисленных входных данных гарантирует целочисленное решение.
В 2005 году в работе «Наибыстрейшие потоки с несколькими источниками» Рауфа (Rauf) алгоритм Хоупа был обобщен на случай сетей с несколькими источниками.
§4.5. Планирование сетей
Несмотря на то, что задача эвакуации и задача о наибыстрейшей перевозке мотивированы необходимостью планирования действий в случае бедствий и непредвиденных ситуаций, они имеют приложения и в других областях. Рассмотрим компьютерную сеть; каждая машина имеет свою очередь на вычисление задач единичного размера. Задача может быть либо вычислена на машине локально, либо послана по сети для удаленного вычисления. Каждое соединение в сети можно охарактеризовать пропускной способностью и временем транзита. Требуется распланировать выполнение задач таким образом, чтобы последняя из них была вычислена как можно раньше.
Эта задача легко сводится к задаче о наибыстрейших перевозках, применяя наш алгоритм решения которой мы получим первый полиномиальный алгоритм решения задаче о планировании вычислительных сетей для задач единичного размера, но только в некоторых очень специальных случаях. Физзано (Fizzano) и Штейн (Stein) рассматривали кольцевые сети с единичными пропускными способностями и транзитными временами. Хоуп предложил алгоритм, работающий в сети общего вида, с произвольными пропускными способностями и временами транзита.
Заключение
Исследования потоков в сетях развивались одновременно с теорией линейного программирования (и теорией оптимизации в более общем случае). Так как потоки в сетях представляют собой специальный вид линейных программ, они могут быть решены как линейные программы. Более того, для сетей с целочисленными пропускными способностями гарантировано наличие целочисленного решения. Доказательство этого факта в 1955 году позволило получить первый алгоритм точного решения потоковых задач в сетях небольшого размера.