Часть 5. Алгоритмы на графах. Эти три реализации поддерживают базовые операции, которые служат основой сете­вого симплексного алгоритма: можно выбирать подходящее ребро

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

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

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

bool onpath(int a, int b, int с) { 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 показана инициализация структур данных, использующих фиктивное ребро с максимальным потоком в нем, как и на рис. 22, 42. На нем показано исходное допустимое остовное дерево, представленное в виде родительских связей, соответствую­щие потенциалы вершин, приведенные стоимости недревесных ребер и исходное множе­ство подходящих ребер. Наряду с этим, вместо того чтобы вычислять величину максималь­ного потока в реализации, мы используем величину истечения истока, которая гарантированно не меньше величины максимального потока; мы используем здесь вели­чину с тем, чтобы легче проследить работу алгоритма.

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

Глава 22, Потоки в сетях

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

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

РИСУНОК 22.49. ИНИЦИАЛИЗАЦИЯ В СЕТЕВОМ СИМПЛЕКСНОМ АЛГОРИТМЕ

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

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

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

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

Часть 5. Алгоритмы на графах

РИСУНОК 22.50. ОСТАТОЧНАЯ СЕТЬ И ОСТОВНЫЕ ДЕРЕВЬЯ (СЕТЕВОЙ СИМПЛЕКСНЫЙ АГЛОРИТМ)

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

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