Дальнейшее обсуждение сетей и связанных с ними алгоритмов см. в Ивен [65], Лоулер [132], Пападимитриу и Стайглиц [154], Тарьян [188]. Хороший обзор сетевых алгоритмов написали Гольд-берг, Тардос и Тарьян [83].

Метод Форда-Фалкерсона изобрели Форд и Фалкерсон [71]. Они же рассмотрели многие задачи, связанные с сетями, в том числе задачу о максимальном потоке и о максимальном паросочетании. Во многих ранних реализациях метода Форда-Фалкерсона дополняющий путь находили с помощью поиска в ширину; Эдмондс и Карп [63] доказали, что в этом случае алгоритм полиномиален. Идею предпотока предложил Карзанов [119]. Метод проталкивания предпотока предложил Гольдберг [82]. Наиболее быстрый (время работы 0(VE\og (V2E)) из известных алгоритмов проталкивания предпотока принадлежит Гольдбергу и Тарьяну [85]. Наилучший известный (время работы 0(\/VE)) алгоритм для задачи о максимальном паросочетании предложили Хопкрофт и Карп [101].

Сортирующие сети

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

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

В разделе 28.1 вводятся понятия сети компараторов, сортирующей сети, времени работы сети. В разделе 28.2 мы докажем правило «нуля и единицы», которое упрощает проверку правильности работы сортирующей сети.

Быстрая сортирующая сеть, которую мы построим, представляет собой параллельную реализацию сортировки слиянием (раздел 1.3.1). Сначала (раздел 28.3) строится битонический сортировщик затем (28.4) он слегка модифицируется и получается сливающая сеть, которая соединяет два упорядоченных набора в один. Наконец (28.5) мы соединяем сливающие сети в сортирующую сеть, которая позволяет отсортировать п объектов за время 0(lg2 п).

Рис. 28.1 28.1 (а) Компаратор со входами i, р выходами х, у. (Ь) Тот же компаратор в виде вертикальной линии. Показаны входы х = 7, у = 3 и выходы х = 3, у = 7.

Рис. 28.2 28.2 (а) Сеть компараторов с 4 входами и 4 выходами, которая является сортирующей. Показаны входные значения в момент 0. (Ь) Значения на выходах компараторов А ш В в момент времени 1. (с) В момент 2 появляются выходные значения компараторов С и В; выходные значения bi и Ъ$ (но не 62,63) определены, (d) Наконец, оставшие два выходных значения появляются на выходах компаратора Е.

28.1. Сети компараторов

Сортирующие сети строятся из компараторов, соединённых проводами. Компаратор (comparator) (рис. 28.1(a)) имеет два входа ж, у и два выхода ж, у. Компаратор получает на вход два числа и переставляет их, если они идут в неправильном порядке. Другими словами,

ж = тгп(х,у), у = тах(х,у).

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

Мы считаем, что время работы компаратора (между получением входных данных и выдачей выходных) постоянно и одинаково для всех компараторов.

С помощью проводов (wires) выходы одних компараторов соединяют со входами других. Кроме того, сеть имеет входные и выходные провода. Рассмотрим сеть компараторов с п входными проводами (input wires) 0,1,0,2,... ,апъ п выходными проводами (output wires) Ь\, 62, • • • , Ьп. На вход поступает последовательность п чисел (которые мы будем обозначать (а,\, 02, , ап), как и сами провода); результатом работы будет последовательность (bi, 62, • • • , bn).

На рисунке 28.2 приводится пример сети компараторов (comparison network). Сеть с п входами и п выходами изображается п горизонтальными прямыми, которые в некоторых местах соединены вертикальными отрезками - компараторами. Прямая - это не один провод, а несколько - проводом является участок между компараторами. Например, верхняя прямая на рисунке 28.2 состоит из трёх проводов: входного провода ai соединенного со входом компаратора А; провода, соединяющего верхний выход компаратора А со входом компаратора С, а также выходного провода Ь\, соединенного с верхним выходом компаратора С.

Каждый вход любого из компараторов соединён либо с одним из входных проводов ai,a2, ,ап, либо с выходом другого компаратора. Каждый выход любого из компараторов соединён либо с входом другого (ровно одного), либо с одним из выходных прово-