Потоки в сетях

Транспортные сети

Наше описание алгоритмов вычисления сетевых потоков мы начнем с идеализированной физической модели, которая наглядно продемонстрирует несколько фундаментальных понятий. Допустим, что имеется система взаимосвязанных нефтепроводных труб различных диаметров, а на соединениях труб установлены вентили, управляющие движением потоков, как показано на рис 22.5. Далее мы будем предполагать, что в системе трубопроводов имеется единственный исток (допустим, нефтяное месторождение) и единственный сток (к примеру, нефтеперерабатывающий завод), в который попадают все потоки. В каждом соединении потоки нефти находятся в равновесии: объем поступающей нефти равен объему вытекающей нефти. Мы будем измерять потоки и пропускную способность труб в одних и тех же единицах (например, в галлонах в секунду).

Если общая пропускная способность труб, входящих в каждый вентиль, равна общей пропускной способности выходящих труб, то решать вообще нечего: нужно просто заполнить по максимуму все трубы. Иначе будут заполнены не все трубы, но нефть будет течь по трубам в соответствии с настройками вентилей и свойством, что объем нефти, поступающей в каждое соединение, равен объему вытекающей нефти. А из баланса в соединениях следует и общий баланс в сети: в лемме 22.1 будет показано, что объем нефти, втекающей в сток, равен объему нефти, вытекающей из истока. А, как показано на рис 22.6, настройки вентилей на соединениях могут оказывать нетривиальное влияние на потоки в сети. И вот нас интересует следующий вопрос: какие настройки вентилей обеспечат максимальный поток нефти из истока в сток?

Эту ситуацию можно непосредственно смоделировать при помощи сети (взвешенный орграф, согласно определению из ) с одним истоком и одним стоком. Ребра сети соответствуют трубам, вершины соответствуют соединениям труб с вентилями, которые регулируют потоки нефти в исходящие ребра, а веса ребер соответствуют пропускной способности труб. Мы считаем ребра ориентированными, т.е. нефть в каждой трубе может течь только в одном направлении. По каждой трубе проходит определенный поток, который меньше или равен ее пропускной способности, и каждая вершина удовлетворяет условию баланса: входной поток равен выходному потоку.

Транспортная сеть - это взвешенная сеть, в которой веса ребер интерпретируются как пропускные способности (вверху). Требуется вычислить второе множество весов ребер, ограниченное пропускными способностями, которые мы называем потоками. Внизу показаны наши соглашения относительно вычерчивания транспортных сетей. Ширина каждого ребра пропорциональна его пропускной способности; объем потока в каждом ребре показан заштрихованной частью; поток на наших рисунках всегда направлен из единственного истока вверху в единственный сток внизу; пересечения (как между ребрами 1-4 и 2-3 в рассматриваемом примере) не представляют вершин, если не обозначены как вершины. За исключением истока и стока, в каждой вершине входной поток равен выходному потоку: например, в вершину 2 входят 2 единицы потока (из вершины 0) и выходят 2 единицы потока (1 единица в вершину 3 и 1 единица в вершину 4).

Открыв вентили вдоль пути 0-1-3-5, можно инициировать в этой сети поток мощностью 2 единицы (вверху); открыв вентили вдоль пути 0-2-4-5, получим еще 1 единицу потока (в центре). Звездочками отмечены заполненные ребра. Поскольку ребра 0-1, 2-4 и 3-5 заполнены, прямого способа увеличить поток из 0 в 5 не существует, но если еще открыть вентиль в вершине 1, чтобы направить часть потока в ребро 1-4 , то будет задействовано ребро 4-5, благодаря чему будет получен максимальный поток в данной сети (внизу).

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

Потоковая модель непосредственно применима к задаче распределения - при этом значения потоков интерпретируются как их интенсивность, и транспортная сеть описывает потоки товаров точно так же, как и потоки нефти. Например, потоки на рис 22.5 можно интерпретировать так: два элемента в единицу времени пересылаются из вершины 0 в 1 и из 0 в 2, один элемент в единицу времени - из 0 в 2, один элемент в единицу времени - из 1 в 3 и из 1 в 4 и т.д.

Другой способ интерпретации потоковой модели для задачи распределения - потоки интерпретируются как объемы товаров, и тогда сеть описывает только одноразовую рассылку товара. Например, потоки на рис 22.5 можно интерпретировать, как трехэтапную поставку четырех единиц товара из вершины 0 в 5: сначала пересылаются две единицы товара из 0 в 1 и две единицы из 0 в 2, так что в каждой из этих вершин остается по две единицы товара. Далее выполняется пересылка по одной единице товара из 1 в 3, из 1 в 4 , из 2 в 3 и из 2 в 4 , и в каждой из вершин 3 и 4 остается по две единицы товара. Рассылка завершается доставкой двух единиц товара из вершины 3 в 5 и двух единиц из 4 в 5.

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

В этом определении слово " выбранный " означает, что вершина s не обязательно должна быть истоком (вершина без входящих ребер), а вершина t - стоком (вершина без исходящих ребер), но мы будем рассматривать их именно так, игнорируя в наших рассуждениях (и алгоритмах) ребра, входящие в s, и ребра, исходящие из t. Во избежание путаницы в наших примерах мы будем рассматривать сети с одним истоком и стоком, а более общие ситуации рассмотрим в разделе 22.4. Вершины s и t мы будем называть, соответственно, " истоком " и " стоком " st-сети, поскольку они выполняют в сети именно эти роли. Остальные вершины сети мы будем называть внутренними вершинами.

Мы будем называть суммарный поток в вершину притоком (inflow) этой вершины, а суммарный поток из вершины - оттоком (outflow) этой вершины. По соглашению потоки в ребрах, входящих в исток, и потоки в ребрах, исходящих из стока, равны нулю, а в лемме 22.1 будет показано, что отток истока всегда равен притоку стока, и этот поток мы будем называть мощностью (value) сети. Имея эти определения, нетрудно дать формальное определение нашей основной задачи.

Максимальный поток. Для заданной st-сети необходимо найти такой поток, что никакой другой поток из s в t не имеет большего значения. Для краткости будем называть такой поток максимальным потоком (maxflow), а задачу вычисления такого потока в сети будем называть задачей о максимальном потоке. В некоторых приложениях достаточно знать только величину максимального потока, но обычно требуется знать структуру потока (величины каждого реберного потока), обеспечивающего эту величину.

На ум тут же приходят различные варианты этой задачи. Можно ли рассматривать сеть с несколькими истоками и стоками? А как насчет сетей без истоков и стоков? Может ли поток проходить по ребрам в обоих направлениях? Возможны ли ограничения на пропускную способность вершин вместо ограничений на ребра (или наряду с ними)? Для алгоритмов на графах характерно то, что отделение тривиальных ограничений от ограничений, влекущих далеко идущие последствия, само по себе может оказаться трудной задачей. После того, как мы рассмотрим алгоритмы решения фундаментальной задачи, в разделах 22.2 и 22.3 мы исследуем эту задачу и приведем примеры сведения к задаче о максимальном потоке множества других с виду различных задач.

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

В доказательстве леммы 22.1 можно обойтись и без фиктивных вершин, добавить в любую транспортную сеть ребро из t в s с пропускной способностью, равной мощности сети, и знать, что приток равен оттоку для любого множества узлов этой расширенной сети. Такой поток называется циркуляцией (circulation), а подобное построение показывает, что задача о максимальном потоке сводится к задаче поиска такой циркуляции, которая обеспечивает максимальный поток в заданном ребре.

Это иллюстрация сохранения баланса потоков при объединении множеств вершин. Два меньших овала соответствуют двум произвольным непересекающимся множествам вершин, а буквы представляют потоки в множествах ребер: A - величина потока в левое множество, кроме притока из правого множества, х - величина потока в левое множество из правого множества и т.д. Если имеет место баланс потоков между двумя множествами, то должно выполняться равенство A + x = B + у для левого множества и C + y = D + x для правого множества. Суммируя эти два равенства и исключая сумму x + у, мы получим A + C = B + D, - т.е. для объединения двух множеств приток равен оттоку.

В некоторых ситуациях подобная формулировка упрощает наши рассуждения. Например, как показано на рис 22.8, она приводит к интересному альтернативному представлению потоков как множества циклов.

Если задано множество циклов и величина потока для каждого цикла, то легко вычислить соответствующую циркуляцию: нужно пройти по каждому циклу и добавить указанную величину потока к каждому ребру. Обратное свойство более интересно: можно найти множество циклов (и величину потока для каждого из них), которое эквивалентно любой заданной циркуляции.

Процесс, описанный в доказательстве, показан на рис 22.9. В случае st-потоков применение этой леммы к циркуляции, полученной добавлением ребра из s в t, позволяет сделать вывод, что любой st-поток можно представить в виде потока вдоль множества не более E ориентированных путей, каждый из которых есть либо путь из s в t, либо цикл.

Здесь показано, что приведенную слева циркуляцию можно разложить на четыре цикла 1-3-5-4-1, 0-1-3-5-4-2-0, 1-3-5-4-2-1 и 3-5-4-3 с весами, соответственно, 2, 1, 1 и 3. Ребра каждого цикла показаны в соответствующем столбце, а суммирование весов каждого ребра в каждом цикле, в который оно входит (по соответствующей строке), дает его вес в циркуляции.

Чтобы разложить произвольную циркуляцию на множество циклов, мы многократно выполняем следующий процесс: проходим по любому пути, пока не встретим какой-либо узел второй раз, затем находим минимальный вес в обнаруженном цикле, после чего вычитаем минимальный вес из весов каждого ребра обнаруженного цикла и удаляем каждое ребро, вес которого стал нулевым. Например, на первой итерации мы проходим по пути 0-1-3-5-4-1 и обнаруживаем цикл 1-3-5-4-1, потом вычитаем 1 из весов всех ребер цикла, и в результате удаляем из цикла ребро 4-1, так как его вес стал нулевым. На второй итерации мы удаляем ребра 0-1 и 2-0, на третьей - 1-3, 4-2 и 2-1, а на последней итерации удаляем 3-5, 5-4 и 4-3.

Эти свойства позволяют получить представление о природе потоков, что будет полезно при разработке и анализе алгоритмов вычисления максимальных потоков.

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

Для реализации алгоритма вычисления максимального потока мы воспользуемся классом GRAPH из , но с указателями на более сложный класс EDGE. Вместо одного веса, как это было в и , мы используем приватные члены данных pcap и pflow (пропускная способность и величина потока), а также общедоступные функции-элементы cap() и flow(), которые возвращают их значения. Хотя сети являются ориентированными графами, наши алгоритмы будут проходить по ребрам в обоих направлениях, поэтому мы используем представление в виде неориентированного графа из и функцию-член from, которая позволяет отличить ребро u-v от ребра v-u .

Такой подход позволяет отделить абстракцию, необходимую нашим алгоритмам (ребра идут в обоих направлениях), от конкретной структуры клиентских данных и ставит перед этими алгоритмами простую цель: присвоить элементам flow в ребрах клиента такие значения, которые максимизируют поток через сеть. Критическим моментом наших реализаций является замена абстракции сети, которая зависит от значений потока и реализуется функциями-членами класса EDGE. Мы рассмотрим реализацию класса EDGE в разделе 22.2 (программа 22.2).

Поскольку транспортные сети обычно разрежены, мы воспользуемся классом GRAPH на основе представления списками смежных вершин, как в реализации класса SparceMultiGRAPH из программы 20.5. Но более важно то, что типичные транспортные сети могут содержать параллельные ребра (различной пропускной способности), соединяющие две вершины. Класс SparceMultiGRAPH не требует специальных мер в подобных ситуациях, но в случае представления графа матрицей смежности клиентам придется объединить такие ребра в одно ребро.

В представлениях сетей, описанных в и 21, применялось соглашение, что веса представляются вещественными числами от 0 до 1. В этой главе мы полагаем, что веса (пропускные способности и величины потоков) представляют собой да-разрядные целые числа (от 0 до 2m - 1 ). Это сделано по двум основным причинам. Во-первых, нам часто придется проверять на равенство различные линейные комбинации весов, а в случае чисел с плавающей точкой это не всегда удобно. Во-вторых, время выполнения алгоритмов может зависеть от относительных значений весов, а параметр M = 2m удобен для ограничения значений весов. Например, отношение наибольшего веса к наименьшему ненулевому весу меньше M. Использование целочисленных весов - лишь один из многочисленных возможных вариантов (см., например, упражнение 20.8) при решении подобных задач.

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

Программа 22.1 представляет собой клиентскую функцию, которая проверяет, удовлетворяют ли потоки условию баланса в каждом узле, и если удовлетворяют, то возвращает значение мощности потока. Вызов этой функции можно включить в алгоритм вычисления максимального потока в качестве заключительной операции. Несмотря на все доверие к лемме 22.1, программистская осторожность требует также проверить, равен ли поток, вытекающий из истока, потоку, втекающему в сток. Иногда имеет смысл проверить, что ни в одном ребре поток не превосходит пропускную способность этого ребра и что структуры данных внутренне непротиворечивы (см. упражнение 22.12).

Программа 22.1. Проверка и вычисление мощности потока

Вызов flow(G, v) вычисляет разность между входным и выходным потоками в вершине v сети G. Вызов flow(G, s, t) проверяет величины сетевых потоков из истока (s) в сток (t). Если входной поток в некотором внутреннем узле не равен выходному потоку или если величина какого-либо потока меньше нуля, то возвращается 0; иначе возвращается величина потока.

template <class Graph, class Edge>
class check {
  public:
 static int flow(Graph G, int v)
   { int x = 0; typename Graph::adjIterator A(G, v);
  for (Edge* e = A.beg(); !A.end(); e = A.nxt())
    x += e->from(v) ? e->flow() : -e->flow();
  return x;
   }
 static bool flow(Graph G, int s, int t)
   { for (int v = 0; v < G.V(); v++)
    if ((v != s)  (v != t))
   if (flow(G, v) != 0) return false;
  int sflow = flow(G, s);
  if (sflow < 0) return false;
  if (sflow + flow(G, t) != 0) return false;
  return true;
   }
  };
   

Эта транспортная сеть используется в нескольких упражнениях данной главы.

Данная транспортная сеть похожа на сеть, изображенной на рис 22.10, только направления двух ребер заменены на обратные, вследствие чего появлились два цикла. Эта транспортная сеть также рассматривается в нескольких упражнениях данной главы.

Упражнения

22.1. Найдите два различных максимальных потока в транспортной сети, изображенной на рис 22.10.

22.2. Пусть все пропускные способности выражаются положительными целыми числами, меньшими M. Каков максимально возможный поток для произвольной st-сети с V вершинами и E ребрами? Дайте два ответа, в зависимости от того, допускаются ли параллельные ребра.

22.3. Приведите алгоритм решения задачи о максимальном потоке для случая, когда сеть образует дерево, если удалить сток.

22.4. Приведите семейство сетей с E ребрами и циркуляцией, в которых процесс, описанный в доказательстве леммы 22.2, порождает E циклов.

22.5. Напишите класс EDGE, представляющий пропускные способности и потоки в виде вещественных чисел от 0 до 1 с d цифрами после десятичной точки, где d - фиксированная константа.

22.6. Напишите программу, которая строит транспортную сеть, считывая из стандартного ввода ребра (пары целых чисел в интервале от 0 до V- 1) с целочисленными пропускными способностями. Считайте, что верхняя граница пропускной способности M не превосходит 2²⁰.

22.7. Добавьте в решение упражнения 22.6, возможность присваивать вершинам символические имена, а не номера (см. программу 17.10).

22.8. Найдите в интернете крупную транспортную сеть, которую можно использовать для тестирования алгоритмов вычисления потоков. Это могут быть сети перевозки материалов (автомобильные, железнодорожные, авиа), сети связи (телефонные или компьютерные сети передачи данных) или распределительные сети. Если пропускные способности не известны, продумайте подходящую модель для их добавления. Напишите программу, использующую интерфейс программы 22.2 для реализации транспортных сетей с вашими данными - возможно, на основе решения упражнения 22.7. При необходимости разработайте дополнительные приватные функции для очистки данных (см. упражнения 17.33-17.35).

22.9. Напишите генератор случайных разреженных сетей с пропускными способностями от 0 до 2²⁰, взяв за основу программу 17.7. Воспользуйтесь отдельным классом для пропускных способностей и разработайте две реализации, одна из которых генерирует равномерно распределенные пропускные способности, а другая - нормально распределенные. Разработайте клиентские программы, которые генерируют случайные сети для обоих типов распределений весов с подобранными значениями V и E, чтобы использовать их для выполнения эмпирических тестов на графах, полученных из различных распределений весов ребер.

22.10. Напишите генератор случайных насыщенных сетей с пропускными способностями от 0 до 2²⁰, взяв за основу программу 17.8 и генераторы пропускных способностей ребер из упражнения 22.9. Напишите клиентские программы генерации случайных сетей для обоих распределений весов с подобранными значениями V и E, чтобы использовать их для выполнения эмпирических тестов на графах, полученных из этих моделей.

22.11. Напишите программу, которая генерирует на плоскости V случайных точек, затем строит транспортную сеть с (двунаправленными) ребрами, соединяющими все пары точек, расположенных на расстоянии не более d одна от другой (см. программу 3.20), и устанавливает пропускную способность каждого ребра с помощью одной из случайных моделей, описанных в упражнении 22.9. Определите, как выбрать d, чтобы ожидаемое количество ребер было равно E.

22.12. Добавьте в программу 22.1 проверку, что величина потока каждого ребра не больше его пропускной способности.

22.13. Найти все максимальные потоки в сети, показанной на рис 22.11. Приведите представление циклами для каждого из них.

22.14. Напишите функцию, которая считывает величины потоков и циклы (по одному в строке, в формате, представленном на рис 22.8) и строит сеть с соответствующим потоком.

22.15. Напишите клиентскую функцию, которая находит представление циклами для потока сети, используя метод, описанный в доказательстве леммы 22.2, и выводит величины потоков и циклы (по одному в строке, в формате, представленном на рис 22.8).

22.16. Напишите функцию, которая удаляет циклы из st-потока сети.

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

22.18. Пусть поток представляет собой товары, которые перевозят на грузовых машинах между городами, при этом под потоком в ребре u-v понимается количество товара, которое нужно доставить из города u в город v в течение дня. Напишите клиентскую функцию, которая выводит график работы для водителей грузовиков: где и сколько погрузить и где и сколько разгрузить. Считайте, что количество грузовиков неограничено, и распределительные пункты не начинают отгрузку, пока не получат весь товар.

Алгоритмы поиска максимального потока расширением пути

Эффективный способ решения задачи о максимальном потоке был разработан Л.Р. Фордом (L.R. Ford) и Д.Р Фалкерсоном (D.R. Fulkerson) в 1962 г. Это обобщенный метод с постепенным увеличением потоков вдоль путей от истока к стоку, на котором основано целое семейство алгоритмов. В классической литературе он известен под названием метода Форда-Фалкерсона; широкое распространение получил также более образный термин - метод расширения пути (augmenting path method).

Рассмотрим произвольный ориентированный путь (не обязательно простой) из истока в сток st-сети. Пусть x есть минимальное значение неиспользованной пропускной способности ребер на этом пути. Мы можем увеличить поток в сети по крайней мере на x, увеличив на данную величину поток во всех ребрах этого пути. Повторяя это действие, мы выполним первую попытку вычисления потока в сети: находим другой путь, увеличиваем поток вдоль этого пути и продолжаем, пока в каждом из путей, ведущих из истока в сток, не окажется хотя бы одно заполненное ребро (и мы не сможем увеличивать потоки этим способом). В одних случаях такой алгоритм вычисляет максимальный поток, но в других случаях это ему не удается. На рис 22.6. показан неудачный случай.

Для исправления алгоритма, чтобы он всегда находил максимальный поток, мы рассмотрим более общий способ увеличения потока вдоль произвольного пути из истока в сток в неориентированном графе, соответствующем данной сети. Ребра любого такого пути - это либо прямые (forward) ребра, направления которых совпадают с направлением потока (при следовании по пути из истока в сток мы проходим по ребру из его начальной вершины в конечную вершину), либо обратные (backward) ребра, которые направлены против потока (при следовании из истока в сток мы проходим по ребру из его конечной вершины в начальную вершину). Тогда, если существует какой-либо путь без заполненных прямых ребер и без пустых обратных ребер, можно увеличить поток в сети, увеличивая потоки в прямых ребрах и уменьшая потоки в обратных ребрах. Величина, на которую можно увеличить поток, ограничена минимумом из неиспользованных пропускных способностей и потоков в обратных ребрах. На рис 22.12 показан соответствующий пример. В новом потоке либо заполняется одно из прямых ребер пути, либо становится пустым одно из обратных ребер этого пути.

Эта последовательность демонстрирует расширение потока в сети вдоль пути из прямых и обратных ребер. Начав с потока, изображенного на левой диаграмме, и выполняя операции слева направо, мы увеличиваем поток в ребре 0-2, а затем в ребре 2-3 (дополнительные потоки показаны черным цветом). Далее мы уменьшаем поток в ребре 1-3 (показан белым цветом), отводя его в ребро 1-4, а затем в 4-5 - в результате получается поток, показанный на правой диаграмме.

Описанный процесс лежит в основе классического алгоритма Форда-Фалкерсона вычисления максимального потока (метод расширения пути). Вот его краткая формулировка:

Начинаем с нулевого потока в любом месте сети. Увеличиваем поток вдоль произвольного пути из истока в сток, содержащего незаполненные ребра или непустые обратные ребра, и продолжаем так, пока в сети не останется ни одного такого пути.

Интересно, что этот метод всегда находит максимальный поток независимо от способа выбора путей. Подобно методу вычисления MST-дерева из и методу Беллмана-Форда поиска кратчайших путей из , это обобщенный алгоритм, который полезен тем, что обосновывает правильность целого семейства более специальных алгоритмов. Для выбора путей годится любой метод.

На рис 22.13 приведено несколько различных последовательностей расширяющих путей, каждая из которых приводит к максимальному потоку в сети. Ниже в этом разделе мы рассмотрим несколько алгоритмов, которые вычисляют последовательности расширяющих путей, и все они находят максимальный поток. Эти алгоритмы различаются по количеству расширяющих путей, которые они вычисляют, по длине путей и трудоемкости их поиска, однако все они реализуют алгоритм Форда-Фалкерсона и находят максимальный поток.

На этих трех примерах мы расширяем поток вдоль различных последовательностей расширяющих путей, пока не сможем найти новые расширяющие пути. В каждом случае находится максимальный поток. Важная классическая теорема из теории сетевых потоков утверждает, что мы получаем максимальный поток в любой сети, независимо от того, какую последовательность путей мы используем (см. лемму 22.5).

Чтобы показать, что любой поток, вычисленный с помощью любой реализации алгоритма Форда-Фалкерсона, и в самом деле имеет максимальную величину, мы покажем, что этот факт эквивалентен другому ключевому факту, известному как теорема о максимальном потоке и минимальном сечении (maxflow-mincut theorem). Понимание этой теоремы - очень важный шаг к пониманию алгоритмов обработки транспортных сетей. Как следует из названия, теорема основана на непосредственной взаимосвязи между потоками и сечениями в сетях, поэтому мы начнем с определения терминов, которые имеют отношение к сечениям.

Напомним, что в соответствии с определением, данным в , сечение, или разрез (cut), графа есть разбиение множества вершин графа на два не-пересекающихся подмножества, а перекрестное ребро (crossing edge) - это ребро, соединяющее вершину одного подмножества с вершиной другого подмножества. Применительно к транспортным сетям мы уточним эти определения следующим образом (см. рис 22.14).

В st-сети имеется один исток s и один сток t. st-сечение - это разбиение вершин на множество, содержащее вершину s (белые кружки), и множество, содержащее вершину t (черные кружки). Ребра, связывающие вершины одного множества с вершинами другого множества (выделены серым цветом), называются секущим множеством. Прямое ребро ведет из вершины множества, содержащего s, в вершину множества, содержащего t, а обратное ребро имеет противоположное направление. В показанном здесь секущем множестве имеются четыре прямых ребра и два обратных ребра.

Каждое перекрестное ребро, соответствующее st-сечению, есть либо st-ребро, которое ведет из вершины, входящей во множество, где находится вершина s, в вершину, входящую во множество, где находится вершина t, либо ts-ребро, которое ведет в обратном направлении. Иногда множество перекрестных ребер называется секущим множеством (cut set). Пропускная способность st-сечения в транспортной сети есть сумма пропускных способностей ребер этого st-сечения, а поток через st-сечение есть разность между суммой потоков st-ребер и суммой потоков ts-ребер этого сечения. Удаление секущего множества делит связный граф на два связных компонента, удаляя все пути, соединяющие какую-либо вершину одного множества с вершиной другого множества. После удаления всех ребер, входящих в st-сечение, в сети не остается путей, соединяющих вершины s и t в соответствующем неориентированном графе, но возврат любого из них может воссоздать такой путь.

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

Минимальное сечение. Для заданной st-сети требуется найти такое st-сечение, что пропускная способность любого другого сечения не меньше найденного. Для краткости мы будем называть такое сечение минимальным сечением (mincut), а задачу вычисления такого сечения в сети - задачей о минимальном сечении (mincut problem).

Задача о минимальном сечении представляет собой обобщение задач о связности графов, которые были кратко рассмотрены в . Мы подробно рассмотрим конкретные взаимосвязи в разделе 22.4.

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

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

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

Другое следствие правильности алгоритма Форда-Фалкерсона заключается в том, что для любой транспортной сети с целочисленными пропускными способностями ребер существует максимальный поток, в котором потоки всех ребер также принимают целочисленные значения. Каждый расширяющий путь увеличивает сетевой поток на некоторое положительное целое число (минимум из незадействованных пропускных способностей в прямых ребрах и потоков в обратных ребрах, а это всегда целые положительные значения). Отсюда и наше решение рассматривать только целочисленные пропускные способности и потоки. Можно рассматривать максимальные потоки с нецелыми величинами, даже когда все пропускные способности заданы целыми числами (см. упражнение 22.23), однако в этом нет необходимости. Это важное ограничение: обобщения, где пропускные способности и потоки измеряются вещественными числами, могут привести к неприятным аномалиям.

В этом списке для сети, изображенной слева, представлены все st-сечения, вершины множества, содержащего вершину s, вершины множества, содержащего вершину t, прямые ребра, обратные ребра и пропускная способность (сумма пропускных способностей прямых ребер). Для любого потока поток через все сечения (потоки в прямых ребрах минус потоки в обратных ребрах) один и тот же. Например, в случае самой левой сети поток через сечение, разделяющее вершины 0 1 3 и 2 4 5, имеет величину 2 + 1 + 2 (потоки в ребрах 0-2, 1-4 и 3-5 соответственно) минус 1 (поток в ребре 2-3), то есть 4. Эти подсчеты дают значение 4 для любого другого сечения в сети, а поток максимален, поскольку его величина равна пропускной способности минимального сечения (см. лемму 22.5). В рассматриваемой сети имеются два минимальных сечения.

Например, алгоритм Форда-Фалкерсона может привести к появлению бесконечной последовательности расширяющих путей, которая даже не сходится к величине максимального потока (см. раздел ссылок).

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

Если ребро v-w пусто (f = 0), то в остаточной сети существует одно ребро, соответствующее v-w, с пропускной способностью с; если ребро v-w заполнено ( f = с), то в остаточной сети существует единственное ребро с пропускной способностью f, соответствующее ребру v-w; а если v-w ни заполнено, ни пусто, то в остаточную сеть входят оба ребра v-w и w-v с соответствующими пропускными способностями.

Программа 22.2 определяет класс EDGE, который мы используем для реализации абстракции остаточной сети. При такой реализации мы все так же работаем исключительно с указателями на клиентские ребра. Наши алгоритмы работают с остаточной сетью, но на самом деле они (через указатели на ребра) проверяют пропускные способности и изменяют потоки ребер в клиентских ребрах. Функции-члены from и other позволяют производить обработку ребер с любой ориентацией: функция e.other(v) возвращает конечную вершину е, отличную от v. Функции-члены capRto и addflowRto(v) реализуют остаточную сеть: если е - указатель на ребро v-w с пропускной способностью с и потоком f, то e->capRto(w) содержит значение c-f, а e->capRto(v) содержит f, e->addflowRto(w, d) увеличивает поток на величину d, а e->addflowRto(v, d) уменьшает его на величину d.

Программа 22.2. Ребра транспортной сети

Для реализации транспортной сети мы используем класс GRAPH неориентированного графа из , который позволяет оперировать указателями на ребра, реализованные в данном интерфейсе. Ребра ориентированы, но функции-члены реализуют абстракцию остаточной сети, которая охватывает оба направления каждого ребра (см. текст).

class EDGE
  { int pv, pw, pcap, pflow;
  public:
 EDGE(int v, int w, int cap) :
   pv(v), pw(w), pcap(cap), pflow(0) { }
 int v() const { return pv; }
 int w() const { return pw; }
 int cap() const { return pcap; }
 int flow() const { return pflow; }
 bool from (int v) const
   { return pv == v; }
 int other(int v) const
   { return from(v) ? pw : pv; }
 int capRto(int v) const
   { return from(v) ? pflow : pcap - pflow; }
 void addflowRto(int v, int d)
   { pflow += from(v) ? -d : d; }
  };
   

Остаточные сети позволяют использовать для поиска расширяющего пути любой обобщенный поиск на графе (см. ), поскольку любой путь из истока в сток в остаточной сети непосредственно соответствует расширяющему пути в исходной сети. Увеличение потока вдоль пути приводит к изменениям в остаточной сети: например, по меньшей мере одно ребро в остаточной сети меняет направление или исчезает (однако использование абстрактной остаточной сети означает, что мы проверяем наличие положительной пропускной способности, но нам не нужно фактически вставлять и удалять ребра). На рис 22.16 показан пример последовательности расширяющих путей и соответствующие остаточные сети.

Программа 22.3 представляет собой реализацию на основе очереди с приоритетами, которая охватывает все эти возможности, используя слегка измененную версию реализации поиска по приоритету на графах из программы 21.1, которая приведена в программе 22.4. Эта реализация позволяет выбирать одну из нескольких различных классических реализаций алгоритма Форда-Фалкерсона, просто указывая различные приоритеты, которые дают различные структуры данных для накопителя.

Программа 22.3. Реализация вычисления максимального потока расширением путей

Данный класс реализует общий алгоритм вычисления максимального потока расширением путей (алгоритм Форда-Фалкерсона). Он использует поиск по приоритету для нахождения пути из истока в сток в остаточной сети (см. программу 22.4), затем добавляет в этот путь максимально возможный поток и повторяет этот процесс, пока не останется ни одного такого пути. Построение объекта этого класса устанавливает в ребрах заданной сети такие величины потоков, при которых поток из истока в сток максимален. Вектор st содержит остовное дерево PFS: в st[v] содержится указатель на ребро, которое соединяет вершину v с ее родителем. Функция ST возвращает родителя для вершины, заданной в ее аргументе. Функция augment использует ST для обхода пути, чтобы вычислить его пропускную способность и затем увеличить поток.

template <class Graph, class Edge>
class MAXFLOW
  { const Graph G; int s, t;
 vector<int> wt;
 vector<Edge *> st;
 int ST(int v) const { return st[v]->other(v); }
 void augment(int s, int t)
   { int d = st[t]->capRto(t);
  for (int v = ST(t); v != s; v = ST(v))
    if (st[v]->capRto(v) < d)
   d = st[v]->capRto(v);
  st[t]->addflowRto(t, d);
  for (int v = ST(t); v != s; v = ST(v))
    st[v]->addflowRto(v, d);
   }
 bool pfs();
  public:
 MAXFLOW(const Graph G, int s, int t) : G(G),
   s(s), t(t), st(G.V()), wt(G.V())
   { while (pfs()) augment(s, t); }
  };
   

Вычисление расширяющих путей в транспортной сети эквивалентно поиску ориентированных путей в остаточной сети, определяемой потоком. Для каждого ребра исходной сети мы создаем в остаточной сети по ребру в каждом направлении: одно в направлении потока с весом, равным незадействованной пропускной способности, а другое - в обратном направлении с весом, равным потоку. Ребра с нулевыми весами не включаются. Первоначально (вверху) остаточная сеть совпадает с транспортной сетью, но веса ребер равны их пропускным способностям.

При расширении потока вдоль пути 0-1-3-5 (второйряд) мы заполняем ребра 0-1 и 3-5 до их пропускной способности, чтобы они поменяли направление в остаточной сети, уменьшаем вес ребра 1-3, чтобы он соответствовал оставшемуся потоку, и добавляем ребро 3-1 с весом 2. Аналогично, при расширении вдоль пути 0-2-4-5 мы заполняем ребро 2-4 до его пропускной способности, чтобы оно сменило направление на обратное, и получаем разнонаправленные ребра между вершинами 0 и 2 и между вершинами 4 и 5, представляющие поток и неиспользованную пропускной способность. После расширения потока вдоль пути 0-2-3-1-4-5 (внизу) в остаточной сети не остается ни одного ориентированного пути из истока в сток, поэтому нет расширяющих путей.

Как было показано в , использование очереди с приоритетами для реализации стека, очереди или рандомизированной очереди в качестве накопителя увеличивает трудоемкость операций с накопителем на множитель lgV Этого можно избежать, используя в реализациях АТД обобщенной очереди наподобие программы 18.10 прямые реализации - поэтому при анализе алгоритмов мы полагаем, что трудоемкость операций с накопителем в рассматриваемых случаях постоянна. Используя единственную реализацию в программе 22.3, мы демонстрируем наличие непосредственных связей между различными реализациями алгоритма Форда-Фалкерсона.

Несмотря на обобщенный характер, программа 22.3 не охватывает всех реализаций алгоритма Форда-Фалкерсона (см. например, упражнения 22.36 и 22.38). Исследователи продолжают разрабатывать новые способы реализации этого алгоритма. Однако семейство алгоритмов, охватываемых программой 22.3, получило широкое распространение, помогает понять процесс вычисления максимальных потоков и знакомит с несложными реализациями, которые хорошо работают на обычно встречающихся сетях.

Программа 22.4. Реализация поиска по приоритетам для нахождения расширяющих путей

Данная реализация поиска по приоритетам получена из реализации, которую мы использовали для алгоритма Дейкстры (программа 21.1), но теперь в ней веса принимают целочисленные значения, обрабатываются ребра остаточной сети, и выполнение прекращается при достижении стока или возврата false, если не существует пути из истока в сток. Заданное здесь определение приоритета P позволяет получить расширяющий путь до максимальной пропускной способности (отрицательные величины сохраняются в очереди с приоритетами в соответствии с интерфейсом программы 20.10). Другие определения P приводят к различным алгоритмам вычисления максимального потока.

  template <class Graph, class Edge>
  bool MAXFLOW<Graph, Edge>::pfs()
 { PQi<int> pQ(G.V(), wt);
   for (int v = 0; v < G.V(); v++)
  { wt[v] = 0; st[v] = 0; pQ.insert(v); }
   wt[s] = -M; pQ.lower(s);
   while (!pQ.empty())
  { int v = pQ.getmin(); wt[v] = -M;
    if (v == t || (v != s  st[v] == 0)) break;
    typename Graph::adjIterator A(G, v);
    for (Edge* e = A.beg(); !A.end(); e = A.nxt())
   { int w = e->other(v);
     int cap = e->capRto(w);
     int P = cap < -wt[v] ? cap : -wt[v];
     if (cap > 0  -P < wt[w])
    { wt[w] = -P; pQ.lower(w); st[w] = e; }
   }
  }
  return st[t] != 0;
 }
   

Как мы вскоре убедимся, эти базовые алгоритмические средства дают простые (и, как правило, полезные) решения задачи о транспортных потоках. Однако исчерпывающий анализ для выбора наилучшего метода сам является сложной задачей, поскольку время выполнения этих методов зависит от:

Эти величины могут изменяться в широких пределах, в зависимости от вида обрабатываемой сети и стратегии поиска на графе (структура данных накопителя).

Видимо, простейшая реализация алгоритма Форда-Фалкерсона использует кратчайший расширяющий путь (кратчайший по количеству ребер в этом пути, а не по потоку или по пропускной способности). Этот метод был предложен Эдмондсом (Edmonds) и Карпом (Karp) в 1972 г. В его реализации в качестве накопителя используется очередь - либо с помощью кольцевого счетчика для P, либо на основе АТД очереди вместо АТД очереди с приоритетами из программы 22.3. В этом случае поиск расширяющего пути превращается в поиск в ширину (BFS) в остаточной сети, в точности как описано в разделах 18.8 и рис 22.2. На рис 22.17 показан пример работы этой реализации метода Форда-Фалкерсона. Мы будем называть этот метод алгоритмом вычисления максимального потока с помощью кратчайших расширяющих путей (shortest-augumenting-path). Как показано на этом рисунке, длины расширяющих путей образуют неубывающую последовательность. Анализ этого метода в лемме 22.7 показывает, что это свойство верно всегда.

Здесь показан процесс поиска максимального потока с помощью реализации метода Форда-Фалкерсона на основе кратчайших расширяющих путей. По мере работы алгоритма длины путей увеличиваются: первые четыре пути в верхнем ряду имеют длину 3, последний путь в верхнем ряду и все пути во втором ряду имеют длину 4; первые два пути в нижнем ряду имеют длину 5, и в конце находятся два пути длиной 7, каждый из которых содержит обратное ребро.

В другой реализация алгоритма Форда-Фалкерсона, предложенной Эдмондсоном и Карпом, выполняется расширение пути, который увеличивает поток на наибольшую величину. Реализацию этого метода обеспечивает значение приоритета P, использованное в программе 22.3. При этом алгоритм выбирает из накопителя такие ребра, чтобы мощность потока, который будет добавлен в прямое ребро или удален из обратного ребра, была максимальной. Этот метод мы будем называть алгоритмом вычисления максимального потока с помощью расширяющий путей с максимальной пропускной способностью (maximum-capacity-augmenting-path). На рис 22.18 показана работа этого алгоритма на той же транспортной сети, что и на рис 22.17.

Это всего лишь два примера (которые мы можем проанализировать!) реализаций алгоритма Форда-Фалкерсона. В конце этого раздела мы познакомимся и с другими реализации. Но сначала мы рассмотрим задачу анализа методов на основе расширения путей с тем, чтобы исследовать их свойства и затем определить метод, который обеспечивает наивысшую производительность.

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

Ситуацию осложняют и многие другие факторы. Например, время выполнения в худшем случае для некоторых версий зависит не только от V и E, но и от значений пропускных способностей ребер в сети. Разработка алгоритма вычисления максимального потока с высокой гарантированной производительностью почти полвека привлекала к себе внимание многих исследователей, которые предложили множество методов. Оценка всех этих методов для различных видов реально встречающихся сетей с достаточной степенью точности позволяет сделать правильный выбор, однако она более расплывчата, чем оценки в других ситуациях, которые мы изучали ранее - например, для алгоритмов сортировки или поиска.

Здесь показан процесс поиска максимального потока с помощью реализации метода Форда-Фалкерсона на основе расширяющих путей с максимальной пропускной способностью. По мере работы алгоритма пропускные способности путей уменьшаются, но их длина может как увеличиваться, так и уменьшаться. Этому методу потребовалось лишь девять расширяющих путей, чтобы вычислить тот же максимальный поток, что и на рис 22.17.

Учитывая эти трудности, рассмотрим теперь классические результаты, касающиеся производительности метода Форда-Фалкерсона в худшем случае: одну общую границу и две границы для частных случаев - для каждого из рассмотренных нами алгоритмов расширения пути. Эти результаты позволят нам скорее понять характеристики алгоритмов, чем точно прогнозировать производительность этих алгоритмов для осмысленного сравнения. Эмпирическое сравнение этих методов будет приведено в конце этого раздела.

Как уже было сказано, в обычных ситуациях от такой границы мало проку, т.к. M может быть очень большим числом. Что еще хуже, легко описать ситуации, в которых количество итераций пропорционально максимальной пропускной способности ребра. Например, предположим, что мы используем алгоритм использования самого длинного расширяющего пути (возможно, основанного на соображении, что чем длиннее путь, тем больший поток можно добавить в ребра сети). Поскольку мы ведем подсчет итераций, мы на время игнорируем затраты на вычисление такого пути. Классический пример, представленный на рис 22.19, показывает сеть, для которой количество итераций алгоритма с использованием самого длинного расширяющего пути равно максимальной пропускной способности ребер. Этот пример показывает, что необходимы более подробные исследования, чтобы выяснить, требуют ли другие конкретные реализации существенное меньше итераций по сравнению с оценкой из леммы 22.6.

Данная сеть демонстрирует, что количество итераций, выполняемых алгоритмом Форда-Фалкер-сона, зависит от пропускных способностей ребер и от последовательности путей, выбираемых реализацией. Сеть состоит из четырех ребер с пропускной способностью X и одного ребра с пропускной способностью 1. В верхней части рисунка показано, что реализация, которая попеременно использует цепочки 0-1-2-3 и 0-2-1-3 в качестве расширяющих путей (например, та, где выбираются длинные пути), потребует X пар итераций - наподобие двух пар, показанных на рисунке, и каждая такая пара увеличивает общих поток на 2. В нижней части рисунка показано, что реализация, которая выбирает в качестве расширяющих путей цепочку 0-1-3, а затем 0-2-3 (например, та, где выбираются короткие пути), вычисляет максимальный поток всего за две итерации. Если пропускные способности ребер выражены, скажем, 32-разрядными целыми числами, то быстродействие верхней реализации будет в миллиарды раз меньше быстродействия нижней реализации.

Для разреженных сетей и сетей с небольшими целочисленными значениями пропускных способностей лемма 22.6 на самом деле дает полезную верхнюю границу времени выполнения любой реализации алгоритма Форда-Фалкерсона.

Это доказательство фактически утверждает, что множитель M можно заменить отношением наибольшей и наименьшей пропускной способности в сети (см. упражнение 22.35). Если это отношение мало, любая реализация алгоритма Форда-Фалкерсона находит максимальный поток за время, пропорциональное худшему времени решения (к примеру) задачи поиска всех кратчайших путей. Существует множество ситуаций, когда пропускные способности весьма небольшие, и множитель M можно не учитывать. Соответствующий пример будет приведен в разделе 22.4.

Если M велико, граница VEM для худшего случая также велика; но она слишком завышена, поскольку получена перемножением границ для худших случаев, которые получены из придуманных примеров. Фактические затраты для сетей, встречающихся на практике, обычно намного ниже.

С теоретической точки зрения наша первая цель - определить с помощью грубой субъективной классификации из , разрешима ли задача о максимальном потоке в сетях с большими целочисленными весами (т.е. существует ли алгоритм с полиномиальным временем выполнения). Только что найденные границы не дают ответа на этот вопрос, т.к. максимальный вес M = 2m может возрастать экспоненциально с увеличением V и E. Для практических целей нужны более точные гарантии производительности. Возьмем типичный практический пример: пусть для представления весов используются 32-разрядные целые числа (m = 32). В графе с сотнями вершин и тысячами ребер следствие из леммы 22.6 утверждает, что алгоритму на базе расширения пути может понадобиться выполнить сотни триллионов операций. Если сеть содержит миллионы вершин, то ничего сказать вообще невозможно, поскольку не только невозможно выразить веса с величинами порядка 2^1000000, но и значения V³ и VE настолько велики, что любые границы при этом теряют всякий смысл. А нам нужна полиномиальная граница для ответа на вопрос о разрешимости и более точные границы для ситуаций, с которыми мы можем столкнуться на практике.

Лемма 22.6. носит общий характер и поэтому применима к любой реализации алгоритма Форда-Фалкерсона. Универсальная природа этого алгоритма позволяет рассматривать целый ряд простых реализаций, позволяющих улучшить рабочие характеристики алгоритма. Мы надеемся, что конкретные реализации могут иметь более низкие границы для худших случаев. Вообще-то это одна из главных причин, чтобы сразу же приступить к их рассмотрению! Теперь, как мы могли убедиться, реализовать и использовать большой класс таких реализаций совсем не сложно: для этого нужно просто подставлять в программу 22.3 различные реализации обобщенной очереди или определения приоритетов. Анализ различий поведения в худшем случае представляет собой еще более трудную задачу, что подтверждается классическими результатами для двух простых реализаций алгоритма расширения путей, которые мы сейчас рассмотрим.

Сначала мы проанализируем алгоритм с использованием кратчайшего расширяющего пути. Этот метод не относится к задаче, представленной на рис 22.19. Его можно использовать для замены множителя M для времени выполнения в худшем случае на выражение VE/2, тем самым заявив, что задача вычисления сетевых потоков является разрешимой. Вообще-то ее можно считать даже легкой (решаемой в реальных ситуациях за полиномиальное время с помощью небольшой, но хитроумной реализации).

Величина V³ достаточно велика и поэтому не может гарантировать высокую производительность на крупных сетях. Но это не должно удерживать нас от применения алгоритма на крупных сетях, т.к. полученная оценка производительности в худшем случае вряд ли будет полезной для прогнозирования производительности алгоритма в практических ситуациях. Например, как было сказано выше, максимальная пропускная способность M (или максимальное отношение пропускных способностей) может быть намного меньше V, и тогда лемма 22.6 определяет более точную границу. Вообще-то в лучшем случае количество расширяющих путей, необходимых для метода Форда-Фалкерсона, меньше степени выхода вершины s или степени захода вершины t, которые, в свою очередь, могут быть намного меньше V. При таком разбросе производительности в лучшем и худшем случаях не стоит сравнивать алгоритмы нахождения расширяющих путей только на основе границ для худшего случая.

Однако существуют другие реализации, которые почти столь же просты, как и метод использования кратчайших расширяющих путей, но имеют более точные границы или хорошо зарекомендовали себя на практике (или и то, и другое). Допустим, в примере, представленном на рис 22.17 и рис 22.18, алгоритм с использованием максимального расширяющего пути использует намного меньше путей для отыскания максимального потока, чем метод с использованием кратчайшего расширяющего пути. Теперь мы проведем анализ худшего случая для рассматриваемого алгоритма.

Во-первых, как и в случае алгоритма Прима и алгоритма Дейкстры (см. и рис 21.2), мы можем реализовать очередь с приоритетами таким образом, что для выполнения одной итерации алгоритма в худшем случае понадобится время, пропорциональное V² (для насыщенных графов) или (E+ V) logV (для разреженных графов). Однако эти оценки слишком пессимистичны, т.к. алгоритм сразу же останавливается при достижении стока. Мы также знаем, что можно немного повысить производительность, воспользовавшись специальными структурами данных. Однако более важной, хотя и более трудной, задачей является определение необходимого количества расширяющих путей.

Для значений M и V, которые обычно встречаются на практике, эта граница значительно ниже границы O(V3) , определяемой леммой 22.7. Во многих практических ситуациях алгоритм поиска максимального расширяющего пути использует значительно меньше итераций, чем алгоритм поиска кратчайшего расширяющего пути, за счет некоторого увеличения затрат на поиск каждого пути.

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

В одном простом алгоритме с помощью расширения путей используется значение уменьшающегося счетчика или стековая реализация для обобщенной очереди из программы 22.3 - при этом поиск расширяющих путей выполняется аналогично поиску в глубину. На рис 22.20 показан поток, вычисленный этим алгоритмом для нашего небольшого примера. Интуитивно понятно, что этот метод быстро работает, легок в реализации и действительно находит максимальный поток. Как мы увидим, его производительность может быть всякой, от очень низкой для одних видов сетей до вполне приемлемой для других.

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

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

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

Чтобы получить начальное представление о возможных количественных различиях, мы воспользуемся двумя моделями транспортных сетей, построенных на основе модели евклидовых графов, которые мы уже применяли для сравнения других алгоритмов на графах. В обеих моделях используется граф из V точек на плоскости со случайными координатами от 0 до 1 и ребер, соединяющих точки, расположенные в пределах фиксированного расстояния друг от друга. Эти модели различаются пропускными способностями, назначаемыми ребрам.

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

Вторая модель назначает случайные пропускные способности из некоторого фиксированного диапазона значений. Эта модель генерирует типы сетей, которые люди обычно представляют себе при обдумывании задачи, а производительность различных алгоритмов на таких сетях дает богатую пищу для размышлений.

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

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

В таблица 22.1. Производительность алгоритма с использованием расширяющих путей зависит не только от количества расширяющих путей, но и от длины таких путей и затрат на их поиск. В частности, время выполнения пропорционально количеству ребер, просмотренных во внутреннем цикле программы 22.3. Как обычно, это количество может меняться в широких пределах - даже для одного и того же графа - и зависит от свойств его представления, но для каждого вида алгоритма все-таки имеются общие характеристики. Например, на рис 22.23 и 22.24 показаны деревья поиска, соответственно, для алгоритма с использованием путей максимальной пропускной способности и алгоритма с использованием кратчайшего пути. Эти примеры подтверждают общий вывод, что метод поиска кратчайшего пути более трудоемок при отыскании расширяющих путей с меньшим потоком, чем алгоритм с использованием максимальной пропускной способности, и помогают понять, почему предпочтение отдается последнему.

В этой таблице представлены параметры производительности различных алгоритмов вычисления сетевых потоков с помощью расширения путей на примере евклидовой сети с соседними связями (со случайными значениями пропускной способности и с величиной максимального потока, равной 286) и с единичными пропускными способностями (при величине максимального потока, равной 1). Алгоритм использования путей с максимальной пропускной способностью превосходит другие алгоритмы на обоих типах сетей. Алгоритм со случайным поиском находит расширяющие пути, которые ненамного длиннее кратчайшего пути, и проверяет меньшее количество узлов. Алгоритм на основе стека очень хорошо работает для случайных весов. Хотя он находит очень длинные пути, он вполне пригоден для работы на сетях с единичными весами.

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

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

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

Пожалуй, основной урок, который можно вынести из подробного исследования конкретных сетей, состоит в огромной разнице между оценками верхней границы, которые даны в леммах 22.6-22.8, и фактическим количеством расширяющих путей, которые требуются алгоритмам в реальных приложениях. Например, в транспортной сети, представленной на рис 22.23, имеется 177 вершин и 2000 ребер с пропускной способностью не более 100 единиц. Поэтому значение 2E lgM в лемме 22.8 больше 25000, но алгоритм с использованием путей с максимальной пропускной способностью находит максимальный поток, перебрав лишь семь расширяющих путей. Аналогично, значение VE/2 для этой сети, определяемое в лемме 22.7, равно 177000, однако алгоритму с использованием кратчайших путей достаточно перебрать лишь 37 путей.

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

Подобные значительные расхождения побуждают исследователей искать более низкие границы для худших случаев. Существует множество других еще не исследованных возможных реализаций алгоритмов, использующих расширение путей, которые могут привести к более заметному повышению производительности в худшем случае или на реальных сетях, чем рассмотренные нами методы (см. упражнения 22.56-22.60). В специальной литературе приведены многочисленные более сложные методы, с улучшенной производительностью в худшем случае (см. раздел ссылок).

На этом рисунке показаны расширяющие пути, вычисленные алгоритмом с использованием кратчайших путей для евклидовой сети со случайными весами, которая изображена на рис 22.22. Здесь же показаны (серым цветом) ребра остовного дерева поиска на графе. В этом случае алгоритм работает гораздо медленнее, чем алгоритм с использованием путей максимальной пропускной способности (см. рис 22.23), т.к. он требует больше расширяющих путей (здесь показаны лишь первые 12 путей из всех 37, а остовные деревья имеют больший размер (обычно содержат почти все вершины).

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

Даже если ограничиться только алгоритмами с использованием расширения путей, мы увидим, что изучение алгоритмов вычисления максимального потока - это и наука, и искусство. Искусство проявляется в выборе стратегии, наиболее эффективной в данной практической ситуации, а наука - в понимании природы задачи. Существуют ли новые структуры данных и алгоритмы, которые могут решить задачу вычисления максимального потока за линейное время, либо можно доказать, что такое решение не существует? В разделе 22.3 будет показано, что никакой алгоритм с использованием расширения путей не может иметь линейную производительность в худшем случае; там же мы рассмотрим другое обобщенное семейство алгоритмов, которые могут это сделать.

Упражнения

22.19. Покажите в стиле рис 22.13 столько различных последовательностей расширяющих путей, сколько вы их сможете найти в транспортной сети, показанной на рис 22.10

22.20. Покажите в стиле рис 22.15 все сечения транспортной сети, показанной на рис 22.10, их секущие множества и пропускные способности.

22.21. Найдите минимальное сечение в транспортной сети, показанной на рис 22.11.

22.22. Допустим, в некоторой транспортной сети достигнут баланс пропускных способностей (для каждого внутреннего узла общая пропускная способность входящих ребер равна общей пропускной способности исходящих ребер). Использует ли алгоритм Форда-Фалкерсона обратные ребра? Докажите, что использует, либо приведите контрпример.

22.23. Определите максимальный поток для транспортной сети с рис 22.5, в которой величина по крайней одного потока не является целым числом.

22.24. Разработайте реализацию алгоритма Форда-Фалкерсона, в которой вместо очереди с приоритетами используется обобщенная очередь (см. ).

22.25. Докажите, что количество расширяющих путей, необходимых для любой реализации алгоритма Форда-Фалкерсона, не более чем в V раз больше наименьшего целого числа, которое больше отношения наибольшей пропускной способности ребра к наименьшей пропускной способности.

22.26. Докажите справедливость нижней границы линейного времени для задачи поиска максимального потока: покажите, что в сети с любыми значениями V и E любой алгоритм вычисления максимального потока должен просмотреть каждое ребро.

22.27. Приведите пример сети наподобие рис 22.19, для которой алгоритм с использованием кратчайших расширяющих путей обладает наихудшим поведением, как на рис 22.19.

22.28. Приведите представление списками смежности для сети, изображенной на рис 22.19, для которой наша реализация поиска с помощью стека (программа 22.3, в которой в качестве обобщенной очереди используется стек) обладает наихудшим поведением.

22.29. Покажите в стиле рис 22.16 транспортную и остаточную сети после каждого расширения пути, когда алгоритм с использованием кратчайших расширяющих путей отыскивает максимальный поток в транспортной сети с рис 22.10. Включите также деревья поиска на графе для каждого расширяющего пути. Если можно выбрать более одного пути, покажите тот, который выбирается реализациями, рассмотренными в этом разделе.

22.30. Выполните упражнение 22.29 для алгоритма с использованием расширяющего пути с максимальной пропускной способностью.

22.31. Выполните упражнение 22.29 для алгоритма с выборкой расширяющего пути из стека.

22.32. Приведите семейство сетей, для которых алгоритм с использованием максимального расширяющего пути перебирает 2E lgM расширяющих путей.

22.33. Можно ли так упорядочить ребра, чтобы рассмотренные нами реализации тратили на поиск пути в упражнении 22.32 время, пропорциональное E? При необходимости измените пример, чтобы достичь этой цели. Опишите представление графа списками смежности, построенное для рассматриваемого примера. Объясните, как можно получить наихудший случай.

22.34. Эмпирически определите количество расширяющих путей и отношения времени выполнения к V для каждого из четырех алгоритмов, описанных в этом разделе, для различных видов сетей (см. упражнения 22.7-22.12).

22.35. Разработайте и протестируйте реализацию метода расширения путей, который использует эвристику кратчайшего пути из истока в сток для евклидовых сетей из .

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

22.37. Реализация программы 22.3 останавливает поиск на графе, как только находит первый расширяющий путь из истока в сток, расширяет поток, а затем начинает поиск с самого начала. Другой способ - продолжить поиск и найти другой путь, пока не будут помечены все вершины. Разработайте и протестируйте второй подход.

22.38. Разработайте и протестируйте метод расширения путей, который использует не простые пути.

22.39. Приведите последовательность простых расширяющих путей, которые создают поток с циклом в сети, показанной на рис 22.11.

22.40. Приведите пример, показывающий, что не все максимальные потоки можно получить расширением потоков вдоль некоторой последовательности простых путей из истока в сток, начиная с пустой сети.

22.41.[ Габов] Разработайте реализацию вычисления максимального потока, которая использует m = lgM этапов, где i-й этап решает задачу о максимальном потоке, используя i первых разрядов в значениях пропускных способностей. Начните с нулевого потока во всей сети; после первого этапа увеличьте вдвое поток, вычисленный на предыдущем этапе. Эмпирически сравните этот метод с базовыми методами на различных сетях (см. упражнения 22.7-22.12).

22.42. Докажите, что время выполнения алгоритма, описанного в упражнении 22.41, равно O(VE lgM).

22.43. Поработайте с гибридными методами, которые вначале используют один метод расширения путей, а затем переключаются на другой метод расширения путей до завершения работы (часть задачи - выбор подходящего критерия для определения момента переключения). Эмпирически сравните этот метод с базовыми методами на различных сетях (см. упражнения 22.7-22.12), обращая больше внимания на те, которые показывают лучшие результаты.

22.44. Поработайте с гибридными методами, которые попеременно используют два или более различных методов расширения путей. Эмпирически сравните этот метод с базовыми методами на различных сетях (см. упражнения 22.7-22.12), обращая больше внимания на те, которые показывают лучшие результаты.

22.45. Поработайте с гибридными методами, которые случайным образом переключаются между двумя или более различными методами расширения путей. Эмпирически сравните этот метод с базовыми методами на различных сетях (см. упражнения 22.7-22.12), обращая больше внимания на те, которые показывают лучшие результаты.

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

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

22.48. Напишите клиентскую программу для графической анимации динамики алгоритмов поиска расширяющих путей. Эта программа должна создавать изображения, подобные рис 22.17 и другим рисункам из этого раздела (см. упражнения 17.55-17.59). Протестируйте полученную реализацию на евклидовых сетях из упражнений 22.7-22.12.

Алгоритмы определения максимальных потоков проталкиванием напора

В этом разделе мы рассмотрим другой способ решения задачи о максимальном потоке. Используя обобщенный метод, который называется методом проталкивания напора (preflow-push), мы будем постепенно проталкивать поток по ребрам, исходящим из вершин, в которых приток превышает отток. Метод проталкивания напора был разработан Гольдбергом (A. Goldberg) и Тарьяном (R.E.Tarjan) в 1986 г. на основе различных уже известных алгоритмов и получил широкое распространение благодаря своей простоте, гибкости и эффективности.

Как сказано в разделе 22.1, поток должен удовлетворять условию баланса: отток из истока должен быть равен притоку в сток, а в каждом внутреннем узле приток равен оттоку. Мы называем такой поток допустимым (feasible) потоком. Алгоритм расширения путей всегда поддерживает допустимость потока, наращивая поток вдоль расширяющих путей, пока не будет достигнут максимальный поток. В отличие от этого, алгоритмы проталкивания напора, которые будут рассмотрены в этом разделе, работают с не допустимыми потоками, и в некоторых вершинах приток может превышать отток: они проталкивают поток через эти вершины, пока поток не станет допустимым (когда не останется таких вершин).

Разность между притоком и оттоком активной вершины называется ее избытком (excess). Чтобы изменить множество активных вершин, мы выбираем одну из них и проталкиваем (push) ее избыток в исходящее ребро, а если пропускной способности этого ребра не хватает, то избыток выталкивается назад по входящему ребру. Если проталкивание балансирует приток и отток, вершина перестает быть активной; поток, протолкнутый в другую вершину, может активировать ее. Метод проталкивания напора представляет собой систематический способ многократного выталкивания избытка из активных вершин; по окончании процесса получается максимальный поток, и нет активных вершин. Активные вершины содержатся в обобщенной очереди. Это решение позволяет получить обобщенный алгоритм, который охватывает целое семейство специальных алгоритмов.

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

В алгоритме проталкивания напора используется список активных узлов, в которых входящие потоки больше исходящих (показаны под каждой диаграммой сети). Одна из версий алгоритма представляет собой цикл, который выбирает из этого списка активный узел и проталкивает поток по исходящим ребрам, пока узел не перестанет быть активным. При этом возможно появление других активных узлов. В данном примере мы проталкиваем поток по ребру 0-1, после чего узел 1 становится активным. После этого мы проталкиваем поток по ребрам 1-2 и 1-3, и узел 1 перестает быть активным, зато активируются узлы 2 и 3. Затем мы проталкиваем поток по ребру 2-4, и 2 становится неактивным узлом. Однако пропускной способности ребра 3-4 недостаточно, чтобы протолкнуть поток по нему и сделать узел 3 неактивным, поэтому поток проталкивается по ребру 3-1 обратно в вершину 1, которая снова активируется. Теперь можно протолкнуть поток по ребру 1-2, а затем по 2-4, после чего все узлы становятся неактивными, и мы получаем максимальный поток.

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

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

Эта сеть представляет семейство сетей с V вершинами, для которых любой алгоритм расширения путей требует V/2 путей длиной V/2 (поскольку каждый расширяющий путь должен содержать длинный вертикальный путь), а для этого потребуется время, пропорциональное V². Алгоритмы проталкивания напора находят максимальный поток в таких сетях за линейное время.

Тривиальная функция высоты, для которой не существует подходящих ребер, имеет вид h(0) = h(1) = ... = h(V - 1) = 0. Если задать h(s) = 1, то любое ребро, исходящее из истока и содержащее поток, соответствует подходящему ребру в остаточной сети.

Можно дать более интересное определение функции высоты, присвоив каждой вершине длину кратчайшего пути от нее до стока (расстояние до корня в любом дереве BFS для обратной сети с корнем в t - см. рис 22.27). Эта функция высоты верна потому, что h(t) = 0, и для любой пары вершин u и v, соединенных ребром u-v, любой кратчайший путь, ведущий в t и начинающийся ребром u-v, имеет длину h(v) + 1; таким образом, длина кратчайшего пути из u в t, т.е. h(u), должна быть меньше или равна этому значению. Эта функция играет особую роль, т.к. она помещает каждую вершину на максимально возможную высоту. Обратные рассуждения показывают, что вершина t должна находиться на высоте 0; единственными вершинами, которые могут находиться на высоте 1, являются вершины, которым соответствуют ребра, направленные в t в остаточной сети; на высоте 2 могут находиться только вершины, ребра из которых направлены в вершины, которые могут быть на высоте 1 и т.д.

Справа изображено дерево BFS с корнем в вершине 5 обращения сети, приведенной слева. Массив h, индексированный именами вершин, содержит расстояние от каждой вершины сети до корня и представляет собой адекватную функцию высоты: для каждого ребра u-v сети значение h[u] меньше или равно h[v]+1.

Смысл функции высоты в следующем: если высота активного узла меньше, чем высота истока, то, возможно, можно как-то протолкнуть поток из этого узла в сток; если высота активного узла больше, чем высота истока, нужно избыток этого узла вытолкнуть обратно в исток. Чтобы обосновать последний факт, мы изменим направление леммы 22.9, где длина кратчайшего пути выступает в качестве верхней границы высоты; вместо этого будем рассматривать высоту как нижнюю границу длины кратчайшего пути.

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

Выбираем активную вершину. Проталкиваем поток через некоторое подходящее ребро, исходящее из этой вершины (если оно есть). Если таких ребер нет, увеличиваем на 1 высоту вершины.

Мы не конкретизируем, как выглядит исходная функция высоты, как выбирается активная вершина, как выбирается подходящее ребро или какая величина потока выталкивается. Мы будем называть этот обобщенный метод как реберный (edge-based) алгоритм проталкивания напора.

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

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

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

Можно уточнить доказательство обязательного завершения алгоритма и получить границу времени выполнения в худшем случае O(V2E ). Детали этого доказательства мы оставляем читателям на самостоятельную проработку (см. упражнения 22.66 и 22.67), а здесь отдадим предпочтение более простому доказательству леммы 22.13, которое относится к более специальной версии алгоритма. А именно, рассматриваемые нами реализации будут основаны на более конкретных повторяющихся инструкциях:

Выбираем активную вершину. Увеличиваем поток в подходящем ребре, исходящем из этой вершины (по возможности заполняем его), и продолжаем так, пока вершина не перестанет быть активной или не останется подходящих ребер. В последнем случае увеличиваем высоту вершины.

То есть после выбора вершины мы выталкиваем из нее как можно больший поток. Если в вершине все равно останется избыток потока, но не останется подходящих ребер, мы увеличиваем на 1 высоту этой вершины. Мы будем называть этот метод вершинным (vertex-based) алгоритмом проталкивания напора. Это специальный случай реберного обобщенного алгоритма, где одна и та же вершина выбирается до тех пор, пока она не перестанет быть активной, либо пока не будут использованы все подходящие ребра, исходящие из нее. Доказательство леммы 22.12 верно для любой реализации реберного обобщенного алгоритма, а это значит, что вершинный алгоритм вычисляет максимальный поток.

Программа 22.5 представляет собой реализацию обобщенного вершинного алгоритма, который использует обобщенную очередь для хранения активных вершин. Эта непосредственная реализация только что описанного метода представляет собой семейство алгоритмов, которые отличаются только исходными функциями высоты (см. например, упражнение 22.52) и реализацией АТД обобщенной очереди. В ней предполагается, что обобщенная очередь отбрасывает повторяющиеся вершины; в противном случае в программу 22.5 можно добавить код, запрещающий занесение дубликатов в очередь (см. упражнения 22.61 и 22.62).

Программа 22.5. Реализация вычисления максимального потока методом проталкивания напора

В данной реализации обобщенного вершинного алгоритма проталкивания напора для вычисления максимального потока используется обобщенная очередь, которая не принимает дубликаты активных вершин. Вектор wt содержит избыточный поток каждой вершины и таким образом неявно определяет множество активных вершин. Здесь вершина s первоначально активна, но никогда не возвращается в очередь, а t никогда не бывает активной. Основной цикл выбирает активную вершину v, затем проталкивает поток через каждое из его подходящих ребер (и при необходимости заносит вершины, принимающие потоки, в список активных вершин) до тех пор, пока либо v станет неактивной, либо будут перебраны все подходящие ребра. В последнем случае высота v увеличивается, а сама она возвращается в очередь.

  template <class Graph, class Edge>
  class MAXFLOW
 { const Graph G;
   int s, t;
   vector<int> h, wt;
   void initheights();
 public:
   MAXFLOW(const Graph G, int s, int t) : G(G),
  s(s), t(t), h(G.V()), wt(G.V(), 0)
  { initheights();
    GQ gQ(G.V());
    gQ.put(s); wt[t] = -(wt[s] = M*G.V());
    while (!gQ.empty())
   { int v = gQ.get();
     typename Graph::adjIterator A(G, v);
     for (Edge* e = A.beg(); !A.end(); e = A.nxt())
    { int w = e->other(v);
      int cap = e->capRto(w);
      int P = cap < wt[v] ? cap : wt[v];
      if (P > 0  v == s || h[v] == h[w]+1)
     { e->addflowRto(w, P);
       wt[v] -= P; wt[w] += P;
       if ((w != s)  (w != t)) gQ.put(w);
     }
    }
     if (v != s  v != t  wt[v] > 0)
    { h[v]+ + ; gQ.put(v); }
   }
  }
 } ;
   

Пожалуй, наиболее простой структурой данных для хранения активных вершин является очередь FIFO. На рис. 22.28 рис 22.28 показана работа этого алгоритма на демонстрационной сети. Из рисунка видно, что последовательность активных вершин удобно разбить на последовательность этапов. Этап - содержимое очереди после обработки всех вершин из предыдущего этапа. Это помогает ограничить общее время выполнения алгоритма.

Поскольку наши реализации используют неявное представление остаточной сети, они просматривают ребра, исходящие из вершины, даже если их нет в остаточной сети (чтобы проверить, находятся они там или нет). Можно показать, что границу V2E из леммы 22.13 можно снизить до V³, если использовать реализацию, в которой используется явное представление остаточной сети. Хотя эта теоретическая граница - наименьшая из тех, с которыми нам приходилось сталкиваться для задачи вычисления максимального потока, она вряд ли заслуживает нашего внимания, особенно для разреженных графов, которые часто встречаются на практике (см. 22.63-22.65).

Как обычно, границы для худшего случая слишком осторожны и поэтому редко пригодны для прогнозирования производительности алгоритма на реальных сетях (хотя разница и не так велика, как в случае алгоритмов с использованием расширяющих путей). Например, алгоритм FIFO находит поток в сети, представленной на рис 22.30, за 15 этапов, а оценка из леммы 22.13 утверждает лишь, что количество этапов не превышает 182.

На этом рисунке показаны транспортные сети (слева) и остаточные сети (справа) для каждого этапа алгоритма проталкивания напора на базе очереди FIFO. Содержимое очередей показано под диаграммами транспортных сетей, а метки расстояний - под диаграммами остаточных сетей. На начальном этапе мы проталкиваем поток по ребрам 0-1 и 0-2, что делает вершины 1 и 2 активными. На втором этапе мы проталкиваем поток через эти две вершины в 3 и 4, после чего они становятся активными, а вершина 1 перестает быть активной (вершина 2 остается активной, а метка ее расстояния увеличивается). На третьем этапе мы проталкиваем поток через вершины 3 и 4 в вершину 5, что делает их неактивными (вершина 2 все еще активна, а ее метка расстояния снова увеличивается). На четвертом этапе 2 остается единственным активным узлом, а ребро 2-0 становится приемлемым из-за увеличения метки расстояния, и одна единица потока проталкивается обратно по ребру 2-0, после чего вычисление завершается.

Данная сеть представляет семейство сетей с Vвер-шинами, на которых общее время работы алгоритма проталкивания напора пропорционально V². Она состоит из ребер с единичной пропускной способностью, исходящих из истока (вершина 0), и горизонтальных ребер с пропускной способностью v - 2, ведущих слева направо в сторону стока (вершина 10). На начальном этапе алгоритма проталкивания напора (вверху) мы проталкиваем одну единицу потока из каждого ребра, ведущего из истока, после чего становятся активными все вершины, кроме истока и стока. В стандартном представлении списками смежности они попадают в очередь FIFO активных вершин в обратном порядке, как показано в строке под диаграммой сети. На втором этапе (в центре) мы выталкиваем единицу потока из 9 в 10, сделав (временно) 9 неактивной; затем выталкиваем единицу потока из 8 в 9, сделав 8 (временно) неактивной, а 9 активной; затем выталкиваем единицу потока из вершины 7 в 8, сделав 7 (временно) неактивной, а 8 активной и т.д. Только вершина 1 остается неактивной. На третьем этапе (внизу) мы выполняем аналогичный процесс, чтобы сделать неактивной вершину 2. Этот процесс продолжается на протяжении V- 2 этапов.

Чтобы повысить производительность, можно попробовать использовать в программе 22.5 стек, рандомизированную очередь или любой другой вид обобщенной очереди. Один из подходов, хорошо зарекомендовавших себя на практике, заключается в такой реализации обобщенной очереди, чтобы функция GQGet возвращала максимальную активную вершину. Мы будем называть этот метод алгоритмом вычисления максимального потока методом проталкивания напора из вершины с максимальной высотой (highest-vertex-preflow-push). Эту стратегию можно реализовать с помощью очереди с приоритетами, но если воспользоваться конкретными особенностями высот, то можно обеспечить выполнение операций на обобщенной очереди за постоянное время. Было доказано, что граница времени выполнения этого алгоритма в худшем случае равна $$$V^{2}\sqrt{E}$$$ (для разреженных графов V5/2 ) (см. раздел ссылок). Как обычно, эта оценка слишком осторожна. Было предложено и множество других вариантов проталкивания напора, и некоторые из них понижают границу времени для худшего случая до значения, близкого к VE (см. раздел ссылок).

В таблице 22.2 сведены значения производительности, показанные алгоритмами проталкивания напора, которые соответствуют приведенным в таблице 22.1 результатам алгоритмов с использованием расширяющих путей, для двух моделей сетей из раздела 22.2. Эти эксперименты для различных алгоритмов проталкивания напора показывают гораздо меньшие различия в производительности, чем в случае различных методов расширения путей.

Данная последовательность диаграмм показывает, как реализация метода проталкивания напора с использованием очереди FIFO находит максимальный поток в демонстрационной сети. Он работает поэтапно. Сначала он проталкивает максимально возможный поток из истока по исходящим из него ребрам (слева вверху). Затем он проталкивает поток из каждого такого узла и продолжает так, пока не будет достигнут баланс для всех узлов.

В этой таблице приведены значения производительности (количество вершин, где величина потока увеличивалась, и количество просмотренных узлов из списков смежности) для различных алгоритмов проталкивания напора на нашем примере евклидовой сети с соседними связями (со случайными значениями пропускных способностей и максимальным потоком 286), и с единичными пропускными способностями (максимальный поток равен 6). Различия в результатах этих методов для обоих видов сетей минимальны. Для случайных пропускных способностей количество проверяемых ребер примерно то же, что и для алгоритма расширения путей (см. таблицу 22.1). Для единичных пропускных способностей алгоритмы с использованием расширяющих путей просматривают в этих сетях значительно меньше ребер.

Существует множество способов изучения реализаций алгоритмов проталкивания напора. Мы уже рассмотрели три основных варианта:

Можно рассмотреть несколько других возможностей и множество вариаций каждой из них, которые порождают множество различных алгоритмов (см., например, упражнения 22.56-22.60). Зависимость производительности алгоритмов от характеристик входной сети еще больше увеличивает количество возможностей.

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

Упражнения

22.49. Опишите работу алгоритма проталкивания напора в сети со сбалансированными пропускными способностями.

22.50. Воспользуйтесь концепциями, описанными в данном разделе (функции высоты, подходящие ребра и проталкивание потока через ребра), для описания алгоритмов вычисления максимального потока расширением путей.

22.51. Покажите в стиле рис 22.28 потоки и остаточные сети после каждого этапа работы алгоритма проталкивания напора с очередью FIFO для отыскания максимального потока в транспортной сети с рис 22.10.

22.52. Реализуйте функцию initheights() для программы 22.5 с помощью поиска в ширину от стока.

22.53. Выполните упражнение 22.51 для алгоритма проталкивания напора из вершины с максимальной высотой.

22.54. Измените программу 22.5, чтобы реализовать алгоритм проталкивания напора из вершины с максимальной высотой, реализовав обобщенную очередь в виде очереди с приоритетами. Проведите эмпирическое тестирование, чтобы добавить в таблицу 22.2 строку для этого варианта алгоритма.

22.55. Начертите графики зависимости количества активных вершин, а также количества вершин и ребер в остаточной сети по мере выполнения алгоритма проталкивания напора с очередью FIFO для конкретных примеров различных сетей (см. упражнения 22.7-22.12).

22.56. Реализуйте обобщенный реберный алгоритм проталкивания напора, который использует обобщенную очередь подходящих ребер. Эмпирически сравните его работу для различных сетей (см. упражнения 22.7-22.12) с базовыми методами, уделяя особое внимание наиболее быстрым реализациям обобщенных очередей.

22.57. Добавьте в программу 22.5 периодический пересчет высот вершин, равных кратчайшим путям в сток в остаточной сети.

22.58. Обдумайте идею равномерного распределения избыточного потока из вершин в исходящие ребра, а не заполнения одних до насыщения, оставляя другие пустыми.

22.59. Эмпирически определите оправданность вычисления кратчайших путей для первоначального задания функции высоты в программе 22.5, сравнив ее производительность для различных сетей (см. упражнения 22.7-22.12) с производительностью при первоначальном обнулении высот вершин.

22.60. Поэкспериментируйте с гибридными методами, содержащими различные сочетания описанных выше идей. Эмпирически сравните различные виды сетей (см. упражнения 22.7-22.12) с базовыми методами, уделяя особое внимание наиболее быстрым вариантам.

22.61. Добавьте в программу 22.5 явное отбрасывание повторяющихся вершин перед занесением в обобщенную очередь. Эмпирически определите для различных сетей (см. упражнения 22.7-22.12), как влияют эти изменения на реальное время выполнения.

22.62. Как повлияет разрешение заносить повторяющиеся вершины в обобщенную очередь на границу времени выполнения в худшем случае из леммы 22.13?

22.63. Измените реализацию программы 22.5, чтобы использовать явное представление остаточной сети.

о 22.64. Уточните границу O (V3) из леммы 12.13 для реализации из упражнения 22.63. Указание. Приведите отдельные границы для количества проталкиваний, которые соответствуют удалению ребер из остаточной сети, и для количества проталкиваний, в результате которых не появляются заполненные или пустые ребра.

22.65. Эмпирически определите для различных сетей (см. упражнения 22.7-22.12) влияние использования явных представлений остаточной сети (см. упражнение 22.63) на реальные значения времени выполнения.

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

22.67. Докажите, что в реберном обобщенном алгоритме проталкивания напора количество проталкиваний, которые не соответствуют удалению ребра из остаточной сети, меньше 4V²( V+E). Указание. Используйте сумму высот активных вершин в качестве функции потенциала.

22.68. Эмпирически определите фактическое количество проверяемых ребер и отношение времени прогона к V для различных версий алгоритма проталкивания напора и для различных сетей (см. упражнения 22.7-22.12). Рассмотрите различные алгоритмы, описанные в тексте и в предыдущих упражнениях, уделяя особое внимание тем, которые лучше работают на больших разреженных сетях. Сравните ваши результаты с результатами из упражнения 22.34.

22.69. Напишите клиентскую программу для графической анимации динамики алгоритма проталкивания напора. Эта программа должна создавать изображения, подобные рис 22.30 и другим рисункам из этого раздела (см. упражнение 22.48). Протестируйте полученную реализацию на евклидовых сетях из упражнений 22.7-22.12.

Сведения к вычислению максимального потока

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

Мы также изучим взаимосвязь между вычислением максимального потока и более сложными задачами, чтобы сформировать контекст для рассмотрения этих задач в дальнейшем. В частности, задача о максимальном потоке представляет собой специальный случай задачи отыскания потока минимальной стоимости, о которой пойдет речь в разделах 22.5 и 22.6. Кроме того, мы покажем, как формулировать задачи вычисления максимального потока в виде задач линейного программирования, которые мы будем рассматривать в части 8. Задача отыскания потока минимальной стоимости и линейное программирование представляют собой более общие модели решения задач, чем модель максимального потока. И хотя обычно решение задач о максимальном потоке с помощью специальных алгоритмов, описанных в разделах 22.2 и 22.3, менее трудоемко, чем с помощью алгоритмов для решения более общих задач, важно знать о взаимосвязи между моделями решения задач при переходе к более сложным моделям.

Мы будем употреблять термин стандартная задача о максимальном потоке (standard maxflow problem) для версии задачи, которую мы изучали до сих пор (максимальный поток в st-сетях с ограниченной пропускной способностью ребер). Этот термин будет применяться исключительно для облегчения ссылок в данном разделе. Вначале мы рассмотрим сведения, на примере которых убедимся, что ограничения в стандартной задаче о максимальном потоке несущественны, т.к. к стандартной задаче сводятся или эквивалентны несколько других задач о потоках. Любую из эквивалентных задач можно принять в качестве " стандартной " задачи. Простым примером такой задачи, который уже упоминался как следствие из леммы 22.1, является задача отыскания циркуляции в сетях, позволяющая получить максимальный поток в заданном ребре. Затем мы рассмотрим другие способы постановки задачи, в каждом случае отмечая их связь со стандартной задачей.

Максимальный поток в сетях общего вида. Нужно найти поток в сети, который максимизирует суммарный отток из ее истоков (и, следовательно, приток в ее стоки). По соглашению, в сети, в которой нет истоков и/или стоков, поток считается нулевым.

В верхней сети имеются три истока (0, 1 и 2) и два стока (5 и 6). Чтобы найти поток, который максимизирует суммарный поток из истоков и в стоки, мы вычисляем максимальный поток в st-сети, представленной внизу. Это копия исходной сети, в которую добавлены исток 7 и сток 8. Из вершины 7 в каждый исходный исток проводим ребро, пропускная способность которого равна суммарной пропускной способности ребер, исходящих из этого истока. А в вершину 8 ведут ребра из каждого исходного стока сети, пропускная способность которых равна суммарной пропускной способности ребер, входящих в стоки исходной сети.

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

Чтобы решить задачу вычисления максимального потока в сети, показанной вверху, и чтобы поток через каждую вершину не превосходил пропускной способности, заданной в массиве capV, индексированном именами вершин, мы строим стандартную сеть, показанную внизу. Для каждого ребра u-v соединяем новую вершину u* (где u* означает v+V) с каждой вершиной u, добавляем ребро, пропускная способность которого равна пропускной способности вершины u, и включаем ребро u*-v. Пары u-u* обведены овалами. Любой поток в нижней сети непосредственно соответствует потоку в верхней сети, который удовлетворяет ограничениям на пропускные способности вершин.

Допуская наличие нескольких стоков и истоков или накладывая ограничения на пропускные способности, мы вроде бы обобщаем задачу о максимальном потоке; однако смысл лемм 22.14 и 22.15 в том, что эти задачи нисколько не сложнее стандартной задачи. Теперь рассмотрим версию задачи, которая поначалу кажется более легкой для решения.

Ациклические сети. Нужно найти максимальный поток в ациклической сети. Осложняет ли наличие циклов в транспортной сети задачу вычисления максимального потока?

Мы уже сталкивались со многими примерами задач обработки орграфов, которые существенно усложняются при наличии в орграфах циклов. Пожалуй, самый наглядный из них - задача вычисления кратчайших путей во взвешенных орграфах, когда веса ребер могут принимать отрицательные значения (см. ) - которая легко решается за линейное время при отсутствии циклов и NP-трудна, если циклы допускаются. Как ни странно, задача о максимальном потоке в ациклических сетях не становится проще.

Каждая вершина u верхней сети соответствует двум вершинам u и u* (где u* означает u+V) нижней сети, а каждое ребро u-v верхней сети соответствует ребру u-v* нижней сети. Кроме того, в нижней сети имеются ребра u-u* без пропускных способностей, источник s с ребрами, ведущими в каждую вершину, не отмеченную звездочкой, и сток t, в который ведут ребра из каждой вершины, помеченной звездочкой. Серые и белые вершины (и ребра, соединяющие серые вершины с белыми) иллюстрируют прямую взаимосвязь сечений в обеих сетях (см. текст).

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

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

Максимальный поток в неориентированных сетях. Неориентированная транспортная сеть - это взвешенный граф с целочисленными весами ребер, которые интерпретируются как пропускные способности. Циркуляция в таких сетях - это назначение весов и

направлений ребрам, которое удовлетворяет условию: поток в каждом ребре не превышает его пропускную способность, а суммарный поток в каждую вершину равен суммарному потоку из этой вершины. Задача о неориентированном максимальном потоке (рис 22.34) состоит в том, чтобы найти циркуляцию, которая максимизирует поток в заданном направлении в заданном ребре (т.е. из некоторой заданной вершины s в другую заданную вершину t). Пожалуй, эта задача более естественно, чем стандартная задача, соответствует модели трубопровода для перекачки жидкостей: она позволяет протекать жидкости по трубам в обоих направлениях.

Чтобы решить задачу о максимальном потоке в неориентированной сети, ее можно рассматривать как ориентированную сеть с ребрами в обоих направлениях. Обратите внимание, что каждому ребру неориентированной сети соответствует четыре ребра в соответствующей ей остаточной сети.

Это доказательство не утверждает, что задача о максимальном потоке в неориентированной сети эквивалентна стандартной задаче. То есть не исключено, что вычисление максимальных потоков в неориентированных сетях может иметь меньшую трудоемкость, чем вычисление максимальных потоков в стандартных сетях (см. упражнение 22.81).

Итак, мы можем обрабатывать сети с несколькими стоками и истоками, неориентированные сети, сети с ограниченными пропускными способностями вершин и многие другие виды сетей (см., например, упражнение 22.79), используя алгоритмы вычисления максимального потока для st-сетей, рассмотренные в двух предыдущих разделах. Более того, лемма 22.16 утверждает, что все эти задачи можно решить даже при помощи алгоритма, который работает только на ациклических сетях.

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

Допустимый поток. Предположим, что каждой вершине транспортной сети присвоен вес, который можно рассматривать как предложение (если он положителен) или как спрос (если отрицателен), а сумма весов всех вершин сети равна нулю. Будем считать поток допустимым (feasible), если разность между притоком и оттоком каждой вершины равна весу этой вершины (предложению, если разность положительна, и спросу, если отрицательна). Пусть дана такая сеть, и нужно определить, возможны ли допустимые потоки. На рис. 22.35 рис 22.35 приведен пример задачи о допустимом потоке.

Вершины с предложением соответствуют складам в задаче о распределении товаров, вершины со спросом соответствуют розничным торговым точкам, а ребра соответствуют дорогам на маршрутах грузоперевозок. Задача о допустимом потоке отвечает на следующий основной вопрос: можно ли найти такой способ доставки товаров, при котором везде предложение соответствует спросу.

В задаче о допустимом потоке в дополнение к пропускным способностям ребер заданы величины предложения и спроса. Необходимо найти такой поток, при котором отток равен сумме поставки и притока в вершинах предложения, и приток равен сумме оттока и спроса в вершинах спроса. Слева представлена задача о допустимом потоке, а правее - три ее решения.

Разработка классов, которые реализуют сведения рассмотренного выше вида, может оказаться сложной задачей для программистов - главным образом потому, что обрабатываемые объекты представлены сложными структурами данных. Нужно ли строить новую сеть, чтобы свести еще одну задачу к стандартной задаче о максимальном потоке? Некоторые из задач требуют для своего решения дополнительных данных - таких как пропускные способности вершин или предложение или спрос - поэтому построение стандартной сети без этих данных может оказаться оправданным. Использование указателей на ребра играет здесь важную роль: если скопировать ребра сети, а затем вычислить максимальный поток, то что потом делать с результатом? Перенос вычисленного потока (вес каждого ребра) из одной сети в другую, когда обе сети представлены списками смежности - отнюдь не тривиальное действие. Когда используются указатели на ребра, новая сеть содержит копии указателей, а не ребер, что позволяет переслать значения потоков непосредственно в сеть клиента. Программа 22.6 представляет собой реализацию, которая демонстрирует некоторые из этих моментов в классе для решения задач поиска подходящего потока с помощью сведения согласно лемме 22.16.

Это стандартная сеть, построенная для задачи о допустимом потоке с рис 22.35 с помощью добавления ребер из нового истока в вершины с предложением (пропускные способности каждого такого ребра равны величине предложения) и ребер в новый сток из вершин со спросом (пропускные способности каждого такого ребра равны величине спроса). В сети на рис 22.35 допустимый поток имеется тогда и только тогда, когда в этой сети имеется поток (максимальный поток), который заполняет все ребра, исходящие из стока, и все ребра, входящие в исток.

Каноническим примером задачи о потоках, которую невозможно решить с помощью модели максимального потока, и которая будет рассмотрена в разделах 22.5 и 22.6, является расширение задачи о допустимом потоке. Добавим второе множество весов ребер, которые будут интерпретироваться как стоимости, определим через них стоимости потоков и поставим задачу найти допустимый поток минимальной стоимости. Эта модель формализует общую задачу распределения товаров. Мы хотим не только знать, можно ли транспортировать товары, но и какова минимальная стоимость развозки.

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

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

Для краткости мы будем далее называть эту задачу просто задачей двудольного сопоставления (bipartite matching), кроме случаев, в которых нужно отличить ее от других подобных задач. Она формализует задачу трудоустройства, которая была упомянута в начале данной главы. Вершины соответствуют соискателям и работодателям, а ребра - отношению " взаимной заинтересованности в трудоустройстве". Решение задачи двудольного сопоставления приводит к максимально возможному трудоустройству. На рис 22.37 показан двудольный граф, моделирующий задачу с рис 22.3.

Без графов очень трудно искать прямое решение задачи о двудольном сопоставлении. Например, эта задача сводится к следующей комбинаторной головоломке: " найти максимальное подмножество из множества пар целых чисел (взятых из непересекающихся множеств), чтобы ни в одной паре не было одинаковых чисел " . Пример, приведенный на рис 22.37, соответствует решению этой головоломки для пар (и многих других задач), какой-либо примитивный систематический перебор пар до возникновения противоречия может потребовать экспоненциального времени. То есть существует слишком много подмножеств пар, чтобы можно было проверить все варианты; решение этой задачи должно быть достаточно разумным, чтобы использовать лишь немногие из них. Решение головоломок сопоставления вроде только что описанной или разработка алгоритмов, которые способны эффективно решать любую такую головоломку - очень непростые задачи, позволяющие продемонстрировать возможности и пользу модели сетевых потоков, которая предоставляет разумный способ построения двудольного сопоставления.

Программа 22.6. Решение задачи о допустимом потоке сведением к задаче о максимальном потоке

Данный класс решает задачу о допустимом потоке с помощью сведения ее к задаче о максимальном потоке, используя построение, представленное на рис 22.36. Конструктор принимает в качестве аргументов сеть и вектор sd, индексированный именами вершин. Если значение sd[i] положительно, то оно представляет предложение в вершине i, а если отрицательно, то спрос.

Как показано на рис 22.36, конструктор строит новый граф с теми же ребрами, но с двумя дополнительными вершинами s и t. Ребра из s ведут в узлы с предложением, а ребра из вершин со спросом ведут в вершину t. Затем он находит максимальный поток и проверяет, заполнены ли все дополнительные ребра до их пропускных способностей.

  #include "MAXFLOW.cc"
  template <class Graph, class Edge>
  class FEASIBLE
 { const Graph G;
   void freeedges(const Graph F, int v)
  { typename Graph::adjIterator A(F, v);
    for (EDGE* e = A.beg(); !A.end(); e = A.nxt())
   delete e;
  }
 public:
   FEASIBLE(const Graph G, vector<int> sd) : G(G)
  { Graph F(G.V()+2);
    for (int v = 0; v < G.V(); v++)
   { typename Graph::adjIterator A(G, v);
     for (EDGE* e = A.beg(); !A.end(); e = A.nxt())
    F.insert(e);
   }
    int s = G.V(), t = G.V()+1;
    for (int i = 0; i < G.V(); i++)
   if (sd[i] >= 0)
     F.insert(new EDGE(s, i, sd[i]));
   else
     F.insert(new EDGE(i, t, -sd[i]));
    MAXFLOW<Graph, Edge>(F, s, t);
    freeedges(F, s); freeedges(F, t);
  }
 } ;
   

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

Например, на рис 22.38 алгоритм вычисления максимального потока с использованием расширяющих путей может использовать пути .

Чтобы найти максимальное сопоставление в двудольном графе (вверху) мы строим st-сеть (внизу), направляем все ребра из верхнего ряда в нижний ряд, добавляем новый исток с ребрами в каждую вершину верхнего ряда, добавляем новый сток, в который ведут ребра из каждой вершины нижнего ряда, и назначаем всем ребрам единичную пропускную способность. При любом потоке можно заполнить не более одного ребра из всех ребер, исходящих из каждой вершины верхнего ряда, а также не более одного ребра из всех ребер, входящих в каждую вершину нижнего ряда, поэтому решение задачи о максимальном потоке для этой сети дает максимальное сопоставление для двудольных графов.

Программа 22.7 является клиентской программой, которая считывает задачу о двудольном сопоставлении из стандартного ввода и решает ее при помощи сведения, описанного в этом доказательстве. Каким будет время выполнения этой программы для очень больших сетей? Разумеется, время выполнения зависит от используемого алгоритма вычисления максимального потока и его реализации. Кроме того, следует учесть, что получаемые при этом сети имеют специальную структуру (двудольные транспортные сети с единичной пропускной способностью ребер). Поэтому время выполнения различных известных нам алгоритмов вычисления максимальных потоков не приближается к границам для худшего случая; более того, можно существенно снизить эти границы. Например, нетрудно улучшить оценку для первой рассмотренной нами границы - для обобщенного алгоритма с использованием расширяющих путей.

Работу алгоритмов расширения путей на двудольной сети с единичной пропускной способностью ребер описать нетрудно. Каждый расширяющий путь наполняет одно ребро, ведущее из истока, и одно ребро, ведущее в сток. Эта ребра никогда не используются как обратные, поэтому может быть не более V расширяющих путей. Для каждого алгоритма, который находит расширяющие пути за время, пропорциональное E, действительна верхняя граница, пропорциональная VE.

Программа 22.7. Поиск двудольного сопоставления сведением к задаче вычисления максимального потока

Этот клиент считывает из стандартного ввода задачу о двудольном сопоставлении с V + V вершинами и E ребрами, а затем строит транспортную сеть, соответствующую этой задаче, находит максимальный поток в сети и использует полученное решение для вывода максимального двудольного сопоставления.

  #include "GRAPHbasic.cc"
  #include "MAXFLOW.cc"
  int main(int argc, char *argv[])
 { int s, t, N = atoi(argv[1]);
   GRAPH<EDGE> G(2*N+2);
   for (int i = 0; i < N; i++)
  G.insert(new EDGE(2*N, i, 1));
   while (cin >> s >> t)
  G.insert(new EDGE(s, t, 1));
   for (int i = N; i < 2*N; i++)
  G.insert(new EDGE(i, 2*N+1, 1));
   MAXFLOW<GRAPH<EDGE>, EDGE>(G, 2*N, 2*N+1);
   for (int i = 0; i < N; i++)
  { GRAPH<EDGE>::adjIterator A(G, i);
    for (EDGE* e = A.beg(); !A.end(); e = A.nxt())
   if (e->flow() == 1  e->from(i))
     cout << e->v() << "-" << e->w() << endl;
  }
 }
   

В таблице 22.3 показаны значения производительности для методов решения задач двудольного сопоставления с использованием различных алгоритмов вычисления расширяющих путей. Из этой таблицы видно, что фактические значения времени решения этой задачи ближе к значению VE для худшего случая, чем к оптимальному (линейному) времени. Разумный выбор и соответствующая настройка реализации, вычисляющей максимальный поток, позволяет увеличить быстродействие этого метода в $$$\sqrt{V}$$$ раз (см. упражнения 22.91 и 22.92).

Здесь представлены показатели производительности (количество расширенных вершин и количество затронутых узлов в списках смежности) для различных алгоритмов вычисления максимального потока методом расширения путей при вычислении максимального двудольного сопоставления для графов с 2000 парами вершин и 500 ребрами (вверху), а также 4000 ребрами (внизу). Для этой задачи наиболее эффективным оказался поиск в глубину.

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

Далее мы обсудим задачи, имеющие отношение к связности графов. Но прежде чем рассматривать использование алгоритмов вычисления максимального потока для решения задач связности, мы исследуем применение теоремы о максимальном потоке и минимальном сечении и завершим то, что начали в - доказательства базовых теорем, относящихся к путям и сечениям в неориентированных графах. Эти доказательства еще раз подчеркивают фундаментальное значение теоремы о максимальном потоке и минимальном сечении.

Соответствующие результаты для неориентированных графов и для вершинной связности в орграфах и неориентированных графах получаются с помощью сведений, подобных рассмотренным в тексте, и оставлены на самостоятельную проработку (упражнения 22.94-22.96).

А теперь обратимся к алгоритмическим следствиям из непосредственной взаимосвязи между потоками и связностью, которая устанавливается теоремой о максимальном потоке и минимальном сечении. Пожалуй, одним из важнейших алгоритмических следствий является лемма 22.5 (задача о минимальном сечении сводится к задаче о максимальном потоке), однако обратное утверждение не доказано (см. упражнение 22.47). Вроде бы информация о минимальном сечении должна облегчить задачу вычисления максимального потока, но никому еще не удалось показать, как это сделать. Этот простой пример подчеркивает необходимость осторожности при сведении одних задач к другим.

Однако алгоритмы вычисления максимального потока все-таки можно использовать для решения различных задач о связности. Например, они помогают решить первые нетривиальные задачи, с которыми мы сталкивались в .

Реберная связность. Каково минимальное количество ребер, которые необходимо удалить, чтобы разделить заданный граф на две части? Найти множество ребер минимальной мощности, обеспечивающее такое разделение.

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

Эти задачи формулируются и для орграфов, поэтому всего требуется рассмотреть четыре задачи. Как и в случае теоремы Менгера, мы подробно рассмотрим одну из них (реберная связность в неориентированных графах), а остальные оставим читателям на самостоятельную проработку.

Этот метод, в отличие от всех других примеров из этого раздела, не является непосредственным сведением одной задачи к другой, но он дает практический алгоритм для вычисления реберной связности. Опять-таки, тщательная настройка реализации вычисления максимального потока для этой конкретной задачи позволяет повысить производительность, и можно решить эту задачу за время, пропорциональное , и которое играет существенную роль в теории алгоритмов, о которой пойдет речь в части 8. Такое сведение не только доказывает разрешимость задачи, но и предлагает алгоритм для ее решения, а это важные первые шаги при решении новой комбинаторной задачи.

Мы завершим данный раздел анализом строгой математической формулировки задачи о максимальном потоке в терминах линейного программирования (см. ). Это упражнение полезно тем, что оно помогает увидеть связи с другими задачами, которые можно сформулировать аналогично.

Формулировка этой задачи тривиальна: имеется система неравенств, в которой каждому ребру соответствует одна переменная, каждому ребру соответствуют два неравенства, и каждой вершине соответствует одно равенство. Значение переменной - это величина потока в ребре, неравенства указывают, что величина потока в ребре должна быть в пределах от нуля до пропускной способности этого ребра, а равенства указывают, что суммарный поток в ребрах, ведущих в каждую вершину, должен быть равен суммарному потоку в ребрах, исходящих из этой вершины.

Пример такого построения приведен на рис 22.39. Аналогично любую задачу о максимальном потоке можно преобразовать в задачу линейного программирования (LP-задачу). Линейное программирование - универсальный способ решения комбинаторных задач, и многие рассматриваемые нами задачи можно сформулировать как LP-задачи. Тот факт, что задачи о максимальном потоке решаются легче, чем LP-задачи, можно объяснить тем, что в LP-формулировке задач о максимальном потоке ограничения имеют особую структуру, которая характерна не для всех LP-задач.

Эта LP-задача эквивалентна задаче о максимальном потоке для сети с рис 22.5. Имеется по одному неравенству для каждого ребра (которое указывает, что поток в этом ребре не может превосходить его пропускной способности) и по одному равенству для каждой вершины (которое указывает, что приток должен быть равен оттоку). В этой сети используется фиктивное ребро из стока в исток, которое предназначено для перехвата сетевого потока (см. обсуждение после леммы 22.2).

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

Построение, представленное на рис 22.39, служит доказательством того, что задача о максимальном потоке сводится к LP-задаче, если не настаивать, чтобы величины потоков были целыми числами. Мы будем подробно рассматривать LP-задачи в части VIII, и там опишем, как справиться с тем, что формулировка задачи о максимальном потоке в терминах линейного программирования не содержит требования, что результаты должны иметь целые значения.

Этот контекст дает четкую математическую основу, которая позволяет рассматривать даже более общие задачи и создавать еще более мощные алгоритмы решения этих задач. Задача о максимальном потоке легко поддается решению и сама по себе довольно универсальна, о чем говорят примеры, приведенные в данном разделе. Далее мы рассмотрим более сложную задачу (но не такую сложную, как линейное программирование), которая охватывает еще более широкий класс практических задач. Мы обсудим варианты построения решений для этих все более общих моделей в конце этой главы, заложив основу для их полного анализа в части 8.

Упражнения

22.70. Определите класс для вычисления циркуляции с максимальным потоком в заданном ребре. Разработайте реализацию, использующую функцию MAXFLOW.

22.71. Определите класс для вычисления максимального потока без ограничения на количество истоков и стоков. Разработайте реализацию, использующую функцию MAXFLOW.

22.72. Определите класс для вычисления максимального потока в неориентированной сети. Разработайте реализацию, использующую функцию MAXFLOW.

22.73. Определите класс для вычисления максимального потока в сети с ограничениями на пропускные способности вершин. Разработайте реализацию, использующую функцию MAXFLOW.

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

22.75. Выполните упражнение 22.18 для случая, когда в каждой точке распределения имеется ограничение на пропускную способность (т.е. существует предел количества товаров, которые могут храниться в этой точке в любой заданный момент времени).

22.76. Покажите, что задача о максимальном потоке сводится к задаче о допустимом потоке (т.е. эти задачи эквивалентны).

22.77. Найдите допустимый поток для транспортной сети, представленной на рис 22.10, при наличии дополнительных ограничений: вершины 0, 2 и 3 являются вершинами предложения с весом 4, а вершины 1, 4 и 5 являются вершинами предложения с весами, соответственно, 1, 3 и 5.

22.78. Напишите программу, которая принимает в качестве входных данных расписание соревнований некоторой спортивной лиги и текущее положение команд и определяет, выбыла ли заданная команда из турнира. Считайте, что связи отсутствуют. Указание. Сведите данную задачу к задаче о допустимом потоке с одним истоком, величина предложения которого равна суммарному количеству игр, которые осталось сыграть в текущем сезоне; с узлами стока, соответствующими каждой паре команд, величина спроса в которых равна количеству оставшихся игр между этой парой; и с узлами распределения, соответствующими каждой команде. Ребра должны соединять узлы предложения с узлами распределения каждой команды (с пропускными способностями, равными количеству игр, которые команда должна выиграть, чтобы выиграть у X, если X выиграет все свои оставшиеся игры). И должно существовать ребро (без пропускной способности), соединяющее узел распределения каждой команды с каждым узлом спроса, имеющим отношение к этой команде.

22.79. Докажите, что задача о максимальном потоке для сетей с низкими пропускными способностями ребер сводится к стандартной задаче о максимальном потоке.

22.80. Докажите, что для сетей с низкими пропускными способностями ребер задача вычисления минимального потока (с учетом пропускных способностей) сводится к задаче о максимальном потоке (см. упражнение 22.79).

22.81. Докажите, что задача о максимальном потоке в st-сетях сводится к задаче о максимальном потоке в неориентированных сетях, либо найдите алгоритм вычисления максимального потока для неориентированных сетей, время выполнения которого в худшем случае значительно лучше, чем для алгоритмов из разделов 22.2 и 22.3.

22.82. Найдите все сопоставления с пятью ребрами для двудольного графа, представленного на рис 22.37.

22.83. Усовершенствуйте программу 22.7, чтобы вершинам можно было присваивать символические имена, а не номера (см. программу 17.10).

22.84. Докажите, что задача двудольного сопоставления эквивалентна задаче вычисления максимального потока в сети с единичными пропускными способностями всех ребер.

22.85. Пример на рис 22.3 можно интерпретировать как описание заявок студентов на работу и заявок работодателей на студентов, которые не обязательно взаимны. Применимо ли сведение, описанное в тексте, к ориентированной задаче двудольного сопоставления, вытекающей из этой интерпретации, где ребра двудольного графа направлены (в любом направлении) из одного множества в другое? Докажите это или приведите контрпример.

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

22.87. Покажите в стиле рис 22.28 работу алгоритма проталкивания напора с использованием очереди FIFO на сети двудольного сопоставления с рис 22.3838.

22.88. Добавьте в таблицу 22.3 данные для различных алгоритмов проталкивания напора.

22.89. Предположим, что в задаче двудольного сопоставления два множества имеют размеры S и T, причем S << T. Приведите как можно более точную границу времени решения этой задачи в худшем случае для сведения, описанного в лемме 22.19, и реализации алгоритма Форда-Фалкерсона с использованием максимальных расширяющих путей (см. лемму 22.8).

22.90. Выполните упражнение 22.89 для реализации алгоритма проталкивания напора с использованием очереди FIFO (см. лемму 22.13).

22.91. Добавьте в таблицу 22.3 данные для реализаций, которые используют метод построения всех расширяющих путей, описанный в упражнении 22.37.

22.92. Докажите, что время выполнения метода, описанного в упражнении 22.91, равно O(JV E) для поиска в ширину.

22.93. На основе эмпирического исследования постройте график зависимости ожидаемого количества ребер в максимальном сопоставлении в случайных двудольных графах с V + V вершинами и E ребрами для разумного множества значений V и значений E, достаточных для получения гладкой кривой от ноля до V.

22.94. Докажите теорему Менгера (лемма 22.20) для неориентированных графов.

22.95. Докажите, что минимальное количество вершин, удаление которых разъединяет две вершины в орграфе, равно максимальному количеству путей между этими двумя вершинами, не пересекающихся по вершинам. Указание. Воспользуйтесь раз-щеплением вершин, как на рис 22.32.

22.96. Распространите ваше доказательство из упражнения 22.95 на неориентированные графы.

22.97. Реализуйте класс реберной связности для АТД графа из , конструктор которого использует алгоритм, описанный в этом разделе, для обеспечения работы общедоступной функции-члена, которая возвращает значение связности графа.

22.98. Добавьте в решение упражнения 22.97 занесение в пользовательский вектор минимального множества ребер, которое разделяет граф. Какой размер этого вектора должен предусмотреть пользователь?

22.99. Разработайте алгоритм вычисления реберной связности орграфов (минимальное количество ребер, удаление которых нарушает сильную связность орграфа). На основе этого алгоритма реализуйте класс для АТД орграфа из главы 19 .

22.100. На основе решений упражнений 22.95 и 22.96 разработайте алгоритмы для вычисления вершинной связности орграфов и неориентированных графов. На базе этих алгоритмов реализуйте классы, соответственно, для АТД орграфа из , и для АТД графа из (см. упражнения 22.97 и 22.98).

22.101. Опишите, как вычислить вершинную связность орграфа путем решения VlgV задач о максимальном потоке в сети с единичными пропускными способностями. Указание. Воспользуйтесь теоремой Менгера и двоичным поиском.

22.102. Пользуясь решением упражнения 22.97, эмпирически определите реберную связность различных графов (см. упражнения 17.63-17.76).

22.103. Сформулируйте в терминах линейного программирования задачу о максимальном потоке в транспортной сети, представленную на рис 22.10.

22.104. Сформулируйте в терминах линейного программирования задачу двудольного сопоставления, представленную на рис 22.37.

Потоки минимальной стоимости

В наличии многочисленных решений для конкретной задачи о максимальном потоке нет ничего удивительного. Но при этом возникает вопрос: можно ли ввести дополнительные критерии, чтобы выбрать один из них? Например, понятно, что существует множество решений для задач вычисления потоков в сети с единичными пропускными способностями, представленных нарис 22.22. Возможно, для нас лучше решение, использующее наименьшее количество ребер или кратчайшие пути. А возможно, нам нужно знать, существует ли решение, использующее непересекающиеся пути. Эти задачи сложнее, чем стандартная задача о максимальном потоке, они описываются более общей моделью, известной как задача о потоке минимальной стоимости (mincost flow problem).

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

Конкретно, мы воспользуемся моделью максимального потока минимальной стоимости (mincost-maxflow): введем тип ребра, который содержит целочисленную стоимость, используем стоимость ребра для естественного определения стоимости потока, а затем поставим задачу определения максимального потока минимальной стоимости. Мы не только получим эффективный алгоритм для этой задачи, но и построим модель ее решения, получившую широкое применение.

Мы все так же считаем, что пропускные способности выражаются положительными целыми числами, меньшими M, а стоимости ребер - неотрицательными числами, меньшими C. (Отказ от использования отрицательных стоимостей мотивируется главным образом соображениями удобства, о чем будет сказано в разделе 22.7.) Как и ранее, мы присваиваем этим граничным значениям специальные обозначения, т.к. от них зависит время выполнения некоторых алгоритмов. С учетом этих простых предположений формулировка задачи, которую мы намереваемся решить, не представляет трудностей.

Максимальный поток минимальной стоимости. Пусть задана транспортная сеть со стоимостями ребер. Нужно найти такой максимальный поток, стоимость которого не больше стоимости любого другого максимального потока.

На рис 22.40 показаны различные максимальные потоки в транспортной сети со стоимостями, в том числе и максимальный поток минимальной стоимости. Разумеется, трудоемкость минимизации стоимости не уступает поиску максимального потока, о котором речь шла в разделах 22.2 и 22.3. Стоимость добавляет новое измерение, а это существенно усложняет дело. Но все-таки мы можем справиться с этими трудностями с помощью обобщенного алгоритма, который похож на алгоритм расширения путей для задачи о максимальном потоке.

Есть много других задач, которые сводятся к задаче о максимальном потоке минимальной стоимости или эквивалентны ей. Например, интересна следующая постановка задачи, т.к. она охватывает задачу распределения товаров, которая была рассмотрена в начале данного раздела.

Допустимый поток минимальной стоимости. Напомним, что поток в сети, содержащей вершины с весами (предложение, если вес положительный, и спрос, если вес отрицательный), называется допустимым (feasible), если сумма весов вершин отрицательна, а разность между притоком и оттоком в каждой вершине равна нулю. Нужно найти в такой сети допустимый поток минимальной стоимости.

Чтобы описать сетевую модель для решения задачи о допустимом потоке минимальной стоимости, мы для краткости используем термин распределительная сеть (distribution network), который будет означать " транспортная сеть с пропускными способностями ребер, стоимостями ребер и весами предложения или спроса в вершинах " .

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

Все эти потоки имеют одну и ту же (максимальную) величину, но их стоимости (сумма произведений потоков в ребрах на стоимости этих ребер) различны. Максимальный поток в центре имеет минимальную стоимость (ни один максимальный поток не имеет меньшей стоимости).

Вследствие этой эквивалентности и в силу того, что задача о допустимом потоке минимальной стоимости непосредственно моделирует задачи распределения товаров и многие другие приложения, мы употребляем для обозначения обеих задач термин поток минимальной стоимости (minicost flow) - даже в контекстах, где возможно упоминание любой из них. Сведения к другим задачам будут рассмотрены в разделе 22.7.

Для реализации стоимостей ребер в транспортных сетях добавим в класс EDGE из раздела 22.1 целочисленный приватный член данных pcost и функцию-элемент cost(), возвращающую значение стоимости клиенту. Программа 22.8 представляет собой клиентскую функцию, которая вычисляет стоимость потока в графе, построенном из указателей на такие ребра. Как и при работе с максимальными потоками, целесообразно реализовать функцию проверки, что значения притока и оттока согласованы в каждой вершине, а структуры данных непротиворечивы (см. упражнение 22.12).

Программа 22.8. Вычисление стоимости потока

Эту функцию, которая возвращает стоимость сетевого потока, можно включить в программу 22.1. Она суммирует произведения стоимостей и потоков для всех ребер с положительной пропускной способностью, позволяя рассматривать ребра без пропускной способности как фиктивные.

  static int cost(Graph G)
 { int x = 0;
   for (int v = 0; v < G.V(); v++)
  { typename Graph::adjIterator A(G, v);
    for (Edge* e = A.beg(); !A.end(); e = A.nxt())
   if (e->from(v)  e->costRto(e->w()) < C)
     x += e->flow()*e->costRto(e->w());
  }
   return x;
 }
   

Первым шагом при разработке алгоритмов для вычисления потока минимальной стоимости необходимо добавить стоимость ребер в определение остаточных сетей.

Это определение почти идентично определению 22.4, но имеет очень важное отличие. Ребра в остаточной сети, представляющие обратные ребра, имеют отрицательную стоимость. Чтобы реализовать это соглашение, мы используем следующую функцию-член в классе ребра:

  int costRto(int v)
 { return from(v) ? -pcost : pcost; }
   

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

Из этой леммы непосредственно следует простой обобщенный алгоритм решения задачи о потоке минимальной стоимости, получивший название алгоритма вычеркивания циклов (cycle-canceling algorithm):

Найдите максимальный поток. Увеличьте поток в произвольном цикле с отрицательной стоимости в остаточной сети, и продолжайте эту процедуру, пока не останется ни одного такого цикла.

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

Поскольку мы уже разработали алгоритмы для вычисления максимального потока и поиска отрицательных циклов, мы сразу же получаем реализацию алгоритма вычеркивания циклов, представленную в программе 22.9. Мы используем любую реализацию вычисления максимального потока для нахождения начального максимального потока и алгоритм Беллмана-Форда для поиска отрицательных циклов (см. упражнение 22.108). К двум этим реализациям остается только добавить цикл увеличения потоков в циклах на графе.

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

Программа 22.9. Вычеркивание циклов

Этот класс решает задачу вычисления максимального потока минимальной стоимости методом вычеркивания отрицательных циклов. Он использует класс MAXFLOW для поиска максимального потока и приватную функцию-член negcyc (см. упражнение 22.108) для нахождения отрицательных циклов. Если отрицательный цикл существует, этот программный код находит такой цикл, вычисляет максимальную величину потока, который нужно протолкнуть через него, и делает это. Функция augment взята из программы 22.3 и была (предусмотрительно!) разработана для правильной работы в случаях, когда путь оказывается циклом.

  template <class Graph, class Edge>
  class MINCOST
 { const Graph G;
   int s, t;
   vector<int> wt;
   vector <Edge *> st;
   int ST(int v) const;
   void augment(int, int);
   int negcyc(int);
   int negcyc();
 public:
   MINCOST(const Graph G, int s, int t) : G(G),
  s(s), t(t), st(G.V()), wt(G.V())
  { MAXFLOW<Graph, Edge>(G, s, t);
    for (int x = negcyc(); x != -1; x = negcyc())
   { augment(x, x); }
  }
 };
   

Каждый из показанных здесь потоков представляет собой максимальный поток в транспортной сети в верхней части рисунка, но только поток, изображенный внизу, является максимальным потоком минимальной стоимости. Чтобы найти его, мы начинаем с произвольного максимального потока и увеличиваем поток по отрицательным циклам. Стоимость начального максимального потока (второй сверху) равна 22, но он не является максимальным потоком минимальной стоимости, т.к. остаточная сеть (показана справа) содержит три отрицательных цикла.

В этом примере мы увеличиваем поток по циклу 4-1-0-2-4 и получаем максимальный поток со стоимостью 21 (третий сверху), который еще содержит один отрицательный цикл. Увеличение потока по этому циклу дает поток минимальной стоимости (внизу). Обратите внимание, что увеличение потока по циклу 3-2-4-1-3 дало бы максимальный поток минимальной стоимости всего за один шаг.

Эта технология вычисления потока минимальной стоимости показана на рис 22.42. На этом рисунке используется начальный поток, равный максимальному потоку - чтобы было ясно, что этот алгоритм просто вычисляет другой поток той же величины, но более низкой стоимости (в общем случае мы не знаем величину этого потока, поэтому после завершения работы в фиктивном ребре еще остается некоторый поток, который мы игнорируем). Из рисунка понятно, что некоторые расширяющие циклы содержат фиктивное ребро и увеличивают поток в сети, а другие циклы не содержат его и снижают стоимость. В конечном итоге мы получаем максимальный поток, и тогда все расширяющие циклы уменьшают стоимость, не меняя величины потока, как если бы мы начали сразу с максимального потока.

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

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

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

Можно разработать стратегию, которая находит циклы отрицательной стоимости и гарантирует, что количество использованных циклов отрицательной стоимости меньше VE (см. раздел ссылок). Этот результат имеет важное значение, т.к. он утверждает, что задача о потоке минимальной стоимости имеет решение (а заодно и все сводящиеся к ней задачи). Однако на практике часто выбирают реализации, которые допускают (теоретически) высокую границу для худшего случая, но реально используют при решении задач значительно меньше итераций.

Здесь показано вычисление максимального потока минимальной стоимости, начиная с первоначально нулевого потока, с помощью алгоритма вычеркивания циклов, который использует фиктивное ребро из стока в исток в остаточной сети с неограниченной пропускной способностью и неограниченной отрицательной стоимостью. Фиктивное ребро превращает любой расширяющий путь из 0 в 5 в отрицательный цикл (хотя он игнорируется при увеличении потока и вычислении его стоимости). Добавление по этому пути ведет к увеличению потока, как в алгоритмах расширения путей (три верхних ряда). При отсутствии циклов, в которые входит фиктивное ребро, в остаточной сети отсутствуют пути из истока в сток - значит, поток максимален (третий ряд сверху). С этого момента увеличение потока по отрицательному циклу снижает стоимость потока без изменения его величины (внизу).

В этом примере сначала вычисляется максимальный поток, а затем уменьшается его стоимость; но это не обязательно. Например, на втором шаге алгоритм мог бы увеличить поток в отрицательном цикле 1-4-5-3-1, а не в цикле 0-1-4-5-0. Поскольку каждое добавление либо увеличивает поток, либо уменьшает стоимость, алгоритм в любом случае продвигается к максимальному потоку минимальной стоимости.

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

Упражнения

22.105. Добавьте стоимости в класс допустимых потоков из упражнения 22.74. Для решения задачи о допустимых потоках минимальной стоимости воспользуйтесь классом MINCOST.

22.106. Приведите более точную верхнюю границу, чем ECM, для стоимости максимального потока в транспортной сети, не все ребра которой имеют максимальную пропускную способность и максимальную стоимость.

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

22.108. Реализуйте функцию negcyc() для программы 22.9, воспользовавшись алгоритмом Беллмана-Форда (см. упражнение 21.134).

22.109. Замените в программе 22.9 инициализацию вычислением потока на инициализацию потоком в фиктивном ребре.

22.110. Приведите все возможные последовательности расширяющих циклов, которые могли бы быть показаны на рис 22.41.

о 22.111. Приведите все возможные последовательности расширяющих циклов, которые могли бы быть показаны на рис 22.42.

22.112. Покажите в стиле рис 22.41 поток и остаточные сети после каждого расширения при использовании программы 22.9 (реализация алгоритма вычеркивания циклов) для отыскания потока минимальной стоимости в транспортной сети, изображенной на рис 22.10. Ребра 0-2 и 0-3 имеют стоимость 2, ребра 2-5 и 3-5 - стоимость 3, ребро 1-4 - стоимость 4, а все остальные ребра - единичную стоимость. Предполагается, что максимальный поток вычисляется с помощью алгоритма, который использует кратчайшие расширяющие пути.

22.113. Выполните упражнение 22.112 в предположении, что программа начинает работу с максимальным потоком в фиктивном ребре из истока в сток, как показано на рис 22.42.

22.114. Добавьте в решения упражнений 22.6 и 22.7 обработку стоимостей в транспортных сетях.

22.115. Добавьте в решения упражнений 22.9-22.11 обработку стоимостей в сетях. Назначьте каждому ребру стоимость, приблизительно пропорциональную евклидовому расстоянию между его вершинами.

Сетевой симплексный алгоритм

Время выполнения алгоритма вычеркивания циклов зависит не только от количества циклов отрицательной стоимости, которые используются для снижения стоимости потока, но и от времени поиска каждого такого цикла. В этом разделе мы рассмотрим базовый подход, который не только резко снижает трудоемкость выявления отрицательных циклов, но и позволяет использовать приемы уменьшения количества итераций. Эта реализация алгоритма вычеркивания циклов называется сетевым симплексным (network simplex) алгоритмом. Он основан на использовании древовидной структуры данных и на переназначении стоимостей, что позволяет быстро выявлять отрицательные циклы.

По отношению к любому потоку ребро может быть пустым, полным или частично заполненным (ни пустое, ни полное). В этом потоке ребро 1-4 пусто; ребра 0-2, 2-3, 2-4, 3-5 и 4-5 заполнены, а ребра 0-1 и 1-3 частично заполнены. Наши графические соглашения дают два способа обозначения состояний ребер: в столбце потока цифры 0 означают пустые ребра, звездочки означают заполненные ребра, а остальные ребра - это частично заполненные ребра. В остаточной сети (внизу) пустые ребра появляются только в левом столбце, полные - в правом столбце, а частично заполненные ребра могут находиться в обоих столбцах.

Прежде чем перейти к описанию сетевого симплексного алгоритма, мы заметим, что по отношению к любому потоку каждое ребро ):

С этой классификацией мы уже сталкивались при использовании остаточных сетей в данной главе. Если ребро u-v пустое, то u-v входит в остаточную сеть, а v-u не входит; если ребро u-v заполнено, то v-u входит в остаточную сеть, а u-v не входит; а если ребро u-v заполнено частично, то в остаточную сеть входят и u-v, и v-u .

В этом контексте направления ребер в остовном дереве игнорируются. То есть любое множество V- 1 ориентированных ребер, которые соединяют V вершин сети между собой (без учета направлений ребер), составляет остовное дерево, а остовное дерево допустимо, если все ребра, не входящие в дерево, являются полными или пустыми.

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

Добавление в остовное дерево любого недревесного ребра приводит к образованию цикла. Механизм, на котором основан сетевой симплексный алгоритм - это множество весов вершин, которое обеспечивает немедленное выявление тех ребер, которые при включении в остовное дерево создают циклы отрицательной стоимости в остаточной сети. Мы будем называть эти веса вершин потенциалами (potential), а потенциал, связанный с вершиной v, будем обозначать ф(v). В зависимости от контекста мы будем рассматривать потенциал то как функцию, определенную на вершинах, то как множество целочисленных весов (предполагая, что каждой вершине присвоен такой вес), то как вектор, индексированный именами вершин (поскольку в реализациях мы храним их именно в таком виде).

Если имеется максимальный поток (вверху), то с помощью двухэтапного процесса, представленного в данном примере, можно построить максимальный поток с таким остовным деревом, что ни одно из ребер, не включенных в остовное дерево, не является частично заполненным ребром. Сначала мы разрываем циклы из частично заполненных ребер: в данном случае мы разрываем цикл 0-2-4-1-0, проталкивая по нему поток величиной 1. Таким способом всегда можно заполнить или опустошить по крайней мере одно ребро; в данном случае мы опустошаем ребро 1-4 и заполняем ребра 0-2 и 2-4 (в центре). Затем мы включаем пустые и полные ребра в множество частично заполненных ребер, чтобы получить остовное дерево; в данном случае мы добавляем ребра 0-2, 1-4 и 3-5 (внизу).

Если начать с потока по фиктивному ребру из истока в сток, то оно оказывается единственно возможным частично заполненным ребром. Поэтому для построения остовного дерева для потока можно использовать любое остовное дерево из остальных ребер. В данном примере ребра 0-5, 0-1, 0-2, 1-3 и 1-4 составляют остовное дерево для исходного максимального потока. Все не включенные в дерево ребра остаются пустыми.

Иначе говоря, приведенная стоимость каждого ребра есть разность между фактической стоимостью ребра и разностью потенциалов вершин этого ребра. В ситуации распределения товаров потенциал узла имеет физический смысл: если интерпретировать потенциал ф(u) как затраты на приобретение единицы товара в узле u, то полная стоимость c*(u, v) + ф (u) - ф (v) означает затраты на закупку товара в узле u, доставку в v и реализацию товара в v.

Мы будем хранить потенциалы вершин в векторе phi, индексированном именами вершин, и вычислять приведенную стоимость ребра v-w, вычитая из стоимости ребра значение (phi[v] -phi[w]). То есть не нужно где-то хранить приведенную стоимость ребра, поскольку ее очень легко вычислить.

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

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

Потенциалы вершин определяются структурой остовного дерева и первоначальным значением потенциала одной любой вершины. Слева приведено множество ребер, которые образуют остовное дерево, состоящее из десяти вершин от 0 до 9. В представлении этого дерева в центре в качестве корня выбрана вершина 5, вершины, соединенные с 5, находятся на уровень ниже и т.д. Присваивание корню нулевого значения потенциала определяет уникальное назначение потенциалов для других узлов, при котором разность потенциалов вершин каждого ребра равна его стоимости. Справа приведено другое представление того же дерева, в котором в качестве корня выбрана вершина 0. После присвоения вершине 0 нулевого значения потенциала будут получены другие потенциалы, которые отличаются от потенциалов на центральной диаграмме на некоторое постоянное значение. Во всех наших вычислениях используется лишь разность потенциалов. Она остается одной и той же для любой пары потенциалов, независимо от начальной вершины (и независимо от присвоенного ей значения) - поэтому выбор исходной вершины и начального значения не играет роли.

Эквивалентная формулировка утверждает, что если имеются поток и множество потенциалов вершин, такое, что все приведенные стоимости древесных ребер равны нулю, все полные недревесные ребра неотрицательны, а пустые недревесные ребра неположительны, то поток является потоком минимальной стоимости.

При наличии подходящих ребер можно выбрать одно из них и выполнить расширение по циклу, который оно образует с древесными ребрами, чтобы получить поток более низкой стоимости. Аналогично реализации вычеркивания циклов из раздела 22.5, пройдем по циклу, чтобы определить максимальный поток, который можно протолкнуть, а затем еще раз пройдем по циклу, чтобы протолкнуть этот поток, который заполнит или опустошит по меньшей мере одно ребро. Если это подходящее ребро, которое было использовано для построения цикла, оно перестает быть подходящим (его приведенная стоимость не изменяется, но оно превращается из полного в пустое или из пустого в полное). Во всех других случаях оно становится частично заполненным. Присоединение его к дереву и удаление из цикла полного или пустого ребра сохраняет инвариантное условие: никакое недревесное ребро не может быть частично заполненным, а само дерево является допустимым остовным деревом. Как и ранее, мы рассмотрим механику этого вычисления ниже в этом разделе.

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

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

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

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

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

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

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

Программа 22.10 представляет собой реализацию, которая присваивает потенциалы вершинам за время, пропорциональное V. В ее основе лежит следующая идея (см. рис 22.47). Мы начинаем с произвольной вершины и рекурсивно вычисляем потенциалы ее предшественников, поднимаясь по родительским ссылкам до самого корня, которому по соглашению присваивается нулевой потенциал. Затем мы выбираем другую вершину и с помощью родительских сссылок рекурсивно вычисляем потенциалы ее предшественников. Рекурсия заканчивается при достижении предшественника с уже известным потенциалом, а затем мы возвращаемся по тому же пути, вычисляя потенциал каждого узла на основе потенциала родительского узла. Этот процесс продолжается до тех пор, пока не будут вычислены все значения потенциалов. Если мы уже прошли по какому-либо пути, то мы больше не посещаем ни одно из его ребер, следовательно, этот процесс выполняется за время, пропорциональное V.

Мы начнем с вершины 0, проходим по пути в корень, обнуляем pt[5], а затем возвращаемся тем же путем назад. В вершине 6 устанавливаем такое значение, чтобы pt[6] - pt[5] было равно стоимости ребра 6-5, затем устанавливаем значение pt[3], чтобы pt[3] - pt[6] было равно стоимости ребра 3-6 и т.д. (слева). После этого мы начинаем с вершины 1 и проходим по родительским ссылкам, пока не встретим вершину с известным потенциалом (в данном случае это 6), и возвращаемся по этому пути, вычислив потенциалы вершин 9 и 1 (в центре). Потом мы начинаем с вершины 2 - мы можем рассчитать ее потенциал из потенциала ее родителя (справа). Перейдя к вершине 3, мы обнаруживаем, что ее потенциал уже известен, и т.д. В данном примере для каждой вершины после 1 мы либо видим, что ее потенциал уже подсчитан, либо можем его вычислить из потенциала ее родителя. Мы никогда не проходим по одному и тому же ребру дважды, независимо от структуры дерева, поэтому общее время этих вычислений линейно.

Программа 22.10. Вычисление потенциалов вершин

Рекурсивная функция phiR поднимается по родительским ссылкам дерева, пока не встретит допустимый потенциал (потенциал корня всегда считается допустимым), а затем вычисляет потенциалы, спускаясь по пройденному пути. Она помечает каждую вершину, потенциал которой вычисляет, текущим значением функции valid.

  int phiR(int v)
 { if (mark[v] == valid) return phi[v];
   phi[v] = phiR(ST(v)) - st[v]->costRto(v);
   mark[v] = valid;
   return phi[v];
 }
   

Для двух заданных вершин их ближайший общий предок (БОП, least common ancestor - LCA) определяется как корень минимального поддерева, которое содержит обе эти вершины. Цикл, который образуется при добавлении ребра, соединяющего две вершины, состоит из этого ребра и ребер двух путей, ведущих из двух этих узлов к их БОП. Расширяющий цикл, образованный добавлением ребра v-w, проходит через v-w в w, затем вверх по дереву к БОП вершин v и w (скажем, r), затем вниз по дереву в v. Поэтому на этих двух путях необходимо рассматривать ребра различной ориентации.

Как и раньше, мы расширяем поток в цикле, вначале пройдя по путям, чтобы выявить максимальную величину потока, которую можно протолкнуть через их ребра, а затем еще раз пройдя по этим путям, чтобы протолкнуть через них поток. Не обязательно рассматривать ребра в порядке их расположения в цикле, достаточно просто рассмотреть каждое из них (в любом направлении). Поэтому можно просто пройти каждый путь из этих узлов до их БОП. Чтобы расширить поток в цикле, образованном при добавлении ребра v-w, мы проталкиваем поток из v в w, из v по пути к ближайшему общему предку r и из w по пути до г, но против направления ребер. Программа 22.11 реализует эту идею в виде функции, которая расширяет поток в цикле и заодно возвращает ребро, которое становится пустым или полным из-за этого расширения.

В программе 22.11 используется простая технология, позволяющая избежать затрат на инициализацию всех меток, которую нужно выполнять при каждом вызове программы. Мы храним эти метки как глобальные переменные, которые вначале обнулены. При каждом поиске БОП мы увеличиваем на 1 глобальный счетчик и помечаем вершины, сохраняя в соответствующем элементе вектора, индексированного именами вершин, значение этого счетчика. После инициализации этот метод позволяет выполнять вычисления за время, пропорциональное длине цикла. В типичных задачах расширение может выполняться для множества небольших циклов, поэтому экономия времени может быть весьма существенной. Как мы убедимся далее, этот метод экономии времени можно применять и в других частях реализации.

Программа 22.11. Расширение потока по циклу

Чтобы найти ближайшего общего предка двух вершин, мы синхронно поднимаемся из них по дереву, помечая встреченные узлы. БОП - первый обнаруженный помеченный узел (возможно, корень дерева). Для расширения потока используется функция, похожая на функцию из программы 22.3; она сохраняет пути по дереву в векторе st и возвращает ребро, которое стало при расширении пустым или полным (см. текст).

  int lca(int v, int w)
 { mark[v] = ++valid; mark[w] = valid;
   while (v != w)
  { if (v != t) v = ST(v);
    if (v != t  mark[v] == valid) return v;
    mark[v] = valid;
    if (w != t) w = ST(w);
    if (w != t  mark[w] == valid) return w;
    mark[w] = valid;
  }
   return v;
 }
 Edge *augment(Edge *x)
   { int v = x->v(), w = x->w(); int r = lca(v, w);
  int d = x->capRto(w);
  for (int u = w; u ! = r; u = ST(u))
    if (st[u]->capRto(ST(u)) < d)
   d = st[u]->capRto(ST(u));
  for (int u = v; u ! = r; u = ST(u))
    if (st[u]->capRto(u) < d)
   d = st[u]->capRto(u);
  x->addflowRto(w, d); Edge* e = x;
  for (int u = w; u ! = r; u = ST(u))
    { st[u]->addflowRto(ST(u), d);
   if (st[u]->capRto(ST(u)) == 0) e = st[u];
    }
  for (int u = v; u ! = r; u = ST(u))
    { st[u]->addflowRto(u, d);
   if (st[u]->capRto(u) == 0) e = st[u];
    }
  return e;
   }
   

Наша третья задача обработки дерева - замена ребра .

Эти три реализации позволяют выполнять базовые операции, на которых основан сетевой симплексный алгоритм: (1) выбор подходящего ребра с помощью прсмотра приведенных стоимостей и потоков; (2) расширение потока в отрицательном цикле, образованном ребрами дерева и выбранным подходящим ребром, пользуясь представлением родительскими ссылками для остовного дерева; и (3) изменение дерева и пересчет потенциалов. Эти операции показаны на примере транспортной сети на рис 22.49 и рис 22.50.

На рис 22.49 показана инициализация структур данных с помощью фиктивного ребра с максимальным потоком в нем, как и на рис 22.42. На нем показано исходное допустимое остовное дерево, представленное родительскими ссылками, соответствующие потенциалы вершин, приведенные стоимости недревесных ребер и исходное множество подходящих ребер.

Этот пример демонстрирует базовые операции с деревом в сетевом симплексном алгоритме для представления родительскими ссылками. Слева изображено дерево, в котором все ссылки направлены вверх, что показывает вектор родительских ссылок ST. (В нашем коде функция ST вычисляет родителя заданной вершины по указателю на ребро, хранящемуся в векторе st, индексированном именами вершин.) Добавление ребра 1-2 образует цикл, в который входят пути из вершин 1 и 2 к их БОП - вершине 11. После удаления одного из этих ребер, скажем, 0-3, структура остается древовидной. Чтобы отразить это изменение в массиве родительских ссылок, мы меняем направления всех ссылок от 2 до 3 (в центре). Дерево справа - то же самое дерево, в котором позиции узлов изменены так, чтобы все ссылки были направлены вверх в соответствии со значениями массива родительских ссылок, представляющего рассматриваемое дерево (справа внизу).

Чтобы выполнить инициализацию структур данных для сетевого симплексного алгоритма, мы начинаем с нулевого потока во всех ребрах (слева), затем добавляем фиктивное ребро 0-5 из истока в сток, величина потока в котором не меньше величины максимального потока (здесь для ясности мы используем значение, равное величине максимального потока). Стоимость 9 фиктивного ребра больше стоимости любого цикла сети; в этой реализации используется значение CV. Фиктивное ребро в транспортной сети не показано, однако включено в остаточную сеть (в центре). Остовное дерево формируется из стока в качестве корня, истока в качестве его единственного потомка, и дерева поиска на графе, индуцированном остальными узлами остаточной сети. Эта реализация использует представление дерева родительскими ссылками в массиве st и функцию ST. На наших рисунках изображена эта реализация и две других: реализация с корнем, показанная справа, и множество заштрихованных ребер в остаточной сети.

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

В столбце " привед. стоим. " (в центре) показаны приведенные стоимости недревесных ребер, которые вычислены для каждого ребра сложением разности потенциалов вершин и его стоимости. Приведенные цены древесных ребер равны нулю и в столбце не указаны. Пустые ребра с отрицательными приведенными стоимостями и полные ребра с положительными приведенными стоимостями (подходящие ребра) отмечены звездочками.

Программа 22.12. Замена остовного дерева

Функция update добавляет ребро в остовное дерево и удаляет из образовавшегося при этом цикла некоторое ребро. Удаляемое ребро находится на пути из одной из вершин добавленного ребра к их БОП. Эта реализация использует функцию onpath для поиска удаляемого ребра и функцию reverse для изменения направления ребра на пути между данным и добавляемым ребром.

 bool onpath(int a, int b, int c)
   { for (int i = a; i ! = c; i = ST(i))
    if (i == b) return true;
  return false;
   }
 void reverse(int u, int x)
   { Edge *e = st[u];
  for (int i = ST(u); i != x; i = ST(i))
    { Edge *y = st[i]; st[i] = e; e = y; }
   }
 void update(Edge *w, Edge *y)
   { int u = y->w(), v = y->v(), x = w->w ();
  if (st[x] != w) x = w->v();
  int r = lca(u, v);
  if (onpath(u, x, r))
    { reverse(u, x); st[u] = y; return; }
  if (onpath(v, x, r))
    { reverse(v, x); st[v] = y; return; }
   }
   

Вместо вычисления величины максимального потока в реализации используется величина оттока из истока, которая гарантированно не меньше величины максимального потока; в данном случае используется величина максимального потока, чтобы было легче проследить работу алгоритма.

Каждый ряд этого рисунка соответствует одной итерации сетевого симплексного алгоритма после инициализации, представленной на рис 22.49. На каждой итерации алгоритм выбирает подходящее ребро, расширяет поток по циклу и изменяет структуры данных следующим образом. Сначала выполняется расширение потока, включая соответствующие изменения в остаточной сети. После этого в древовидную структуру ST добавляется подходящее ребро, и из цикла, которое оно образует с ребрами дерева, удаляется ребро. Потом изменения в структуре дерева отображаются в таблице потенциалов phi. Затем изменяются приведенные стоимости недревесных ребер (столбец " привед. стоим. " в центре), чтобы отобразить изменения значений потенциалов, и эти значения используются для выявления пустых ребер с отрицательной приведенной стоимостью и полных ребер с положительной приведенной стоимостью как подходящих ребер (помечены звездочками около приведенных стоимостей). Реализации не обязательно должны выполнять именно такие вычисления (они просто должны вычислить изменения потенциалов и приведенных стоимостей, чего достаточно для выявления подходящих ребер), однако мы приводим здесь все числа, чтобы дать полное представление об алгоритме.

Последнее расширение в этом примере вырождено. Оно не увеличивает поток, но и не выявляет подходящих ребер - это гарантирует, что данный поток является максимальным потоком минимальной стоимости.

На рис 22.50 показаны изменения в структурах данных для каждой последовательности подходящих ребер и расширения потока по циклам отрицательной стоимости. Эта последовательность не отражает какой-либо конкретный метод выбора подходящих ребер; в ней представлены решения, которые делают расширяющие пути такими, как на рис 22.42. На этих рисунках изображены все потенциалы вершин и все приведенные стоимости после каждого цикла расширения, даже если многие из этих значений определены неявно и не обязательно должны вычисляться типовыми реализациями. Эти рисунки демонстрируют общее продвижение алгоритма и состояние структур данных при переходах алгоритма от одного допустимого остовного дерева к другому, когда в дерево добавляется подходящее ребро и из образовавшегося цикла удаляется одно из ребер.

Один из критических фактов, представленных на рис 22.50, заключается в том, что алгоритм может просто не завершить работу, т.к. пустые или полные ребра остовного дерева могут помешать протолкнуть поток по найденному отрицательному циклу. То есть можно найти походящее ребро и отрицательный цикл, который оно образует с ребрами остовного дерева, но максимальная величина потока, которую можно протолкнуть через этот цикл, может оказаться равной 0. В этом случае мы заменим подходящим ребром одно из ребер цикла, однако снизить стоимость потока не удастся. Чтобы алгоритм завершал свою работу, необходимо сделать так, чтобы алгоритм не начал выполнять бесконечную последовательность расширений потока на нулевую величину.

Если расширяющий цикл содержит более одного полного или пустого ребра, то подстановка алгоритма из программы 22.12 всегда удаляет из дерева то ребро, которое расположено ближе других к БОП двух вершин подходящего ребра. К счастью, доказано, что такая стратегия выбора ребра для удаления из цикла обеспечивает завершение работы алгоритма (см. раздел ссылок).

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

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

Программа 22.14 представляет собой полную реализацию сетевого симплексного алгоритма, которая использует стратегию выбора подходящего ребра, дающего отрицательный цикл с максимальным абсолютным значением стоимости. Эта реализация использует функции работы с деревьями и поиск подходящих ребер из программ 22.10-22.13, но здесь применимо замечание к нашей первой реализации вычеркивания циклов (программа 22.9): удивительно, что такой небольшой кодовый фрагмент позволяет получать полезные решения в контексте общей модели решения задач о потоках минимальной стоимости.

Программа 22.13. Поиск подходящих ребер

Данная функция находит подходящее ребро минимальной приведенной стоимости. Эта примитивная реализация выполняет обход всех ребер в сети.

 int costR(Edge *e, int v)
   { int R = e->cost() + phi[e->w()] - phi[e->v()];
  return e->from(v) ? R : -R;
   }
 Edge *besteligible()
   { Edge *x = 0; 
  for (int v = 0, min = C*G.V(); v < G.V(); v++)
    { typename Graph::adjIterator A(G, v);
   for (Edge* e = A.beg(); !A.end(); e = A.nxt())
     if (e->capRto(e->other(v)) > 0)
    if (e->capRto(v) == 0) if (costR(e, v) < min)
      { x = e; min = costR(e, v) ; }
    }
  return x;
   }
   

Граница производительности в худшем случае для программы 22.14 по меньшей мере в V раз меньше, чем граница для реализации с вычеркиванием циклов из программы 22.9, т.к. время, необходимое на одну итерацию, равно просто E (чтобы найти подходящее ребро), а не VE (чтобы найти отрицательный цикл). Можно подумать, что применение максимального расширения приведет к меньшему количеству расширений, чем выбор первого попавшегося отрицательного цикла, который находит алгоритм Беллмана-Форда, однако этот способ ничего не улучшает. Конкретные границы количества расширяющих циклов трудно вычислить, и обычно эти границы намного выше, чем величины, которые наблюдаются на практике. Как уже было сказано, имеются теоретические результаты, показывающие, что некоторые стратегии гарантируют, что количество расширяющих циклов ограничено полиномом от количества ребер, хотя в практических реализациях обычно используются варианты с экспоненциальным худшим случаем.

В свете всех этих соображений существует множество возможностей для повышения производительности рассматриваемых алгоритмов. Например, еще одна реализация сетевого симплексного алгоритма приведена в программе 22.15. Примитивная реализация в программе 22.14 всегда требует времени, пропорционального V, на обновление потенциалов дерева, и всегда тратит время, пропорциональное E, на поиск подходящего ребра с максимальной приведенной стоимостью. Реализация в программе 22.15 ликвидирует эти затраты в типичных сетях.

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

Программа 22.14. Сетевой симплексный алгоритм (базовая реализация)

Данный класс использует сетевой симплексный алгоритм для решения задачи о потоке минимальной стоимости. Он использует стандартную функцию поиска в глубину dfsR на исходном дереве (см. упражнение 22.117), затем входит в цикл, в котором использует функции из программ 22.10-22.13 для вычисления потенциалов всех вершин, просмотра всех ребер и отыскания такого, которое образует отрицательный цикл минимальной стоимости, и расширения потока по этому циклу.

  template <class Graph, class Edge>
  class MINCOST
 { const Graph G; int s, t; int valid;
   vector<Edge *> st; vector<int> mark, phi;
   void dfsR(Edge);
   int ST(int);
   int phiR(int);
   int lca(int, int); Edge *augment(Edge *);
   bool onpath(int, int, int);
   void reverse(int, int);
   void update(Edge *, Edge *);
   int costR(Edge *, int); Edge *besteligible();
 public:
   MINCOST(Graph G, int s, int t) : G(G), s(s), t(t)
  st(G.V()), mark(G.V(), -1), phi(G.V())
  { Edge *z = new EDGE(s, t, M*G.V(), C*G.V());
    G.insert(z);
    z->addflowto(t, z->cap());
    dfsR(z);
    for (valid = 1; ; valid++ )
   { phi[t] = z->costRto(s); mark[t] = valid;
     for (int v = 0; v < G.V(); v++)
    if (v != t) phi[v] = phiR(v);
     Edge *x = besteligible();
     if (costR(x, x->v()) == 0) break;
     update(augment(x), x);
   }
    G.remove(z); delete z;
 }
   

Программа 22.15. Сетевой симплексный алгоритм (улучшенная реализация)

Замена ссылок на phi обращениями к phiR в функции R и замена цикла for в конструкторе программы 22.14 данным кодом дает реализацию сетевого симплексного алгоритма, которая экономит время на каждой итерации, вычисляя потенциалы только когда это необходимо, и выбирая первое обнаруженное подходящее ребро.

  int old = 0;
  for (valid = 1; valid != old; )
 { old = valid;
   for (int v = 0; v < G.V(); v++)
  { typename Graph::adjIterator A(G, v);
    for (Edge* e = A.beg(); !A.end(); e = A.nxt())
   if (e->capRto(e->other(v)) > 0)
     if (e->capRto(v) == 0)
    { update(augment(e), e); valid++; }
  }
 }
   

В худшем случае при поиске подходящего ребра придется проверить все ребра или их большую часть, но обычно нужно проверить сравнительно небольшое количество ребер, чтобы отыскать подходящее. Один из подходов - каждый раз начинать все с начала; другой подход - случайный выбор исходной точки (см. упражнение 22.126). Такое использование случайности делает маловероятным появление неестественно длинных последовательностей расширяющих путей.

Во-вторых, для вычисления потенциалов мы принимаем " отложенный " подход. Вместо того чтобы вычислять все потенциалы в векторе phi, индексированном именами вершин, а потом выбирать их по мере необходимости, мы вызываем функцию phiR, чтобы получить каждое значение потенциала; она поднимается по дереву до обнаружения допустимого потенциала, а затем вычисляет все необходимые потенциалы на этом пути. Чтобы реализовать такой подход, мы просто заменяем обращение к массиву phi[u] на вызов функции phiR(u). В худшем случае мы вычисляем все потенциалы так же, как и раньше, однако при просмотре лишь нескольких подходящих ребер мы вычисляем только те потенциалы, которые необходимы для выявления этих ребер.

Такие изменения никак не влияют на производительность алгоритма в худшем случае, но они, несомненно, ускоряют его работу в реальных ситуациях. Несколько других соображений по повышению производительности сетевого симплексного алгоритма анализируются в упражнениях (см. упражнения 22.i26-22.i30), и это лишь незначительная часть того, что было предложено.

Как мы неоднократно подчеркивали в этой книге, задача анализа и сравнения алгоритмов на графах сложна сама по себе. С появлением сетевого симплексного алгоритма эта задача еще больше усложнилась из-за различных подходов к реализации и большого разнообразия приложений, с которыми нам приходится сталкиваться (см. раздел 22.5). Какая из реализаций лучше? Стоит ли сравнивать реализации по известным границам для худших случаев? Насколько точно можно выразить различие в производительности различных реализаций для конкретных приложений? Следует ли использовать различные реализации, приспособленные для конкретных случаев?

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

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

Упражнения

22.116. Приведите максимальный поток с соответствующим допустимым остовным деревом для транспортной сети с рис 22.10.

22.117. Реализуйте функцию dfsR для программы 22.14.

22.118. Реализуйте функцию, которая удаляет циклы из частично заполненных ребер из потока заданной сети и строит допустимое остовное дерево для полученного потока, как показано на рис 22.44. Оформите созданную функцию так, чтобы ее можно было использовать для построения исходного дерева в программе 22.14 или в программе 22.15.

22.119. Покажите, как изменятся таблицы потенциалов на рис 22.46 при изменении ориентации ребра, соединяющего вершины 6 и 5.

22.120. Постройте транспортную сеть и приведите такую последовательность расширяющих ребер, что обобщенный сетевой симплексный алгоритм не остановится.

22.121. Покажите в стиле рис 22.47 процесс вычисления потенциалов для дерева с корнем в вершине 0 с рис 22.46.

22.122. Покажите в стиле рис 22.50 процесс вычисления максимального потока минимальной стоимости в транспортной сети с рис 22.10, начав с базового максимального потока и связанного с ним базового остовного дерева, которые найдены в упражнении 22.116.

22.123. Пусть все недревесные ребра пусты. Напишите функцию, которая вычисляет потоки в древесных ребрах и помещает поток в ребро, соединяющее вершину v с ее родителем в дереве, в v-й элемент вектора flow.

22.124. Выполните упражнение 22.123 для случая, когда некоторые недревесные ребра могут быть полными.

22.125. Воспользуйтесь программой 22.12 в качестве основы для алгоритма построения MST-дерева. Эмпирически сравните полученную реализацию с тремя базовыми алгоритмами вычисления MST из главы 20 (см. упражнение 20.66).

22.126. Опишите, что нужно изменить в программе 22.15, чтобы она каждый раз начинала поиск подходящего ребра со случайно выбранного ребра, а не с самого начала.

22.127. Измените решение упражнения 22.126, чтобы каждый поиск подходящего ребра программа начинала с того места, где был завершен предыдущий поиск.

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

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

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

22.131. Эмпирически определите количество итераций, количество вычислений потенциалов вершин и отношение времени выполнения к E для нескольких версий сетевого симплексного алгоритма и для различных видов сетей (см. упражнения 22.7-22.12). Рассмотрите различные алгоритмы, описанные в тексте и в предыдущих упражнениях, уделяя особое внимание тем, которые лучше работают на больших разреженных сетях.

22.132. Напишите клиентскую программу для графической анимации динамики сетевых симплексных алгоритмов. Эта программа должна создавать изображения, подобные рис 22.50 и другим рисункам из этого раздела (рис 22.48). Протестируйте полученную реализацию на евклидовых сетях из упражнений 22.7-22.12.

Сведения к задаче о потоке минимальной стоимости

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

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

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

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

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

Таким образом, все задачи, рассмотренные в , которые сводятся к задаче кратчайших путей из одного истока, также сводятся к задаче о потоке минимальной стоимости. Это множество задач, в частности, включает задачу календарного планирования работ с конечными сроками и с разностными ограничениями.

Как мы убедились при изучении задач о максимальном потоке, имеет смысл проанализировать детали работы сетевого симплексного алгоритма при решении задачи поиска кратчайших путей с помощью сведения, описанного в лемме 22.29. В этом случае алгоритм использует остовное дерево с корнем в истоке - примерно как алгоритмы на основе поиска, которые были рассмотрены в главе 21 - но потенциалы и приведенные стоимости увеличивают гибкость при разработке методов выбора следующего ребра для включения в дерево.

Обычно мы не используем тот факт, что задача о потоке минимальной стоимости является естественным обобщением и задачи о максимальном потоке, и задачи поиска кратчайших путей, т.к. для обеих этих задач существуют специальные алгоритмы, гарантирующие более высокую производительность. Однако если таких реализаций нет, то качественная реализация сетевого симплексного алгоритма вполне может обеспечить быстрое решение конкретных экземпляров обеих задач. Разумеется, при использовании или построении систем обработки сетей, в которых применяются такие сведения, следует избегать циклов сведения. Например, реализация алгоритма вычеркивания циклов в программе 22.9 использует для решения задачи о потоке минимальной стоимости как алгоритмы вычисления максимального потока, так и алгоритмы поиска кратчайших путей (см. упражнение 21.96).

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

Это сведение показывает, что можно рассматривать только положительные стоимости, хотя на практике мы обычно так не делаем, т.к. наши реализации из разделов 22.5 и 22.6 имеют дело исключительно с остаточными сетями и без проблем обрабатывают отрицательные стоимости. Иногда важно иметь какую-то нижнюю границу стоимостей, но эта граница не должна быть нулевой (см. упражнение 22.145).

Далее мы покажем, что, как и в случае задачи о максимальном потоке, при желании можно ограничиться рассмотрением ациклических сетей. Более того, можно также считать, что ребра не имеют пропускных способностей (не существует верхней границы для величины потока в таких ребрах). Сочетание этих двух вариантов приводит к следующей классической формулировке задачи о потоке минимальной стоимости.

Транспортная задача. Нужно решить задачу о потоке минимальной стоимости для двудольной распределительной сети, все ребра которой направлены из вершины с предложением в вершину со спросом и имеют неограниченную пропускную способность. Как было сказано в начале данной главы (см. рис 22.2), обычно эта задача моделирует распределение товаров из складов (вершины с предложением) в торговые точки (вершины со спросом) по каналам распределения (ребра) с конкретной стоимостью доставки единицы товара.

Поскольку мы не рассматривали прямые алгоритмы решения транспортной задачи, это сведение представляет собой лишь академический интерес. Чтобы воспользоваться им, необходимо преобразовать полученную задачу к (другой) задаче вычисления потока минимальной стоимости, воспользовавшись простым сведением, упомянутым в начале доказательства леммы 22.31. Возможно, на практике такие сети допускают более эффективные решения, а возможно, и нет. Цель изучения эквивалентности транспортной задачи и задачи о потоке минимальной стоимости в том, чтобы уяснить, что отказ от пропускных способностей и ограничение двудольными сетями не может существенно упростить задачу вычисления потока минимальной стоимости, как это может показаться.

В этом контексте нам придется рассмотреть другую классическую задачу. Она обобщает задачу о двудольном сопоставлении, которая подробно рассмотрена в разделе 22.4, и так же обманчиво проста.

Задача о назначениях. Для заданного взвешенного двудольного графа нужно найти множество ребер минимальной общей стоимости, чтобы каждая вершина была соединена в точности с одной другой вершиной.

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

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

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

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

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

Решение этой задачи описывает наилучший маршрут почтальона (который должен пройти все улицы на своем пути). Решение этой задачи может также описывать маршрут снегоочистителя во время метели; существует и множество других аналогичных применений.

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

Тщательный анализ задачи о почтальоне еще раз демонстрирует тонкую грань между тривиальными и трудноразрешимыми задачами в области алгоритмов на графах. Предположим, что мы рассматриваем двунаправленный вариант этой задачи, когда сеть неориентированная, а почтальон должен пройти по каждому ребру в обоих направлениях. Тогда, как было сказано в разделе 18.5 , поиск в глубину (или любой другой поиск на графе) даст нам немедленное решение. Но если достаточно одного прохода по ребру в каком-либо направлении, то решение задачи оказывается намного сложнее, чем просто сведение к задаче о потоке минимальной стоимости, с которым мы только что ознакомились, хотя задача все еще разрешима. Если некоторые ребра ориентированы, а другие нет, задача становится NP-трудной (см. раздел ссылок).

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

Так же, как при изучении максимального потока, мы можем выяснить, как представить любую задачу о минимальном потоке в виде LP-задачи (см. рис 22.53). Ее формулировка является простым расширением формулировки задачи о максимальном потоке: мы добавляем уравнения, в которых фиктивной переменной приравнивается стоимость потока, затем стараемся минимизировать эту переменную. LP-модели позволяют добавить произвольные (линейные) ограничения. Некоторые из этих ограничений могут привести к задачам, все равно эквивалентным задачам о потоках минимальной стоимости, другие - нет. То есть многие задачи не сводятся к задачам о потоках минимальной стоимости: например, линейное программирование охватывает гораздо более широкое множество задач. Задача о потоке минимальной стоимости представляет собой следующий шаг к той обобщенной модели решения задачи, которая будет рассматриваться в части VIII.

Эта линейная программа эквивалентна задаче о максимальном потоке минимальной стоимости для сети с0 рис 22.40. Равенства для вершин и неравенства для ребер те же, что и на рис.22.39, но цель здесь другая. Переменная c представляет собой общую стоимость, которая является линейной комбинацией других переменных. В данном случае с = -9x50 + x01 + x02 + x13 + x14 + 4x23 + 2x24 + 2x35 + x45 .

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

Упражнения

22.133. Покажите, что когда сетевой симплексный алгоритм вычисляет максимальный поток, остовное дерево представляет собой объединение ребра t-s, дерева, содержащего вершину s, и дерева, содержащего вершину t.

22.134. Разработайте реализацию, вычисляющую максимальный поток на основе упражнения 22.133. Выбирайте подходящее ребро случайным образом.

22.135. Покажите в стиле рис 22.50 процесс вычисления максимального потока в транспортной сети, изображенной на рис 22.10, используя описанное в тексте сведение и реализацию сетевого симплексного алгоритма из программы 22.14.

22.136. Покажите в стиле рис 22.50 процесс построения кратчайших путей из вершины 0 в транспортной сети, изображенной на рис 22.10, используя описанное в тексте сведение и реализацию сетевого симплексного алгоритма из программы 22.14.

22.137. Докажите, что все ребра остовного дерева, описанного в доказательстве леммы 22.29, принадлежат путям, ведущим из истока к листьям.

22.138. Докажите, что остовное дерево, описанное в доказательстве леммы 22.29, соответствует дереву кратчайших путей в исходной сети.

22.139. Предположим, что вы используете сетевой симплексный алгоритм для решения задачи, полученной в результате сведения задачи о кратчайших путях из одного истока, как описано в доказательстве леммы 22.29. (1). Докажите, что этот алгоритм никогда не использует расширяющий путь нулевой стоимости. (2) Покажите, что удаляемое из цикла ребро всегда является родителем конечной вершины ребра, добавленного в цикл. (3) Из упражнения 22.138 следует, что сетевой симплексный алгоритм не обязан использовать потоки в ребрах. Представьте полную реализацию, в которой используется этот факт. Выбирайте новое древесное ребро случайным образом.

22.140. Пусть каждое ребро сети имеет положительную стоимость. Докажите, что задача построения дерева кратчайших путей из одного истока минимальной стоимости сводится к задаче о максимальном потоке минимальной стоимости.

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

22.142. Реализуйте класс, который находит максимальные потоки минимальной стоимости в распределительных сетях с отрицательными стоимостями. Воспользуйтесь полученным классом для решения упражнения 22.105 (где все стоимости неотрицательны).

22.143. Пусть стоимости ребер равны -1, а не 1. Покажите, как найти максимальный поток минимальной стоимости путем преобразования заданной сети в сеть с положительными стоимостями с последующим вычислением максимального потока минимальной стоимости в новой сети.

22.144. Реализуйте класс, который находит максимальные потоки минимальной стоимости в сетях с отрицательной стоимостью. Воспользуйтесь классом MINCOST (в котором считается, что все стоимости неотрицательны).

22.145. Зависят ли реализации из разделов 22.5 и 22.6 существенным образом от того, что цены неотрицательны? Если зависят, то объясните, как. Если не зависят, покажите, какие нужны (если нужны) изменения, чтобы они работали для сетей с отрицательными стоимостями, либо объясните, почему такие изменения невозможны.

22.146. Добавьте в АТД допустимого потока из упражнения 22.74 возможность указания нижних границ пропускных способностей ребер. Реализуйте класс, который вычисляет максимальный поток минимальной стоимости с учетом этих границ (если он возможен).

22.147. Приведите результат использования сведения транспортной сети, описанной в упражнении 22.112, к транспортной задаче.

22.148. Покажите, что задача о максимальном потоке минимальной стоимости сводится к транспортной задаче со всего лишь V дополнительными вершинами и ребрами, если выполнить построение, аналогичному тому, что приведено в доказательстве леммы 22.16.

22.149. Реализуйте класс для решения транспортной задачи, основанный на простом сведении задачи о потоке минимальной стоимости, описанном в доказательстве леммы 22.30.

22.150. Разработайте реализацию класса для решения задачи вычисления потока минимальной стоимости на основе сведения к транспортной задаче, описанного в доказательстве леммы 22.31.

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

22.152. Напишите программу, генерирующую случайные экземпляры транспортной задачи, и используйте их для эмпирических тестов различных алгоритмов и реализаций, решающих эту задачу.

22.153. Найдите в интернете пример крупной транспортной задачи.

22.154. Эмпирически сравните два различных метода сведения произвольных задач о потоках минимальной стоимости к транспортной задаче, которые приведены в доказательстве леммы 22.31.

22.155. Напишите программу, генерирующую случайные экземпляры задачи о назначениях, и используйте их для эмпирических тестов различных алгоритмов и реализаций, решающих эту задачу.

22.156. Найдите в интернете пример крупной задачи о назначениях.

22.157. Задача о трудоустройстве, описанная в тексте, дает большее преимущество работодателям (максимизируется их общий вес). Сформулируйте версию этой задачи, где претенденты на рабочие места также могут высказывать свои пожелания. Объясните, как решить такую задачу.

22.158. Эмпирически сравните производительность двух реализаций сетевого симплексного алгоритма из раздела 22.6 при решении случайных вариантов задачи о назначениях (см. упражнение 22.155) с Vвершинами и E ребрами и разумным выбором значений V и E.

22.159. Понятно, что задача о почтальоне не имеет решения для сетей, которые не являются сильно связными (почтальон может посетить только вершины, содержащиеся в том сильном компоненте, где он начинает свой обход), однако это не оговаривается в сведении, которое описано в лемме 22.33. Что произойдет, если применить сведение к сети, которая не является сильно связной?

22.160. Эмпирические определите среднюю длину пути почтальона для различных взвешенных графов (см. упражнения 21.4-21.8).

22.161. Приведите прямое доказательство того, что задача о кратчайшем пути из одного истока сводится к задаче о назначениях.

22.162. Приведите формулировку произвольной задачи о назначениях в виде LP-задачи.

22.163. Выполните упражнение 22.18 для случая, когда стоимость каждого ребра равна - 1 (чтобы свести к минимуму пустое место в грузовых машинах).

22.164. Найдите такую модель стоимостей для упражнения 22.18, чтобы ее решением был максимальный поток, требующий минимальное количество дней.

Перспективы

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

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

Задача о максимальном сопоставлении (maximum matching). В графах со взвешенными ребрами нужно найти подмножество ребер, в котором ни одна из вершин не появляется больше одного раза, и никакое другое множество ребер не имеет большего суммарного веса. Задачу о сопоставлении максимальной мощности (maximum cardinality matching) в невзвешенных графах можно непосредственно свести к этой задаче, присвоив всем ребрам единичные веса.

Задача о назначениях и задачи о двудольном сопоставлении максимальной мощности сводятся к задаче максимального сопоставления для графов общего вида. С другой стороны, максимальное сопоставление не сводится к потокам минимальной стоимости, поэтому и рассмотренные выше алгоритмы не применимы к нему. Эта задача разрешима, хотя трудоемкость ее решения в случае крупных графов весьма велика. Описание многочисленных методов, предложенных для решения задачи сопоставления на графах общего вида, заняло бы целый том: эта задача относится к числу наиболее интенсивно изучаемых в теории графов. В этой книге мы закончили изложение потоками минимальной стоимости, но мы еще вернемся к задаче о максимальном сопоставлении в части VIII.

Задача о многопродуктовом потоке (multicommodity flow). Предположим, что нам нужно вычислить второй поток, такой, что сумма обоих потоков в ребре ограничена пропускной способностью ребра, оба потока сбалансированы, а их суммарная стоимость минимальна. Такое изменение моделирует наличие двух различных типов материалов в задаче о распределении товаров. Например, следует ли загрузить больше гамбургеров или картошки в грузовик, который едет в ресторан быстрого питания? Это изменение существенно усложняет задачу и требует для ее решения более сложных алгоритмов, чем рассмотренные в этой книге. К примеру, для такого общего случая не известен какой-либо аналог теоремы о максимальном потоке минимальной стоимости. Формулировка этой задачи в виде LP-задачи - простое расширение примера с рис 22.53, следовательно, эта задача разрешима (т.к. разрешима LP-задача).

Выпуклые и нелинейные стоимости. Рассмотренные нами простые функции стоимости представляют собой линейные комбинации переменных, а наши алгоритмы для их решения существенно зависят от простой математической структуры этих функций. Однако во многих приложениях возникают более сложные функции. Например, если нужно минимизировать расстояние, появляются суммы квадратов стоимостей. Такие задачи невозможно сформулировать в виде LP-задач, поэтому они требуют специальных, еще более мощных, моделей решения задач. Многие из этих задач являются неразрешимыми.

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

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

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

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

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

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

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

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

Но какой бы подход мы ни выбрали, цель остается прежней: нам нужен широкий спектр моделей для решения задач, эффективные алгоритмы решения задач в рамках этих моделей, а также эффективные реализации этих алгоритмов, позволяющие решать практические задачи. Разработка все более универсальных моделей решения задач (таких как задачи вычисления кратчайших путей, максимальных потоков и потоков минимальной стоимости) и все более мощных алгоритмов общего характера (таких как алгоритм Беллмана-Форда для задачи вычисления кратчайших путей, алгоритм расширения путей для задачи о максимальном потоке и сетевой симплексный алгоритм для задачи о максимальном потоке минимальной стоимости) позволили нам существенно продвинуться в направлении этой цели. Значительная часть этой работы была выполнена в пятидесятые и шестидесятые годы. А позже появились фундаментальные структуры данных (части I-IV) и алгоритмы, обеспечивающие эффективные реализации этих общих методов (данная книга), ставшие мощной силой, которая привела нас к возможности решать такой широкий класс крупных задач.

Ссылки для части V

Перечисленные ниже учебники по алгоритмам охватывают большую часть алгоритмов обработки графов из глав 17-21. Эти книги - основные справочники, в которых всесторонне описаны фундаментальные и дополнительные алгоритмы обработки гра-форв с обширными ссылками на современную литературу. В книге Ивена (Even) и монографии Тарьяна (Tarjan) всесторонне освещены многие рассмотренные нами темы. Стоит прочитать и первоначальную статью Тарьяна о применении поиска в глубину для решении задачи сильной связности и других задач. Реализация топологической сортировки с очередью истоков из взята из книги Кнута. Ниже приведен список литературы по некоторым другим рассмотренным нами алгоритмам.

Алгоритмы для вычисления минимальных остовных деревьев в насыщенных графах из имеют солидный возраст, но все-таки интересно прочитать исходные статьи Дейкстры (Dijkstra), Прима (Prim) и Крускала (Kruskal). Обзор Грэма и Хелла (Graham and Hell) содержит исчерпывающую и увлекательную историю предмета. Статья Шазель (Chazelle) - шедевр в области линейных алгоритмов построения MST-дерева.

Книга Агуджи, Магнанти и Орлина (Ahuja, Magnanti and Orlin) - исчерпывающий текст по алгоритмам вычисления сетевых потоков (и алгоритмов поиска кратчайших путей). В этой книге имеется более подробная информация практически по каждой теме из глав 21 и 22. Еще один источник дополнительного материала - классическая книга Пападимитриу и Штайглица (Papadimitriou and Steiglitz). Хотя большая часть книги посвящена более сложным темам, в ней тщательно описаны и многие рассмотренные нами алгоритмы. Обе книги содержат обширную и подробную информацию об исходном материале из исследовательской литературы. Классическая работа Форда и Фалкерсона (Ford and Fulkerson) до сих пор достойна чтения, т.к. содержит введение во многие фундаментальные понятия.

Мы кратко упомянули множество дополнительных тем из (пока не выпущенной) части VIII - например, сводимость, разрешимость и линейное программирование. Данный список ссылок в основном содержит подробное изложение материала повышенной сложности. Многие из них упоминаются в текстах алгоритмов, а в книге Пападимитриу и Штайглица приведено исчерпывающее введение. По этим темам имеется и множество других книг и обширная исследовательская литература.

1. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.

2. Chazelle, "A minimum spanning tree algorithm with inverse-Ackermann type complexity," Journal of the ACM, 47 (2000).

3. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн, Алгоритмы: построение и анализ, 2-е издание, ИД "Вильямс", 2009 г.

4. E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik, 1 (1959).

5. P. Erdos and A. Renyi, "On the evolution of random graphs," Magyar Tud. Akad. Mat. Kutato Int Kozl, 5 (1960).

6. S. Even, Craph Algorithms, Computer Science Press, 1979.

7. L. R. Ford and D. R. Fulkerson, Flows in Networks, Princeton University Press, 1962.

8. H. N. Gabow, "Path-based depth-first search for strong and bicon-nected components," Information Processing Letters, 74 (2000).

9. R. L. Graham and P. Hell, "On the history of the minimum spanning tree problem," Annals of the History of Computing, 7 (1985).

10. D. B. Johnson, "Efficient shortest path algorithms," Journal of the ACM, 24(1977).

11. Д.Э. Кнут, Искусство программирования, том 1: Основные алгоритмы, 3-е издание, ИД "Вильямс", 2008 г.; Д.Э. Кнут, Искусство программирования, том 2: Получисленные алгоритмы, 3-е издание, ИД "Вильямс", 2008 г.; Д.Э. Кнут, Искусство программирования, том 3. Сортировка и поиск, 2-е издание, ИД "Вильямс", 2008 г.

12. J. R. Kruskal Jr., "On the shortest spanning subtree of a graph and the traveling salesman problem," Proceedings AMS, 7, 1 (1956).

13. K. Mehlhorn, Data Structures and Algorithms 2: NP-Completeness and Graph Algorithms, Springer-Verlag, 1984.

14. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and CompleXity, Prentice-Hall, 1982.

15. R. C. Prim, "Shortest connection networks and some generalizations," Bell System Technical Journal, 36 (1957).

16. R. E. Tarjan, "Depth-first search and linear graph algorithms," SIAM Journal on Computing, 1, 2 (1972).

17. R. E. Tarjan, Data Structures and Network Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983.