А. Шень ðòïçòáííéòï÷áîéå ÔÅÏÒÅÍÙ É ÚÁÄÁÞÉ Издание седьмое, дополненное Москва

8. КАК ОБОЙТИСЬ
БЕЗ РЕКУРСИИ
Для универсальных языков программирования (каковым является
паскаль) рекурсия не даёт ничего нового: для всякой рекурсивной про-
граммы можно написать эквивалентную программу без рекурсии. Мы
не будем доказывать этого, а продемонстрируем некоторые приёмы,
позволяющие избавиться от рекурсии в конкретных ситуациях.
Зачем это нужно? Ответ прагматика мог бы быть таким: во мно-
гих компьютерах (в том числе, к сожалению, и в современных, исполь-
зующих так называемые RISC-процессоры), рекурсивные программы
в несколько раз медленнее соответствующих нерекурсивных программ.
Ещё один возможный ответ: в некоторых языках программирования ре-
курсивные программы запрещены. А главное, при удалении рекурсии
возникают изящные и поучительные конструкции.
8.1. Таблица значений (динамическое
программирование)
8.1.1. Следующая рекурсивная процедура вычисляет числа сочета-
ний (биномиальные коэффициенты). Напишите эквивалентную нере-
курсивную программу.
function C(n,k: integer):integer;
{n >= 0; 0 <= k <=n}
begin
if (k = 0) or (k = n) then begin
C:=1;
end else begin {0C:= C(n-1,k-1)+C(n-1,k)
end;
end;

136
8. Как обойтись без рекурсии
Замечание. 𝐶
𝑘
𝑛
| число 𝑘-элементных подмножеств 𝑛-элементного
множества. Соотношение 𝐶
𝑘
𝑛
= 𝐶
𝑘
−
1
𝑛
−
1
+ 𝐶
𝑘
𝑛
−
1
получится, если мы фикси-
руем некоторый элемент 𝑛-элементного множества и отдельно подсчи-
таем 𝑘-элементные подмножества, включающие и не включающие этот
элемент. Таблица значений 𝐶
𝑘
𝑛
1
1
1
1
2
1
1
3
3
1
.
.
.
.
.
.
.
.
.
называется треугольником Паскаля (того самого). В нём каждый эле-
мент, кроме крайних единиц, равен сумме двух стоящих над ним.
Решение. Можно воспользоваться формулой
𝐶
𝑘
𝑛
=
𝑛!
𝑘! (𝑛
−
𝑘)!
Мы, однако, не будем этого делать, так как хотим продемонстрировать
более общие приёмы устранения рекурсии. Вместо этого составим та-
блицу значений функции C(n,k) = 𝐶
𝑘
𝑛
, заполняя её для 𝑛 = 0, 1, 2, . . .,
пока не дойдём до интересующего нас элемента.
8.1.2. Что можно сказать о времени работы рекурсивной и нере-
курсивной версий в предыдущей задаче? Тот же вопрос о памяти.
Решение. Таблица занимает место порядка 𝑛
2
, его можно сократить
до 𝑛, если заметить, что для вычисления следующей строки треуголь-
ника Паскаля нужна только предыдущая. Время работы остаётся по-
рядка 𝑛
2
. Рекурсивная программа требует существенно большего вре-
мени: вызов C(n,k) сводится к двум вызовам для C(n-1,...), те |
к четырём вызовам для C(n-2,...) и так далее. Таким образом, время
оказывается экспоненциальным (порядка 2
𝑛
). Используемая рекурсив-
ной версией память пропорциональна 𝑛 | умножаем глубину рекурсии
(𝑛) на количество памяти, используемое одним экземпляром процедуры
(константа).
Кардинальный выигрыш во времени при переходе от рекурсивной
версии к нерекурсивной связан с тем, что в рекурсивном варианте одни
и те же вычисления происходят много раз. Например, вызов C(5,3)

8.1. Таблица значений (динамическое программирование)
137
в конечном счёте порождает два вызова C(3,2):
C(5,3)
↘
↘
C(4,2)
C(4,3)
↘
↘
↘
↘
C(3,1)
C(3,2)
C(3,3)
Заполняя таблицу, мы каждую клетку заполняем только однажды |
отсюда и экономия. Этот приём называется динамическим программи-
рованием, и применим в тех случаях, когда объём хранимой в таблице
информации оказывается не слишком большим.
8.1.3. Поговорите на ту же тему на примере рекурсивной и (про-
стейшей) нерекурсивной программ для вычисления чисел Фибоначчи,
заданных соотношением
˘
1
= ˘
2
= 1; ˘
𝑛
= ˘
𝑛
−
1
+ ˘
𝑛
−
2
(𝑛 > 2).
8.1.4. Дан выпуклый 𝑛-угольник (заданный координатами своих
вершин в порядке обхода). Его разрезают на треугольники диагоналя-
ми, для чего необходимо 𝑛
−
2 диагонали (это можно доказать индукци-
ей по 𝑛). Стоимостью разрезания назовём сумму длин всех использован-
ных диагоналей. Найдите минимальную стоимость разрезания. Число
действий должно быть ограничено некоторым многочленом от 𝑛. (Пере-
бор не подходит, так как число вариантов не ограничено многочленом.)
Решение. Будем считать, что вершины пронумерованы от 1 до 𝑛
и идут по часовой стрелке. Пусть 𝑘, 𝑙 | номера вершин, причём 𝑙 > 𝑘.
Через 𝐴(𝑘, 𝑙) обозначим многоугольник, отрезаемый от нашего хор-
дой 𝑘 { 𝑙. (Эта хорда разрезает многоугольник на два, один из которых
включает сторону 1 { 𝑛; через 𝐴(𝑘, 𝑙) мы обозначаем другой.) Исходный
многоугольник естественно обозначить 𝐴(1, 𝑛). При 𝑙 = 𝑘 + 1 получа-
ется «двуугольник» с совпадающими сторонами.
q
q
q
q
q
A
A
A
A
q
q
q
q
A
A
A
A
1
𝑘
𝑙
𝑛
𝐴(𝑘, 𝑙)

138
8. Как обойтись без рекурсии
Через 𝑎(𝑘, 𝑙) обозначим стоимость разрезания многоугольника 𝐴(𝑘, 𝑙)
диагоналями на треугольники. Напишем рекуррентную формулу для
𝑎(𝑘, 𝑙). При 𝑙 = 𝑘 + 1 получается двуугольник, и мы полагаем 𝑎(𝑘, 𝑙) = 0.
При 𝑙 = 𝑘 + 2 получается треугольник, и в этом случае также 𝑎(𝑘, 𝑙) = 0.
Пусть 𝑙 > 𝑘 + 2.
q
q
A
A
A
A
q
q
q
q
𝑘
𝑙
𝑖
@
@
@
@
@
@
Хорда 𝑘 { 𝑙 является стороной многоугольника 𝐴(𝑘, 𝑙) и, следовательно,
стороной одного из треугольников, на которые он разрезан. Противо-
положной вершиной 𝑖 этого треугольника может быть любая из вершин
𝑘 + 1, . . . , 𝑙
−
1, и минимальная стоимость разрезания может быть вы-
числена как
min
{
(длина хорды 𝑘 { 𝑖) + (длина хорды 𝑖 { 𝑙) + 𝑎(𝑘, 𝑖) + 𝑎(𝑖, 𝑙)
}
по всем 𝑖 = 𝑘 + 1, . . . , 𝑙
−
1. При этом надо учесть, что при 𝑞 = 𝑝 + 1
хорда 𝑝 { 𝑞 | не хорда, а сторона, и её длину надо считать равной 0
(по стороне разрез не проводится).
Составив таблицу для 𝑎(𝑘, 𝑙) и заполняя её в порядке возрастания
числа вершин (равного 𝑙
−
𝑘 + 1), мы получаем программу, использую-
щую память порядка 𝑛
2
и время порядка 𝑛
3
(однократное применение
рекуррентной формулы требует выбора минимума из не более чем 𝑛 чи-
сел).
8.1.5. Матрицей размера 𝑚
×
𝑛 называется прямоугольная таблица
из 𝑚 строк и 𝑛 столбцов, заполненная числами. Матрицу размера 𝑚
×
𝑛
можно умножить на матрицу размера 𝑛
×
𝑘 (ширина левого сомножи-
теля должна равняться высоте правого), и получается матрица разме-
ром 𝑚
×
𝑘. Ценой такого умножения будем считать произведение 𝑚𝑛𝑘
(таково число умножений, которые нужно выполнить при стандартном
способе умножения | но сейчас это нам не важно). Умножение матриц
ассоциативно, поэтому произведение 𝑠 матриц можно вычислять в раз-
ном порядке. Для каждого порядка подсчитаем суммарную цену всех
матричных умножений. Найдите минимальную цену вычисления произ-
ведения, если известны размеры всех матриц. Число действий должно
быть ограничено многочленом от числа матриц.

8.1. Таблица значений (динамическое программирование)
139
Пример. Матрицы размером 2
×
3, 3
×
4, 4
×
5 можно перемножать
двумя способами. В первом цена равна 2
·
3
·
4 + 2
·
4
·
5 = 24 + 40 = 64,
во втором цена равна 3
·
4
·
5 + 2
·
3
·
5 = 90.
Решение. Представим себе, что первая матрица написана на отрезке
[0, 1], вторая | на отрезке [1, 2], . . . , 𝑠-я | на отрезке [𝑠
−
1, 𝑠]. Матри-
цы на отрезках [𝑖
−
1, 𝑖] и [𝑖, 𝑖 + 1] имеют общий размер, позволяющий
их перемножить. Обозначим его через 𝑑[𝑖]. Таким образом, исходным
данным в задаче является массив 𝑑[0] . . . 𝑑[𝑠].
Через 𝑎(𝑖, 𝑗) обозначим минимальную цену вычисления произведе-
ния матриц на участке [𝑖, 𝑗] (при 0
6
𝑖 < 𝑗
6
𝑠). Искомая величина равна
𝑎(0, 𝑠). Величины 𝑎(𝑖, 𝑖 + 1) равны нулю (матрица одна и перемножать
ничего не надо). Рекуррентная формула будет такой:
𝑎(𝑖, 𝑗) = min
{
𝑎(𝑖, 𝑘) + 𝑎(𝑘, 𝑗) + 𝑑[𝑖]𝑑[𝑘]𝑑[𝑗]
}
где минимум берётся по всем возможных местам последнего умноже-
ния, то есть по всем 𝑘 = 𝑖 + 1, . . . , 𝑗
−
1. В самом деле, произведение
матриц на отрезке [𝑖, 𝑘] есть матрица размера 𝑑[𝑖]𝑑[𝑘], произведение
матриц на отрезке [𝑘, 𝑗] имеет размер 𝑑[𝑘]𝑑[𝑗], и цена вычисления их
произведения равна 𝑑[𝑖]𝑑[𝑘]𝑑[𝑗].
Замечание. Две последние задачи похожи. Это сходство станет яс-
нее, если написать матрицы-множители на сторонах 1 { 2, 2 { 3, . . . ,
(𝑠
−
1) { 𝑠 многоугольника, а на каждой хорде 𝑖 { 𝑗 написать произве-
дение всех матриц, стягиваемых этой хордой.
8.1.6. Железная дорога с односторонним движением имеет 𝑛 стан-
ций. Известны цены билетов от 𝑖-й станции до 𝑗-й (при 𝑖 < 𝑗 | в обрат-
ную сторону проезда нет). Найдите минимальную стоимость проез-
да от начала до конца (с учётом возможной экономии за счёт переса-
док).
8.1.7. Задано конечное множество с бинарной операцией (вообще
говоря, не коммутативной и даже не ассоциативной). Имеется 𝑛 эле-
ментов 𝑎
1
, . . . , 𝑎
𝑛
этого множества и ещё один элемент 𝑥. Проверьте,
можно ли так расставить скобки в произведении 𝑎
1
×
. . .
×
𝑎
𝑛
, чтобы
в результате получился 𝑥. Число операций должно не превосходить 𝐶𝑛
3
для некоторой константы 𝐶 (зависящей от числа элементов в выбран-
ном конечном множестве).
Решение. Заполняем таблицу, в которой для каждого участка
𝑎
𝑖
. . . 𝑎
𝑗
нашего произведения хранится список всех возможных его зна-
чений (при разной расстановке скобок).

140
8. Как обойтись без рекурсии
По существу этот же приём применяется в полиномиальном алго-
ритме проверки принадлежности слова произвольному контекстно-сво-
бодному языку (см. главу
15
).
Следующая задача (задача о рюкзаке) уже упоминалась в главе
3
.
8.1.8. Имеется 𝑛 положительных целых чисел 𝑥
1
, . . . , 𝑥
𝑛
и число 𝑁.
Выясните, можно ли получить 𝑁, складывая некоторые из чисел 𝑥
1
, . . .
. . . , 𝑥
𝑛
. Число действий должно быть порядка 𝑁𝑛.
[Указание. После 𝑖 шагов хранится множество тех чисел на отрезке
0 . . . 𝑁, которые представимы в виде суммы некоторых из 𝑥
1
. . . 𝑥
𝑖
.]
Замечание. Мы видели, что замена рекурсивной программы на за-
полнение таблицы значений иногда позволяет уменьшить число дей-
ствий. Примерно того же эффекта можно добиться иначе: оставить
программу рекурсивной, но в ходе вычислений запоминать уже вычи-
сленные значения, а перед очередным вычислением проверять, нет ли
уже готового значения.
8.2. Стек отложенных заданий
Другой приём устранения рекурсии продемонстрируем на примере
задачи о ханойских башнях.
8.2.1. Напишите нерекурсивную программу для нахождения после-
довательности перемещений колец в задаче о ханойских башнях.
Решение. Вспомним рекурсивную программу, перекладывающую
i верхних колец с m на n:
procedure move(i,m,n: integer);
var s: integer;
begin
if i = 1 then begin
writeln (’сделать ход ’, m, ’->’, n);
end else begin
s:=6-m-n; {s - третий стержень: сумма номеров равна 6}
move (i-1, m, s);
writeln (’сделать ход ’, m, ’->’, n);
move (i-1, s, n);
end;
end;
Видно, что задача «переложить i верхних дисков с m-го стержня на n-й»
сводится к трём задачам того же типа: двум задачам с i-1 дисками

8.2. Стек отложенных заданий
141
и к одной задаче с единственным диском. Занимаясь этими задачами,
важно не позабыть, что ещё осталось сделать.
Для этой цели заведём стек отложенных заданий, элементами ко-
торого будут тройки
⟨
i, m, n
⟩
. Каждая такая тройка интерпретируется
как заказ «переложить i верхних дисков с m-го стержня на n-й». Зака-
зы упорядочены в соответствии с требуемым порядком их выполнения:
самый срочный | вершина стека. Получаем такую программу:
procedure move(i,m,n: integer);
begin
сделать стек заказов пустым
положить в стек тройку 
{инвариант: осталось выполнить заказы в стеке}
while стек непуст do begin
удалить верхний элемент, переложив его в 
if j = 1 then begin
writeln (’сделать ход’, p, ’->’, q);
end else begin
s:=6-p-q;
{s - третий стержень: сумма номеров равна 6}
положить в стек тройки , <1,p,q>, 
end;
end;
end;
(Заметим, что первой в стек кладётся тройка, которую надо выполнять
последней.) Стек троек может быть реализован как три отдельных сте-
ка. (Кроме того, в паскале есть специальный тип, называемый «запись»
(record), который может быть применён.)
8.2.2. (Сообщил А. К. Звонкин со ссылкой на Анджея Лисовского.)
Для задачи о ханойских башнях есть и другие нерекурсивные алгорит-
мы. Вот один из них: простаивающим стержнем (не тем, с которого
переносят, и не тем, на который переносят) должны быть все стерж-
ни по очереди. Другое правило: поочерёдно перемещать наименьшее
кольцо и не наименьшее кольцо, причём наименьшее | по кругу.
8.2.3. Используйте замену рекурсии стеком отложенных заданий
в рекурсивной программе печати десятичной записи целого числа.
Решение. Цифры добываются с конца и закладываются в стек, а за-
тем печатаются в обратном порядке.
8.2.4. Напишите нерекурсивную программу, печатающую все вер-
шины двоичного дерева.

142
8. Как обойтись без рекурсии
Решение. В этом случае стек отложенных заданий будет содержать
заказы двух сортов: «напечатать данную вершину» и «напечатать все
вершины поддерева с данным корнем» (при этом nil считается корнем
пустого дерева). Таким образом, элемент стека есть пара:
⟨
тип заказа,
номер вершины
⟩
.
Вынимая элемент из стека, мы либо сразу исполняем его (если это
заказ первого типа), либо помещаем в стек три порождённых им зака-
за | в одном из шести возможных порядков.
8.2.5. Что изменится, если требуется не печатать вершины двоич-
ного дерева, а подсчитать их количество?
Решение. Печатание вершины следует заменить прибавлением еди-
ницы к счётчику. Другими словами, инвариант таков: (общее число
вершин) = (счётчик) + (сумма чисел вершин в поддеревьях, корни ко-
торых лежат в стеке).
8.2.6. Для некоторых из шести возможных порядков возможны уп-
рощения, делающие ненужным хранение в стеке элементов двух видов.
Укажите некоторые из них.
Решение. Если требуемый порядок таков:
корень, левое поддерево, правое поддерево,
то заказ на печатание корня можно не закладывать в стек, а выполнять
сразу.
Несколько более сложная конструкция применима для порядка
левое поддерево, корень, правое поддерево.
В этом случае все заказы в стеке, кроме самого первого (напечатать
поддерево) делятся на пары:
напечатать вершину x, напечатать «правое поддерево» x
(= поддерево с корнем в правом сыне x). Объединив эти пары в за-
казы специального вида и введя переменную для отдельного хранения
первого заказа, мы обойдёмся стеком однотипных заказов.
То же самое, разумеется, верно, если поменять местами левое и пра-
вое | получается ещё два порядка.
Замечание. Другую программу печати всех вершин дерева можно
построить на основе программы обхода дерева, разобранной в главе
3
.
Там используется команда «вниз». Поскольку теперешнее представле-
ние дерева с помощью массивов l и r не позволяет найти предка задан-
ной вершины, придётся хранить список всех вершин на пути от корня
к текущей вершине. См. также главу
9
.

8.3. Более сложные случаи рекурсии
143
8.2.7. Напишите нерекурсивный вариант программы быстрой сор-
тировки (см. с.
132
). Как обойтись стеком, глубина которого ограни-
чена 𝐶 log 𝑛, где 𝑛 | число сортируемых элементов?
Решение. В стек кладутся пары
⟨
𝑖, 𝑗
⟩
, интерпретируемые как от-
ложенные задания на сортировку соответствующих участков массива.
Все эти заказы не пересекаются, поэтому размер стека не может превы-
сить 𝑛. Чтобы ограничиться стеком логарифмической глубины, будем
придерживаться такого правила: глубже в стек помещать больший из
возникающих двух заказов. Пусть 𝑓(𝑛) | максимальная глубина сте-
ка, которая может встретиться при сортировке массива из не более
чем 𝑛 элементов таким способом. Оценим 𝑓(𝑛) сверху таким способом:
после разбиения массива на два участка мы сначала сортируем более
короткий (храня в стеке более длинный про запас), при этом глубина
стека не больше 𝑓(𝑛/2) + 1, затем сортируем более длинный, так что
𝑓(𝑛)
6
max(𝑓(𝑛/2) + 1, 𝑓(𝑛
−
1)),
откуда очевидной индукцией получаем 𝑓(𝑛) = 𝑂(log 𝑛).
8.3. Более сложные случаи рекурсии
Пусть функция 𝑓 с натуральными аргументами и значениями опре-
делена рекурсивно условиями
𝑓(0) = 𝑎,
𝑓(𝑥) = ℎ(𝑥, 𝑓(𝑙(𝑥))) (𝑥 > 0)
где 𝑎 | некоторое число, а ℎ и 𝑙 | известные функции. Другими слова-
ми, значение функции 𝑓 в точке 𝑥 выражается через значение 𝑓 в точке
𝑙(𝑥). При этом предполагается, что для любого 𝑥 в последовательности
𝑥, 𝑙(𝑥), 𝑙(𝑙(𝑥)), . . .
рано или поздно встретится 0.
Если дополнительно известно, что 𝑙(𝑥) < 𝑥 для всех 𝑥, то вычисле-
ние 𝑓 не представляет труда: вычисляем последовательно 𝑓(0), 𝑓(1),
𝑓(2), . . .
8.3.1. Напишите нерекурсивную программу вычисления 𝑓 для об-
щего случая.
Решение. Для вычисления 𝑓(𝑥) вычисляем последовательность
𝑙(𝑥), 𝑙(𝑙(𝑥)), 𝑙(𝑙(𝑙(𝑥))), . . .

144
8. Как обойтись без рекурсии
до появления нуля и запоминаем её, а затем вычисляем значения 𝑓 в точ-
ках этой последовательности, идя справа налево.
Ещё более сложный случай из следующей задачи вряд ли встретит-
ся на практике (а если и встретится, то проще рекурсию не устранять,
а оставить). Но тем не менее: пусть функция 𝑓 с натуральными аргу-
ментами и значениями определяется соотношениями
𝑓(0) = 𝑎,
𝑓(𝑥) = ℎ(𝑥, 𝑓(𝑙(𝑥)), 𝑓(𝑟(𝑥))) (𝑥 > 0),
где 𝑎 | некоторое число, а 𝑙, 𝑟 и ℎ | известные функции. Предпола-
гается, что если взять произвольное число и начать применять к нему
функции 𝑙 и 𝑟 в произвольном порядке, то рано или поздно получится 0.
8.3.2. Напишите нерекурсивную программу вычисления 𝑓.
Решение. Можно было бы сначала построить дерево, у которого
в корне находится 𝑥, а в сыновьях вершины 𝑖 стоят 𝑙(𝑖) и 𝑟(𝑖) | если
только 𝑖 не равно нулю. Затем вычислять значения функции, идя от
листьев к корню. Однако есть и другой способ.
Обратной польской записью (или постфиксной записью) выраже-
ния называют запись, где знак функции стоит после всех её аргументов,
а скобки не используются. Вот несколько примеров:
𝑓(2)
2 𝑓
𝑓(𝑔(2))
2 𝑔 𝑓
𝑠(2, 𝑡(7))
2 7 𝑡 𝑠
𝑠(2, 𝑢(2, 𝑠(5, 3))
2 2 5 3 𝑠 𝑢 𝑠
Постфиксная запись выражения позволяет удобно вычислять его с по-
мощью стекового калькулятора. Этот калькулятор имеет стек, кото-
рый мы будем представлять себе расположенным горизонтально (числа
вынимаются и кладутся справа), и клавиши | числовые и функцио-
нальные. При нажатии на клавишу с числом это число кладётся в стек.
При нажатии на функциональную клавишу соответствующая функция
применяется к нескольким аргументам у вершины стека. Например,
если в стеке были числа
2 3 4 5 6
и нажата функциональная клавиша 𝑠, соответствующая функции от
двух аргументов, то в стеке окажутся числа
2 3 4 𝑠(5, 6).

8.3. Более сложные случаи рекурсии
145
Перейдём теперь к нашей задаче. В процессе вычисления значения
функции 𝑓 мы будем работать со стеком чисел, а также с последова-
тельностью чисел и символов f, l, r, h, которую мы будем интерпре-
тировать как последовательность нажатий клавиш на стековом каль-
куляторе. Инвариант такой:
если стек чисел представляет собой текущее состояние сте-
кового калькулятора, то после нажатия всех клавиш после-
довательности в стеке останется единственное число, и оно
будет искомым ответом.
Пусть нам требуется вычислить значение 𝑓(𝑥). Тогда вначале мы по-
мещаем в стек число 𝑥, а последовательность содержит единственный
символ f. (При этом инвариант соблюдается.) Далее с последователь-
ностью и стеком выполняются такие преобразования:
старый
старая
новый
новая
стек
последовательность
стек
последовательность
𝑋
𝑥 𝑃
𝑋 𝑥
𝑃
𝑋 𝑥
l 𝑃
𝑋 𝑙(𝑥)
𝑃
𝑋 𝑥
r 𝑃
𝑋 𝑟(𝑥)
𝑃
𝑋 𝑥 𝑦 𝑧
h 𝑃
𝑋 ℎ(𝑥, 𝑦, 𝑧)
𝑃
𝑋 0
f 𝑃
𝑋 𝑎
𝑃
𝑋 𝑥
f 𝑃
𝑋
𝑥 𝑥 l f 𝑥 r f h 𝑃
Здесь 𝑥, 𝑦, 𝑧 | числа, 𝑋 | последовательность чисел, 𝑃 | последова-
тельность чисел и символов f, l, r, h. В последней строке предполага-
ется, что 𝑥
̸
= 0. Эта строка соответствует равенству
𝑓(𝑥) = ℎ(𝑥, 𝑓(𝑙(𝑥)), 𝑓(𝑟(𝑥))).
Преобразования выполняются, пока последовательность не станет пу-
ста. В этот момент в стеке окажется единственное число, которое и бу-
дет ответом.
Замечание. Последовательность по существу представляет собой
стек отложенных заданий (вершина которого находится слева).

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-го города во
все остальные за время 𝑂(n
3
).
Решение. Обозначим через МинСт(1,s,k) наименьшую стоимость
проезда из 1 в s менее чем с k пересадками. Тогда выполняется та-

9.1. Кратчайшие пути
147
кое соотношение:
МинСт(1, s, k+1) = min
(︁
МинСт(1,s,k), min
i=1..n
МинСт(1,i,k) + a[i][s])
)︁
Как отмечалось выше, искомым ответом является МинСт(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)}
end;
for i := 1 to n do begin x[s] := y[s]; end;
k := k + 1;
end;
Приведённый алгоритм называют алгоритмом динамического про-
граммирования, или алгоритмом Форда { Беллмана.
9.1.3. Докажите, что программа останется правильной, если не за-
водить массива y, а производить изменения в самом массиве x (заменив
в программе все вхождения буквы y на x и затем удалить ставшие лиш-
ними строки).
Решение. Инвариант будет таков:
МинСт(1,i,n)
6
x[i]
6
МинСт(1,i,k).
Этот алгоритм может быть улучшен в двух отношениях: можно за
то же время 𝑂(n
3
) найти наименьшую стоимость проезда i
→
j для
всех пар i, j (а не только при i = 1), а можно сократить время работы
до 𝑂(n
2
). Правда, в последнем случае нам потребуется, чтобы все цены
a[i][j] были неотрицательны.
9.1.4. Найдите наименьшую стоимость проезда i
→
j для всех i, j
за время 𝑂(n
3
).

148
9. Разные алгоритмы на графах
Решение. Для k = 0 . . . n через A(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. Как проверить за 𝑂(n
3
) действий, имеет ли граф с n верши-
нами циклы с отрицательной суммой?
[Указание. Можно применять алгоритм Флойда, причём разрешать
i = j в A(i,j,k), пока не появится первый отрицательный цикл.]
9.1.6. Имеется 𝑛 валют и таблица обменных курсов (сколько фло-
ринов дают за талер и т.п.). Коммерсант хочет неограниченно обога-
титься, обменивая свой начальный капитал туда-сюда по этим курсам.
Как проверить, возможно ли это?
[Указание. После логарифмирования деньги уподобляются расстоя-
ниям.]
9.1.7. Известно, что все цены неотрицательны. Найдите наимень-
шую стоимость проезда 1
→
i для всех i = 1 . . . n за время 𝑂(n
2
).
Решение. В процессе работы алгоритма некоторые города будут
выделенными (в начале | только город 1, в конце | все). При этом:
•
для каждого выделенного города i хранится наименьшая стои-
мость пути 1
→
i; при этом известно, что минимум достигается
на пути, проходящем только через выделенные города;
•
для каждого невыделенного города i хранится наименьшая стои-
мость пути 1
→
i, в котором в качестве промежуточных исполь-
зуются только выделенные города.
Множество выделенных городов расширяется на основании следую-
щего замечания: если среди всех невыделенных городов взять тот, для
которого хранимое число минимально, то это число является истин-

9.1. Кратчайшие пути
149
ной наименьшей стоимостью. В самом деле, пусть есть более короткий
путь. Рассмотрим первый невыделенный город на этом пути | уже до
него путь длиннее! (Здесь существенна неотрицательность цен.)
Добавив выбранный город к выделенным, мы должны скорректи-
ровать информацию, хранимую для невыделенных городов. При этом
достаточно учесть лишь пути, в которых новый город является послед-
ним пунктом пересадки, а это легко сделать, так как минимальную
стоимость проезда в новый город мы уже знаем.
При самом бесхитростном способе хранения множества выделенных
городов (в булевом векторе) добавление одного города к числу выде-
ленных требует времени 𝑂(n).
Этот алгоритм называют алгоритмом Дейкстры.
9.1.8. Имеется 𝑛 городов, соединённых дорогами (с односторонним
движением). Для любых городов 𝑖, 𝑗 известен максимальный вес груза,
который можно везти из 𝑖 в 𝑗 (грузоподъёмность дороги). Найдите за
время 𝑂(𝑛
2
) для всех городов максимальный вес груза, который в них
можно привезти из столицы.
[Указание. Действуйте аналогично алгоритму Дейкстры, заменив
сумму на максимум.]
Отыскание кратчайшего пути имеет естественную интерпретацию
в терминах матриц. Пусть 𝐴 | матрица цен одной авиакомпании,
а 𝐵 | матрица цен другой. Пусть мы хотим лететь с одной пересад-
кой, причём сначала самолётом компании 𝐴, а затем | компании 𝐵.
Сколько нам придётся заплатить, чтобы попасть из города i в город j?
9.1.9. Докажите, что эта матрица вычисляется по обычной формуле
для произведения матриц, только вместо суммы надо брать минимум,
а вместо умножения | сумму.
9.1.10. Докажите, что таким образом определённое произведение
матриц ассоциативно.
9.1.11. Докажите, что задача о кратчайших путях эквивалентна вы-
числению 𝐴
∞
для матрицы цен 𝐴: в последовательности 𝐴, 𝐴
2
, 𝐴
3
, . . .
все элементы, начиная с некоторого, равны искомой матрице стоимо-
стей кратчайших путей. (Если нет отрицательных циклов!)
9.1.12. Начиная с какого элемента можно гарантировать равенство
в предыдущей задаче?

150
9. Разные алгоритмы на графах
Обычное (не модифицированное) умножение матриц тоже может
оказаться полезным, только матрицы должны быть другие. Пусть есть
не все рейсы (как раньше), а только некоторые, a[i][j] равно 1, если
рейс есть, и 0, если рейса нет. Возведём матрицу a (обычным образом)
в степень k и посмотрим на её (i-j)-й элемент.
9.1.13. Чему он равен?
Ответ. Числу различных способов попасть из i в j за k рейсов
(с k-1 пересадками).
При описании кратчайших путей случай, когда есть не все рейсы,
можно свести к исходному, введя фиктивные рейсы с бесконечно боль-
шой (или достаточно большой) стоимостью. Тем не менее возникает
такой вопрос. Число реальных рейсов может быть существенно мень-
ше 𝑛
2
, поэтому интересны алгоритмы, которые работают эффективно
в такой ситуации. Исходные данные естественно представлять тогда
в такой форме: для каждого города известно число выходящих из него
рейсов, их пункты назначения и цены.
9.1.14. Докажите, что алгоритм Дейкстры можно изменить таким
образом, чтобы для 𝑛 городов и 𝑚 рейсов (всего) он требовал не более
𝐶(𝑛 + 𝑚) log 𝑛 операций.
[Указание. Что надо сделать на каждом шаге? Выбрать невыделен-
ный город с минимальной стоимостью и скорректировать цены для всех
городов, в которые из него есть маршруты. Если бы кто-то сообщал
нам, для какого города стоимость минимальна, то хватило бы 𝐶(𝑛 + 𝑚)
действий. А поддержание сведений о том, какой элемент в массиве ми-
нимален (см. задачу на с.
115
), обходится ещё в множитель log 𝑛.]
Иногда нам нужны не все города. Пусть, скажем, в графе дорог
нужно найти кратчайший путь между двумя близкими посёлками |
тогда города и дороги в другой части страны нас явно не интересуют.
С точки зрения алгоритма, если нас интересует расстояние от i до j,
то алгоритм Дейкстры, вычисляющий расстояния от i до всех городов,
можно остановить, как только город j станет выделенным.
9.1.15. Покажите, что в этот момент выделены могут быть только
города, которые не дальше от i, чем j.
[Указание. Для невыделенного города с минимальной стоимостью
расстояние до него равно его стоимости, а для любого другого невы-
деленного города 𝑢 расстояние не меньше (сравним с расстоянием до
первого невыделенного города на кратчайшем пути в 𝑢).]

9.1. Кратчайшие пути
151
Если мы (как это часто делают на практике) храним отдельно вы-
деленные города (как множество, см. главы
13
и
14
), а также невы-
деленные города конечной стоимости (множество плюс приоритетная
очередь, с.
115
), предыдущая задача ограничивает количество храни-
мых городов: это города, отстоящие от i не больше, чем город j, а
также все их соседи. Такой способ хранения полезен, если граф задан
неявно | скажем, если мы ищем кратчайший путь из одной позиции
какой-то головоломки в другую. (При реализации алгоритма Дейкстры
от приоритетной очереди, помимо взятия наименьшего элемента, пона-
добится операция увеличения приоритета элемента, но её тоже легко
реализовать при способе хранения, описанном в задаче
6.4.2
.)
Предыдущие замечания особенно полезны в сочетании с методом
потенциалов. Пусть есть некоторая функция 𝜙 на вершинах графа,
называемая потенциалом. Изменим длины всех рёбер графа, прибавив
к длине ребра из 𝑢 в 𝑣 величину 𝜙(𝑣)
−
𝜙(𝑢).
9.1.16. Докажите, что при таком изменении графа кратчайшие пу-
ти сохранятся (кратчайший путь из одной вершины в другую останется
кратчайшим), но их длины изменятся: к длине кратчайшего пути из 𝑝
в 𝑞 прибавится 𝜙(𝑞)
−
𝜙(𝑝).
[Указание. К длине любого пути из 𝑝 в 𝑞 прибавится как раз та же
самая разность 𝜙(𝑞)
−
𝜙(𝑝) (при сложении добавок к длинам рёбер все
промежуточные члены сократятся).]
Эта задача вместе с предыдущими используется в алгоритме, на-
зываемом 𝐴
*
-поиском. Пусть нам надо найти кратчайшее расстояние
от i до j. Возьмём в качестве потенциала некоторую эвристическую
оценку расстояния до j. Тогда рёбра, идущие в сторону уменьшения
этой оценки, станут короче, и поэтому алгоритм будет рассматривать
их в первую очередь. Нужно только, чтобы длина всех рёбер остава-
лась неотрицательной, то есть чтобы длина ребра 𝑢𝑣 была не меньше
𝜙(𝑢)
−
𝜙(𝑣).
9.1.17. Покажите, что если это свойство выполнено, то эвристиче-
ская оценка расстояния будет (гарантированно) нижней оценкой.
[Указание. Как она меняется вдоль кратчайшего пути?]
9.1.18. Пусть рёбра в графе | это дороги, а их длина измеряет-
ся вдоль дороги. Что тогда можно выбрать в качестве такой нижней
оценки?
Ответ. Геометрическое расстояние (по поверхности Земли) до j.

152
9. Разные алгоритмы на графах
9.2. Связные компоненты, поиск в глубину
и ширину
Наиболее простой случай задачи о кратчайших путях | если все
цены равны 0 или +
∞
. Другими словами, мы интересуемся возможно-
стью попасть из 𝑖 в 𝑗, но за ценой не постоим. В других терминах: мы
имеем ориентированный граф (картинку из точек, некоторые из кото-
рых соединены стрелками) и нас интересуют вершины, доступные из
данной.
Для этого случая задачи о кратчайших путях приведённые в пре-
дыдущем разделе алгоритмы | не наилучшие. В самом деле, более бы-
страя рекурсивная программа решения этой задачи приведена в главе
7
,
а нерекурсивная | в главе
6
. Сейчас нас интересует такая задача: не
просто перечислить все вершины, доступные из данной, но перечислить
их в определённом порядке. Два популярных случая | поиск в ширину
и в глубину.
Поиск в ширину.
Надо перечислить все вершины ориентированного графа, доступ-
ные из данной, в порядке увеличения длины пути от неё. (Тем самым мы
решим задачу о кратчайших путях, когда цены рёбер равны 1 или +
∞
.)
9.2.1. Придумайте алгоритм решения этой задачи с числом дей-
ствий не более 𝐶
·
(число рёбер, выходящих из интересующих нас вер-
шин).
Решение. Эта задача рассматривалась в главе
6
, с.
114
. Здесь мы
приведём подробное решение. Пусть 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 вершины;

9.2. Связные компоненты, поиск в глубину и ширину
153
(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). Докажем это.
Обозначим через 𝑉 (𝑘) множество всех вершин, расстояние которых
от i (в описанном смысле) равно 𝑘. Имеет место такое соотношение:
𝑉 (𝑘 + 1) = (концы рёбер с началами в 𝑉 (𝑘))
∖
(𝑉 (0)
∪
. . .
∪
𝑉 (𝑘))
Докажем, что для любого 𝑘 = 0, 1, 2 . . . в ходе работы программы будет
такой момент (после очередной итерации цикла while), когда
в очереди стоят все элементы 𝑉 (𝑘) и только они;
напечатаны все элементы 𝑉 (0), . . . , 𝑉 (𝑘).
(Для 𝑘 = 0 это будет состояние перед циклом.) Рассуждая по индукции,
предположим, что в очереди скопились все элементы 𝑉 (𝑘). Они будут
просматриваться в цикле, пока не кончатся (поскольку новые элемен-
ты добавляются в конец, они не перемешаются со старыми). Концы
ведущих из них рёбер, если они уже не напечатаны, печатаются и ста-
вятся в очередь | то есть всё как в записанном выше соотношении
для 𝑉 (𝑘 + 1). Так что когда все старые элементы кончатся, в очереди
будут стоять все элементы 𝑉 (𝑘 + 1).
Поиск в глубину.
Рассматривая поиск в глубину, удобно представлять себе ориенти-
рованный граф как образ дерева. Более точно, пусть есть ориентиро-
ванный граф, одна из вершин которого выделена. Будем предполагать,

154
9. Разные алгоритмы на графах
что все вершины доступны из выделенной по ориентированным путям.
Построим дерево, которое можно было бы назвать «универсальным на-
крытием» нашего графа. Его корнем будет выделенная вершина графа.
Из корня выходят те же стрелки, что и в графе | их концы будут сы-
новьями корня. Из них в дереве выходят те же стрелки, что и в графе
и так далее. Разница между графом и деревом в том, что пути в гра-
фе, ведущие в одну и ту же вершину, в дереве «расклеены». В других
терминах: вершина дерева | это путь в графе, выходящий из корня.
Её сыновья | это пути, продолженные на одно ребро. Заметим, что
дерево бесконечно, если в графе есть ориентированные циклы.
Имеется естественное отображение дерева в граф (вершин в вер-
шины). При этом каждая вершина графа имеет столько прообразов,
сколько путей в неё ведёт. Поэтому обход дерева (посещение его вершин
в том или ином порядке) одновременно является и обходом графа |
только каждая вершина посещается многократно.
Будем предполагать, что для каждой вершины графа выходящие
из неё рёбра упорядочены (например, пронумерованы). Тем самым для
каждой вершины дерева выходящие из неё рёбра также упорядочены.
Будем обходить дерево так: сначала корень, а потом поддеревья (в по-
рядке ведущих в них рёбер). Такой обход дерева рассматривался нами
в главе
7
. Ему соответствует обход графа. Если выкинуть из этого об-
хода повторные посещения уже посещённых вершин, то получится то,
что называется «поиск в глубину».
Другими словами, на путях, выходящих из выделенной вершины,
введём порядок: путь предшествует своему продолжению; если два пу-
ти расходятся в некоторой вершине, то меньшим считается тот, кото-
рый выходит из неё по меньшему ребру. Вершины теперь упорядочива-
ются в соответствии с минимальными путями, в них ведущими. Обход
вершин графа в указанном порядке называется поиском в глубину.
9.2.2. Напишите программу поиска в глубину.
[Указание. Возьмём программу обхода дерева (корень
→
левое под-
дерево
→
правое поддерево) из главы
7
или из главы
8
и используем
её применительно к обстоятельствам. Главное изменение: не надо по-
сещать вершины повторно. Так что если мы попали в уже посещённую
вершину, то можно с ней ничего не делать. (Если путь не минимален
среди ведущих в данную вершину, то и все его продолжения не мини-
мальны | их просматривать не надо).]
Замечание. Напомним, что в главе
8
упоминались две возможности
устранения рекурсии в программе обхода дерева (с.
142
). Оба варианта
можно использовать для поиска в глубину.

9.2. Связные компоненты, поиск в глубину и ширину
155
Поиск в глубину лежит в основе многих алгоритмов на графах, по-
рой в несколько модифицированном виде.
9.2.3. Неориентированный граф называется двудольным, если его
вершины можно раскрасить в два цвета так, что концы любого ребра |
разного цвета. Составьте алгоритм проверки, является ли заданный
граф двудольным, в котором число действий не превосходит 𝐶
·
(число
рёбер + число вершин).
[Указание. (а) Каждую связную компоненту можно раскрашивать
отдельно. (б) Выбрав цвет одной вершины и обходя её связную компо-
ненту, мы определяем единственно возможный цвет остальных.]
Замечание. В этой задаче безразлично, производить поиск в ширину
или в глубину.
9.2.4. Составьте нерекурсивный алгоритм топологической сорти-
ровки ориентированного графа без циклов. (Рекурсивный алгоритм
см. на с.
128
.)
Решение. Предположим, что граф имеет вершины с номерами 1 . . . n,
для каждой вершины i известно число num[i] выходящих из неё рёбер
и номера вершин dest[i][1], . . . , dest[i][num[i]], в которые эти рё-
бра ведут. Будем условно считать, что рёбра перечислены «слева напра-
во»: левее то ребро, у которого номер меньше. Нам надо напечатать все
вершины в таком порядке, чтобы конец любого ребра был напечатан
перед его началом. Мы предполагаем, что в графе нет ориентирован-
ных циклов | иначе такое невозможно.
Для начала добавим к графу вершину 0, из которой рёбра ведут
в вершины 1, . . . , n. Если её удастся напечатать с соблюдением правил,
то тем самым все вершины будут напечатаны.
Алгоритм хранит путь, выходящий из нулевой вершины и идущий
по рёбрам графа. Переменная l отводится для длины этого пути. Путь
образован вершинами vert[1] . . . vert[l] и рёбрами, имеющими номе-
ра edge[1] . . . edge[l]. Номер edge[s] относится к нумерации рёбер,
выходящих из вершины vert[s]. Тем самым для всех s должны выпол-
няться неравенство
edge[s]
6
num[vert[s]]
и равенство
vert[s+1] = dest [vert[s]] [edge[s]].
Заметим, что конец последнего ребра нашего пути (то есть вершина
dest[vert[l]][edge[l]], не включается в массив vert. Кроме того,

156
9. Разные алгоритмы на графах
для последнего ребра мы делаем исключение, разрешая ему указывать
«в пустоту», т. е. разрешаем edge[l] равняться num[vert[l]]+1.
В процессе работы алгоритм будет печатать номера вершин, при
этом соблюдая требование «вершина напечатана только после тех вер-
шин, в которые из неё ведут рёбра». Кроме того, будет выполняться
такое требование (И):
вершины пути, кроме последней (vert[1] . . . vert[l]) не на-
печатаны, но свернув с пути налево, мы немедленно упира-
емся в напечатанную вершину.
Вот что получается:
l:=1; vert[1]:=0; edge[1]:=1;
while not( (l=1) and (edge[1]=n+1)) do begin
if edge[l]=num[vert[l]]+1 then begin
{путь кончается в пустоте, поэтому все вершины,
следующие за vert[l], напечатаны - можно
печатать vert[l]}
writeln (vert[l]);
l:=l-1; edge[l]:=edge[l]+1;
end else begin
{edge[l] <= num[vert[l]], путь кончается в
вершине}
lastvert:= dest[vert[l]][edge[l]]; {последняя}
if lastvert напечатана then begin
edge[l]:=edge[l]+1;
end else begin
l:=l+1; vert[l]:=lastvert; edge[l]:=1;
end;
end;
end;
{путь сразу же ведёт в пустоту, поэтому все вершины
левее, то есть 1..n, напечатаны}
9.2.5. Докажите, что если в графе нет циклов, то этот алгоритм
заканчивает работу.
Решение. Пусть это не так. Каждая вершина может печататься то-
лько один раз, так что с некоторого момента вершины не печатаются.
В графе без циклов длина пути ограничена (вершина не может входить
в путь дважды), поэтому подождав ещё, мы можем дождаться момен-
та, после которого путь не удлиняется. После этого может разве что
увеличиваться edge[l] | но и это не беспредельно.

9.3. Сети, потоки и разрезы
157
Тем самым мы построили искомый нерекурсивный алгоритм топо-
логической сортировки графа.
9.2.6. Докажите, что время работы этого алгоритма не превосхо-
дит 𝑂(число вершин + число рёбер).
9.2.7. Как модифицировать алгоритм так, чтобы он отыскивал
один из циклов, если таковые имеются, и производил топологическую
сортировку, если циклов нет?
9.3. Сети, потоки и разрезы
В этом разделе мы разберём алгоритм для решения ещё одного типа
задач, связанных с графами.
9.3.1. В пункте 𝐴 добывают нефть, а в пункте 𝐵 её перерабатыва-
ют. Доставка от добычи до переработки происходит по трубам. Около
каждой трубы показана её пропускная способность: сколько единиц
нефти можно по ней прокачать за единицу времени. Какое максималь-
ное количество нефти можно доставить из 𝐴 в 𝐵 за единицу времени
и как это сделать?
𝐴
𝐵
6
4
4
6
1
Решение. Сразу же ясно, что больше 10 из 𝐴 не вывезти (потому что
есть только трубы 4 и 6), да и в 𝐵 не доставить по той же причине. Но
даже и 10 не получится: пришедшие по верхней трубе 6 единиц некуда
девать (максимум можно отправить 5 = 4 + 1). Но 9 единиц пропустить
по сети можно:
𝐴
𝐵
5[6]
4[4]
4[4]
5[6]
1[1]
Около каждой трубы указано направление потока и его величина
(в квадратных скобках | максимально возможная величина).

158
9. Разные алгоритмы на графах
Легко поверить, что это наилучший вариант и что больше 9 единиц
пропустить по сети нельзя, но если кто сомневается, можно объяснить
это так. Проведём в сети границу (пунктирная линия на рисунке), раз-
деляющую 𝐴 и 𝐵.
𝐴
𝐵
4
4
1
Через неё ведут трубы пропускной способности 4, 1, 4, в сумме 9,
так что больше не получится.
В этом разделе мы увидим, что примерно так же обстоит дело и в
общем случае: в любой сети максимально возможный поток ограничен
минимальным разрезом той же величины, и разберём один (самый пер-
вый и самый простой) алгоритм поиска этого потока и этого разреза.
Но прежде чем это всё точно сформулировать и доказать, надо до-
говориться об обозначениях. В нашем примере трубы были «неориенти-
рованные» | они могли работать в обе стороны, и пропускные способ-
ности туда и сюда были одинаковые. Но это не обязательно: будем счи-
тать, что по трубе из узла 𝑖 в узел 𝑗 можно прокачивать 𝑐[𝑖, 𝑗] единиц,
а в обратную сторону 𝑐[𝑗, 𝑖] единиц, и эти границы в принципе могут
быть разными (например, для односторонней трубы одно из этих чи-
сел равно нулю). Мы предполагаем, что узлы сети (= вершины графа)
пронумерованы от 1 до 𝑛, так что 𝑐 будет двумерным массивом чисел.
Эти обозначения вызывают несколько естественных вопросов:
•
Чему равно 𝑐[𝑖, 𝑗], если из 𝑖 в 𝑗 нет трубы? Ответ: отсутствующая
труба | всё равно что труба с нулевой пропускной способностью,
так что мы полагаем 𝑐[𝑖, 𝑗] = 𝑐[𝑗, 𝑖] = 0 в этом случае. (При оценке
времени работы алгоритма нам будет важно, какие рёбра есть, а
каких нет, но пока что можно считать так.)
•
А если из 𝑖 в 𝑗 ведут две трубы? Ответ: такое не разрешается, но
это не важно, потому что несколько труб можно всегда заменить
одной, сложив их пропускные способности.
•
Чему равны 𝑐[𝑖, 𝑖]? Ответ: не имеет значения, но можно считать,
что 𝑐[𝑖, 𝑖] = 0.
Массив 𝑐[𝑖, 𝑗] задаёт сеть (по-английски network), значение 𝑐[𝑖, 𝑗]
называют пропускной способностью (capacity) трубы из 𝑖 в 𝑗. Теперь

9.3. Сети, потоки и разрезы
159
надо договориться, как мы будем представлять и хранить в алгоритме
поток (Ӏow) в этой сети, то есть схему транспортировки. Тут полезна
маленькая хитрость: поток из 𝑗 в 𝑖 мы будем считать потоком из 𝑖 в 𝑗,
но с противоположным знаком. Другими словами, мы будем рассматри-
вать массив 𝑓[𝑖, 𝑗] того же размера, у которого 𝑓[𝑖, 𝑗] =
−
𝑓[𝑗, 𝑖] при всех
𝑖, 𝑗 от 1 до 𝑛. Из этого условия следует, что 𝑓[𝑖, 𝑖] = 0 (и это логич-
но: нам не нужен поток из вершины в себя). Более формально, пусть
фиксированы два разных числа 𝑠 (номер узла-источника) и 𝑡 (номер
узла-потребителя). Иногда 𝑠 называют истоком (source), а 𝑡 называют
стоком (sink). Массив 𝑓 называют потоком в сети 𝑐, если
•
𝑓[𝑖, 𝑗] =
−
𝑓[𝑗, 𝑖] для всех 𝑖, 𝑗 от 1 до 𝑛 (уже обсуждали);
•
𝑓[𝑖, 𝑗]
6
𝑐[𝑖, 𝑗] для всех 𝑖, 𝑗 от 1 до 𝑛 (поток по ребру не превышает
его пропускной способности);
•
∑︀
𝑛
𝑗=1
𝑓[𝑖, 𝑗] = 0 при всех 𝑖, отличных от 𝑠 и 𝑡.
Последнее условие означает, что во всех вершинах, кроме 𝑠 и 𝑡, на-
ша условная нефть не добывается и не теряется | сколько приходит,
столько и уходит. Заметим, что наши соглашения о знаках позволяют
записать это условие, не разделяя входящие и выходящие рёбра, и это
удобно.
9.3.2. Как в этих обозначениях записать сеть и поток из нашего
примера?
Решение. Обозначим верхнюю и нижнюю вершины через 𝐶 и 𝐷 (мы
используем буквы вместо номеров, но понятно, что имеется в виду).
𝑐
𝐴 𝐵 𝐶 𝐷
𝐴
0
0
6
4
𝐵
0
0
4
6
𝐶
6
4
0
1
𝐷
4
6
1
0
𝑓
𝐴
𝐵
𝐶
𝐷
𝐴
0
0
5
4
𝐵
0
0
−
4
−
5
𝐶
−
5
4
0
1
𝐷
−
4
5
−
1
0
Обратите внимание, что матрица 𝑓, как говорят, кососимметрич-
на (симметричные относительно главной диагонали клетки содержат
противоположные числа), а матрица 𝑐 симметрична. Кососимметрич-
ность матрицы 𝑓 | это результат нашего соглашения, что поток из 𝑖
в 𝑗 в нашей бухгалтерии учитывается дважды, со знаком плюс в одной
клетке и со знаком минус в симметричной. На всякий случай ещё раз
подчеркнём, что нет двух отдельных потоков «из 𝑖 в 𝑗» и «из 𝑗 в 𝑖»,
которые можно менять независимо; есть только один поток, который

160
9. Разные алгоритмы на графах
лишь записывается в двух клетках с противоположными знаками. (По-
добно тому, как переток электричества из одной страны в другую одна
страна записывает как экспорт, а другая как импорт.)
А матрица 𝑐 симметрична из-за того, что мы рассматриваем сим-
метричные трубы | и это, в отличие от кососимметричности потока,
не обязательно. Вполне можно было бы рассматривать одностороннюю
трубу (см. ниже).
9.3.3. Какие условия накладываются на поток из 𝑖 в 𝑗, если 𝑐[𝑖, 𝑗] = 2
и 𝑐[𝑗, 𝑖] =
−
2?
Решение. Условия дают 𝑓[𝑖, 𝑗]
6
2 и 𝑓[𝑗, 𝑖] =
−
𝑓[𝑖, 𝑗]
6
−
2, то есть
𝑓[𝑖, 𝑗]
>
2. Таким образом, в этой сети требуется 𝑓[𝑖, 𝑗] = 2, не больше
и не меньше. (Можно представить себе трубу, в которой по каким-то
технологическим причинам нельзя останавливать или даже уменьшать
перекачку ниже максимального уровня.)
9.3.4. Как отразить в наших обозначениях одностороннюю трубу,
по которой можно перекачивать из 𝑖 в 𝑗 не более 2 единиц, а обратно
ничего перекачивать нельзя?
Ответ. 𝑐[𝑖, 𝑗] = 2, 𝑐[𝑗, 𝑖] = 0.
9.3.5. Как записать в терминах 𝑐[𝑖, 𝑗] условие «поток из 𝑖 в 𝑗 должен
быть не меньше 2 и не больше 3»?
Ответ. 𝑐[𝑖, 𝑗] = 3, 𝑐[𝑗, 𝑖] =
−
2.
9.3.6. Что можно сказать о потоке в сети, если 𝑐[𝑖, 𝑗] = 2, 𝑐[𝑗, 𝑖] =
−
3?
Ответ. Такого потока не существует.
Если отрицательные значения 𝑐[𝑖, 𝑗] вас пугают, то можно догово-
риться рассматривать только сети, где 𝑐[𝑖, 𝑗]
>
0 при всех 𝑖, 𝑗. В такой
сети всегда есть поток (нулевой | все требования выполнены). Так
мы и считаем в дальнейшем, если обратное не оговорено явно. Заметь-
те, что среди 𝑓[𝑖, 𝑗] отрицательные числа всё равно будут (если поток
ненулевой) | в силу кососимметричности.
В следующей задаче требуется перевести очевидный факт на мате-
матический язык и доказать его.
9.3.7. Покажите, что для любого потока выполнено равенство
∑︁
𝑖
𝑓[𝑠, 𝑖] =
∑︁
𝑗
𝑓[𝑗, 𝑡].
Что означает это равенство на человеческом языке?

9.3. Сети, потоки и разрезы
161
Решение. Левая часть | это суммарный поток из истока (в принци-
пе туда может что-то и втекать, тогда в этой сумме есть отрицатель-
ные члены), а правая часть | суммарный поток в сток. Равенство, та-
ким образом, можно назвать «законом сохранения материи»; оно верно,
если в сети нет утечек и дополнительных источников (одно из наших
условий).
Общее значение левой и правой части называют суммарной величи-
ной потока 𝑓.
Как это (очевидное) утверждение доказать формально? Вот как:
рассмотрим сумму
∑︀
𝑛
𝑖,𝑗=1
𝑓[𝑖, 𝑗]. Эта сумма равна нулю, так как члены
𝑓[𝑖, 𝑗] и 𝑓[𝑗, 𝑖] сокращаются, а все 𝑓[𝑖, 𝑖] равны нулю. С другой стороны,
её можно переписать как
𝑛
∑︁
𝑖=1
𝑛
∑︁
𝑗=1
𝑓[𝑖, 𝑗].
По определению потока внутренняя сумма равна нулю, кроме случаев
𝑖 = 𝑠 и 𝑖 = 𝑡, так что от всей суммы (равной нулю, напомним) остаётся
0 =
𝑛
∑︁
𝑗=1
𝑓[𝑠, 𝑗] +
𝑛
∑︁
𝑗=1
𝑓[𝑡, 𝑗].
Поскольку 𝑓[𝑡, 𝑗] =
−
𝑓[𝑗, 𝑡], изменяем знаки во втором слагаемом и по-
лучаем искомое равенство.
Теперь мы должны перевести на тот же математический язык ут-
верждение о разрезах. Будем называть разрезом разбиение всех чисел
от 1 до 𝑛 (узлов сети) на два непересекающихся класса 𝑆 и 𝑇 , в котором
исток 𝑠 попадает в 𝑆, а сток 𝑡 попадает в 𝑇 . Будем обозначать такой
разрез (𝑆, 𝑇 ). Пусть, помимо этого, у нас есть поток 𝑓. Тогда можно
посчитать поток через разрез, то есть сумму
∑︁
𝑢
∈
𝑆,𝑣
∈
𝑇
𝑓[𝑢, 𝑣],
которую мы будем обозначать через 𝑓(𝑆, 𝑇 ).
Подсчёт потока через разрез | это именно то, что делает тамо-
женная статистика с потоком товаров через границу. И если товары
производятся в одной стране, а потребляются в другой (и только), то
эта сумма равна производству в истоке и потреблению в стоке. Следу-
ющая задача предлагает доказать это формально.

162
9. Разные алгоритмы на графах
9.3.8. Пусть (𝑆, 𝑇 ) | произвольный разрез сети, а 𝑓 | поток в этой
сети. Докажите, что равенство предыдущей задачи можно дополнить:
∑︁
𝑖
𝑓[𝑠, 𝑖] = 𝑓(𝑆, 𝑇 ) =
∑︁
𝑗
𝑓[𝑗, 𝑡].
Решение. Будем действовать по аналогии с предыдущей задачей:
рассмотрим сумму
∑︁
𝑖
∈
𝑆,𝑗
∈{
1...,𝑛
}
𝑓[𝑖, 𝑗],
но ограничим суммирование только парами (𝑖, 𝑗), для которых 𝑖
∈
𝑆.
Теперь уже сокращения не получится: хотя рёбра, у которых оба конца
в 𝑆, появляются с плюсом и с минусом и по-прежнему сокращаются,
останутся рёбра, у которых 𝑖
∈
𝑆, а 𝑗
∈
𝑇 , им сократиться не с кем,
обратного ребра в сумме нет. Так что от всей суммы останется 𝑓(𝑆, 𝑇 ).
С другой стороны, если переписать сумму как
∑︁
𝑖
∈
𝑆
𝑛
∑︁
𝑗=1
𝑓[𝑖, 𝑗],
то все внутренние суммы равны нулю при 𝑖
̸
= 𝑠, так что останется как
раз поток, выходящий из истока 𝑠.
9.3.9. Повторите рассуждение для потока, входящего в сток.
Заметим, что при подсчёте потока через разрез в сумме могут быть
слагаемые разных знаков. Даже если какой-то товар производится то-
лько в одной стране, и потребляется только в другой, всё равно потоки
через границу могут быть в обе стороны (представьте себе нефтепро-
вод из трёх частей, который идёт зигзагом, сначала пересекая границу,
потом обратно, и потом снова туда). Естественно, что при подсчёте по-
тока слагаемые разного знака полностью или частично сокращаются.
9.3.10. Как изменится поток через разрех, если мы поменяем 𝑆 и 𝑇
(а также исток 𝑠 и сток 𝑡) местами, не меняя массива 𝑓?
Ответ. Изменит знак.
Зная пропускные способности рёбер через разрез, можно ограни-
чить суммарный поток через него:
9.3.11. Пусть дана сеть с пропускными способностями 𝑐[𝑖, 𝑗] и не-
который поток 𝑓[𝑖, 𝑗] в ней. Пусть, с другой стороны, в этой сети есть

9.3. Сети, потоки и разрезы
163
некоторый разрез (𝑆, 𝑇 ). Докажите, что суммарная величина потока не
превосходит пропускной способности разреза, определяемой как
∑︁
𝑢
∈
𝑆,𝑣
∈
𝑇
𝑐[𝑢, 𝑣].
Решение. Доказательство короче формулировки: мы знаем, что сум-
марная величина потока равна потоку через разрез, а он (очевидно) не
превосходит пропускной способности этого разреза.
Заметим, что в сумме, определяющей пропускную способность раз-
реза, все слагаемые неотрицательны (напомним, что мы ограничива-
емся случаем неотрицательных чисел 𝑐[𝑖, 𝑗]) | для потоков это было не
так.
9.3.12. Иногда вместо потоков рассматривают предпотоки, в кото-
рых разрешаются потери перекачиваемой жидкости (но она не может
взяться из ниоткуда). Как изменится определение? Покажите, что не-
смотря на такое пренебрежение экологией, количество жидкости, при-
ходящей в сток, всё равно не превосходит пропускной способности лю-
бого разреза.
Фиксируем некоторую сеть, и будем рассматривать в ней разные
потоки (напомним, что мы считаем 𝑐[𝑖, 𝑗] неотрицательными, так что
нулевой поток всегда существует) и разные разрезы. У каждого потока
есть суммарная величина, а у каждого разреза | пропускная способ-
ность. Задача
9.3.11
утверждает, что все первые не превосходят всех
вторых | по очевидным причинам. Оказывается | и это утверждение
называют теоремой Форда { Фалкерсона, | что это неравенство обра-
щается в равенство для некоторого потока (максимального потока)
и некоторого разреза (минимального разреза). Другими словами, есть
число, которое является одновременно суммарной величиной некоторо-
го потока и пропускной способностью некоторого разреза. Это число
ограничивает сверху любой поток (потому что любой поток ограни-
чен сверху минимальным разрезом) и снизу любой разрез (потому что
любой разрез ограничен снизу максимальным потоком). Так что дей-
ствительно названия «максимальный» и «минимальный» для потоков и
разрезов оправданы.
Мы докажем теорему Форда { Фалкерсона, но не сразу. Начнём с
более слабого утверждения.
9.3.13. Пусть имеется сеть 𝑐 и некоторый поток 𝑓 в ней. Тогда
выполнено одно из двух: либо в сети 𝑐 существует поток большей ве-

164
9. Разные алгоритмы на графах
личины, либо в ней есть разрез, у которого пропускная способность
равна величине потока 𝑓.
(Как мы видели, эти случаи исключают друг друга: если поток ра-
вен некоторому разрезу, то большего потока уже быть не может.)
Это утверждение очевидно следует из теоремы Форда { Фалкерсона:
сравнивая поток с максимальным (который существует по этой теоре-
ме), мы либо можем его увеличить, либо замечаем, что он уже равен
минимальному разрезу. Но обратное рассуждение так просто не про-
ходит (см. обсуждение после решения задачи).
Решение. Основная идея состоит в рассмотрении остаточной сети
(residual network). Представим себе, что по трубе с пропускной способ-
ностью 3 в каком-то направлении идёт поток величины 2. В этом случае
при необходимости можно увеличить этот поток ещё на 1; как говорят,
остаточная пропускная способность этой трубы (в том же направле-
нии) равна 1. Более хитрый пример: пусть есть односторонняя труба
пропускной способности 2, и она полностью использована. Тогда воз-
никает «виртуальная» труба
1
в обратную сторону с той же пропускной
способностью 2: если мы захотим добавить поток в обратном направле-
нии, нужно просто уменьшить исходный поток на соответствующую
величину. Формально говоря, мы рассматриваем остаточную сеть 𝑐
′
,
положив 𝑐
′
[𝑖, 𝑗] = 𝑐[𝑖, 𝑗]
−
𝑓[𝑖, 𝑗]. Заметим, что по определению потока
все значения 𝑐
′
[𝑖, 𝑗] неотрицательны (и нулевой поток в остаточной се-
ти соответствует неизменённому потоку исходной).
9.3.14. Если в двусторонней трубе с пропускной способностью 3
сейчас поток 2 в одну сторону, то каковы пропускные способности
остаточной сети в ту и другую сторону?
Продолжим решение задачи
9.3.13
. Для данной сети 𝑐 и потока 𝑓
в ней рассмотрим остаточную сеть. Построим ориентированный граф,
проведя рёбро из 𝑢 в 𝑣 в тех случаях, когда в остаточной сети ненуле-
вая (положительная) пропускная способность 𝑐[𝑢, 𝑣]. Этот остаточный
граф отражает возможности дополнительных поставок. (Заметьте, что
в нём вполне могут быть одновременно рёбра из 𝑢 в 𝑣 и обратно.) Те-
перь есть два случая:
•
В остаточном графе есть путь из истока 𝑠 в сток 𝑡. Такой
путь называют дополняющим путём (augmenting path), посколь-
ку вдоль него можно пропустить дополнительный поток из 𝑠 в 𝑡.
1
В газотранспортной отрасли это называют «виртуальным реверсом» и много
спорят о законности этого.

9.3. Сети, потоки и разрезы
165
Почему? Посмотрим на положительные остаточные пропускные
способности вдоль этого пути. Возьмём наименьшую из них, пусть
это какое-то 𝛿 > 0. Добавим к исходному потоку дополнительный
поток величины 𝛿, то есть увеличим исходный поток по рёбрам
дополняющего пути на 𝛿, а по другим рёбрам оставим как бы-
ло. (Педантичный читатель или редактор справедливо укажет на
неточность в последнем предложении: если в дополняющий путь
входит ребро из 𝑢 в 𝑣, то мы увеличиваем 𝑓[𝑢, 𝑣] на 𝛿 и уменьшаем
𝑓[𝑣, 𝑢] на 𝛿 в соответствии с нашим соглашением о знаках.) Легко
проверить, что это будет потоком (добавка 𝛿 как вошла, так и
выйдет), и суммарная величина потока увеличится на 𝛿.
•
В остаточном графе нет пути из 𝑠 в 𝑡. Другими словами, верши-
на 𝑡 не входит в число вершин, доступных в этом графе из 𝑠. Тогда
понятно, где «узкое место», в котором надо провести разрез: пусть
𝑆 | вершины, доступные из 𝑠 в остаточном графе (включая сам
исток 𝑠), а 𝑇 | все остальные (включая сток 𝑡). Из 𝑆 в 𝑇 не
ведёт рёбер в остаточном графе (из доступной вершины нельзя
попасть в недоступную, иначе она была бы доступной). Значит,
для рёбер из 𝑆 в 𝑇 их пропускная способность 𝑐[𝑢, 𝑣] использует-
ся потоком 𝑓[𝑢, 𝑣] полностью, и потому пропускная способность
разреза равна потоку 𝑓(𝑆, 𝑇 ) через разрез.
Эти два случая и соответствуют двум вариантам из условия задачи.
9.3.15. В решении есть небольшая неточность: нужно было брать
не просто путь в остаточном графе, а путь, не проходящий дважды по
одному ребру (например, кратчайший). Почему это важно?
Решение. Если путь дважды проходит по ребру, то поток по этому
ребру придётся увеличивать на 2𝛿, а это может превзойти остаточную
пропускную способность.
9.3.16. Докажите, что во втором из рассмотренных случаев (когда
пропускная способность равна величине потока) поток по всем рёбрам
пересекает разрез в одну и ту же сторону, то есть 𝑓[𝑢, 𝑣]
>
0 для всех
𝑢
∈
𝑆, 𝑣
∈
𝑇 .
Решение. Неравенство между потоком и пропускной способностью
получается сложением неравенств 𝑓[𝑢, 𝑣]
6
𝑐[𝑢, 𝑣]; оно обращается в ра-
венство, лишь если все складываемые неравенства обращаются в равен-
ства, и в этом случае 𝑓[𝑢, 𝑣] = 𝑐[𝑢, 𝑣]
>
0 по предположению.
Теперь попробуем доказать теорему Форда { Фалкерсона, то есть
построить поток, равный разрезу (точнее: поток, суммарная величина

166
9. Разные алгоритмы на графах
которого равна пропускной способности некоторого разреза). Будем
рассуждать так. Начнём с произвольного потока (например, нулевого).
Мы только что доказали, что либо его можно увеличить, либо он уже
равен некоторому разрезу. Во втором случае всё хорошо. В первом уве-
личим поток, и снова применим то же рассуждение. Либо поток можно
ещё увеличить, либо есть равный ему разрез | если первое, увеличим
ещё и так далее, пока это не станет невозможным. Когда это случится,
мы получим максимальный поток, равный минимальному разрезу.
9.3.17. В чём ошибка в этом рассуждении?
Решение. Ниоткуда не следует, что этот процесс увеличения когда-
то остановится, так что слова «когда это случится» неоправданно опти-
мистичны.
И это не просто теоретическая возможность, такое реально быва-
ет, если никак не ограничивать выбор дополняющего пути. Начальный
пример Форда { Фалкерсона был довольно сложный, но потом были при-
думаны более простые (Цвик в статье 1995 года построил пример с
6 вершинами и 8 рёбрами и показал, что ни один из параметров нельзя
уменьшить, Theoretical Computer Science, 148(1), 165{170, 1995). Идею
таких примеров понять не так сложно. Представим себе сеть, в кото-
рой есть три ребра небольшой пропускной способности, а кроме этого
много рёбер большой пропускной способности, которые связывают все
остальные пары вершин.
𝑠
𝑡
Конечно, тогда эти рёбра малой пропускной способности не очень-то
и нужны, но мы хотим показать лишь, что при некотором способе вы-
бирать дополняющий путь процесс продолжается бесконечно. Так что
мы имеем право выбирать дополняющий путь как хотим. А именно,
рассмотрим путь, в котором два ребра из трёх проходятся в прямом
направлении, а третье в обратном. Таких путей возьмём три (в зави-
симости от того, какое ребро проходится в обратном направлении), на

9.3. Сети, потоки и разрезы
167
рисунке показан один из трёх.
𝑠
𝑡
Что происходит при дополнении потока по таким путям? Если до
этого рёбра были недогружены на 𝑎, 𝑏, 𝑐, то после этого в двух из них
недогруз уменьшится, а в одном увеличится:
(𝑎, 𝑏, 𝑐)
(𝑎
−
𝛿, 𝑏
−
𝛿, 𝑐+𝛿) или (𝑎
−
𝛿, 𝑏+𝛿, 𝑐
−
𝛿) или (𝑎+𝛿, 𝑏
−
𝛿, 𝑐
−
𝛿)
При этом 𝛿 выбирается максимально возможным, чтобы при дальней-
шем увеличении недогруз уже стал бы отрицательным | то есть од-
но из чисел станет равным нулю. Следующий шаг (указанного вида)
определяется однозначно: надо уменьшать два положительных числа,
увеличивая нулевое, до тех пор, пока наименьшее из двух не обратится
в нуль, и так далее. Легко сообразить, что если после первого шага
недогруз будет (0, 𝛼, 𝛽), где 𝛼 и 𝛽 несоизмеримы (их отношение ирра-
ционально), то процесс будет продолжаться неограниченно.
9.3.18. Покажите, что если 𝛾 обратно золотому сечению, то есть
является (положительным) решением уравнения 𝛾 + 𝛾
2
= 1, то начав с
тройки (0, 1, 𝛾), мы получим тройки (𝛾, 𝛾
2
, 0), (𝛾
3
, 0, 𝛾
2
) и так далее |
так что процесс будет продолжаться бесконечно.
В приведённом выше рассуждении пропущен один момент: почему
остальные рёбра (большой пропускной способности, как мы сказали)
никогда не насытятся? Но видно (особенно в последнем примере), что
увеличение общего потока ограничено, так что если пропускные спо-
собности остальных рёбер достаточно велики, то до их насыщения дело
никогда не дойдёт.
Построенный пример существенным образом использует иррацио-
нальные числа.
9.3.19. Покажите, что в сети с целыми (или хотя бы рациональ-
ными) пропускными способностями аналогичная ситуация невозмож-

168
9. Разные алгоритмы на графах
на: увеличение потока вдоль дополняющего пути, как его ни выбирать,
рано или поздно даст поток, в котором дополняющего пути не будет.
Из этого утверждения (и ранее доказанного) следует теорема Фор-
да { Фалкерсона для частного случая графов с целыми пропускными
способностями.
Решение. Если все пропускные способности целые, и мы начинаем
с нулевого потока, то дробные числа не могут возникнуть (и остаточ-
ные пропускные способности, и минимум их вдоль дополняющего пути
будут целыми, и при вычитании тоже будут только целые числа. Зна-
чит, каждый раз поток увеличивается по крайней мере на 1, и рано
или поздно это кончится (поток ограничен любым разрезом). Для ра-
циональных чисел можно перейти к другой единице измерения потока,
чтобы все числа стали целыми.
В этом рассуждении число шагов может быть большим даже для
маленького графа. Это видно на совсем простом примере.
𝑠
𝑡
𝑝
𝑞
𝑁
𝑁
𝑁
𝑁
1
9.3.20. Покажите, что на графе на рисунке (где 𝑁 | большое це-
лое число) при неудачном выборе дополняющих путей число итераций
будет не меньше 𝑁.
Решение. Будем поочерёдно использовать 𝑠{𝑝{𝑞{𝑡 и 𝑠{𝑞{𝑝{𝑡 в каче-
стве дополняющих путей, начав с нулевого потока. Тогда на первом ша-
ге поток увеличится на 1, а на каждом следующем будет увеличиваться
на 2. Максимальный поток (который вообще не использует ребро 𝑝{𝑞)
равен 2𝑁, так что до него надо сделать как минимум 𝑁 итераций.
(Видно, как неудачный выбор дополняющего пути приводит к долгой
работе в тривиальном примере.)
9.3.21. Рассмотрим сеть с целыми пропускными способностями. До-
кажите, что максимальный поток в ней всегда можно выбрать целочи-
сленным (нецелые потоки могут давать тот же результат, но не могут
давать большего).

9.3. Сети, потоки и разрезы
169
Решение. Описанный процесс увеличения даёт целые потоки | и
когда он закончится, поток равен разрезу, а этого не может превзойти
никакой поток, целый или нет.
Как же найти максимальный поток и минимальный разрез для про-
извольной сети? Самый простой алгоритм для этого, называемый ал-
горитмом Эдмондса { Карпа в честь его изобретателей, следует опи-
санной схеме с единственным добавлением: в качестве дополняющего
пути всегда берётся кратчайший путь из 𝑠 в 𝑡 в остаточном графе.
Мы уже знаем, как быстро искать кратчайший путь, так что это не
проблема. Осталось только доказать, что при этом процесс сойдётся,
и оценить число итераций. Начнём с первого. Вот простое (но невер-
ное!) рассуждение: на каждом шаге одно из рёбер дополняющего пути
используется полностью, и тем самым больше по нему ничего пропу-
стить нельзя. Значит, количество рёбер в остаточном графе каждый
раз уменьшается, и бесконечно так продолжаться не может.
9.3.22. Что неверно в этом рассуждении? (Оно не может быть вер-
ным, так как мы не используем, что дополняющий путь кратчайший.)
Решение. Хотя одно из рёбер дополняющего пути действительно
пропадает, но общее число рёбер может не уменьшиться или даже уве-
личиться, поскольку возникают реверсные рёбра. (Мы видели на при-
мерах, что одно и то же ребро может входить в дополняющий путь то
в одну сторону, то в другую.)
Но тем не менее что-то в таком роде (что остаточный граф посте-
пенно «прореживается») сказать можно.
9.3.23. Выберем какую-то вершину 𝑢 графа и будем следить за рас-
стоянием в остаточном графе от 𝑠 до 𝑢. Докажите, что в ходе алго-
ритма это расстояние не может уменьшаться (а может оставаться не-
изменным или увеличиваться).
Аналогичное утверждение верно и для расстояния от 𝑢 до 𝑡 (симме-
трия).
Решение. Пусть мы сделали несколько шагов алгоритма, и имеется
остаточная сеть (и соответствующий остаточный граф). Расклассифи-
цируем все вершины по длине кратчайшего пути из 𝑠 в этом графе: в
𝑆
0
входит сама вершина 𝑠, в 𝑆
1
| вершины, куда из 𝑠 ведёт ребро, в
𝑆
2
| вершины на расстоянии 2, и так далее. (Эта классификация не
зависит от выбора вершины 𝑢.) Если расстояние от 𝑠 до 𝑢 было равно
какому-то 𝑖, то вершина 𝑢 попадёт в класс 𝑆
𝑖
.

170
9. Разные алгоритмы на графах
Заметим, что кратчайший путь из 𝑠 в 𝑢 должен проходить по оче-
реди через вершины в классах 𝑆
0
, 𝑆
1
, . . . , 𝑆
𝑖
: пропустить класс он не
может, так как на каждом шаге расстояние меняется на 1, а оставать-
ся в том же классе или идти назад нельзя, тогда путь не будет крат-
чайшим. То же самое можно сказать и про рёбра дополняющего пути.
После увеличения потока вдоль дополняющего пути добавятся обрат-
ные рёбра этого пути (если их не было) | и все эти рёбра будут идти
из класса с большим номером в класс с меньшим номером. И потому
их добавление не сократит путь из 𝑠 в 𝑢: даже если вообще добавить
все рёбра, ведущие из класса с большим номером в класс с меньшим
номером, путь не сократится | какой смысл идти в точку, которая
ближе к началу пути, чем текущая?
Так что расстояние или останется прежним, или увеличится (ведь
одно из рёбер дополняющего пути пропало, и другого пути той же
длины может не быть).
Формально говоря, мы не рассмотрели случай, когда расстояние
уже было бесконечным (пути из 𝑠 в 𝑢 не было) и не доказали, что оно
останется бесконечным. Тут надо сказать так: новые рёбра могут вести
только в вершины, доступные из 𝑠, потому новых доступных вершин
не появится.
Как мы уже говорили, на каждом шаге работы алгоритма (увели-
чение потока вдоль дополняющего пути) одно из рёбер дополняющего
пути (то, где пропускная способность минимальна | его ещё назы-
вают критическим ребром) исчезает, заменяясь на противоположное.
Если мы оценим сверху, сколько раз это может происходить с каждым
ребром, то получим и верхнюю оценку для числа шагов (умножив на
общее число рёбер).
9.3.24. Докажите, что одно и то же ребро не может быть критиче-
ским (в ту и в другую сторону) более чем 𝑂(𝑛) раз. (Напомним, что
𝑛 | число вершин.)
Решение. Пусть нас интересует ребро 𝑢{𝑣. Оно может быть крити-
ческим лишь поочерёдно в ту и в другую сторону. Будем следить, как
меняются расстояния от истока до 𝑢 и до 𝑣. Мы уже знаем, что они мо-
гут только возрастать (и не превосходят 𝑛, раз у нас всего 𝑛 вершин).
При этом, когда ребро критическое, одно из расстояний превышает
другое ровно на 1, как мы видели. Остаётся заметить, что если есть
два пешехода, которые идут по дороге в 𝑛 километров, не поворачивая
назад, и в какой-то момент первый обгонял второго на километр, потом
второй первого, потом снова первый второго и так далее, общее число
таких моментов не больше 𝑛 (потому что между соседними моментами

9.3. Сети, потоки и разрезы
171
один из пешеходов должен пройти как минимум два километра, а всего
они проходят 2𝑛).
Отсюда следует, что алгоритм Эдмондса { Карпа всегда завершает
работу, и тем самым мы доказали теорему Форда { Фалкерсона в общем
случае (не только для целых пропускных способностей).
Можно попробовать оценить время работы этого алгоритма. Сразу
видно, что он, как говорят, полиномиальный (время работы ограничено
полиномом от 𝑛), никакого перебора экспоненциального числа вариан-
тов в нём нет. При практической реализации полезно хранить данные
(значения 𝑐 и 𝑓) не про все пары вершин, а только для тех пар, которые
в изначальной сети соединены ребром (и у каждой вершины иметь спи-
сок соседей в исходном графе) | для всех остальных пар и в массиве
𝑐, и в массиве 𝑓 стоят только нули, которые так и остаются нулями.
Если, следуя традиции, обозначать число вершин за 𝑉 , а число рёбер
за 𝐸, то при таком способе хранения данных
•
поиск кратчайшего пути (поиск в ширину) требует 𝑂(𝐸) шагов;
•
коррекция вдоль дополняющего пути требует 𝑂(𝑉 ) шагов (что
поглощается 𝑂(𝐸) шагами поиска);
•
число итераций есть 𝑂(𝐸𝑉 ), потому что каждое из 𝐸 рёбер явля-
ется критическим 𝑂(𝑉 ) раз.
9.3.25. Какое общее число шагов дают эти оценки?
Ответ. Всего получается 𝑂(𝐸
2
𝑉 ).
Есть много более эффективных алгоритмов (построенных на раз-
ных идеях), это большой раздел информатики, но мы ограничимся при-
ведённым простым алгоритмом, и в заключение приведём два примера,
когда этот алгоритм можно использовать для решения других задач.
Первый пример совсем простой.
9.3.26. Рассмотрим сеть без стока и истока, и будем искать в ней
циркуляции (жидкость циркулирует по трубам,
∑︀
𝑗
𝑓[𝑖,𝑗] = 0 при всех 𝑖).
Будем разрешать отрицательные значения функции 𝑐[𝑖, 𝑗] (что означа-
ет, что в некоторых трубах указано минимальное допустимое значение
потока). Как проверить, возможна ли в данной сети циркуляция?
Решение. Добавим к сети отдельные вершины стока и истока, и
соединим их со всеми вершинами исходной сети трубами пропускной
способности 𝑐, где 𝑐 | достаточно большая константа.

172
9. Разные алгоритмы на графах
𝑠
𝑡
Построим в полученной сети некоторый поток. Для этого пустим по
каждой трубе какое-то разрешённое количество жидкости (предпола-
гаем, что для каждой трубы условия на 𝑓[𝑖, 𝑗] и 𝑓[𝑗, 𝑖] не противоречат
друг другу, иначе задача тривиальна), беря эту жидкость при необхо-
димости по трубе из истока и сливая её по трубе в сток. Проблем не
возникнет, поскольку мы предположили, что 𝑐 достаточно велико.
Итак, у нас есть некоторый поток в результирующей сети. Теперь
используем алгоритм Эдмондса { Карпа для его максимизации. Ясно,
что не может получиться больше 𝑐𝑉 , где 𝑉 | число вершин, и что
ровно 𝑐𝑉 получится в том и только том случае, когда в исходной сети
существует циркуляция.
Второй пример | эта задача о максимальном паросочетании в дву-
дольном графе. В адаптированном для школьников варианте её можно
сформулировать так. Есть несколько школьников, каждый из них ре-
шил несколько задач. Надо организовать разбор максимального числа
задач, при этом один и тот же школьник не может выступать дважды,
и нельзя дважды рассказывать одну и ту же задачу.
9.3.27. Схема «кто что решил» показана на рисунке (слева школь-
ники 𝑎, 𝑏, 𝑐, 𝑑, 𝑒, справа задачи 1, 2, 3, 4, 5). Какое максимальное число
задач можно разобрать, соблюдая ограничения?
𝑎
𝑏
𝑐
𝑑
𝑒
1
2
3
4
5
школьники
задачи

9.3. Сети, потоки и разрезы
173
Решение. Можно организовать разбор трёх задач (паросочетание
𝑎{2, 𝑏{1, 𝑒{5, см. рисунок).
Как убедиться, что больше нельзя, не перебирая варианты? Заме-
тим, что школьники 𝑎, 𝑐, 𝑑, 𝑒 не решили ничего, кроме задач 2 и 5 (а
школьник 𝑑 даже и задачу 2 не решил, но это не важно). Поэтому из них
могут выступить только двое | а двое других останутся не у дел.
Терминология: двудольный граф на рисунках состоит из левой доли
(школьники) и правой доли (задачи). Паросочетание (способ разбо-
ра) | набор рёбер, у которых все левые концы разные (ни один школь-
ник не выступает дважды) и все правые концы разные (ни одну задачу
не рассказывают дважды). Аналогичную задачу о максимальном па-
росочетании можно поставить для произвольного двудольного графа
(произвольной схемы соединения вершин слева и справа).
9.3.28. Найдите максимальное паросочетание в произвольном дву-
дольном графе, сведя эту задачу к отысканию максимального потока.
Решение. Будем считать рёбра графа идущими слева направо и име-
ющими неограниченную пропускную способность, и добавим исток сле-
ва и сток справа, соединив их с вершинами односторонними рёбрами с
пропускной способностью 1.
𝑠
𝑡
1
1
1
1
Целочисленный поток в таком графе | это в точности паросоче-
тание. В самом деле, приходящая из истока единица потока должна
куда-то направиться. Поскольку поток целый, то она может пойти то-
лько по одному ребру. И если два таких использованных ребра при-

174
9. Разные алгоритмы на графах
ведут в одну вершину справа, то из неё уже поток не сможет выйти.
А как искать максимальный целочисленный поток, мы знаем, для этого
даже алгоритм Эдмондса { Карпа не нужен, можно использовать любые
дополняющие пути.
В этой задаче дополняющие пути в остаточной сети имеют ясный
смысл: из левой доли мы идём вправо по неиспользованным рёбрам гра-
фа, потом влево по использованным, потом снова вправо по неисполь-
зованным и так далее, поэтому этот алгоритм называют иногда «поиск
максимального паросочетания с помощью чередующихся цепей».
Мы поняли, что (целочисленные) потоки в построенной сети со-
ответствуют паросочетаниям. А чему соответствуют разрезы и что
можно извлечь из совпадения максимального потока и минимального
разреза? Вспомним объяснение про школьников: поток не может быть
большим, потому что есть четыре школьника, которые решили одни и
те же две задачи. Оказывается, что именно такого рода препятствие
есть всегда, и это как раз соответствует разрезу в сети.
Представим себе, что в левой доле, где всего 𝑚 вершин, есть набор
𝑈 из 𝑢 вершин, у которых все их соседи входят в какой-то набор 𝑉 из
меньшего числа вершин 𝑣 в правой доле.
𝑚
𝑛
𝑈
𝑉
𝑢
𝑣
Это означает, что как минимум 𝑢
−
𝑣 вершин слева останутся без дела,
так что максимальное паросочетание не превосходит
𝑚
−
(𝑢
−
𝑣) = 𝑚
−
𝑢 + 𝑣.
Оказывается, что такую оценку всегда можно сделать точной.

9.3. Сети, потоки и разрезы
175
9.3.29. Пусть в двудольном графе (слева 𝑚 вершин, справа 𝑛 вер-
шин) не существует паросочетания размера 𝑘 > 0. Тогда в левой доле
есть набор 𝑈 из 𝑢 вершин, а в правой доле есть набор 𝑉 из 𝑣 вершин, для
которых (1) все соседи вершин из 𝑈 попадают в 𝑉 ; (2) 𝑚
−
𝑢 + 𝑣 < 𝑘.
(Поскольку исходная задача симметрична, можно сформулировать
и симметричное утверждение о вершинах в правой доле и их соседях в
левой доле; это эквивалентно переходу от множеств 𝑈 и 𝑉 к их допол-
нениям.)
Решение. Рассмотрим максимальный разрез | по теореме Фор-
да { Фалкерсона он меньше 𝑘. Левая его компонента 𝑆 содержит исток,
какие-то вершины левой доли (назовём их 𝑈), и какие-то вершины пра-
вой доли (назовём их 𝑉 ).
𝑚
𝑛
𝑈
𝑉
𝑠
𝑡
Заметим, что вершина в 𝑈 не может быть соединена ребром с вер-
шиной не из 𝑉 , потому что тогда это ребро попадает в разрез, а та-
кие рёбра имеют неограниченную (очень большую) пропускную спо-
собность. Пусть в 𝑈 попало 𝑢 вершин, а в 𝑉 попало 𝑣 вершин. Какие
рёбра пересекают разрез? Это 𝑚
−
𝑢 рёбер, которые из истока ведут в
вершины не из 𝑈, а также 𝑣 рёбер, которые из 𝑉 ведут в сток. Все они
имеют пропускную способность 1, поэтому минимальный разрез равен
𝑚
−
𝑢 + 𝑣 и меньше 𝑘 (мы с этого начали).
То же самое утверждение в чуть другой форме:
9.3.30. В школе работает несколько кружков. Требуется в каждом
кружке выбрать старосту из числа участников этого кружка, причём
один человек не может быть старостой двух кружков. Докажите, что
это невозможно в том и только том случае, когда при некотором 𝑢
найдётся 𝑢 кружков, в которых вместе занимается меньше 𝑢 человек.
Решение. Кружки | точки в левой доле, школьники | в правой, а
рёбра ведут от кружка ко всем его участникам.

176
9. Разные алгоритмы на графах
В такой форме это утверждение называют теоремой Холла о пред-
ставителях (староста представляет свой кружок). В одну сторону оно
очевидно: если в 𝑢 кружках всего занимаются меньше 𝑢 человек, то
старост выбрать не удастся. В обратную сторону оно, как мы видели,
следует из теоремы Форда { Фалкерсона. Но можно доказать его и без
неё.
9.3.31. Докажите это обратное утверждение индукцией по числу
кружков, рассмотрев два случая: (1) есть набор из некоторого числа 𝑢
кружков, в которых вместе занимаются ровно 𝑢 школьников, и (2) все-
гда есть запас: для любого семейства кружков общее число школьников
в них больше числа кружков в семействе.
Вот ещё одна переформулировка того же утверждения, называемая
теоремой Кёнига; её преимущество в том, что обе доли графа входят
в неё симметричным образом.
9.3.32. Покажите, что размер максимального паросочетания в дву-
дольном графе равен размеру минимального вершинного покрытия.
(Множество вершин называется вершинным покрытием, если у любо-
го ребра хотя бы один конец принадлежит этому множеству. Вершины
можно выбирать из обеих долей.)
Следующую задачу можно найти в сборниках олимпиадных задач
для школьников, но, по-видимому, её решение по существу требует те-
оремы Холла в том или ином виде (а особенно просто её решить, зная
о потоках и разрезах).
9.3.33. На контрольной каждый школьник решил 5 задач, и каждую
задачу решило 5 школьников. Докажите, что можно организовать раз-
бор так, чтобы каждый школьник рассказал одну из решённых им задач
и все задачи были бы разобраны.
[Указание. Число задач равно числу школьников (посчитаем реше-
ния двумя способами), обозначим его за 𝑛. В соответствующем графе
есть дробный поток величины 𝑛, в котором каждая задача рассказы-
вается с весом 1/5, значит, есть и целый поток такой величины. (Если
избегать упоминания потоков, то можно заметить, что препятствие к
разбору всех задач из теоремы Холла невозможно, потому что в этом
случае из 𝑈 выходит больше рёбер, чем может зайти в 𝑉 .)]

10. СОПОСТАВЛЕНИЕ
С ОБРАЗЦОМ
10.1. Простейший пример
10.1.1. Имеется последовательность символов x[1] . . . x[n]. Опреде-
лите, имеются ли в ней идущие друг за другом символы abcd. (Други-
ми словами, требуется выяснить, есть ли в слове x[1] . . . x[n] подслово
abcd.)
Решение. Имеется примерно n (если быть точным, n-3) позиций,
на которых может находиться искомое подслово в исходном слове. Для
каждой из позиций можно проверить, действительно ли там оно нахо-
дится, сравнив четыре символа. Однако есть более эффективный спо-
соб. Читая слово x[1] . . . x[n] слева направо, мы ожидаем появления бу-
квы a. Как только она появилась, мы ищем за ней букву b, затем c, и,
наконец, d. Если наши ожидания оправдываются, то слово abcd обнару-
жено. Если же какая-то из нужных букв не появляется, мы оказываемся
у разбитого корыта и начинаем всё сначала.
Этот простой алгоритм можно описать в разных терминах. Ис-
пользуя терминологию так называемых конечных автоматов, мож-
но сказать, что при чтении слова x слева направо мы в каждый мо-
мент находимся в одном из следующих состояний: «начальное» (0),
«сразу после a» (1), «сразу после ab» (2), «сразу после abc» (3) и «сра-
зу после abcd» (4). Читая очередную букву, мы переходим в следу-
ющее состояние по правилу, указанному в таблице (см. следующую
страницу). Как только мы попадём в состояние 4, работа заканчива-
ется.
Наглядно выполнение алгоритма можно представить себе так: фиш-
ка двигается из кружка в кружок по стрелкам; стрелка выбирается так,
чтобы надпись на ней соответствовала очередной букве входного слова.
Чтобы этот процесс был успешным, нужно, чтобы для каждой буквы

178
10. Сопоставление с образцом
Текущее
Очередная
Новое
состояние
буква
состояние
0
a
1
0
кроме a
0
1
b
2
1
a
1
1
кроме a,b
0
2
c
3
2
a
1
2
кроме a,c
0
3
d
4
3
a
1
3
кроме a,d
0
Правила перехода для конечного автомата
была ровно одна подходящая стрелка из любого кружка.
0
1
2
3
4
𝑎
𝑎
𝑎
̸
= 𝑎, 𝑑
̸
= 𝑎, 𝑐
̸
= 𝑎, 𝑏
̸
= 𝑎
𝑎
𝑏
𝑐
𝑑
начало
Соответствующая программа очевидна (мы указываем новое состо-
яние, даже если оно совпадает со старым; эти строки можно опустить):
i:=1; state:=0;
{i - первая непрочитанная буква, state - состояние}
while (i <> n+1) and (state <> 4) do begin
if state = 0 then begin
if x[i] = a then begin
state:= 1;
end else begin
state:= 0;
end;
end else if state = 1 then begin
if x[i] = b then begin
state:= 2;
end else if x[i] = a then begin
state:= 1;

10.1. Простейший пример
179
end else begin
state:= 0;
end;
end else if state = 2 then begin
if x[i] = c then begin
state:= 3;
end else if x[i] = a then begin
state:= 1;
end else begin
state:= 0;
end;
end else if state = 3 then begin
if x[i] = d then begin
state:= 4;
end else if x[i] = a then begin
state:= 1;
end else begin
state:= 0;
end;
end;
end;
answer := (state = 4);
Иными словами, мы в каждый момент храним информацию о том,
какое максимальное начало нашего образца abcd является концом про-
читанной части. (Его длина и есть то «состояние», о котором шла речь.)
Терминология, нами используемая, такова. Слово | это любая по-
следовательность символов из некоторого фиксированного конечного
множества. Это множество называется алфавитом, его элементы |
буквами. Если отбросить несколько букв с конца слова, останется дру-
гое слово, называемое началом первого. Любое слово также считает-
ся своим началом. Конец слова | то, что останется, если отбросить
несколько первых букв. Любое слово считается своим концом. Подсло-
во | то, что останется, если отбросить буквы и с начала, и с конца.
(Другими словами, подслова | это концы начал, или, что то же, начала
концов.)
В терминах индуктивных функций (см. раздел
1.3
) ситуацию можно
описать так: рассмотрим функцию на словах, которая принимает два
значения «истина» и «ложь» и истинна на словах, имеющих abcd своим
подсловом. Эта функция не является индуктивной, но имеет индуктив-
ное расширение
𝑥
↦→
длина максимального начала слова abcd, являющегося концом 𝑥.

180
10. Сопоставление с образцом
10.2. Повторения в образце | источник
проблем
10.2.1. Можно ли в предыдущих рассуждениях заменить слово abcd
на произвольное слово?
Решение. Нет, и проблемы связаны с тем, что в образце могут быть
повторяющиеся буквы. Пусть, например, мы ищем вхождения слова
ababc. Вот появилась буква a, за ней идёт b, за ней идёт a, затем снова b.
В этот момент мы с нетерпением ждём буквы c. Однако | к нашему
разочарованию | вместо неё появляется другая буква, и наш образец
ababc не обнаружен. Однако нас может ожидать утешительный приз:
если вместо c появилась буква a, то не всё потеряно: за ней могут по-
следовать буквы b и c, и образец-таки будет найден.
Вот картинка, поясняющая сказанное:
x y z a b a b a b c . . .
←
входное слово
a b a b c
←
мы ждали образца здесь
a b a b c
←
а он оказался здесь
Таким образом, к моменту
x y z a b a b
←
входное слово
a b a b c
←
мы ждали образца здесь
a b a b c
←
а он оказался здесь
есть два возможных положения образца, каждое из которых подлежит
проверке. Тем не менее по-прежнему возможен конечный автомат, чи-
тающий входное слово буква за буквой и переходящий из состояния
в состояние в зависимости от прочитанных букв.
10.2.2. Укажите состояния соответствующего автомата и табли-
цу перехода (новое состояние в зависимости от старого и читаемой
буквы).
Решение. По-прежнему состояния будут соответствовать наиболь-
шему началу образца, являющемуся концом прочитанной части слова.
Их будет шесть: 0, 1 (a), 2 (ab), 3 (aba), 4 (abab), 5 (ababc). Таблица
перехода показана на следующей странице.

10.2. Повторения в образце | источник проблем
181
Текущее
Очередная Новое
состояние буква
состояние
0
a
1 (a)
0
кроме a
0
1 (a)
b
2 (ab)
1 (a)
a
1 (a)
1 (a)
кроме a,b
0
2 (ab)
a
3 (aba)
2 (ab)
кроме a
0
3 (aba)
b
4 (abab)
3 (aba)
a
1 (a)
3 (aba)
кроме a,b
0
4 (abab)
c
5 (ababc)
4 (abab)
a
3 (aba)
4 (abab)
кроме a,c
0
Для проверки посмотрим, к примеру, на вторую снизу строку. Ес-
ли прочитанная часть кончалась на abab, а затем появилась буква a,
то теперь прочитанная часть кончается на ababa. Наибольшее начало
образца (ababc), являющееся её концом | это aba.
Философский вопрос: мы говорили, что трудность состоит в том,
что есть несколько возможных положений образца, каждое из которых
может оказаться истинным. Им соответствуют несколько начал образ-
ца, являющихся концами входного слова. Но конечный автомат помнит
лишь самое длинное из них. Как же остальные?
Философский ответ. Дело в том, что самое длинное из них опре-
деляет все остальные | это его концы, одновременно являющиеся его
началами.
Не составляет труда для любого конкретного образца написать про-
грамму, осуществляющую поиск этого образца описанным способом.
Однако хотелось бы написать программу, которая ищет произволь-
ный образец в произвольном слове. Это можно делать в два этапа:
сначала по образцу строится таблица переходов конечного автомата,
а затем читается входное слово и состояние преобразуется в соответ-
ствии с этой таблицей. Подобный метод часто используется для бо-
лее сложных задач поиска (см. далее), но для поиска подслова суще-
ствует более простой и эффективный алгоритм, называемый алгорит-
мом Кнута { Морриса { Пратта. (Ранее сходные идеи были предложены
Ю. В. Матиясевичем.) Но прежде нам понадобятся некоторые вспомо-
гательные утверждения.

182
10. Сопоставление с образцом
10.3. Вспомогательные утверждения
Для произвольного слова 𝑋 рассмотрим все его начала, одновре-
менно являющиеся его концами, и выберем из них самое длинное. (Не
считая, конечно, самого слова 𝑋.) Будем обозначать его 𝑙(𝑋).
Примеры: 𝑙(aba) = a, 𝑙(abab) = ab, 𝑙(ababa) = aba, 𝑙(abc) = пустое
слово.
10.3.1. Докажите, что все слова 𝑙(𝑋), 𝑙(𝑙(𝑋)), 𝑙(𝑙(𝑙(𝑋))) и т. д. явля-
ются началами слова 𝑋.
Решение. Каждое из них (согласно определению) является началом
предыдущего.
По той же причине все они являются концами слова 𝑋.
10.3.2. Докажите, что последовательность предыдущей задачи об-
рывается (на пустом слове).
Решение. Каждое слово короче предыдущего.
10.3.3. Докажите, что любое слово, одновременно являющееся нача-
лом и концом слова 𝑋 (кроме самого 𝑋) входит в последовательность
𝑙(𝑋), 𝑙(𝑙(𝑋)), . . .
Решение. Пусть слово 𝑌 есть одновременно начало и конец 𝑋. Слово
𝑙(𝑋) | самое длинное из таких слов, так что 𝑌 не длиннее 𝑙(𝑋). Оба эти
слова являются началами 𝑋, поэтому более короткое из них является
началом более длинного: 𝑌 есть начало 𝑙(𝑋). Аналогично, 𝑌 есть конец
𝑙(𝑋). Рассуждая по индукции, можно предполагать, что утверждение
задачи верно для всех слов короче 𝑋, в частности, для слова 𝑙(𝑋). Так
что слово 𝑌 , являющееся концом и началом 𝑙(𝑋), либо равно 𝑙(𝑋), либо
входит в последовательность 𝑙(𝑙(𝑋)), 𝑙(𝑙(𝑙(𝑋))),. . . , что и требовалось
доказать.
10.4. Алгоритм Кнута { Морриса { Пратта
Алгоритм Кнута { Морриса { Пратта (КМП) получает на вход слово
X = x[1]x[2] . . . x[n]
и просматривает его слева направо буква за буквой, заполняя при этом
массив натуральных чисел l[1] . . . l[n], где
l[i] = длина слова 𝑙(x[1] . . . x[i])

10.4. Алгоритм Кнута { Морриса { Пратта
183
(функция 𝑙 определена в предыдущем пункте). Словами: l[i] есть дли-
на наибольшего начала слова x[1] . . . x[i], одновременно являющегося
его концом.
10.4.1. Какое отношение всё это имеет к поиску подслова? Други-
ми словами, как использовать алгоритм КМП для определения того,
является ли слово A подсловом слова B?
Решение. Применим алгоритм КМП к слову A#B, где # | специаль-
ная буква, не встречающаяся ни в A, ни в B. Слово A является подсловом
слова B тогда и только тогда, когда среди чисел в массиве l будет число,
равное длине слова A.
10.4.2. Опишите алгоритм заполнения таблицы l[1] . . . l[n].
Решение. Предположим, что первые i значений l[1] . . . l[i] уже
найдены. Мы читаем очередную букву слова (т. е. x[i+1]) и должны
вычислить l[i+1].
1
i i+1
уже прочитанная часть x
⏟
⏞
𝑍
⏟
⏞
𝑍
Другими словами, нас интересуют начала 𝑍 слова x[1] . . . x[i+1],
одновременно являющиеся его концами | из них нам надо выбрать
самое длинное. Откуда берутся эти начала? Каждое из них (не счи-
тая пустого) получается из некоторого слова 𝑍
′
приписыванием буквы
x[i+1]. Слово 𝑍
′
является началом и концом слова x[1] . . . x[i]. Одна-
ко не любое слово, являющееся началом и концом слова x[1] . . . x[i],
годится | надо, чтобы за ним следовала буква x[i+1].
Получаем такой рецепт отыскания слова 𝑍. Рассмотрим все нача-
ла слова x[1] . . . x[i], являющиеся одновременно его концами. Из них
выберем подходящие | те, за которыми идёт буква x[i+1]. Из подхо-
дящих выберем самое длинное. Приписав в его конец x[i+1], получим
искомое слово 𝑍.
Теперь пора воспользоваться сделанными нами приготовлениями
и вспомнить, что все слова, являющиеся одновременно началами и кон-
цами данного слова, можно получить повторными применениями к нему
функции 𝑙 из предыдущего раздела. Вот что получается:
i:=1; l[1]:= 0;
{таблица l[1]..l[i] заполнена правильно}
while i <> n do begin
len := l[i]

184
10. Сопоставление с образцом
{len - длина начала слова x[1]..x[i], которое является
его концом; все более длинные начала оказались
неподходящими}
while (x[len+1] <> x[i+1]) and (len > 0) do begin
{начало не подходит, применяем к нему функцию l}
len := l[len];
end;
{нашли подходящее или убедились в отсутствии}
if x[len+1] = x[i+1] do begin
{x[1]..x[len] - самое длинное подходящее начало}
l[i+1] := len+1;
end else begin
{подходящих нет}
l[i+1] := 0;
end;
i := i+1;
end;
10.4.3. Докажите, что число действий в приведённом только что
алгоритме не превосходит 𝐶n для некоторой константы 𝐶.
Решение. Это не вполне очевидно: обработка каждой очередной бу-
квы может потребовать многих итераций во внутреннем цикле. Однако
каждая такая итерация уменьшает len по крайней мере на 1, и в этом
случае l[i+1] окажется заметно меньше l[i]. С другой стороны, при
увеличении i на единицу величина l[i] может возрасти не более чем
на 1, так что часто и сильно убывать она не может | иначе убывание
не будет скомпенсировано возрастанием.
Более точно, можно записать неравенство
l[i+1]
6
l[i]
−
(число итераций на i-м шаге) + 1
или
(число итераций на i-м шаге)
6
l[i]
−
l[i+1] + 1.
Остаётся сложить эти неравенства по всем i и получить оценку сверху
для общего числа итераций.
10.4.4. Будем использовать этот алгоритм, чтобы выяснить, явля-
ется ли слово X длины n подсловом слова Y длины m. (Как это делать
с помощью специального разделителя #, описано выше.) При этом чи-
сло действий будет не более 𝐶(n + m), и используемая память тоже.
Придумайте, как обойтись памятью не более 𝐶n (что может быть су-
щественно меньше, если искомый образец короткий, а слово, в котором
его ищут | длинное).

10.5. Алгоритм Бойера { Мура
185
Решение. Применяем алгоритм КМП к слову A#B. При этом вычи-
сление значений l[1], . . . , l[n] проводим для слова X длины n и запо-
минаем эти значения. Дальше мы помним только значение l[i] для
текущего i | кроме него и кроме таблицы l[1] . . . l[n], нам для вы-
числений ничего не нужно.
На практике слова X и Y могут не находиться подряд, поэтому про-
смотр слова X и затем слова Y удобно оформить в виде разных циклов.
Это избавляет также от хлопот с разделителем.
10.4.5. Напишите соответствующий алгоритм (проверяющий, явля-
ется ли слово X = x[1] . . . x[n] подсловом слова Y = y[1] . . . y[m]).
Решение. Сначала вычисляем таблицу l[1] . . . l[n] как раньше. За-
тем пишем такую программу:
j:=0; len:=0;
{len - длина максимального начала слова X, одновременно
являющегося концом слова y[1]..y[j]}
while (len <> n) and (j <> m) do begin
while (x[len+1] <> y[j+1]) and (len > 0) do begin
{начало не подходит, применяем к нему функцию l}
len := l[len];
end;
{нашли подходящее или убедились в отсутствии}
if x[len+1] = y[j+1] do begin
{x[1]..x[len] - самое длинное подходящее начало}
len := len+1;
end else begin
{подходящих нет}
len := 0;
end;
j := j+1;
end;
{если len=n, слово X встретилось; иначе мы дошли до конца
слова Y, так и не встретив X}
10.5. Алгоритм Бойера { Мура
Этот алгоритм делает то, что на первый взгляд кажется невозмож-
ным: в типичной ситуации он читает лишь небольшую часть всех букв
слова, в котором ищется заданный образец. Как так может быть? Идея
проста. Пусть, например, мы ищем образец abcd. Посмотрим на четвёр-
тую букву слова: если, к примеру, это буква e, то нет никакой необхо-

186
10. Сопоставление с образцом
димости читать первые три буквы. (В самом деле, в образце буквы e
нет, поэтому он может начаться не раньше пятой буквы.)
Мы приведём самый простой вариант этого алгоритма, который не
гарантирует быстрой работы во всех случаях. Пусть x[1] . . . x[n] |
образец, который надо искать. Для каждого символа s найдём самое
правое его вхождение в слово X, то есть наибольшее k, при котором
x[k] = s. Эти сведения будем хранить в массиве pos[s]; если символ s
вовсе не встречается, то нам будет удобно положить pos[s] = 0 (мы
увидим дальше, почему).
10.5.1. Как заполнить массив pos?
Решение.
положить все pos[s] равными 0
for i:=1 to n do begin
pos[x[i]]:=i;
end;
В процессе поиска мы будем хранить в переменной last номер бу-
квы в слове, против которой стоит последняя буква образца. Вначале
last = n (длина образца), затем last постепенно увеличивается.
last:=n;
{все предыдущие положения образца уже проверены}
while last <= m do begin {слово не кончилось}
if x[n] <> y[last] then begin {последние буквы разные}
last := last + (n - pos[y[last]]);
{n - pos[y[last]] - это минимальный сдвиг образца,
при котором напротив y[last] встанет такая же
буква в образце. Если такой буквы нет вообще,
то сдвигаем на всю длину образца}
end else begin
если нынешнее положение подходит, т.е. если
x[1]..x[n] = y[last-n+1]..y[last],
то сообщить о совпадении;
last := last+1;
end;
end;
Знатоки рекомендуют проверку совпадения проводить справа налево,
т. е. начиная с последней буквы образца (в которой совпадение заведомо
есть). Можно также немного сэкономить, произведя вычитание заранее
и храня не pos[s], а n-pos[s], т. е. число букв в образце справа от
последнего вхождения буквы s.

10.6. Алгоритм Рабина
187
Возможны разные модификации этого алгоритма. Например, можно
строку last:=last+1 заменить на last:=last+(n-u), где u | коорди-
ната второго справа вхождения буквы x[n] в образец.
10.5.2. Как проще всего учесть это в программе?
Решение. При построении таблицы pos написать
for i:=1 to n-1 do...
(далее как раньше), а в основной программе вместо last:=last+1 на-
писать
last:= last+n-pos[y[last]];
Приведённый нами упрощённый вариант алгоритма Бойера { Мура
в некоторых случаях требует существенно больше n действий (число
действий порядка mn), проигрывая алгоритму Кнута { Морриса { Прат-
та.
10.5.3. Приведите пример ситуации, в которой образец не входит
в слово, но алгоритму требуется порядка mn действий, чтобы это уста-
новить.
Решение. Пусть образец имеет вид baaa . . . aa, а само слово состоит
только из букв a. Тогда на каждом шаге несоответствие выясняется
лишь в последний момент.
Настоящий (не упрощённый) алгоритм Бойера { Мура гарантиру-
ет, что число действий не превосходит 𝐶(m + n) в худшем случае. Он
использует идеи, близкие к идеям алгоритма Кнута { Морриса { Прат-
та. Представим себе, что мы сравнивали образец со входным словом,
идя справа налево. При этом некоторый кусок 𝑍 (являющийся концом
образца) совпал, а затем обнаружилось различие: перед 𝑍 в образце
стоит не то, что во входном слове. Что можно сказать в этот момент
о входном слове? В нём обнаружен фрагмент, равный 𝑍, а перед ним
стоит не та буква, что в образце. Эта информация может позволить
сдвинуть образец на несколько позиций вправо без риска пропустить
его вхождение. Эти сдвиги следует вычислить заранее для каждого
конца 𝑍 нашего образца. Как говорят знатоки, всё это (вычисление та-
блицы сдвигов и её использование) можно уложить в 𝐶(m + n) действий.
10.6. Алгоритм Рабина
Этот алгоритм основан на простой идее. Представим себе, что в сло-
ве длины 𝑚 мы ищем образец длины 𝑛. Вырежем окошечко размера 𝑛

188
10. Сопоставление с образцом
и будем двигать его по входному слову. Нас интересует, не совпадает
ли слово в окошечке с заданным образцом. Сравнивать по буквам долго.
Вместо этого фиксируем некоторую функцию, определённую на словах
длины 𝑛. Если значения этой функции на слове в окошечке и на образце
различны, то совпадения нет. Только если значения одинаковы, нужно
проверять совпадение по буквам.
Что мы выигрываем при таком подходе? Казалось бы, ничего |
ведь чтобы вычислить значение функции на слове в окошечке, всё рав-
но нужно прочесть все буквы этого слова. Так уж лучше их сразу срав-
нить с образцом. Тем не менее выигрыш возможен, и вот за счёт чего.
При сдвиге окошечка слово не меняется полностью, а лишь добавляется
буква в конце и убирается в начале. Хорошо бы, чтобы по этим данным
можно было рассчитать, как меняется функция.
10.6.1. Приведите пример удобной для вычисления функции.
Решение. Заменим все буквы в слове и образце их номерами, пред-
ставляющими собой целые числа. Тогда удобной функцией является
сумма цифр. (При сдвиге окошечка нужно добавить новое число и вы-
честь пропавшее.)
Для каждой функции существуют слова, к которым она примени-
ма плохо. Зато другая функция в этом случае может работать хорошо.
Возникает идея: надо запасти много функций и в начале работы алго-
ритма выбирать из них случайную. (Тогда враг, желающий подгадить
нашему алгоритму, не будет знать, с какой именно функцией ему бо-
роться.)
10.6.2. Приведите пример семейства удобных функций.
Решение. Выберем некоторое число 𝑝 (желательно простое, см. да-
лее) и некоторый вычет 𝑥 по модулю 𝑝. Каждое слово длины 𝑛 будем
рассматривать как последовательность целых чисел (заменив буквы ко-
дами). Эти числа будем рассматривать как коэффициенты многочле-
на степени 𝑛
−
1 и вычислим значение этого многочлена по модулю 𝑝
в точке 𝑥. Это и будет одна из функций семейства (для каждой пары 𝑝
и 𝑥 получается, таким образом, своя функция). Сдвиг окошка на 1 со-
ответствует вычитанию старшего члена (𝑥
𝑛
−
1
следует вычислить за-
ранее), умножению на 𝑥 и добавлению свободного члена.
Следующее соображение говорит в пользу того, что совпадения не
слишком вероятны. Пусть число 𝑝 фиксировано и к тому же простое,
а 𝑋 и 𝑌 | два различных слова длины 𝑛. Тогда им соответствуют раз-
личные многочлены (мы предполагаем, что коды всех букв различны |

10.7. Более сложные образцы и автоматы
189
это возможно, если 𝑝 больше числа букв алфавита). Совпадение значе-
ний функции означает, что в точке 𝑥 эти два различных многочлена
совпадают, то есть их разность обращается в 0. Разность есть много-
член степени 𝑛
−
1 и имеет не более 𝑛
−
1 корней. Таким образом, если
𝑛 много меньше 𝑝, то случайному 𝑥 мало шансов попасть в неудачную
точку.
10.7. Более сложные образцы и автоматы
Мы можем искать не конкретное слово, а подслова заданного вида.
Например, можно искать слова вида a?b, где вместо ? может стоять
любая буква (иными словами, нас интересует буква b на расстоянии 2
после буквы a).
10.7.1. Укажите конечный автомат, проверяющий, есть ли во вход-
ном слове фрагмент вида a?b.
Решение. Читая слово, следует помнить, есть ли буква a на послед-
нем месте и на предпоследнем | пока не встретим искомый фрагмент.
Автомат имеет состояния 00, 01, 10, 11, их смысл таков:
00 на предпоследнем и последнем местах нет a
01 на предпоследнем нет, на последнем есть
10 не предпоследнем есть, на последнем нет
11 есть и там, и там
Таблица переходов автомата:
Текущее
Очередная
Новое
состояние
буква
состояние
00
a
01
00
не a
00
01
a
11
01
не a
10
10
a
01
10
b
найдено
10
не a и не b
00
11
a
11
11
b
найдено
11
не a и не b
10
Другой стандартный знак в образце | это звёздочка (*), на ме-
сто которой может быть подставлено любое слово. Например, образец

190
10. Сопоставление с образцом
ab*cd означает, что мы ищем подслово ab, за которым следует что
угодно, а затем (на любом расстоянии) идёт cd.
10.7.2. Укажите конечный автомат, проверяющий, есть ли во вход-
ном слове образец ab*cd (в описанном только что смысле).
Решение.
Текущее
Очередная
Новое
состояние
буква
состояние
начальное
a
a
начальное
не a
начальное
a
b
ab
a
a
a
a
не a и не b начальное
ab
c
abc
ab
не c
ab
abc
d
найдено
abc
c
abc
abc
не c и не d
ab
Ещё один вид поиска | это поиск любого из слов некоторого списка.
10.7.3. Дан список слов 𝑋
1
, . . . , 𝑋
𝑘
и слово 𝑌 . Как определить, вхо-
дит ли хотя бы одно из слов 𝑋
𝑖
в слово 𝑌 (как подслово)? Количество
действий не должно превосходить константы, умноженной на суммар-
ную длину всех слов (из списка и того, в котором происходит поиск).
Решение. Очевидный способ состоит в том, чтобы каждое слово
из списка проверять отдельно (с помощью одного из рассмотренных
алгоритмов). Однако при этом мы не укладываемся в заданное число
действий (из-за умножения 𝑘 на длину слова 𝑌 ).
Посмотрим на дело с другой стороны. Каждому образцу из списка
соответствует конечный автомат с некоторым множеством состояний.
Эти автоматы можно объединить в один, множеством состояний ко-
торого будет произведение множеств состояний всех тех автоматов.
Это | очень большое множество. Однако на самом деле большинство
его элементов недоступны (не могут появиться при чтении входного
слова) и за счёт этого получается экономия. Примерно эту идею (но
в изменённом виде) мы и будем использовать.
Вспомним алгоритм Кнута { Морриса { Пратта. В нём, читая вход-
ное слово, мы хранили наибольшее начало образца, являющееся кон-
цом прочитанной части. Теперь нам следует хранить для каждого из

10.7. Более сложные образцы и автоматы
191
образцов наибольшее его начало, являющееся концом прочитанной ча-
сти. Решающим оказывается такое замечание: достаточно хранить са-
мое длинное из них | все остальные по нему восстанавливаются (как
наибольшие начала образцов, являющиеся его концами).
Склеим все образцы в дерево, объединив их совпадающие начальные
участки. Например, набору образцов
{
aaa, aab, abab
}
соответствует дерево
r
-
a
r
-
H
H
H
H
H
j
a
b
r
-
*
a
r
-
b
a
r
-
b
r
r
r
Формально говоря, вершинами дерева являются все начала всех образ-
цов, а сыновья вершины получаются приписыванием буквы.
Читая входное слово, мы двигаемся по этому дереву: текущая вер-
шина | это наибольшая (самая правая) из вершин, являющихся концом
прочитанной части ( = наибольший конец прочитанной части, являю-
щийся началом одного из образцов).
Определим функцию 𝑙, аргументами и значениями которой являют-
ся вершины дерева. Именно, 𝑙(𝑃 ) = наибольшая вершина дерева, явля-
ющаяся концом 𝑃 . (Напомним, вершины дерева | это слова.) Нам по-
надобится такое утверждение:
10.7.4. Пусть 𝑃 | вершина дерева. Докажите, что множество всех
вершин, являющихся концами 𝑃 , равно
{
𝑙(𝑃 ), 𝑙(𝑙(𝑃 )), . . .
}
Решение. См. доказательство аналогичного утверждения для алго-
ритма Кнута { Морриса { Пратта.
Теперь ясно, что нужно делать, находясь в вершине 𝑃 и читая бу-
кву z входного слова. Надо просматривать последовательно верши-
ны 𝑃 , 𝑙(𝑃 ), 𝑙(𝑙(𝑃 )),. . . , пока не обнаружится такая, из которой выходит
стрелка с буквой z. Та вершина, в которую эта стрелка ведёт, и будет
нашим следующим положением.
Остаётся понять, как для каждой вершины дерева вычислить указа-
тель на значение функции 𝑙 в этой вершине. Это делается как раньше,
при этом значения 𝑙 для более коротких слов используются при вычисле-
нии очередного значения функции 𝑙. Это означает, что вершины дерева
следует просматривать в порядке возрастания их длины. Нетрудно по-
нять, что всё это можно уложить в требуемое число действий (хотя

192
10. Сопоставление с образцом
константа зависит от числа букв в алфавите). Относящиеся к этому
подробности см. в главе
9
.
Можно поинтересоваться, какие свойства слов распознаются с по-
мощью конечных автоматов. Оказывается, что существует просто опи-
сываемый класс образцов, задающий все такие свойства | класс регу-
лярных выражений.
Определение. Пусть фиксирован конечный алфавит `, не содержа-
щий символов ˜, 𝜀, (, ), * и | (они будут использоваться для построения
регулярных выражений и не должны перемешиваться с буквами). Ре-
гулярные выражения строятся по таким правилам:
(а) буква алфавита ` | регулярное выражение;
(б) символы ˜, 𝜀 | регулярные выражения;
(в) если 𝐴, 𝐵, 𝐶, . . . , 𝐸 | регулярные выражения, то
(𝐴𝐵𝐶 . . . 𝐸) | регулярное выражение;
(г) если 𝐴, 𝐵, 𝐶, . . . , 𝐸 | регулярные выражения, то
(𝐴|𝐵|𝐶| . . . |𝐸) | регулярное выражение;
(д) если 𝐴 | регулярное выражение, то 𝐴* | регулярное выражение.
Каждое регулярное выражение задаёт множество слов в алфавите ` по
таким правилам:
(а) букве соответствует одноэлементное множество, состоящее из од-
нобуквенного слова, состоящего из этой буквы;
(б) символу 𝜀 соответствует пустое множество, а символу ˜ | одноэле-
ментное множество, единственным элементом которого является
пустое слово;
(в) регулярному выражению (𝐴𝐵𝐶 . . . 𝐸) соответствует множество
всех слов, которые можно получить, если к слову из 𝐴 приписать
слово из 𝐵, затем из 𝐶,. . . , затем из 𝐸 (конкатенация множеств);
(г) регулярному выражению (𝐴|𝐵|𝐶| . . . |𝐸) соответствует объеди-
нение множеств, соответствующих выражениям 𝐴, 𝐵, 𝐶, . . . , 𝐸;
(д) регулярному выражению 𝐴* соответствует итерация множества,
соответствующего выражению 𝐴, то есть множество всех слов,
которые можно так разрезать на куски, что каждый кусок при-
надлежит множеству, соответствующему выражению 𝐴. (В част-
ности, пустое слово всегда содержится в 𝐴*.)

10.7. Более сложные образцы и автоматы
193
Множества, соответствующие регулярным выражениям, называют-
ся регулярными. Вот несколько примеров:
Выражение
Множество
(a|b)*
все слова из букв a и b
(aa)*
слова из чётного числа букв a
(˜|a|b|aa|ab|ba|bb) все слова длины не более 2 из букв a, b
10.7.5. Напишите регулярное выражение, которому соответствует
множество всех слов из букв a и b, в которых число букв a чётно.
Решение. Выражение b* задаёт все слова без буквы a, а выражение
(b* a b* a b*) | все слова ровно с двумя буквами a. Остаётся объеди-
нить эти множества, а потом применить итерацию:
( (b* a b* a b*)
|
b* )*
Другой вариант ответа:
(b* a b* a)* b*
10.7.6. Напишите регулярное выражение, которое задаёт множе-
ство всех слов из букв a, b, c, в которых слово bac является подсловом.
Решение. ((a|b|c)* bac (a|b|c)*)
10.7.7. Напишите регулярное выражение, которое задаёт множе-
ство всех слов из букв a, b, c, в которых слово bac не является под-
словом.
[Указание. Эта задача сложнее предыдущей; видимо, самый простой
способ её решить | перейти к конечным автоматам и вернуться обрат-
но (см. ниже задачу
10.7.14
).]
Теперь задачу о поиске образца в слове можно переформулировать
так: проверить, принадлежит ли слово множеству, соответствующему
данному регулярному выражению.
10.7.8. Какие выражения соответствуют образцам a?b и ab*cd, рас-
смотренным ранее? (В образце символ * используется не в том смысле,
что в регулярных выражениях!) Предполагается, что алфавит содер-
жит буквы a, b, c, d, e.
Решение.
((a|b|c|d|e)* a (a|b|c|d|e) b (a|b|c|d|e)*)
((a|b|c|d|e)* ab (a|b|c|d|e)* cd (a|b|c|d|e)*)

194
10. Сопоставление с образцом
10.7.9. Докажите, что для всякого регулярного выражения можно
построить конечный автомат, который распознаёт соответствующее
этому выражению множество слов.
Решение. Нам потребуется новое понятие | понятие источни-
ка, или недетерминированного конечного автомата. Представим се-
бе ориентированный граф | картинку из нескольких точек (вершин)
и некоторых стрелок, соединяющих эти точки (рёбер). Пусть на неко-
торых рёбрах написаны буквы (не обязательно на всех). Пусть также
среди вершин выбраны две | начальная Н и конечная К. Такая кар-
тинка называется источником.
Будем двигаться различными способами из Н в К, читая буквы по
дороге (на тех стрелках, где они есть). Каждому пути из Н в К, таким
образом, соответствует некоторое слово. А источнику в целом соответ-
ствует множество слов | тех слов, которые можно прочесть на путях
из Н в К.
Замечание. Если нарисовать состояния конечного автомата в ви-
де точек, а переходы при чтении букв изобразить в виде стрелок, то
станет ясно, что конечный автомат | это частный случай источника.
(С дополнительными требованиями: (а) на всех стрелках, за исключе-
нием ведущих в К, есть буквы; (б) для любой точки на выходящих из
неё стрелках каждая буква встречается ровно один раз.)
Мы будем строить конечный автомат по регулярному выражению
в два приёма. Сначала мы построим источник, которому соответству-
ет то же самое множество слов. Затем для произвольного источника
построим автомат, который проверяет, принадлежит ли слово соот-
ветствующему множеству.
10.7.10. По регулярному выражению постройте источник, задаю-
щий то же множество.
Решение. Индукция по построению регулярного выражения. Бу-
квам соответствуют графы из одной стрелки. Объединение реализу-
ется так:
r
-
3
Q
Q
Q
Q
Q
Q
s
Н
r
Н
3
r
Н
2
r
Н
1
r
3
К
3
r
-
К
2
r
Q
Q
Q
Q
Q
Q
s
К
1
r
К

10.7. Более сложные образцы и автоматы
195
Нарисована картинка для объединения трёх множеств, прямоугольни-
ки | это источники, им соответствующие; указаны начальные и ко-
нечные вершины. На новых стрелках (их 6) букв не написано.
Конкатенации соответствует картинка
r
-
Н
r
Н
1
К
1
r
-
r
Н
2
К
2
r
-
r
Н
3
К
3
r
-
r
К
Наконец, итерации соответствует картинка
s
s
-
Н
Н
1
s
-
J
J
J
J
]
К
1
s
s
К
10.7.11. Дан источник. Постройте конечный автомат, проверяю-
щий, принадлежит ли входное слово соответствующему множеству (то
есть можно ли прочесть это слово, идя из Н в К).
Решение. Состояниями автомата будут множества вершин источ-
ника. Именно, прочтя некоторое начало 𝑋 входного слова, мы будем
помнить множество всех вершин источника, в которые можно пройти
из начальной, прочитав на пути слово 𝑋.
Тем самым задача
решена.
Оказывается, что регулярные выражения, автоматы и источники
распознают одни и те же множества. Чтобы убедиться в этом, нам
осталось решить такую задачу:
10.7.12. Дан источник. Постройте регулярное выражение, задаю-
щее то же множество, что и этот источник.
Решение. Пусть источник имеет вершины 1, . . . , 𝑘. Будем считать,
что 1 | это начало, а 𝑘 | конец. Через 𝐷
𝑖,𝑗,𝑠
обозначим множество всех
слов, которые можно прочесть на пути из 𝑖 в 𝑗, если в качестве проме-
жуточных пунктов разрешается использовать только вершины 1, . . . , 𝑠.
Согласно определению, источнику соответствует множество 𝐷
1,𝑘,𝑘
.
Индукцией по 𝑠 будем доказывать регулярность всех множеств 𝐷
𝑖,𝑗,𝑠
при всех 𝑖 и 𝑗. При 𝑠 = 0 это очевидно (промежуточные вершины за-
прещены, поэтому каждое из множеств состоит только из букв).

196
10. Сопоставление с образцом
Из чего состоит множество 𝐷
𝑖,𝑗,𝑠+1
? Отметим на пути моменты,
в которых он заходит в (𝑠 + 1)-ю вершину. При этом путь разбивается
на части, каждая из которых уже не заходит в неё. Поэтому легко
сообразить, что
𝐷
𝑖,𝑗,𝑠+1
= 𝐷
𝑖,𝑗,𝑠
|
(𝐷
𝑖,𝑠+1,𝑠
𝐷
𝑠+1,𝑠+1,𝑠
* 𝐷
𝑠+1,𝑗,𝑠
)
(вольность записи: мы используем для операций над множествами обо-
значения как для регулярных выражений). Остаётся воспользоваться
предположением индукции.
10.7.13. Где ещё используется то же самое рассуждение?
Ответ. В алгоритме Флойда вычисления цены кратчайшего пути,
см. главу
9
(Разные алгоритмы на графах).
10.7.14. Докажите, что класс множеств, задаваемых регулярными
выражениями, не изменился бы, если бы мы разрешили использовать не
только объединение, но и отрицание (а следовательно, и пересечение |
оно выражается через объединение и отрицание).
Решение. Для автоматов переход к отрицанию очевиден.
Замечание. На практике важную роль играет число состояний авто-
мата. Оказывается, что тут всё не так просто, и переход от источника
к автомату требует экспоненциального роста числа состояний. Подроб-
ное рассмотрение связанных с этим теоретических и практических во-
просов | дело особое (см. книгу Ахо, Ульмана и Сети о компиляторах).
10.8. Суффиксные деревья
До сих про наши программы сначала получали образец, который на-
до искать, а потом текст, в котором надо искать. В следующих задачах
всё наоборот.
10.8.1. Программа получает на вход слово 𝑌 длины 𝑚 и может его
обрабатывать (пока без ограничений на время и память). Затем она
получает слово 𝑋 длины 𝑛 и должна сообщить, является ли оно подсло-
вом слова 𝑌 . При этом число операций при обработке слова 𝑋 должно
быть порядка 𝑛 (не превосходить 𝑐𝑛, где константа 𝑐 может зависеть
от размера алфавита). Как написать такую программу?
Решение. Пока не накладывается никаких ограничений на время
и память при обработке 𝑌 , это не представляет труда. Именно, надо
склеить все подслова слова 𝑌 в дерево, объединив слова с общими нача-

10.8. Суффиксные деревья
197
лами (как мы это делали, распознавая вхождения нескольких образцов).
Например, для 𝑌 = 𝑎𝑏𝑎𝑏𝑐 получится такое дерево подслов (на ребре на-
писана буква, которая добавляется при движении по этому ребру; вер-
шины находятся во взаимно однозначном соответствии с подсловами
слова 𝑌 ):
𝑏
𝑎
𝑐
𝑏
𝑏
𝑏
𝑎
𝑎
𝑐
𝑐
𝑐
𝑐
Пусть такое дерево построено. После этого, читая слово 𝑋 слева на-
право, мы прослеживаем 𝑋 в дереве, начав с корня; слово 𝑋 будет под-
словом слова 𝑌 , если при этом мы не выйдем за пределы дерева.
Заметим, что аналогичная конструкция годится для любого множе-
ства слов 𝑈, а не только для множества всех подслов данного слова: по-
сле того как соответствующее дерево построено, мы можем про любое
слово 𝑋 определить его принадлежность к 𝑈 за время, пропорциональ-
ное длине 𝑋. (Надо только дополнительно хранить в вершине дерева
информацию, принадлежит ли соответствующее ей слово множеству 𝑈
или лишь является началом другого слова, принадлежащего 𝑈.)
10.8.2. Решите предыдущую задачу с дополнительным ограничени-
ем: объём используемой памяти пропорционален длине слова 𝑌 .
Решение. Прежний способ не годится: число вершин дерева равно
числу подслов слова 𝑌 , а у слова длины 𝑚 число подслов может быть
порядка 𝑚
2
, а не 𝑚. Однако мы можем «сжать» наше дерево, оставив
вершинами лишь точки ветвления (где больше одного сына). Тогда на
рёбрах дерева надо написать уже не буквы, а куски слова 𝑌 .
Вот что получится при сжатии нашего примера:
𝑏
𝑎𝑏
𝑐
𝑐
𝑎𝑏𝑐
𝑐
𝑎𝑏𝑐
Будем считать (здесь и далее), что последняя буква слова 𝑌 больше
в нём не встречается. (Этого всегда можно достичь, дописав допол-
нительный фиктивный символ.) Тогда листья сжатого дерева соответ-
ствуют концам слова 𝑌 , а внутренние вершины (точки ветвления) |

198
10. Сопоставление с образцом
таким подсловам 𝑠 слова 𝑌 , которые встречаются в 𝑌 несколько раз,
и притом с разными буквами после 𝑠.
У каждой внутренней вершины (не листа) сжатого дерева есть не
менее двух сыновей. В деревьях с такими свойствами число внутренних
вершин не превосходит числа листьев. (В самом деле, при движении сле-
ва направо в каждой точке ветвления добавляется новый путь к листу.)
Поскольку листьев 𝑚, всего вершин не более 2𝑚, и мы уложимся в ли-
нейную по 𝑚 память, если будем экономно хранить пометки на рёбрах.
Каждая такая пометка является подсловом слова 𝑌 , и потому доста-
точно указывать координату её начала и конца в 𝑌 . Это не помешает
впоследствии прослеживать произвольное слово 𝑋 в этом дереве буква
за буквой, просто в некоторые моменты мы будем находиться внутри
рёбер (и должны помнить, внутри какого ребра и в какой позиции мы
находимся). При появлении новой буквы слова 𝑋 её нужно сравнить
с соответствующей буквой пометки этого ребра (что можно сделать за
𝑂(1) действий, так как координату этой буквы мы знаем.)
Построенное нами сжатое дерево называют сжатым суффиксным
деревом слова 𝑌 (концы слова называют «суффиксами»).
10.8.3. Покажите, что построение сжатого суффиксного дерева
можно выполнить за время 𝑂(𝑚
2
) с использованием 𝑂(𝑚) памяти.
Решение. Будем добавлять в суффиксное дерево суффиксы по очере-
ди. Добавление очередного суффикса делается так же, как и проверка
принадлежности: мы читаем его буква за буквой и прокладываем путь
в дереве. В некоторый момент добавляемый суффикс выйдет за пре-
делы дерева (напомним, что мы считаем, что последний символ слова
уникален).
Если это произойдёт посередине ребра, то ребро придётся в этом
месте разрезать. Ребро превратится в два, его пометка разрежется на
две, появится новая вершина (точка ветвления) и её новый сын-лист.
Если точка ветвления совпадёт с уже имевшейся в дереве, то у неё
появится новый сын-лист. В любом случае после обнаружения места
ветвления требуется 𝑂(1) операций для перестройки дерева (в частно-
сти, разрезание пометки на две выполняется легко, так как пометки
хранятся в виде координат начала и конца в слове 𝑌 ).
Гораздо более сложной задачей является построение сжатого суф-
фиксного дерева за линейное время (вместо квадратичного, как в пре-
дыдущей задаче). Чтобы изложить алгоритм Маккрейта, который ре-
шает эту задачу, нам понадобятся некоторые приготовления.
Для начала опишем более подробно структуру дерева, которое мы
используем, и операции с ним.

10.8. Суффиксные деревья
199
Мы рассматриваем деревья с корнем, на рёбрах которых написаны
слова (пометки); все пометки являются подсловами некоторого заранее
фиксированного слова 𝑌 . При этом выполнены такие свойства:
•
каждая внутренняя вершина имеет хотя бы двух сыновей;
•
пометки на рёбрах, выходящих из данной вершины, начинаются
на разные буквы.
Каждой вершине 𝑣 такого дерева соответствует слово, которое за-
писано на пути от корня 𝑟 к вершине 𝑣. Будем обозначать это слово 𝑠(𝑣).
Обозначим пометку на ребре, ведущем к 𝑣, через 𝑙(𝑣), а отца верши-
ны 𝑣 | через 𝑓(𝑣). Тогда 𝑠(𝑟) = ˜ (пустое слово), а
𝑠(𝑣) = 𝑠(𝑓(𝑣)) + 𝑙(𝑣)
для любой вершины 𝑣
̸
= 𝑟 (знак «+» обозначает соединение строк).
Помимо вершин дерева, мы будем рассматривать позиции в нём, ко-
торые могут быть расположены в вершинах, а также «внутри рёбер»
(разделяя пометку этого ребра на две части). Формально говоря, по-
зиция представляет собой пару (𝑣, 𝑘), где 𝑣 | вершина (отличная от
корня), а 𝑘 | целое число в промежутке [0,
|
𝑙(𝑣)
|
), указывающее, на
сколько букв надо вернуться от 𝑣 к корню. Здесь
|
𝑙(𝑣)
|
| длина по-
метки 𝑙(𝑣); значение 𝑘 = 𝑙(𝑣) соответствовало бы предыдущей вершине
и потому не допускается. К числу позиций мы добавляем также па-
ру (𝑟, 0), соответствующую корню дерева. Каждой позиции 𝑝 = (𝑣, 𝑘)
соответствует слово 𝑠(𝑝), которое получается удалением 𝑘 последних
символов из 𝑠(𝑣).
Пусть 𝑝 | произвольная позиция в дереве, а 𝑤 | слово. Пройти
вдоль 𝑤, начиная с 𝑝, означает найти другую позицию 𝑞, для которой
𝑠(𝑞) = 𝑠(𝑝) + 𝑤. Если такая позиция есть, то (при описанном способе
хранения пометок, когда указываются координаты их начала и конца
внутри 𝑌 ) её можно найти за время, пропорциональное длине слова 𝑤.
Если такой позиции нет, то в какой-то момент мы «свернём с пути»;
в этот момент можно пополнить дерево, сделав отсутствующую в де-
реве часть слова 𝑤 пометкой на пути к новому листу. Надо только,
чтобы эта пометка была подсловом слова 𝑌 (при нашем способе хране-
ния пометок); это будет гарантировано, если прослеживаемое слово 𝑤
является подсловом слова 𝑌 .
Заметим, что при этом может образоваться новая вершина (если
развилка оказалась внутри ребра), а может и не образоваться (если раз-
вилка оказалась в вершине). Число действий при такой модификации

200
10. Сопоставление с образцом
пропорционально длине пройденной части слова (длина непройденной
не важна).
Оказывается, что навигацию в дереве можно ускорить, если заранее
известно, что она будет успешной.
10.8.4. Пусть для данной позиции 𝑝 и слова 𝑤 заранее известно,
что в дереве есть позиция 𝑞, для которой 𝑠(𝑞) = 𝑠(𝑝) + 𝑤. Покажите,
что позицию 𝑞 можно найти за время, пропорциональное числу рёбер
дерева на пути от 𝑝 к 𝑞. (Это число может быть значительно меньше
длины слова 𝑤, если пометки на рёбрах длинные.)
Решение. В самом деле, при навигации нужно ориентироваться лишь
в вершинах (выбирать исходящее ребро в зависимости от очередной
буквы); в остальных местах путь однозначный и потому можно сдви-
гаться сразу к концу ребра.
Подведём итоги. Рассмотренный способ хранения деревьев позволя-
ет (для фиксированного слова 𝑌 )
•
создать дерево из одного корня [𝑂(1)];
•
найти отца любой вершины (кроме корня) [𝑂(1)];
•
узнать пометку любой вершины (кроме корня), то есть пометку
ведущего к ней ребра [𝑂(1)];
•
пройти из любой позиции 𝑝 вдоль любого слова 𝑤, если заранее
известно, что мы не выйдем из дерева; результат | позиция 𝑞
в дереве, для которой 𝑠(𝑞) = 𝑠(𝑝) + 𝑤 [𝑂(число рёбер на пути)];
•
добавить слово 𝑤 (некоторое подслово слова 𝑌 ), начав с позиции 𝑝;
если при этом в дереве нет позиции 𝑞, для которой 𝑠(𝑞) = 𝑠(𝑝) +
+ 𝑤, то дерево меняется и такая позиция 𝑞 создаётся (она будет
листом) [𝑂(число букв в 𝑤, не вошедших в 𝑙(𝑞)];
•
наконец, для любого слова 𝑋 можно выяснить, найдётся ли в де-
реве позиция 𝑞, для которой 𝑠(𝑞) = 𝑋 [𝑂(
|
𝑋
|
)].
В квадратных скобках указано число действий при выполнении со-
ответствующих операций.
Ещё мы будем хранить в вершинах дерева «суффиксные ссылки»
(в каждой вершине будет не более одной ссылки на другую вершину),
но сначала надо объяснить, что это такое.
Начнём с полного (не сжатого) суффиксного дерева для слова 𝑌 .
Каждой его вершине (кроме корня) отвечает некоторое непустое под-
слово слова 𝑌 . Если мы отрежем у этого подслова последнюю букву,

10.8. Суффиксные деревья
201
то в дереве спустимся на один шаг к корню. Но что будет, если мы
отрежем первую букву? Снова получится подслово, но оно уже будет
совсем в другом месте дерева.
Вот как выглядят эти переходы в нашем примере (отрезание первой
буквы соответствует пунктирной стрелке):
𝑏
𝑎
𝑐
𝑏
𝑏
𝑏
𝑎
𝑎
𝑐
𝑐
𝑐
𝑐
Эти стрелки мы будем называть суффиксными ссылками, посколь-
ку они соответствуют переходу от слова к его суффиксу на единицу
меньшей длины. Они определены для всех вершин, кроме корня.
Формально можно сказать так. Пусть 𝑤
′
означает слово 𝑤 без пер-
вой буквы (𝑤
′
определено для любого непустого слова 𝑤). Тогда суф-
фиксная ссылка ведёт из вершины 𝑝 в вершину 𝑞, если 𝑠(𝑞) = 𝑠(𝑝)
′
(на-
помним, что 𝑠(𝑢) | слово, соответствующее вершине 𝑢).
10.8.5. Как связаны суффиксные ссылки двух соседних вершин (от-
ца и сына)?
Ответ. Они указывают на соседние вершины, и буква на соединяю-
щем их ребре та же самая.
10.8.6. Докажите, что при переходе к сжатому суффиксному дереву
ссылки по-прежнему идут из вершины в вершину (не внутрь рёбер).
Решение. В самом деле, по нашему предположению последняя бу-
ква слова больше в нём не встречается, поэтому из листа ссылка ведёт
в лист. А если вершина (отличная от корня) является точкой ветвле-
ния, то соответствующее ей слово 𝑠 встречается с различными буквами
после него. Другими словами, для некоторых букв 𝑎 и 𝑏 слова 𝑠𝑎 и 𝑠𝑏
являются подсловами слова 𝑌 . Отрезав от них первую букву, получим
слова 𝑠
′
𝑎 и 𝑠
′
𝑏, которые также являются подсловами слова 𝑌 , поэтому
и 𝑠
′
является точкой ветвления.
Вот что получится для нашего примера:
𝑏
𝑎𝑏
𝑐
𝑐
𝑎𝑏𝑐
𝑐
𝑎𝑏𝑐

202
10. Сопоставление с образцом
Теперь мы уже готовы к изложению алгоритма Маккрейта. Сжа-
тое суффиксное дерево строим постепенно, добавляя к нему суффиксы
по мере уменьшения их длины. Обозначим через 𝑌
𝑖
суффикс, начинаю-
щийся с 𝑖-й буквы слова 𝑌 . (Таким образом, 𝑌
1
= 𝑌 , а 𝑌
𝑚
состоит из
одной буквы.) После 𝑖 шагов построения наше дерево будет хранить
𝑌
1
, . . . , 𝑌
𝑖
.
10.8.7. Покажите, что суффиксные ссылки в таком дереве опреде-
лены корректно (ведут в другую вершину того же дерева) для всех вер-
шин, кроме, возможно, последнего добавленного листа (соответствую-
щего слову 𝑌
𝑖
) и его отца.
Решение. В самом деле, суффиксная ссылка из листа 𝑌
𝑗
ведёт
в лист 𝑌
𝑗+1
, и потому ей есть куда вести. Рассмотрим теперь внутрен-
нюю вершину 𝑣, не являющуюся отцом последнего листа. Пусть в ней
разветвляются два пути в листья 𝑌
𝑗
и 𝑌
𝑘
. Без ограничения общности
можно считать, что 𝑗, 𝑘 < 𝑖 (если один из путей ведёт в 𝑌
𝑖
, то его можно
заменить другим, ведь вершина 𝑣 по предположению не последняя раз-
вилка на этом пути). Отрезав от этих путей первый символ, получим
пути в листья 𝑌
𝑗+1
и 𝑌
𝑘+1
; эти пути присутствуют в дереве (посколь-
ку 𝑗 + 1 и 𝑘 + 1 не превосходят 𝑖), а точка их развилки будет концом
суффиксной ссылки вершины 𝑣.
Суффиксные ссылки для листьев нам не понадобятся, и вычислять
мы их не будем, а для всех остальных вершин дерева мы их будем вы-
числять и хранить. Более точно, после 𝑖 шагов алгоритма
•
в дереве хранятся слова 𝑌
1
, . . . 𝑌
𝑖
(и все их начала);
•
адрес листа, соответствующего последнему добавленному суф-
фиксу (𝑌
𝑖
) хранится в переменной last;
•
для всех внутренних вершин дерева, кроме, быть может, отца вер-
шины last, хранится правильная суффиксная ссылка.
Надо понять, как поддерживать это при добавлении очередного
суффикса. Можно, не мудрствуя лукаво, добавлять 𝑌
𝑖+1
буква за бу-
квой, начиная с корня дерева. (Именно так мы раньше и делали, и это
требовало квадратичного времени.)
Какие тут возможны оптимизации? Первая связана с тем, что мы
можем двигаться по дереву быстрее, если знаем, что заведомо из него
не выйдем. Вторая связана с использованием суффиксных ссылок.
Оба варианта предполагают, что отец 𝑢 листа last не совпадает
с корнем. (Если совпадает, нам придётся добавлять 𝑌
𝑖+1
от корня.)

10.8. Суффиксные деревья
203
Пусть tail | пометка листа last, а head = 𝑠(𝑢); другими словами, слово
head соответствует вершине 𝑢. Тогда
𝑌
𝑖
= head + tail.
Отрезая первую букву, получаем
𝑌
𝑖+1
= head
′
+ tail.
Заметим, что head
′
заведомо не выходит за пределы дерева. В са-
мом деле, 𝑢 было точкой ветвления, поэтому помимо листа 𝑌
𝑖
через
точку 𝑢 проходил и лист 𝑌
𝑗
с 𝑗 < 𝑖. Тогда 𝑌
𝑗
начинается на head, а 𝑌
𝑗+1
начинается на head
′
и уже есть в дереве.
Поэтому мы можем сначала проследить head
′
(найти позицию 𝑣, для
которой 𝑠(𝑣) = head
′
), а потом уже добавить tail, начиная с 𝑣.
head
tail last [𝑌
i
]
[𝑌
j
]
𝑢
Первый способ оптимизации: head
′
заведомо есть в дереве.
Эта оптимизация никак не использует суффиксных ссылок. Второй
способ оптимизации их использует и позволяет (в том случае, когда
применим) обойтись без прослеживания 𝑌
𝑖+1
от корня (как ускорен-
ного, так и обычного). Пусть на пути к листу last, представляющему
суффикс 𝑌
𝑖
, имеется вершина 𝑣, у которой суффиксная ссылка указы-
вает на вершину 𝑤, так что 𝑠(𝑤) = 𝑠(𝑣)
′
. Пусть 𝑝 | слово на пути от 𝑣
к last. Тогда
𝑌
𝑖
= 𝑠(𝑣) + 𝑝, 𝑌
𝑖+1
= 𝑌
′
𝑖
= 𝑠(𝑣)
′
+ 𝑝 = 𝑠(𝑤) + 𝑝,
и для добавления 𝑌
𝑖+1
в дерево достаточно добавить слово 𝑝, начиная
с вершины 𝑤.
Второй способ оптимизации сочетается с первым: отрезок слова 𝑝
от 𝑣 до отца листа last можно проходить с уверенностью, что мы не
выйдем за пределы дерева.
Итак, мы можем описать действия, выполняемые при добавлении
очередного суффикса 𝑌
𝑖+1
в дерево, следующим образом.

204
10. Сопоставление с образцом
𝑝
𝑝
last [𝑌
i
]
[𝑌
i+1
]
𝑣
𝑤
Второй способ оптимизации: пользуемся суффиксной ссылкой
вершины на пути к last.
Пусть 𝑢 | отец листа last, соответствующего последнему уже до-
бавленному суффиксу 𝑌
𝑖
.
Случай 1: 𝑢 есть корень дерева. Тогда ни одна из оптимизаций не
применима, и мы добавляем 𝑌
𝑖+1
, начиная от корня.
Случай 2: 𝑢 не есть корень дерева, но отец 𝑢 есть корень дере-
ва (лист last находится на высоте 2). Тогда 𝑌
𝑖
= head + tail, где head
и tail | пометки вершин 𝑢 и last. Мы применяем первую оптимизацию
и прослеживаем head
′
с гарантией до некоторой позиции 𝑧, а потом
добавляем tail от 𝑧.
Случай 3: 𝑢 не есть корень дерева и его отец 𝑣 также не есть
корень дерева. Тогда для 𝑣 имеется суффиксная ссылка на некото-
рую вершину 𝑤, и 𝑠(𝑤) = 𝑠(𝑣)
′
. Пусть pretail | пометка вершины 𝑢,
а tail | пометка листа last, при этом 𝑌
𝑖
= 𝑠(𝑣) + pretail + tail и потому
𝑌
𝑖+1
= 𝑌
′
𝑖
= 𝑠(𝑤) + pretail + tail. Остаётся проследить pretail от верши-
ны 𝑤 с гарантией, получив некоторую позицию 𝑧, а потом добавить tail
от вершины 𝑧.
Остаётся ещё понять, как поддерживать структуру суффиксных
ссылок (адрес нового листа у нас получается при добавлении сам собой,
так что с ним проблем нет) и оценить число действий при выполнении
этих процедур последовательно для всех суффиксов.
Начнём с суффиксных ссылок. По правилам они должны быть у всех
внутренних вершин, кроме отца только что добавленного листа. Поэто-
му нам надо заботиться об отце листа last, соответствующего 𝑌
𝑖
(этот
лист перестал быть «только что добавленным»; напротив, единственная
новая вершина как раз является отцом только что добавленного листа
и в ней суффиксная ссылка не нужна). Это актуально в случаях 2 и 3,
но в этих случаях по ходу дела была найдена нужная вершина 𝑧, куда
и будет направлена суффиксная ссылка из 𝑢. Строго говоря, 𝑧 могла
быть не вершиной, а позицией, но тогда после добавления она станет
вершиной (отцом только что добавленного листа) | ведь в новом де-

10.8. Суффиксные деревья
205
реве 𝑢 уже не является отцом последнего листа, и потому суффиксная
ссылка из 𝑢, как было доказано, должна вести в вершину. (Другими
словами, в случаях 2 и 3, если позиция 𝑧 была внутри ребра, то в ней
ребро разрезается.)
Всё сказанное можно условно записать в виде такого алгоритма до-
бавления суффикса 𝑌
𝑖+1
:
{
дерево содержит суффиксы 𝑌
1
, . . . , 𝑌
𝑖
𝑠(last) = 𝑌
𝑖
имеются корректные суффиксные ссылки для всех
внутренних вершин, кроме отца листа last
}
𝑢 := отец листа last;
tail := пометка листа last;
{
𝑌
𝑖
= 𝑠(𝑢) + tail
}
if 𝑢 = корень дерева then begin
{
𝑌
𝑖+1
= tail
′
}
добавить tail
′
, начиная с корня,
полученный лист поместить в last
end else begin
𝑣 := отец вершины 𝑢;
pretail := пометка вершины 𝑢;
{
𝑌
𝑖
= 𝑠(𝑣) + pretail + tail
}
if 𝑣 = корень дерева then begin
{
𝑌
𝑖+1
= pretail
′
+ tail
}
проследить pretail
′
из корня в 𝑧
end else begin
𝑤 := суффиксная ссылка вершины 𝑣;
{
𝑠(𝑤) = 𝑠(𝑣)
′
, 𝑌
𝑖+1
= 𝑠(𝑤) + pretail + tail
}
проследить pretail из 𝑤 в 𝑧
end;
{
осталось добавить tail из 𝑧 и ссылку из 𝑢 в 𝑧
}
if позиция 𝑧 является вершиной then begin
поместить в 𝑢 ссылку на 𝑧;
добавить tail, начиная с 𝑧,
полученный лист поместить в last;
end else begin
добавить tail, начиная с 𝑧,
полученный лист поместить в last;
поместить в 𝑢 ссылку на отца листа last;
end
end;

206
10. Сопоставление с образцом
Осталось оценить число действий, которые выполняются при после-
довательном добавлении суффиксов 𝑌
1
, . . . , 𝑌
𝑚
. При добавлении каждо-
го следующего суффикса выполняется ограниченное количество дей-
ствий, если не считать действий при «прослеживании» и «добавлении».
Нам надо установить, что общее число действий есть 𝑂(𝑚); для это-
го достаточно отдельно доказать, что суммарное число действий при
всех прослеживаниях есть 𝑂(𝑚) и суммарное число действий при всех
добавлениях есть 𝑂(𝑚). (Заметим, что некоторые прослеживания или
добавления могут быть долгими | но это компенсируется другими.)
Прослеживания. Длительность прослеживания пропорциональна чи-
слу 𝑘 задействованных в нём рёбер, но при этом высота последнего
добавленного листа (число рёбер на пути к нему) увеличивается на
𝑘
−
𝑂(1) (по сравнению с предыдущим добавленным листом). Чтобы
убедиться в этом, достаточно заметить, что в третьем случае высота
вершины 𝑠(𝑤) может быть меньше высоты вершины 𝑠(𝑣) разве что на
единицу, поскольку суффиксные ссылки из всех вершин на пути к 𝑣 (не
считая корня, где нет суффиксной ссылки) ведут в вершины на пути
к 𝑤. Поскольку высота любого листа ограничена числом 𝑚, заключаем,
что общая длительность всех прослеживаний есть 𝑂(𝑚).
Добавления. Рассуждаем аналогично, но следим не за высотой по-
следнего листа, а за длиной его пометки. При добавлении слова tail (или
tail
′
) число действий пропорционально числу просмотренных букв, но
каждая просмотренная буква (кроме, быть может, одной) уменьшает
длину пометки хотя бы на единицу: в пометке остаются лишь непросмо-
тренные буквы (не считая первой). Поэтому на все добавления уходит
в общей сложности 𝑂(𝑚) действий.
Тем самым мы доказали, что описанный алгоритм строит сжатое
суффиксное дерево слова 𝑌 длины 𝑚 за 𝑂(𝑚) действий. После этого для
любого слова 𝑋 длины 𝑛 можно за 𝑂(𝑛) действий выяснить, является
ли 𝑋 подсловом слова 𝑌 .
10.8.8. Как модифицировать алгоритм построения суффиксного де-
рева, чтобы не только узнавать, является ли данное слово 𝑋 подсловом
слова 𝑌 , но и (если является) указывать место, где оно встречается
(одно из таких мест, если их несколько)? Время построения должно
оставаться 𝑂(
|
𝑌
|
), время поиска подслова | 𝑂(
|
𝑋
|
).
Решение. Каждая вершина сжатого суффиксного дерева соответ-
ствует некоторому подслову слова 𝑌 ; в момент, когда эта вершина была
добавлена в дерево, известно, в каком месте есть такое подслово, и мож-
но записать в вершине, где соответствующее подслово кончается.

10.8. Суффиксные деревья
207
10.8.9. Как модифицировать этот алгоритм, чтобы для каждого
подслова можно было бы указывать его первое (самое левое) вхожде-
ние?
[Указание. При возникновении новой вершины на ребре нужно брать
её первое вхождение (информация о котором есть на конце ребра), а не
второе, только что обнаруженное.]
10.8.10. Как модифицировать этот алгоритм, чтобы для каждого
подслова можно было бы указывать его последнее (самое правое) вхо-
ждение?
[Указание. Если при каждом проходе корректировать информацию
вдоль пути, это будет долго; быстрее построить дерево, затем вновь его
обойти и для каждой вершины вычислить момент последнего появления
соответствующего подслова.]
10.8.11. Как использовать сжатое суффиксное дерево, чтобы для
данного слова 𝑌 за время 𝑂(
|
𝑌
|
) найти самое длинное подслово, которое
входит в 𝑌 более одного раза?
Решение. Такое подслово является внутренней вершиной сжатого
суффиксного дерева, поэтому достаточно из всех его вершин взять
ту, которой соответствует самое длинное слово. Для этого достаточ-
но обойти все его вершины (длину можно вычислять по мере обхода,
складывая длины пометок на рёбрах).
На практике можно использовать также и другой способ нахожде-
ния самого длинного подслова, входящего дважды, | так называемый
массив суффиксов. А именно, будем рассматривать число 𝑖 как «код»
конца слова, начинающего с 𝑖-й буквы. Введём на кодах порядок, со-
ответствующий лексикографическому (словарному) порядку на словах:
код 𝑖 предшествует коду 𝑗, если конец слова, начинающийся с 𝑖, в лекси-
кографическом порядке идёт раньше конца слова, начинающегося с 𝑗.
После этого отсортируем коды в соответствии с этим порядком, по-
лучив некоторую перестановку массива 1, 2, 3, . . . , 𝑚 (где 𝑚 | длина
исходного слова 𝑌 ). Если какое-то слово 𝑋 входит в слово 𝑌 дважды,
то оно является началом двух концов слова 𝑌 . При этом эти концы
можно выбрать соседними в лексикографическом порядке, поскольку
все промежуточные слова тоже начинаются на 𝑋. Значит, достаточно
для всех соседних концов посмотреть, сколько начальных букв у них
совпадает, и взять максимум.
Этот способ требует меньше памяти (нам нужен лишь один массив
из целых чисел той же длины, что исходное слово), но может требо-
вать большого времени: во-первых, сортировка сама по себе требует

208
10. Сопоставление с образцом
порядка 𝑚 log 𝑚 сравнений, во-вторых, каждое сравнение может длить-
ся долго, если совпадающий кусок большой. Но в случаях, когда длин-
ных совпадающих кусков мало, такой алгоритм работает неплохо.
10.8.12. Примените один из таких алгоритмов к любимой книге
и объясните результат.
[Указание. Длинные повторяющиеся куски могут быть художествен-
ным приёмом (как в известном стишке про дом, который построил
Джек) или следствием забывчивости автора. Для современных авто-
ров возможно также неумеренное использование функций вырезания
и вставки (заливки текста в мышь и выливания из мыши, если исполь-
зовать графический интерфейс) в текстовом редакторе.]

11. АНАЛИЗ ИГР
11.1. Примеры игр
11.1.1. Двое играют в такую игру: на столе лежит 20 спичек; игра-
ющие по очереди могут взять от 1 до 4 спичек; кто не может сделать
хода (спичек не осталось) | проигрывает. Кто выигрывает при пра-
вильной игре?
Решение. Второй выигрывает, если будет дополнять ход первого
до 5 спичек (если первый берёт одну, второй должен взять четыре и так
далее). Тогда после четырёх раундов спичек не останется и первый
проиграет.
11.1.2. Кто выиграет | первый или второй | если спичек не 20,
а 23?
Решение. Первый: если он возьмёт три спички, то станет вторым
в уже разобранной игре и потому сможет выиграть.
Аналогично получается ответ и для произвольного числа спичек 𝑁:
если 𝑁 кратно пяти, то выигрывает второй, а если нет, то первый.
11.1.3. Изменим условия игры: пусть взявший последнюю спичку
проигрывает. Кто теперь выигрывает при правильной игре?
11.1.4. Пусть теперь игрокам разрешено брать 1, 2 или 4 спички,
а кто не может сделать ход, проигрывает. Кто выигрывает при пра-
вильной игре, если вначале было 20 спичек?
Решение. Здесь уже не так просто сразу указать выигрышную стра-
тегию для первого или второго. Начнём с небольшого числа спичек,
изобразив разрешённые ходы в виде стрелок (рис.
11.1
). Игрок, ока-
завшийся в позиции 0, проигрывает (таковы правила), поэтому соот-
ветствующий кружок пометим буквой П. Игрок, оказавшийся в пози-
циях 1, 2 или 4, выигрывает, поскольку он может забрать все спички
и перевести противника по стрелке в позицию 0. Поэтому мы пометим

210
11. Анализ игр
0
1
2
3
4
5
6
7
8
9
П
В
В
В
П
В
В
П
В
П
Рис. 11.1. Игра со спичками.
эти позиции буквой В. Теперь ясно, что позиция 3 является проигрыш-
ной: из неё можно пойти только в 1 и 2, и тогда противник (как мы
уже знаем) выиграет. Пометим её буквой П. Далее замечаем, что по-
зиции 4, 5 и 7 будут выигрышными (поскольку из них можно попасть
в проигрышную для противника позицию 3; заметим, что из позиции 4
можно выиграть и быстрее, пойдя в 0). Теперь видно, что позиция 6
проигрышная (все стрелки из неё ведут в выигрышные для противника
позиции), 8 | выигрышная, 9 | проигрышная и так далее с периодом 3.
Таким образом, если число спичек делится на 3, то позиция про-
игрышная, если нет | то выигрышная. Поэтому в игре с 20 спичками
первый игрок выигрывает.
11.1.5. Как он для этого должен играть?
Решение. Ставить противника в проигрышную позицию, то есть
следить, чтобы после его хода число спичек было кратно трём (в част-
ности, в начале игры взять 2 спички, чтобы осталось 18).
11.1.6. На столе лежат две кучки спичек: в одной 𝑚, в другой 𝑛. За
один ход разрешается взять любое (ненулевое) число спичек, но только
из одной кучки (можно взять все спички в ней); кто не может сделать
ход, проигрывает. Кто выигрывает при правильной игре?
Ответ: при 𝑚 = 𝑛 выигрывает второй, при 𝑚
̸
= 𝑛 | первый.
11.1.7. На шахматной доске стоит ладья, которую игроки по очере-
ди двигают, при этом разрешено сдвигать её влево и вниз (оставлять
на месте нельзя); кто не может сделать ход, проигрывает. Кто выигры-
вает при правильной игре?
[Указание. Как эта игра связана с предыдущей?]
11.1.8. (Игра «ним») Имеется 𝑘 кучек из 𝑛
1
, . . . , 𝑛
𝑘
спичек; за один
ход можно взять любое (ненулевое) число спичек, но только из одной
кучи (можно взять все спички в ней); кто не может сделать ход, про-
игрывает. Кто выигрывает при правильной игре?

11.2. Цена игры
211
Решение. Запишем числа 𝑛
1
, . . . , 𝑛
𝑘
в двоичной системе счисления
друг под другом, как если бы мы собирались их складывать. Если в ка-
ждом разряде при этом оказалось чётное число единиц, то выигрывает
второй, в остальных случаях | первый. В самом деле, если во всех
разрядах чётное число единиц, то после уменьшения одного из чисел
какой-то из его разрядов изменится и в этом разряде получится не-
чётное число единиц. (Это соответствует тому, что из проигрышной
позиции любой ход ведёт в выигрышную.) Если же в некоторых («пло-
хих») разрядах нечётное число единиц, возьмём старший плохой разряд
и то из чисел, которое содержит в этом разряде единицу. Тогда, изме-
нив в этом числе все плохие разряды, получим меньшее число, которое
поставит противника в проигрышную позицию. (См. правила для вы-
игрышных и проигрышных позиций в следующем разделе.)
11.1.9. В ряд лежат 𝑁 ящиков, в каждом из них по монете. За один
ход игрок может взять любую монету или любые две монеты из сосед-
них ящиков; кто не может сделать ход, проигрывает. Кто выигрывает
при правильной игре?
Решение. Первый: он должен взять одну или две монеты в центре,
а потом симметрично повторять ходы второго.
11.2. Цена игры
Анализируя игры в предыдущем разделе, мы использовали следую-
щие (очевидные) правила:
1. Если из некоторой позиции 𝑝 можно пойти (по стрелкам) в некото-
рую проигрышную (для попавшего в неё игрока) позицию, то позиция 𝑝
является выигрышной (для попавшего в неё).
2. Если из некоторой позиции 𝑝 можно пойти только в выигрышные
позиции, то позиция 𝑝 является проигрышной.
11.2.1. Докажите, что если число позиций в игре конечно, нет ци-
клов (нельзя вернуться в однажды пройденную позицию) и про все
заключительные позиции (где нельзя сделать хода) известно, кто вы-
игрывает, то правила 1 и 2 однозначно разбивают все позиции на вы-
игрышные и проигрышные.
Решение. Будем применять эти правила, пока это возможно. Ясно,
что никакая позиция не будет объявлена одновременно выигрышной
и проигрышной (для попавшего в неё). Надо лишь доказать, что не
останется «сомнительных» позиций (не отнесённых ни к выигрышным,

212
11. Анализ игр
ни к проигрышным). Заметим, что из каждой сомнительной позиции
ведёт стрелка хотя бы в одну сомнительную позицию. (В самом деле,
если все стрелки ведут в несомненные позиции, то либо все они вы-
игрышные, либо есть хоть одна проигрышная, и можно было бы вос-
пользоваться одним из двух правил.) Значит, идя по стрелкам в сомни-
тельные позиции, мы рано или поздно получим цикл, что противоречит
предположению.
11.2.2. Сформулируйте и докажите аналогичное утверждение для
игр, допускающих ничьи.
Игры с ничейным исходом являются частными случаями конечных
игр с полной информацией и нулевой суммой, рассматриваемых в тео-
рии игр. Чтобы задать такую игру, необходимо:
1) указать конечное множество, элементы которого называются по-
зициями;
2) для каждой позиции указать, является ли она заключительной
(игра закончена) или нет;
3) для каждой заключительной позиции указать результат игры (чи-
сло); это число понимается как сумма денег, которую один игрок
платит другому;
4) для каждой незаключительной позиции указать, кто из игроков
должен делать ход в этой позиции и какие разрешены ходы (в ка-
кие позиции этот игрок может перейти);
5) указать начальную позицию игры.
При этом требуется, чтобы не было циклов (нельзя было вернуться
в уже пройденную позицию после нескольких ходов).
Позиции игры удобно рассматривать как вершины графа и изобра-
жать точками; возможные ходы при этом становятся рёбрами графа
и изображаются стрелками. Игру можно рассматривать как передви-
жение фишки, обозначающей текущую позицию игры, по этому графу.
В каждой вершине написано, кто должен делать ход (если игра не кон-
чилась) или кто и сколько выиграл (если игра кончилась). Одна из
вершин указана как начальная позиция.
Будем называть игроков Макс и Мин и считать, что результат игры
определяет, сколько Мин платит Максу. (Мотивировка: Макс хочет,
чтобы это число было максимальным, а Мин | минимальным | а луч-
ше всего отрицательным, поскольку тогда он получает деньги!) Кто

11.2. Цена игры
213
из игроков делает первый ход, определяется начальной позицией. За-
метим, что мы теперь не предполагаем, что игроки ходят по очереди:
один и тот же игрок может делать несколько ходов подряд.
(Тем самым, например, в игре со спичками каждый кружок на ри-
сунке
11.1
теперь превращается в две позиции: с ходом Макса и с ходом
Мина.)
Игра, в которой один из игроков выигрывает, а другой проигрыва-
ет, соответствует значениям
±
1 в заключительных вершинах (+1 озна-
чает выигрыш Макса,
−
1 означает выигрыш Мина). Игры с ничейными
исходами получатся, если приписать число 0 ничейным позициям.
Определим теперь понятие стратегии. Стратегия для Макса (или
Мина) определяет, как он должен ходить в каждой из позиций (где ход
за ним); формально это функция 𝑠, определённая на множестве позиций,
где ход за ним. Значениями этой функции являются позиции, при этом
ходы должны быть допустимыми, то есть из 𝑝 в 𝑠(𝑝) должна вести
стрелка.
Стратегии такого типа называют в теории игр позиционными, под-
чёркивая, что выбор хода зависит лишь от текущей позиции, но не
от истории игры (как мы в эту позицию попали). (Другие страте-
гии нам не понадобятся, так что слово «позиционная» мы будем опус-
кать.)
Если фиксировать стратегии для Макса и Мина, то исход игры пре-
допределён: эти стратегии однозначно определяют последовательность
позиций («партию») и результат игры.
11.2.3. Докажите, что для любой игры 𝐺 можно найти число 𝑐 и
стратегии 𝑀 и 𝑚 для Макса и Мина, при которых:
(1) Макс, пользуясь стратегией 𝑀, гарантирует себе выигрыш не
менее 𝑐, как бы ни играл Мин;
(2) Мин, пользуясь стратегией 𝑚, гарантирует себе проигрыш не
более 𝑐, как бы ни играл Макс.
Число 𝑐 называют ценой игры 𝐺. Заметим, что цена игры опре-
деляется однозначно: из условий (1) и (2) следует, что у Макса нет
стратегии, гарантирующей ему выигрыш больше 𝑐 (поскольку она не
может это сделать против стратегии 𝑚), а у Мина нет стратегии, га-
рантирующей ему проигрыш меньше 𝑐.
Для игр с двумя исходами утверждение задачи (называемое тео-
ремой Цермело) означает, что ровно у одного из игроков имеется вы-
игрышная стратегия. Если разрешить и ничьи, то либо у одного из
игроков есть выигрышная стратегия, либо у обоих есть стратегия, га-
рантирующая ничью.

214
11. Анализ игр
Решение. Пусть 𝑝 | произвольная позиция игры 𝐺. Рассмотрим
игру 𝐺
𝑝
, которая отличается от 𝐺 лишь начальной позицией, и эта на-
чальная позиция есть 𝑝. (Если 𝑝 | заключительная вершина, то игра 𝐺
𝑝
тривиальна: игра кончается, не начавшись, и игрокам сообщается ре-
зультат игры.) Как мы сейчас увидим, цену игры 𝐺
𝑝
(как функцию
от 𝑝) можно определить рекурсивно, начиная с заключительных пози-
ций.
Более точно, рассмотрим следующее рекурсивное определение неко-
торой функции 𝑐, определённой на вершинах графа:
•
𝑐(𝑝) равно выигрышу Макса (=проигрышу Мина) в позиции 𝑝,
если позиция 𝑝 является заключительной;
•
𝑐(𝑝) = max
{
𝑐(𝑝
′
)
}
, если в вершине 𝑝 ходит Макс; максимум берёт-
ся по всем вершинам 𝑝
′
, в которые Макс может пойти из 𝑝 по
правилам игры;
•
𝑐(𝑝) = min
{
𝑐(𝑝
′
)
}
, если в вершине 𝑝 ходит Мин; минимум берётся
по всем вершинам 𝑝
′
, в которые Мин может пойти из 𝑝 по прави-
лам игры.
Лемма. Это определение корректно: существует и единственна
функция 𝑐 (аргументы | вершины графа, значения | числа), удовле-
творяющая указанным требованиям.
Доказательство леммы. Назовём рангом вершины максимальное чи-
сло ходов, которое можно сделать из этой вершины. Поскольку по пред-
положению в игре нет циклов, то ранг любой вершины не больше числа
вершин. Докажем индукцией по 𝑘, что существует и единственна функ-
ция 𝑐, определённая на вершинах ранга не больше 𝑘 и удовлетворяющая
рекурсивному определению. Для 𝑘 = 0 это очевидно. Шаг индукции ис-
пользует такое (очевидное) замечание: если из вершины 𝑝 можно сде-
лать ход в вершину 𝑝
′
, то ранг вершины 𝑝
′
меньше ранга вершины 𝑝.
Поэтому рекурсивное определение однозначно задаёт значения на вер-
шинах ранга 𝑘, если известны значения на вершинах меньших рангов.
Лемма доказана.
Осталось доказать, что значение 𝑐(𝑝) является ценой игры 𝐺
𝑝
. Рас-
смотрим следующую (позиционную) стратегию для Макса: из верши-
ны 𝑝 ходить в ту вершину 𝑝
′
, для которой значение 𝑐(𝑝
′
) максимально
(и равно 𝑐(𝑝)). Если Макс следует этой стратегии, то независимо от
ходов Мина значение 𝑐(𝑞) для текущей вершины 𝑞 не убывает в ходе
игры (при ходах Мина оно убывать вообще не может, при ходах Мак-
са оно не убывает по построению стратегии). Тем самым в вершине 𝑝

11.2. Цена игры
215
Максу гарантирован выигрыш не меньше 𝑐(𝑝). Аналогичным образом,
если Мин ходит в ту вершину 𝑝
′
, где достигается минимум 𝑐(𝑝
′
) (рав-
ный 𝑐(𝑝)), то значение 𝑐(𝑞) не возрастает в ходе игры и потому Мин
проигрывает не более 𝑐(𝑝).
Теорема Цермело доказана.
11.2.4. Игра в крестики-нолики состоит в следующем: на большом
квадратном поле два игрока по очереди ставят крестики и нолики в ещё
не занятые клетки (начинают крестики). Выигрывает тот, кто первым
поставит пять своих знаков подряд (по вертикали, горизонтали или
диагонали). Если всё поле заполнено, а такого не случилось, партия
считается ничейной. Докажите, что у крестиков есть стратегия, га-
рантирующая им ничью или выигрыш.
Решение. Согласно теореме Цермело, в противном случае у ноликов
есть стратегия, гарантирующая им выигрыш. Покажем, что крести-
ки могут использовать по существу ту же стратегию, забыв о своём
первом ходе. А именно, представим себе, что крестики делают про-
извольный первый ход (карандашом), а затем отвечают (чернилами)
на ходы ноликов по выигрышной стратегии для ноликов (считая ходы
ноликов крестиками и забыв о своём первом ходе).
Может ли при этом первый ход помешать? Может, если стратегия
указывает как раз на ту клетку, где уже стоит карандашный крестик.
В этом случае надо карандашный крестик обвести чернилами, а каран-
дашом сделать ход в любую свободную клетку. Если свободных клеток
нет, то позиция соответствует (с точностью до замены крестиков на
нолики) заключительной позиции в выигрышной партии для ноликов,
и потому является выигрышной.
Кроме того, игра может кончиться раньше времени, если карандаш-
ный крестик образует выигрышный ряд с чернильными | но это нам
только лучше.
Таким образом, мы доказали, что если у ноликов есть выигрыш-
ная стратегия, то и у крестиков есть выигрышная стратегия | и если
дать этим стратегиям играть друг против друга, получится противо-
речие.
11.2.5. Докажите, что цена любой игры равна выигрышу в одной
из заключительных вершин.
11.2.6. Покажите, что теорема Цермело вытекает из своего част-
ного случая игр с двумя исходами (выигрыш первого и второго).
[Указание. Для каждого Ó будем считать выигрыш меньше 𝑐 про-
игрышем, а больше 𝑐 | выигрышем.]

216
11. Анализ игр
11.2.7. Пусть дана некоторая игра 𝐺. Выберем одну из заключи-
тельных вершин и будем менять выигрыш в этой вершине: положив его
равным 𝑐, получим игру 𝐺[𝑐]. Рассмотрим цену этой игры как функцию
от 𝑐. Что это может быть за функция?
Ответ. Цена игры 𝐺[𝑐] равна ближайшей к 𝑐 точке некоторого от-
резка [𝑎, 𝑏] (зависящего от игры 𝐺).
Вот ещё один пример игры, где теорема Цермело позволяет до-
казать существование выигрышной стратегии для первого игрока.
Эта игра названа в книгах М. Гарднера («Математические досуги»,
М.: Мир, 1972; «Математические головоломки и развлечения», М.: Мир,
1971) игрой Гейла или «бридж-ит». Рассмотрим прямоугольную сеть
из пунктирных линий высоты 𝑛 и ширины 𝑛 + 1 (рис.
11.2
); вершины
Рис. 11.2. Игра Гейла.
сети соединены пунктирными отрезками длины 1. Первый игрок ка-
ждым своим ходом обводит (сплошной линией) один из отрезков. Его
задача | соединить сплошными линиями левую и правую стороны пря-
моугольника. Задача второго игрока | ему помешать; каждым своим
ходом он стирает один из отрезков (лишая первого возможности впо-
следствии его обвести). Игра заканчивается, когда все отрезки обведе-
ны или стёрты; первый выиграл, если при этом левая и правая стороны
прямоугольника соединены.
11.2.8. Используя теорему Цермело, докажите, что первый игрок
имеет выигрышную стратегию.
[Указание. Игру можно представить в более симметричном виде, ес-
ли добавить сетку для второго игрока (рис.
11.3
) и считать, что второй
хочет соединить верхнюю и нижнюю стороны своей сетки, а линиям
первого и второго игроков запрещено пересекаться (тем самым прове-
дя свою линию, второй игрок как бы стирает пересекающую её линию

11.2. Цена игры
217
первого). Если игра закончилась (в каждой возможной точке пересече-
ния проведена вертикальная или горизонтальная линия), то ровно один
из игроков выиграл: можно пройти по линиям или слева направо, или
сверху вниз, но не одновременно. Аккуратное доказательство этого ин-
туитивно ясного топологического факта, впрочем, не так просто.]
Рис. 11.3. Игра Гейла, симметричный вариант.
Как пишет Гарднер, Клод Шеннон (создатель теории информации)
придумал для этой игры любопытную «физическую» стратегию, кото-
рая легко обобщается на любую сеть линий. Представим себе, что все
стороны всех клеток сети (для первого игрока) представляют собой
резисторы одинакового сопротивления, кроме левой и правой сторон
прямоугольника, которые сделаны из провода нулевого сопротивления.
Первый игрок своим ходом закорачивает эти сопротивления, а второй
игрок разрывает их (делает бесконечными). Стратегия первого игрока
состоит в том, что надо подключить напряжение между левой и правой
сторонами прямоугольника, и закорачивать (обводить) то сопротивле-
ние, через которое идёт максимальный ток (или, что то же самое, на
котором падает наибольшая разность потенциалов). Если таких сопро-
тивлений оказалось несколько, можно закорачивать любое из них.
Из книг Гарднера не ясно, является ли эта стратегия выигрыш-
ной. Зато там приведена явная выигрышная стратегия (со ссылкой
на О. Гросса). Чтобы объяснить её, будем считать, что целью первого
игрока является не дать второму соединить верх и низ. (Мы уже упо-
минали, что эта цель равносильна исходной.) Начальный ход первого
игрока показан на рис.
11.4
; этот ход запрещает одно из рёбер второго
игрока. Разделим остальные рёбра второго игрока на пары соседних,
как показано на том же рисунке. Первый игрок препятствует второ-
му провести оба ребра какой-либо пары: если второй провёл одно из
рёбер пары, первый не даёт провести второе ребро этой пары (прове-

218
11. Анализ игр
Рис. 11.4. Игра Гейла: выигрышная стратегия.
дя пересекающее его своё ребро). Следующая задача показывает, что
эта стратегия является выигрышной (первый игрок не даёт второму
соединить верх и низ и потому соединяет левую и правую стороны).
11.2.9. Докажите, что любой путь по линиям пунктирной сетки,
соединяющий верх и низ рисунка
11.4
, обязательно покрывает два ребра
одной пары.
Решение. Для ясности оставим на рисунке только пунктирные ли-
нии и соответствующие вершины (рис.
11.5
). Отметим серую область,
как показано на рисунке; тем самым рёбра делятся на серые и белые.
Рис. 11.5. Игра Гейла: анализ выигрышной стратегии.
Предположим, что имеется путь снизу вверх, который не покрывает ни
одной пары рёбер. Можно считать, что этот путь не проходит дваж-
ды через одну вершину (выбросим циклы). Каждый шаг на этом пути
может относиться к одной из восьми категорий: четыре направления
(север, восток, юг и запад) комбинируются с двумя цветами (серым

11.3. Вычисление цены: полный обход
219
и белым). Как видно из рисунка, путь должен начинаться с серого ша-
га на север, а заканчиваться белым шагом на север.
Покажем, что это невозможно в силу наших ограничений (нельзя
использовать два ребра одной пары и нельзя дважды проходить через
одну вершину). Что, к примеру, может следовать за серым шагом на
север? Ещё один серый шаг на север, серый шаг на запад или белый
шаг на восток. За серым шагом на запад может следовать серый шаг
на запад или серый шаг на север. Разбирая поочерёдно все варианты,
легко убедиться, что путь, начавшись серым шагом на север, никогда
не выйдет (если не нарушит правил) за пределы множества
{
серый шаг на север, серый шаг на запад,
белый шаг на восток, белый шаг на юг
}
.
Поэтому белый шаг на север (который должен быть последним в пути)
невозможен, и мы доказали, что верх и низ рисунка нельзя соединить
путём, не проходящим по двум рёбрам одной пары.
11.2.10. Двое играют на бесконечной клетчатой бумаге, по очереди
обводя красным и синим стороны клеток (за один ход можно обвести
одну сторону любой клетки, если она ещё не обведена). Докажите, что
второй может воспрепятствовать первому построить замкнутый путь
из линий своего цвета.
[Указание. Он может помешать первому, например, повернуть с за-
пада на север, разбив все стороны клеток на пары и не давая покрыть
оба члена пары.]
11.2.11. (Для знакомых с теорией вероятностей) На поле для игры
Гейла (рис.
11.2
) каждая из пунктирных линий обведена с вероятно-
стью 1/2 независимо от других. Докажите, что путь от левой до правой
стороны (по обведённым линиям) существует с вероятностью 1/2.
11.3. Вычисление цены: полный обход
Как видно из доказательства теоремы Цермело, для нахождения
оптимальной стратегии достаточно уметь вычислять цены всех вер-
шин. В этом разделе мы рассмотрим случай, когда позиции игры обра-
зуют дерево (ведущие вверх рёбра дерева соответствуют возможным
в данной позиции ходам) и покажем, как применить программу обхода
дерева (глава
3
).

220
11. Анализ игр
Напомним, что мы рассматривали Робота, который в каждый мо-
мент находится в одной из вершин дерева и умеет выполнять команды
вверх налево, вправо и вниз. Робот начинает работу в корне дерева
(роль которого теперь играет начальная позиция игры). Раньше Робот
умел ещё обрабатывать вершины; теперь мы предполагаем, что он мо-
жет определить тип текущей вершины (один из трёх: max, min и final,
что соответствует вершинам Макса, Мина и заключительным) и может
определить стоимость текущей вершины, если она является заключи-
тельной.
11.3.1. Напишите программу, которая управляет Роботом и вычи-
сляет цену игры.
Решение. Напишем рекурсивную процедуру, которая, начав с неко-
торой вершины, обходит поддерево этой вершины, возвращает Робота
на место и сообщает цену вершины (где она начала и кончила):
procedure find_cost (var c: integer)
var x: integer;
begin
if тип = final then begin
c:= стоимость;
end else if тип = max then begin
вверх_налево;
find_cost (c);
{c = максимум цен текущей вершины и братьев слева}
while есть_справа do begin
вправо;
find_cost (x);
c := max (c,x);
end;
{c=цена вершины под текущей}
вниз;
end else begin {тип = мин}
...аналогично с заменой max(c,x) на min(c,x)
end;
end;
Мы пользуемся тем, что у вершин типа max и min есть хотя бы
один сын (вершины без сыновей должны быть заключительными, и мы
предполагаем, что они отнесены к типу final).
11.3.2. Напишите нерекурсивную программу для вычисления цены
игры (заданной деревом, по которому ходит Робот).

11.3. Вычисление цены: полный обход
221
Решение. Как обычно, рекурсию можно устранить, используя стек.
В данном случае каждый элемент стека будет хранить информацию
об одном из предков текущей вершины (чем дальше, тем глубже | на
дне стека будет информация о корне). Когда мы находимся в корне,
стек пуст, при движении вверх по дереву он удлиняется, при движении
вниз | укорачивается.
Каждый элемент стека представляет собой пару; первый элемент |
тип соответствующей вершины (min/max), а второй элемент | мини-
мум/максимум значений всех её сыновей левее текущего. В программе
из главы
3
существенную роль играли два утверждения: ОЛ означало,
что обработаны все вершины левее текущей (те, путь в которые от-
клоняется налево от пути в текущую); ОЛН означало, что обработаны
все вершины левее и над текущей (это бывало, когда мы проходили
вершину второй раз).
Помимо стека (который всегда будет хранить данные, указанные
выше) программа использует ещё переменную c. В ситуации ОЛ эта
переменная не используется, а в ситуации ОЛН она хранит цену те-
кущей вершины. Покажем, как можно поддерживать это, описав дей-
ствия с переменной и стеком для каждого варианта движения Робота
(ср. с.
64
):
•
{
ОЛ, не есть сверху
}
обработать
{
ОЛН
}
:
в переменную c записываем цену текущего листа;
•
{
ОЛ, есть сверху
}
вверх налево
{
ОЛ
}
:
перед тем, как идти вверх, добавляем в стек тип текущей вершины
(max/min) и значение
−∞
/+
∞
соответственно, имея в виду, что
максимум пустого множества равен
−∞
, а минимум равен +
∞
;
•
{
есть справа, ОЛН
}
вправо
{
ОЛ
}
:
обновляем значение в вершине стека, беря максимум или мини-
мум (в зависимости от типа вершины стека) со значением пере-
менной c;
•
{
не есть справа, есть снизу, ОЛН
}
вниз
{
ОЛН
}
:
в переменную c помещаем максимум/минимум (в зависимости от
типа вершины стека) её прежнего значения и значения на вершине
стека (оно забирается из стека, и стек укорачивается).
Легко видеть, что при этом утверждения о содержании стека и зна-
чении переменной c не нарушаются, и по окончанию работы программы
стек будет пуст, а значение переменной c будет равно цене игры.

222
11. Анализ игр
11.3.3. Как изменить эту программу, чтобы вычислить цены всех
вершин?
[Указание. В состоянии ОЛН мы знаем цену текущей вершины, и
такое случается для всех вершин.]
11.4. Альфа-бета-процедура
Мы видели, как можно вычислить цену игры, обойдя все вершины её
дерева. Однако иногда можно сэкономить и часть дерева не посещать.
Пусть, например, игра имеет два исхода (выигрыш и проигрыш) и мы
обнаружили (после просмотра части дерева), что некоторый ход явля-
ется для нас выигрышным. Тогда нет смысла рассматривать остальные
ходы. Более общо, если мы нашли ход, гарантирующий нам максималь-
ный выигрыш (допускаемый правилами игры), то нет смысла искать
дальше.
Подобная оптимизация возможна не только в тех случаях, когда
мы знаем максимально возможный выигрыш. Пусть, например, дере-
во игры имеет такой вид, как на рис.
11.6
, причём 𝑎
>
𝑏 и мы обходим
вершины дерева слева направо. Тогда после просмотра вершины 𝑎 мы
max
min
𝑎
𝑏
Рис. 11.6. Оптимизация возможна при 𝑎
>
𝑏.
знаем, что цена корневой вершины не меньше 𝑎. Перейдя к min-вершине
и просмотрев её первого сына 𝑏, мы определяем, что цена min-вершины
не больше 𝑏 и (при 𝑏
6
𝑎) она не может повлиять на цену корня. Поэтому
следующие вершины (серая область на рисунке) и их поддеревья нам
просматривать не нужно.
Применённую в обоих случаях оптимизацию можно описать так.
Приступая к оценке некоторой вершины, мы знаем некоторый про-
межуток [𝑚, 𝑀], в пределах которого нас интересует цена этой вер-
шины | либо потому, что она заведомо не может выйти за пределы

11.4. Альфа-бета-процедура
223
промежутка (как в первом случае, когда лучше выигрыша ничего не
бывает), либо потому, что это нам ничего не даёт (как во втором слу-
чае, когда все цены меньше 𝑎 для нас неотличимы от 𝑎).
Более формально, введём обозначение 𝑥
[𝑎,𝑏]
, где 𝑥 | число, а [𝑎, 𝑏] |
промежуток:
𝑥
[𝑎,𝑏]
=
⎧
⎪
⎨
⎪
⎩
𝑎, если 𝑥
6
𝑎;
𝑥, если 𝑎
6
𝑥
6
𝑏;
𝑏, если 𝑏
6
𝑥.
Другими словами, 𝑥
[𝑎,𝑏]
| ближайшая к 𝑥 точка промежутка [𝑎, 𝑏], ко-
торую можно назвать «приведённым к [𝑎, 𝑏] значением 𝑥». Теперь можно
сказать, что после просмотра вершины 𝑎 на рисунке
11.6
нас интересу-
ет приведённая к [𝑎, +
∞
] цена min-вершины (все значения, меньшие 𝑎,
безразличны), а после просмотра вершины 𝑏 эта приведённая цена уже
известна (равна 𝑎). Аналогичным образом цена игры с двумя исходами
±
1 равна её приведённой к отрезку [
−
1, +1] цене, и после обнаружения
выигрышного хода становится ясным, что эта цена равна +1.
Используя это соображение, напишем оптимизированный алгоритм,
в котором рекурсивно определяется приведённая к промежутку [𝑎, 𝑏]
цена игры в текущей вершине:
procedure find_reduced_cost (a,b: integer; var c: integer)
var x: integer;
begin
if тип = final then begin
c:= стоимость, приведённая к [a,b]
end else if тип = max then begin
вверх_налево;
find_reduced_cost (a,b,c);
{c = максимум цены вершины и братьев слева,
приведённый к [a,b]
while есть_справа and (cвправо;
find_reduced_cost (c,b,x);
c := x;
end;
{c=цена вершины под текущей, приведённая к [a,b]}
вниз;
end else begin {тип = мин}
...симметрично
end;
end;

224
11. Анализ игр
Этот алгоритм часто называют 𝛼-𝛽-процедурой по историческим
причинам (границы интервала обозначались буквами 𝛼 и 𝛽). Подробно
(запутанная) история этого алгоритма описана в статье Кнута и Му-
ра в журнале Arti˛cial Intelligence, 6(4), 293{326 (1975). В частности,
они пишут, что этот алгоритм переоткрывался несколько раз, внача-
ле воспринимался как эвристический (т.е. сокращающий перебор, но
не гарантирующий точного ответа), а опубликован он был впервые в
статье Брудно 1963 года «с довольно сложным доказательством» (как
пишут Кнут и Мур).
Естественный вопрос: насколько такого рода оптимизация помога-
ет уменьшить перебор? Мы рассмотрим простейший пример. Пусть
игра имеет фиксированную длину, из каждой позиции возможны два
хода, игроки ходят по очереди, каждый делает 𝑛 ходов и цены листьев
равны 0 или 1. Дерево такой игры | полное двоичное дерево, min-
и max-уровни чередуются, в листьях написаны нули и единицы, и нужно
вычислить значение в корне. (Если считать, что 1 = истина, 0 = ложь,
то максимум и минимум соответствуют операциям OR (ИЛИ) и AND
(И), поэтому иногда говорят об AND-OR-дереве.)
Сколько листьев нужно посетить, чтобы вычислить значение в кор-
не? Напомним, что всего листьев 2
2𝑛
для дерева с 2𝑛 уровнями (каждый
из игроков делает 𝑛 ходов).
11.4.1. Докажите, что для любых значений в листьях описанный
нами оптимизированный алгоритм просматривает не менее 2
𝑛
листьев.
Решение. На уровне 2 находятся четыре вершины. В ходе работы
алгоритм должен узнать цену игры хотя бы в двух из них. В самом
деле, пусть нижняя вершина есть min-вершина. Если в ней нуль, то
в одном из её сыновей тоже нуль. А раз это max-вершина, то для уста-
новления этого факта нужно знать цену обоих сыновей (равную нулю).
Второй случай: в корне единица. Тогда в обеих его сыновьях должна
быть единица, и чтобы быть в этом уверенным, нужно в каждом из них
посмотреть как минимум одного сына.
Аналогично ради каждого значения на уровне 2 нужны два значе-
ния на уровне 4 и так далее | в конце концов на уровне 2𝑛 нужно
знать 2
𝑛
значений.
Для наглядности мы говорили о конкретном алгоритме, описанном
выше. Но справедлив и более общий факт: любой набор значений в ли-
стьях, который однозначно определяет значение в корне, содержит не
менее 2
𝑛
значений.
11.4.2. Проведите аккуратное доказательство этого утверждения.

11.4. Альфа-бета-процедура
225
[Указание. По существу уже всё доказано, надо только это офор-
мить.]
Только что полученная оценка относилась к самому благоприятному
случаю. Утверждение следующей задачи, напротив, говорит о наихуд-
шем случае.
11.4.3. Пусть у нас спрашивают значения в листьях AND-OR-дерева
в заранее неизвестном нам порядке, и мы можем называть эти значения
по собственному усмотрению. Докажите, что мы можем действовать
так, чтобы до последнего момента (пока есть хоть одно не названное
значение) цена корня оставалось бы неизвестной (то есть могла быть
и нулём, и единицей в зависимости от ещё не названных значений).
Эта задача показывает, что любой алгоритм отыскания цены кор-
ня в наиболее неблагоприятном случае вынужден обходить все листья
(в частности, наш оптимизированный алгоритм никакого выигрыша не
даёт).
Решение. Будем доказывать это индукцией по высоте дерева. Пусть
корень является AND-вершиной. Тогда будем оттягивать (по предполо-
жению индукции) определение значений в детях корня, а когда дальше
оттягивать будет нельзя (последний лист поддерева становится извест-
ным), сделаем так, чтобы это поддерево было истинным. Тем самым
значение в корне совпадает со значением в другом поддереве и может
оставаться неопределённым до последнего момента.
Более интересной является оценка среднего числа опрошенных ли-
стьев. Будем считать, что алгоритм find reduced cost применяет-
ся к некоторому фиксированному AND-OR-дереву (с фиксированны-
ми значениями в листьях), но для каждой вершины порядок просмотра
двух её детей выбирается случайно. Тогда общее число просмотренных
листьев становится случайной величиной.
11.4.4. Докажите, что математическое ожидание этой случайной
величины (среднее по всем порядкам просмотров) для любого AND-
OR-дерева высоты 2𝑛 (с 4
𝑛
вершинами) не превосходит 3
𝑛
.
Решение. Рассмотрим сначала случай 𝑛 = 1, то есть дерево глуби-
ны 2. Пусть его корень является AND-вершиной. Если в корне находит-
ся 0, то на первом уровне 0, 0 или 0, 1. В первом случае нам достаточно
просмотреть две вершины (найдя первый нуль, мы не ищем второй).
Во втором случае с вероятностью 1/2 нам хватит двух, а с вероятно-
стью 1/2 понадобится три или четыре. Если же в AND-корне находит-
ся 1, то в обеих OR-вершинах первого уровня находится единица, и на

226
11. Анализ игр
каждую из них нужно в среднем не больше 3/2 просмотров листьев
(с вероятностью не менее 1/2 мы сразу попадаем в лист с единицей
и второй лист не смотрим).
Дальнейшее рассуждение легко происходит по индукции. Пусть
среднее значение числа запрашиваемых листьев для любого дерева глу-
бины 2𝑘 не превосходит 3
𝑘
. Рассмотрим дерево глубины 2𝑘 + 2 с фик-
сированными значениями в листьях. Для каждого выбора порядка на
первых двух уровнях известно, какие из четырёх вершин высоты 2 бу-
дут рассмотрены. По предположению среднее число использованных ли-
стьев при рассмотрении каждой вершины высоты 2 (усреднение по всем
порядкам обхода) не больше 3
𝑘
. Дополнительно усредняем по порядкам
на двух первых уровнях и замечаем, что в среднем рассматривается не
больше трёх вершин высоты 2.
11.4.5. Получите более точную оценку для числа просмотренных
листьев в предыдущей задаче. [Указание. Используйте разные оценки
в зависимости от значения в корне; это позволит заменить
√
3 в оценке
на меньшее число (1 +
√
33)/4.]
11.4.6. Покажите, что для любого набора значений в листьях AND-
OR-дерева существует такой порядок просмотра сыновей, при котором
потребуется просмотреть не более 2
𝑛
листьев.
11.5. Ретроспективный анализ
Существенно ли описанное в прошлом разделе улучшение алгорит-
ма (переход от полного перебора к 𝛼-𝛽-процедуре)? С одной стороны,
да: в нашем примере переход от 4
𝑛
к 3
𝑛
даёт выигрыш в (4/3)
𝑛
раз,
а (4/3)
𝑛
экспоненциально растёт с ростом 𝑛. С другой стороны, экс-
понента остаётся экспонентой, даже если её показатель уменьшается
с 4 до 3, поэтому надежды полностью проанализировать даже не очень
сложную и долгую игру таким способом почти нет.
Поэтому на практике обычно выбирают некоторую оценку пози-
ции | легко вычислимую функцию, которая по мнению практиков
как-то отражает преимущество того или иного игрока (скажем, мате-
риальный перевес в шахматах). Затем вместо настоящей игры рассма-
тривают ограниченную игру, в которой делается сравнительно неболь-
шое число 𝑘 ходов, а затем результатом игры считается оценка полу-
ченной позиции, и в этой игре выполняют перебор (применяя 𝛼-𝛽-опти-
мизацию). Конечно, это ничего не гарантирует в настоящей игре, но
что поделаешь.

11.5. Ретроспективный анализ
227
Бывают, однако, и ситуации, когда удаётся определить цену данной
позиции точно. Это удаётся сделать для шахматных эндшпилей с не-
большим числом фигур | например, можно рассчитать, за какое ми-
нимальное число ходов можно поставить мат королём, слоном и конём
против одинокого короля в заданных начальных условиях. Заметим,
что при этом число ходов может измеряться десятками, а каждый ход
имеет десятки вариантов, поэтому о полном переборе (или даже о не-
сколько сокращённом) не может идти и речи.
11.5.1. Придумайте другой подход, использующий ограниченность
общего числа возможных позиций (скажем, для четырёх упомянутых
фигур на шахматной доске это 64
4
= 2
24
= 16 «мегапозиций»; с учётом
очерёдности хода будет 32 мегапозиции; массив такого размера поме-
щается в память современных компьютеров без труда).
Решение. Заведём массив, отведя ячейку для каждой позиции. Про-
смотрим его один раз и отметим все матовые позиции (записав туда
число 0 в знак того, что позиция проиграна и больше ходить нельзя).
Затем просмотрим массив ещё раз и пометим как выигрышные все по-
зиции, из которых можно пойти в матовые (напишем там 1 в знак того,
что можно выиграть за 1 ход). Затем отметим все (ещё не отмеченные)
позиции, из которых все ходы ведут в позиции с меткой 1, написав
там
−
2; они проигрываются в два хода. Затем | позиции, из которых
есть ход в позиции с меткой
−
2 (написав там 3), после этого | позиции,
из которых все ходы ведут в 1- или 3-позиции (написав там
−
4) и т. п.
Так будем делать до тех пор, пока будут появляться новые пометки.
Как только это кончится, для каждой позиции будет известно, можно
ли в ней выиграть и сколько ходов для этого нужно.
Фактически эта процедура повторяет доказательство теоремы Цер-
мело (но дополнительно мы получаем информацию о том, сколько ходов
до выигрыша или проигрыша при наилучшей игре).
11.5.2. Могут ли при этом остаться неотмеченные позиции и чему
они соответствуют?
Ответ. Это позиции, в которых оба игрока могут гарантировать
сколь угодно длинную игру без проигрыша. Впрочем, правило тро-
екратного повторения позиции в шахматах в этом случае позволяет
считать партию ничейной. (На самом деле учёт этого правила суще-
ственно осложняет ситуацию, поскольку теперь в понятие позиции на-
до включать информацию о том, какие конфигурации фигур на доске
уже встречались.)

228
11. Анализ игр
А. Л. Брудно заметил, что есть ситуация, в которой такой «ретро-
спективный» анализ требует совсем небольших ресурсов и может быть
реализован на очень небольшой памяти, хотя для человека соответству-
ющая задача не проста: пусть белые имеют короля на поле c3, которого
им запрещено двигать, и ферзя (на каком-то другом поле) и хотят по-
ставить мат одинокому чёрному королю. Ограничение (неподвижность
короля), затрудняющее жизнь человеку-шахматисту, облегчает анализ
(уменьшая количество позиций почти что в 64 раза за счёт того, что
не надо рассматривать разные положения короля!)
Использование таблицы описанного типа можно считать примене-
нием метода динамического программирования (мы не вычисляем цену
игры для одной и той же позиции снова и снова, обходя дерево, а за-
полняем таблицу цен систематически).

12. ОПТИМАЛЬНОЕ
КОДИРОВАНИЕ
12.1. Коды
Имея 2
𝑛
символов, мы можем кодировать каждый из них 𝑛 бита-
ми, поскольку существует 2
𝑛
комбинаций из 𝑛 битов. Например, мож-
но закодировать 4 = 2
2
символа А, Г, Т, Ц (используемые при запи-
си геномов) двухбитовыми комбинациями 00, 01, 10 и 11. Другой при-
мер: последовательностями из 8 битов (байтами) можно закодировать
256 символов (и этого хватает на латинские и русские буквы, знаки
препинания и др.).
Более формально: пусть нам дан алфавит, то есть конечное мно-
жество, элементы которого называются символами или буквами этого
алфавита. Кодом для алфавита 𝐴 называется функция (таблица) 𝛼, ко-
торая для каждого символа 𝑎 из 𝐴 указывает двоичное слово 𝛼(𝑎), на-
зываемое кодовым словом, или просто кодом этого символа. (Двоичное
слово | конечная последовательность нулей и единиц.) Не требуется,
чтобы коды всех символов имели равные длины.
Мы допускаем, чтобы разные символы имели одинаковые коды. Со-
гласно нашему определению, разрешается все буквы алфавита закоди-
ровать словом 0 (и даже пустым словом) | но, конечно, такой код будет
бесполезен. Хороший код должен позволять декодирование (восстано-
вление последовательности символов по её коду).
Формально это определяется так. Пусть фиксирован алфавит 𝐴 и
код 𝛼 для этого алфавита. Для каждого слова 𝑃 в алфавите 𝐴 (то есть
для любой конечной последовательности букв алфавита 𝐴) рассмотрим
двоичное слово 𝛼(𝑃 ), которое получается, если записать подряд коды
всех букв из 𝑃 (без каких-либо разделителей). Код 𝛼 называется одно-
значным, если коды различных слов различны: 𝛼(𝑃 )
̸
= 𝛼(𝑃
′
) при 𝑃
̸
= 𝑃
′
.
12.1.1. Рассмотрим трёхбуквенный алфавит
{
𝑎, 𝑏, 𝑐
}
и код 𝛼(𝑎) = 0,
𝛼(𝑏) = 01 и 𝛼(𝑐) = 00. Будет ли этот код однозначным?

230
12. Оптимальное кодирование
Решение. Нет, поскольку слова 𝑎𝑎 и 𝑐 кодируются одинаково.
12.1.2. Для того же алфавита рассмотрим код 𝛼(𝑎) = 0, 𝛼(𝑏) = 10
и 𝛼(𝑐) = 11. Будет ли этот код однозначным?
Решение. Будет. Чтобы доказать это, достаточно объяснить, как
можно восстановить слово 𝑃 по его коду 𝛼(𝑃 ). Если 𝛼(𝑃 ) начинается
с нуля, то ясно, что слово 𝑃 начинается с 𝑎. Если 𝛼(𝑃 ) начинается
с единицы, то слово 𝑃 начинается с 𝑏 или с 𝑐 | чтобы узнать, с чего
именно, достаточно посмотреть на второй бит слова 𝛼(𝑃 ). Восстановив
первую букву слова 𝑃 , мы забываем о ней и о её коде, и продолжаем
всё сначала.
Верно и более общее утверждение. Назовём код префиксным, если
коды букв не являются началами друг друга (слово 𝛼(𝑝) не является
началом слова 𝛼(𝑞), если буквы 𝑝 и 𝑞 различны).
12.1.3. Докажите, что любой префиксный код является однознач-
ным.
Решение. Декодирование можно вести слева направо. Первая буква
восстанавливается однозначно: если для двух букв 𝑝 и 𝑞 слова 𝛼(𝑝)
и 𝛼(𝑞) являются началами кода, то одно из слов 𝛼(𝑝) и 𝛼(𝑞) является на-
чалом другого, что невозможно для префиксного кода. И так далее.
12.1.4. Приведите пример однозначного кода, не являющегося пре-
фиксным.
[Указание. Пусть 𝛼(𝑎) = 0, 𝛼(𝑏) = 01, 𝛼(𝑐) = 11. Этот код является
«суффиксным», но не префиксным.]
12.1.5. Найдите таблицу для азбуки Морзе. Объясните, почему её
можно использовать на практике, хотя она не является ни префиксным,
ни даже однозначным кодом.
12.2. Неравенство Крафта { Макмиллана
Зачем вообще нужны коды с разной длиной кодовых слов? Дело в
том, что на практике разные символы алфавита встречаются с разной
частотой, и выгодно закодировать частые символы короткими слова-
ми. (Это соображение, кстати, учитывалось при составлении азбуки
Морзе.)
Пусть для каждой буквы 𝑎 алфавита 𝐴 фиксирована её частота
𝑝(𝑎) | положительное число, причём суммы частот всех букв равны

12.2. Неравенство Крафта { Макмиллана
231
единице. Тогда для любого кода 𝛼 можно определить среднюю длину
этого кода как сумму
𝐸 =
∑︁
𝑝(𝑎)
|
𝛼(𝑎)
|
по всем буквам 𝑎
∈
𝐴, где
|
𝛼(𝑎)
|
| длина кодового слова 𝛼(𝑎) буквы 𝑎.
(Смысл этого определения: если в слове длины 𝑁 буква 𝑎 встречается
с частотой 𝑝(𝑎), то таких букв будет 𝑁𝑝(𝑎) и на их кодирование уйдёт
𝑁𝑝(𝑎)
|
𝛼(𝑎)
|
битов; общая длина кода будет
∑︀
𝑁𝑝(𝑎)
|
𝛼(𝑎)
|
и в среднем
на кодирование каждой буквы уйдёт 𝐸 битов.)
Теперь возникает задача: для данных частот построить однознач-
ный код минимальной средней длины. Теоретически это можно сделать
перебором (если в коде есть хотя бы одно очень длинное кодовое слово,
то его средняя длина велика, поэтому такие коды можно не рассматри-
вать; остаётся конечное число вариантов). Но можно обойтись и без
перебора, и в этом разделе мы научимся это делать.
Для начала поймём, что мешает нам выбирать кодовые слова корот-
кими. Оказывается, что есть ровно одно препятствие: длины 𝑛
1
, . . . , 𝑛
𝑘
кодовых слов должны удовлетворять неравенству
2
−
𝑛
1
+ 2
−
𝑛
2
+ . . . + 2
−
𝑛
𝑘
6
1,
называемому в теории кодирования неравенством Крафта { Макмил-
лана.
12.2.1. Проверьте, что оно выполнено для рассмотренных выше
примеров однозначных кодов.
12.2.2. Докажите, что для всякого префиксного кода выполняется
неравенство Крафта { Макмиллана.
Решение. Отрезок [0, 1] можно разбить на две половины. Назовём
левую 𝐼
0
, а правую 𝐼
1
. Каждую из них разобьём пополам: отрезок 𝐼
0

жүктеу/скачать 1,66 Mb.

Достарыңызбен бөлісу: