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

Мы будем называть этот метод алгоритмом вычисления максимального потока мето­дом выталкивания превосходящего потока из вершины с максимальной высотой (highest-vertex­preflow-push). Мы можем реализовать данную стратегию за счет использования очереди по приоритету, однако существует возможность воспользоваться конкретными особеннос­тями высот, чтобы обеспечить выполнение операций на обобщенной очереди за посто­янное время. Было доказано, что временная граница для худшего случая выполнения этого алгоритма есть V²√ E (для разреженных графов она принимает вид V^5/2) (см. раздел ссы­лок)', по обыкновению, эта оценка носит пессимистичный характер. Было предложено и множество других вариантов выталкивания превосходящего потока, некоторые из них понижают временную границу для худшего случая до значения, близкого к VE (см. раз­дел ссылок).

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

Программная реализация обобщенного вершинного алгоритма выталкивания превосходящего потока для вычисления максимального потока использует обобщенную очередь, не принимающую дубликаты активных вершин. Вектор wt содержит избыточный поток в каждой вершине, благодаря чему неявно определяет множество активных вершин. Предполагается, что вершина s первоначально активна, но никогда не возвращается в очередь, a 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]+l) { 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); } } }

};

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

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

Таблица 22.2. Эмпирические исследования алгоритмов выталкивания превосходящих
потоков___________________________________________________________________

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

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

■ Сравнение вершинного обобщенного алгоритма с реберным.

■ Реализация обобщенной очереди.

■ Первоначальная установка значений высоты.

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

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