ся.) Далее с последовательностью и стеком выполняются такие пре-
образования:
старый старая новый новая
стек последовательность стек последовательность
X x P X x P
X x l P X l(x) P
X x r P X r(x) P
X x y z h P X h(x,y,z) P
X 0 f P X a P
X x f P X x x l f x r f h P
Обозначения: x, y, z,.. - числа, X - последовательность чисел, P
- последовательность чисел и символов "f", "l", "r", "h". В пос-
ледней строке предполагается, что m не равно 0. Эта строка соот-
ветствует равенству
f(x) = h(x, f(l(x)), f(r(x))),
Эти преобразования выполняются, пока последовательность не ста-
нет пуста. В этот момент в стеке окажется единственное число,
которое и будет ответом.
Замечание. Последовательность по существу представляет со-
бой стек отложенных заданий (вершина которого находится слева).
Глава 9. Разные алгоритмы на графах
9.1. Кратчайшие пути
В этом разделе рассматриваются различные варианты одной за-
дач. Пусть имеется n городов, пронумерованных числами от 1 до n.
Для каждой пары городов с номерами i, j в таблице a[i][j] хра-
нится целое число - цена прямого авиабилета из города i в город
j. Считается, что рейсы существуют между любыми городами, a[i,i]
= 0 при всех i, a[i][j] может отличаться от a[j,i]. Наименьшей
стоимостью проезда из i в j считается минимально возможная сумма
цен билетов для маршрутов (в том числе с пересадками), ведущих
из i в j. (Она не превосходит a[i][j], но может быть меньше.)
В предлагаемых ниже задачах требуется найти наименьшую сто-
имость проезда для некоторых пар городов при тех или иных огра-
ничениях на массив a и на время работы алгоритма.
9.1.1. Предположим, что не существует замкнутых маршрутов,
для которых сумма цен отрицательна. Доказать, что в этом случае
маршрут с наименьшей стоимостью существует.
Решение. Маршрут длиной больше n всегда содержит цикл, по-
этому минимум можно искать среди маршрутов длиной не более n, а
их конечное число.
Во всех следующих задачах предполагается, что это условие
(отсутствие циклов с отрицательной суммой) выполнено.
9.1.2. Найти наименьшую стоимость проезда из 1-го города во
все остальные за время O(n в степени 3).
Решение. Обозначим через МинСт(1,s,к) наименьшую стоимость
проезда из 1 в s менее чем с k пересадками. Тогда выполняется
такое соотношение:
МинСт (1,s,k+1) = наименьшему из чисел МинСт(1,s,k) и
МинСт(1,i,k) + a[i][s] (i=1..n)
Как отмечалось выше, искомым ответом является МинСт(1,i,n) для
всех i=1..n.
k:= 1;
for i := 1 to n do begin x[i] := a[1][i]; end;
{инвариант: x[i] := МинСт(1,i,k)}
while k <> n do begin
| for s := 1 to n do begin
| | y[s] := x[s];
| | for i := 1 to n do begin
| | | if y[s] > x[i]+a[i][s] then begin
| | | | y[s] := x[i]+a[i][s];
| | | end;
| | end
| | {y[s] = МинСт(1,s,k+1)}
| | for i := 1 to n do begin x[s] := y[s]; end;
| end;
| k := k + 1;
end;
Приведенный алгоритм называют алгоритмом динамического програм-
мирования, или алгоритмом Форда - Беллмана.
9.1.3. Доказать, что программа останется правильной, если
не заводить массива y, а производить изменения в самом массиве x
(заменив в программе все вхождения буквы y на x и затем удалить
ставшие лишними строки).
Решение. Инвариант будет таков:
МинСт(1,i,n) <= x[i] <= MинСт(1,i,k)
Этот алгоритм может быть улучшен в двух отношениях: можно
за то же время O(n в степени 3) найти наименьшую стоимость про-
езда i->j для ВСЕХ пар i,j (а не только с i=1), а можно сокра-
тить время работы до O(n в степени 2). Правда, в последнем слу-
чае нам потребуется, чтобы все цены a[i][j] были неотрицательны.
9.1.4. Найти наименьшую стоимость проезда i->j для всех i,j
за время O(n в степени 3).
Решение. Для k = 0..n через А(i,j,k) обозначим наименьшую
стоимость маршрута из i в j, если в качестве пересадочных разре-
шено использовать только пункты с номерами не больше k. Тогда
A(i,j,0) = a[i][j],
а
A(i,j,k+1) = min (A(i,j,k), A(i,k+1,k)+A(k+1,j,k))
(два варианта соответствуют неиспользованию и использованию
пункта k+1 в качестве пересадочного; отметим, что в нем незачем
бывать более одного раза).
Этот алгоритм называют алгоритмом Флойда.
9.1.5. Известны, что все цены неотрицательны. Найти на-
именьшую стоимость проезда 1->i для всех i=1..n за время O(n в
степени 2).
Решение. В процессе работы алгоритма некоторые города будут
выделенными (в начале - только город 1, в конце - все). При
этом:
для каждого выделенного города i хранится наименьшая сто-
имость пути 1->i; при этом известно, что минимум достигается на
пути, проходящем только через выделенные города;
для каждого невыделенного города i хранится наименьшая сто-
имость пути 1->i, в котором в качестве промежуточных используют-
ся только выделенные города.
Множество выделенных городов расширяется на основании сле-
дующего замечания: если среди всех невыделенных городов взять
тот, для которого хранимое число минимально, то это число явля-
ется истинной наименьшей стоимостью. В самом деле, пусть есть
более короткий путь. Рассмотрим первый невыделенный город на
этом пути - уже до него путь длиннее! (Здесь существенна неотри-
цательность цен.)
Добавив выбранный город к выделенным, мы должны скорректи-
ровать информацию, хранимую для невыделенных городов. При этом
достаточно учесть лишь пути, в которых новый город является пос-
ледним пунктом пересадки, а это легко сделать, так как минималь-
ную стоимость проезда в новый город мы уже знаем.
При самом бесхитростном способе хранения множества выделен-
ных городов (в булевском векторе) добавление одного города к
числу выделенных требует времени O(n).
Этот алгоритм называют алгоритмом Дейкстры.
Отыскании кратчайшего пути имеет естественную интерпретацию
в терминах матриц. Пусть A - матрица цен одной аваиакомпании, а
B - матрица цен другой. (Мы считаем, что диагональные элементы
матриц равны 0.) Пусть мы хотим лететь с одной пересадкой, при-
чем сначала самолетом компании A, а затем - компании B. Сколько
нам придется заплатить, чтобы попасть из города i в город j?
9.1.6. Доказать, что эта матрица вычисляется по обычной
формуле для произведения матриц, только вместо суммы надо брать
минимум, а вместо умножения - сумму.
9.1.7. Доказать, что таким образом определенное произведе-
ние матриц ассоциативно.
9.1.8. Доказать, что задача о кратчайших путях эквивалентна
вычислению "бесконечной степени" матрицы цен A: в последова-
тельности A, A*A, A*A*A,... все элементы, начиная с некоторого,
равны искомой матрице стоимостей кратчайших путей. (Если нет от-
рицательных циклов!)
9.1.9. Начиная с какого элемента можно гарантировать ра-
венство в предыдущей задаче?
Обычное (не модифицированное) умножение матриц тоже может
оказаться полезным, только матрицы должны быть другие. Пусть
есть не все рейсы (как в следующем разделе), а только некоторые,
a[i,j] равно 1, если рейс есть, и 0, если рейса нет. Возведем
матрицу a (обычным образом) в степень k и посмотрим на ее i-j-ый
элемент.
9.1.10. Чему он равен?
Ответ. Числу различных способов попасть из i в j за k
рейсов.
Случай, когда есть не все рейсы, можно свести к исходному,
введя фиктивные рейсы с бесконечно большой (или достаточно
большой) стоимостью. Тем не менее возникает такой вопрос. Число
реальных рейсов может быть существенно меньше n*n, поэтому инте-
ресны алгоритмы, которые работают эффективно в такой ситуации.
Исходные данные естественно представлять тогда в такой форме:
для каждого города известно число выходящих из него рейсов, их
пункты назначения и цены.
9.1.11. Доказать, что алгоритм Дейкстры можно модифициро-
вать так, чтобы для n городов и k маршрутов он требовал не более
C*(n+k log n) операций.
Указание. Что надо сделать на каждом шаге? Выбрать невыде-
ленный город с минимальной стоимостью и скорректировать цены для
всех городов, в которые из него есть маршруты. Если бы кто-то
сообщал нам, для какого города стоимость минимальна, то хватило
бы C*(n+k) действий. А поддержание сведений о том, какой элемент
в массиве минимален (см. задачу 6.4.1 в главе о типах данных)
обходится еще в множитель log n.
9.2. Связные компоненты, поиск в глубину и ширину
Наиболее простой случай задачи о кратчайших путях - если
все цены равны 0 или бесконечны. Другими словами, мы интересуем-
ся возможностью попасть из i в j, но за ценой не постоим (и она
нас не интересует). В других терминах: мы имеем ориентированный
граф (картинку из точек, некоторые из которых соединены стрелка-
ми) и нас интересуют вершины, доступные из данной.
Для этого случая задачи о кратчайших путях приведенные в
предыдущем разделе алгоритмы - не наилучшие. В самом деле, более
быстрая рекурсивная программа решения этой задачи приведена в
главе 7 (Рекурсия), а нерекурсивная - в главе 6 (Типы данных).
Сейчас нас интересует такая задача: не просто перечислить все
вершины, доступные из данной, но перечислить их в определенном
порядке. Два популярных случая - поиск в ширину и в глубину.
Поиск в ширину: надо перечислить все вершины ориентирован-
ного графа, доступные из данной, в порядке увеличения длины пути
от нее. (Тем самым мы решим задачу о кратчайших путях, кода цены
ребер равны 1 или бесконечны.)
9.2.1. Придумать алгоритм решения этой задачи с числом
действий не более C*(число ребер, выходящих из интересующих нас
вершин).
Решение. Эта задача рассматривалась в главе 6 (Типы дан-
ных), 6.3.7 - 6.3.8. Здесь мы приведём подробное решение. Пусть
num[i] - количество ребер, выходящих из i, out[i][1],...,
out[i][num[i]] - вершины, куда ведут ребра. Вот программа, при-
ведённая ранее:
procedure Доступные (i: integer);
| {напечатать все вершины, доступные из i, включая i}
| var X: подмножество 1..n;
| P: подмножество 1..n;
| q, v, w: 1..n;
| k: integer;
begin
| ...сделать X, P пустыми;
| writeln (i);
| ...добавить i к X, P;
| {(1) P = множество напечатанных вершин; P содержит i;
| (2) напечатаны только доступные из i вершины;
| (3) X - подмножество P;
| (4) все напечатанные вершины, из которых выходит
| ребро в ненапечатанную вершину, принадлежат X}
| while X непусто do begin
| | ...взять какой-нибудь элемент X в v;
| | for k := 1 to num [v] do begin
| | | w := out [v][k];
| | | if w не принадлежит P then begin
| | | | writeln (w);
| | | | добавить w в P;
| | | | добавить w в X
| | | end;
| | end;
| end;
end;
Тогда нам было безразлично, какой именно элемент множества X вы-
бирается. Если мы будем считать X очередью (первым пришел - пер-
мым ушел), то эта программа напечатает все вершины, доступные из
i, в порядке возрастания их расстояния от i (числа ребер на
кратчайшем пути из i). Докажем это.
Обозначим через V(k) множество всех вершин, расстояние ко-
торых от i (в описанном смысле) равно k. Имеет место такое соот-
ношение:
V(k+1) = (концы ребер с началами в V(k))-V(0)-V(1)-...-V(k)
(знак "-" обозначает вычитание множеств). Докажем, что для любо-
го k=0,1,2... в ходе работы программы будет такой момент (после
очередной итерации цикла while), когда
в очереди стоят все элементы V(k) и только они
напечатаны все элементы V(1),...,V(k)
