![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. Эти три реализации поддерживают базовые операции, которые служат основой сетевого симплексного алгоритма: можно выбирать подходящее ребро
Программа 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.50 служит иллюстрацией изменений в структурах данных для каждой последовательности подходящих ребер и наращивания на базе циклов с отрицательной стоимостью. Эта последовательность не отражает какого-либо конкретного метода выбора подходящих ребер; она представляет выборы, которые делают аугментальные пути такими, какими они показаны на рис. 22.42. На этих рисунках изображены все потенциалы вершин и все приведенные стоимости по завершении каждого наращивания цикла, даже Глава 22, Потоки в сетях
Один из критических фактов, иллюстрацией которого служит пример, представленный на рис. 22.50, заключается в том, что алгоритм может не остановиться, поскольку порожние или заполненные ребра остовного дерева могут воспрепятствовать проталкиванию потока вдоль отрицательного цикла, который мы выявляем. Таким образом, мы можем выявить походящее ребро и отрицательный цикл, который оно образует с ребрами остовного дерева, тем не менее, максимальная величина потока, которую мы можем протолкнуть через этот цикл, может оказаться равной 0. И в этом случае мы выполняем подстановку подходящего ребра вместо одного из ребер цикла, однако нам не удастся снизить стоимость потока. Чтобы добиться того, чтобы алгоритм самостоятельно прекращал свою работу, необходимо выполнять специальную проверку, иначе алгоритм будет выполнять бесконечную последовательность наращиваний потока на нулевую величину. РИСУНОК 22.49. ИНИЦИАЛИЗАЦИЯ В СЕТЕВОМ СИМПЛЕКСНОМ АЛГОРИТМЕ Чтобы выполнить инициализацию структуры данных для сетевого симплексного алгоритма, мы начинаем с того, что всем ребрам назначаем нулевой поток (диаграмма слева), затем добавляем фиктивное ребро 0-5 из истока в сток, величина потока в котором не меньше величины максимального потока (для ясности мы воспользуемся значением, равным здесь величине максимального потока). Значение стоимости 9 фиктивного ребра больше стоимости любого цикла сети; в этой реализации мы используем значение CV. Фиктивное ребро в транспортной сети не показано, однако оно включено в остаточную сеть (диаграмма в цикле). Мы инициализируем остовное дерево стоком в качестве корня и с истоком в качестве его единственного потомка, и деревом поиска графа, индуцированного остальными узлами остаточной сети. Такая реализация использует представление дерева в виде родительских связей в массиве st и функцию ST; на наших рисунках изображена эта реализация и две других: корневая реализация, показанная справа, и множество заштрихованных ребер в остаточной сети. Потенциалы вершин содержатся в массиве pt и вычисляются с учетом структуры дерева с таким расчетом, чтобы разность потенциалов вершин конкретного древесного ребра была равна его стоимости. В столбце, обозначенном как costR и расположенном в центре диаграммы, показаны приведенные стоимости недревесных ребер, которые вычислены для каждого ребра путем прибавления разности потенциалов вершин к их стоимости. Приведенная цена древесных ребер равна нулю и в столбце не проставляется. Порожние ребра с отрицательными приведенными стоимостями и заполненные ребра с положительными приведенными стоимостями (подходящие ребра) помечены звездочками. Часть 5. Алгоритмы на графах
Каждый ряд этого рисунка соответствует итерации сетевого симплексного алгоритма по завершении инициализации, представленной на рис. 22.49. На каждой итерации алгоритм выбирает подходящее ребро, наращивает поток в цикле и обновляет структуры данных следующим образом: сначала наращивается поток, включая соответствующие изменения в остаточной сети. Во-вторых, древовидная структура ST подвергается изменению за счет добавления подходящего ребра и удаления соответствующего ребра из цикла, которое подходящее ребро образует с древесными ребрами. В третьих, таблица потенциалов phi обновляется с целью отобразить изменения в структуре дерева. В-четвертых, приведенные стоимости недревесных ребер (столбец, обозначенный меткой costR в центре) обновляются с целью отобразить изменения значений потенциалов, и эти значения используются для выявления порожних ребер с отрицательной приведенной стоимостью и заполненных ребер с положительной приведенной стоимостью как подходящих ребер (помечены звездочками на приведенных стоимостях). Реализации не обязательно должны выполнять все эти вычисления (они просто должны вычислить изменения потенциалов и приведенных стоимостей, этого достаточно для выявления подходящих ребер), однако мы приводим здесь все числа, чтобы дать полное представление о работе рассматриваемого алгоритма. Завершающее наращивание в этом примере вырождается. Оно не увеличивают потока, но и не выявляет подходящих ребер, откуда следует, что этот поток есть максимальный поток минимальной стоимости.
|