```pascal
procedure add(i:1..n);
begin
    if вершина i закрашена then begin
        ничего делать не надо
    end else begin
        закрасить i (напечатать и пометить как закрашенную
            для всех j, соседних с i
        add(j);
    end;
end;
end;
```

Докажем, что эта процедура действует правильно (в предположении, что рекурсивные вызовы работают правильно). В самом деле, ничего, кроме связанной компоненты незакрашенного графа, она закрасить не может. Проверим, что вся она будет закрашена. Пусть k — вершина, доступная из вершины i по пути i → j → ... → k, проходящему только по незакрашенным вершинам. Будем рассматривать только пути, не возвращающиеся снова в i. Из всех таких путей выберем путь с наименьшим j (в порядке просмотра соседей в процедуре). Тогда при рассмотрении предыдущих соседей ни одна из вершин пути j → ... → k не будет закрашена (наче j не было бы минимальным) и потому k окажется в связанной компоненте незакрашенного графа к моменту вызова add(j). Что и требовалось.

Чтобы установить конечность глубины рекурсии, заметим, что на каждом уровне рекурсии число незакрашенных вершин уменьшается хотя бы на 1.

Оценим число действий. Каждая вершина закрашивается не более одного раза — при первым вызове add(i) с данным i. Все последующие вызовы происходят при закрашивании соседей — количество таких вызовов не больше числа соседей — и сводятся к проверке того, что вершина i уже закрашена. Первый же вызов состоит в просмотре всех соседей и рекурсивных вызовах add(j) для всех них. Таким образом, общее число действий, связанных с вершиной i, не превосходит константы, умноженной на число её соседей. Отсюда и вытекает требуемая оценка. ☐

7.4.6. Решите ту же задачу для ориентированного графа (напечатать все вершины, доступные из данной по стрелкам; граф может содержать циклы).

Ответ. Годится по существу та же программа (строку «для всех соседей» надо заменить на «для всех вершин, куда ведут стрелки»). ☐
Следующий вариант задачи о связной компоненте имеет скорее теоретическое значение (и называется теоремой Сэвича).

7.4.7. Ориентированный граф имеет $2^n$ вершин (двоячные слова длины $n$) и задан в виде функции есть-ребро, которая по двум вершинам $x$ и $y$ сообщает, есть ли в графе ребро из $x$ в $y$. Составьте алгоритм, который для данной пары вершин $u$ и $v$ определяет, есть ли путь (по рёбрам) из $u$ в $v$, используя память, ограниченную многочленом от $n$. (Время при этом может быть — и будет — очень большим.)

[Указание. Используйте рекурсивную процедуру, выясняющую, существует ли путь из $x$ в $y$ длины не более $2^k$ (и вызывающую себя с уменьшенным на единицу значением $k$).] □

**Быстрая сортировка Хоара.** В заключение приведём рекурсивный алгоритм сортировки массива, который на практике является одним из самых быстрых. Пусть дан массив $a[1]...a[n]$. Рекурсивная процедура `sort(1,r:integer)` сортирует участок массива с индексами из полуинтервала `(1,r]`, то есть $a[1+1]...a[r]$, не затрагивая остального массива.

```
procedure sort (1,r: integer);
begin
    if 1 = r then begin
        ничего делать не надо - участок пуст
    end else begin
        выбрать случайное число s в полуинтервале (1,r]
        b := a[s]
        переставить элементы сортируемого участка так, чтобы
        сначала шли элементы, меньше b - участок (1,11]
        затем элементы, равные b - участок (11,rr]
        затем элементы, большие b - участок (rr,r]
        sort (1,11);
        sort (rr,r);
    end;
end;
```

Разделение элементов сортируемого участка на три категории (меньшие, равные, больше) рассматривалась в главе 1, с. 36 (это можно сделать за время, пропорциональное длине участка). Конечность глубины рекурсии гарантируется тем, что длина сортируемого участка на каком уровне рекурсии уменьшается хотя бы на 1.

7.4.8. (Для знакомых с основами теории вероятностей). Докажите, что математическое ожидание числа операций при работе этого ал-
горитма не превосходит $Cn \log n$, причём константа $C$ не зависит от сортируемого массива.

[Указание. Пусть $T(n)$ — максимум математического ожидания числа операций для всех входов длины $n$. Из текста процедуры вытекает такое неравенство:

$$T(n) \le Cn + \frac{1}{n} \sum_{k+l=n-1} (T(k) + T(l))$$

Первый член соответствует распределению элементов на меньшие, равные и большие. Второй член — это среднее математическое ожидание для всех вариантов случайного выбора. (Строго говоря, поскольку среди элементов могут быть равные, в правой части вместо $T(k)$ и $T(l)$ должны стоять максимумы $T(x)$ по всем $x$, не превосходящим $k$ или $l$, но это не мешает дальнейшим рассуждениям.) Далее индукцией по $n$ нужно доказывать оценку $T(n) \le C'n \ln n$. При этом для вычисления среднего значения $x \ln x$ по всем $x = 1, \dots, n-1$ нужно вычислять $\int_1^n x \ln x dx$ по частям как $\int \ln x d(x^2)$. При достаточно большом $C'$ член $Cn$ в правой части перевешивается за счёт интеграла $\int x^2 d\ln x$, и индуктивный шаг проходит.] $\square$

**7.4.9.** Имеется массив из $n$ различных целых чисел и число $k$. Требуется найти $k$-е по величине число в этом массиве, сделав не более $Cn$ действий, где $C$ — некоторая константа, не зависящая от $k$ и $n$.

**Замечание.** Сортировка позволяет очевидным образом сделать это за $Cn \log n$ действий. Очевидный способ: найти наименьший элемент, затем найти второй, затем третий, ..., $k$-й требует порядка $kn$ действий, то есть не годится (константа при $n$ зависит от $k$).

[Указание. Изящный (хотя практически и бесполезный — константы слишком велики) способ сделать это таков:

А. Разобьём наш массив на $n/5$ групп, в каждой из которых по 5 элементов. Каждую группу упорядочим.

Б. Рассмотрим средние элементы всех групп и перепишем их в массив из $n/5$ элементов. С помощью рекурсивного вызова найдём средний по величине элемент этого массива.

В. Сравним этот элемент со всеми элементами исходного массива: они разделятся на большие его и меньшие его (и один равный ему). Подсчитав количество тех и других, мы узнаем, в какой из этих частей должен находиться искомый ($k$-й) элемент и каков он там по порядку.

Г. Применим рекурсивно наш алгоритм к выбранной части.
Пусть $T(n)$ — максимально возможное число действий, если этот способ применять к массивам из не более чем $n$ элементов ($k$ может быть каким угодно). Имеем оценку:

$$T(n) \le Cn + T(n/5) + T(\text{примерно } 0,7n).$$

Последнее слагаемое объясняется так: при разбиении на части каждая часть содержит не менее $0,3n$ элементов. В самом деле, если $x$ — средний из средних, то примерно половина всех средних меньше $x$. А если в пятёрке средний элемент меньше $x$, то ещё два заведомо меньше $x$. Тем самым по крайней мере $3/5$ от половины элементов меньше $x$.

Теперь по индукции можно доказать оценку $T(n) \le Cn$ (решающую роль при этом играет то обстоятельство, что $1/5 + 0,7 < 1$). □
## 8. КАК ОБОЙТИСЬ БЕЗ РЕКУРСИИ

Для универсальных языков программирования (каковым является паскаль) рекурсия не даёт ничего нового: для всякой рекурсивной программы можно написать эквивалентную программу без рекурсии. Мы не будем доказывать этого, а продемонстрируем некоторые приёмы, позволяющие избавиться от рекурсии в конкретных ситуациях.

Зачем это нужно? Ответ прагматика мог бы быть таким: во многих компьютерах (в том числе, к сожалению, и в современных, использующих так называемые RISC-процессоры), рекурсивные программы в несколько раз медленнее соответствующих нерекурсивных программ. Ещё один возможный ответ: в некоторых языках программирования рекурсивные программы запрещены. А главное, при удалении рекурсии возникают изящные и поучительные конструкции.

### 8.1. Таблица значений (динамическое программирование)

8.1.1. Следующая рекурсивная процедура вычисляет числа сочетаний (биномиальные коэффициенты). Напишите эквивалентную нерекурсивную программу.

```pascal
function C(n,k: integer):integer;
  {n >= 0; 0 <= k <= n}
begin
  if (k = 0) or (k = n) then begin
    C:=1;
  else begin {0<k<n}
    C:= C(n-1,k-1)+C(n-1,k)
  end;
end;
```
**Замечание.** $C_n^k$ — число k-элементных подмножеств n-элементного множества. Соотношение $C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$ получится, если мы фиксируем некоторый элемент n-элементного множества и отдельно подсчитаем k-элементные подмножества, включающие и не включающие этот элемент. Таблица значений $C_n^k$

<figure><img src="image_66.png" /></figure>

называется треугольником Паскаля (того самого). В нём каждый элемент, кроме крайних единиц, равен сумме двух стоящих над ним.

**Решение.** Можно воспользоваться формулой

$$C_n^k = \frac{n!}{k!(n-k)!}$$

Мы, однако, не будем этого делать, так как хотим продемонстрировать более общие приёмы устранения рекурсии. Вместо этого составим таблицу значений функции $С(n,k) = C_n^k$, заполняя её для $n = 0, 1, 2, ...$, пока не дойдём до интересующего нас элемента. ☐

**8.1.2.** Что можно сказать о времени работы рекурсивной и нерекурсивной версий в предыдущей задаче? Тот же вопрос о памяти.

**Решение.** Таблица занимает место порядка $n^2$, его можно сократить до $n$, если заметить, что для вычисления следующей строки треугольника Паскаля нужна только предыдущая. Время работы остаётся порядка $n^2$. Рекурсивная программа требует существенно большего времени: вызов $С(n,k)$ сводится к двум вызовам для $С(n-1,...)$, те — к четырём вызовам для $С(n-2,...)$ и так далее. Таким образом, время оказывается экспоненциальным (порядка $2^n$). Используемая рекурсивной версией память пропорциональна $n$ — умножаем глубину рекурсии ($n$) на количество памяти, используемое одним экземпляром процедуры (константа). ☐

Кардинальный выигрыш во времени при переходе от рекурсивной версии к нерекурсивной связан с тем, что в рекурсивном варианте одни и те же вычисления происходят много раз. Например, вызов $С(5,3)$
в конечном счёте порождает два вызова $С(3,2)$:

<figure><img src="image_67.png" /></figure>

Заполняя таблицу, мы каждую клетку заполняем только однажды — отсюда и экономия. Этот приём называется динамическим программированием, и применим в тех случаях, когда объём хранимой в таблице информации оказывается не слишком большим.

**8.1.3.** Поговорите на ту же тему на примере рекурсивной и (простейшей) нерекурсивной программ для вычисления чисел Фибоначчи, заданных соотношением

$$ \Phi_1 = \Phi_2 = 1; \quad \Phi_n = \Phi_{n-1} + \Phi_{n-2} \quad (n > 2). $$

☐

**8.1.4.** Дан выпукльный $n$-угольник (заданный координатами своих вершин в порядке обхода). Его разрезают на треугольники диагоналями, для чего необходимо $n-2$ диагонали (это можно доказать индукцией по $n$). Стоимостью разрезания назовём сумму длин всех использованных диагоналей. Найдите минимальную стоимость разрезания. Число действий должно быть ограничено некоторым многочленом от $n$. (Перебор не подходит, так как число вариантов не ограничено многочленом.)

**Решение.** Будем считать, что вершины пронумерованы от 1 до $n$ и идут по часовой стрелке. Пусть $k, l$ — номера вершин, причём $l > k$. Через $A(k,l)$ обозначим многоугольник, отрезаемый от нашего хордой $k-l$. (Эта хорда разрезает многоугольник на два, один из которых включает сторону $1-n$; через $A(k,l)$ мы обозначаем другой.) Исходный многоугольник естественно обозначить $A(1,n)$. При $l=k+1$ получается «двуугольник» с совпадающими сторонами.

<figure><img src="image_68.png" /></figure>
Через $a(k,l)$ обозначим стоимость разрезания многоугольника $A(k,l)$ диагоналями на треугольники. Напишем рекуррентную формулу для $a(k,l)$. При $l = k + 1$ получается двуугольник, и мы полагаем $a(k,l) = 0$. При $l = k + 2$ получается треугольник, и в этом случае также $a(k,l) = 0$. Пусть $l > k + 2$.

<figure><img src="image_69.png" /></figure>

Хорда $k-l$ является стороной многоугольника $A(k,l)$ и, следовательно, стороной одного из треугольников, на которые он разрезан. Противоположной вершиной $i$ этого треугольника может быть любая из вершин $k+1,...,l-1$, и минимальная стоимость разрезания может быть вычислена как

$$ \min\{(\text{длина хорды } k-i) + (\text{длина хорды } i-l) + a(k,i) + a(i,l)\} $$

по всем $i = k + 1,..., l - 1$. При этом надо учесть, что при $q = p + 1$ хорда $p-q$ — не хорда, а сторона, и её длину надо считать равной 0 (по стороне разрез не проводится).

Составив таблицу для $a(k,l)$ и заполняя её в порядке возрастания числа вершин (равного $l-k+1$), мы получаем программу, использующую память порядка $n^2$ и время порядка $n^3$ (однократное применение рекуррентной формулы требует выбора минимума из не более чем $n$ чисел). $\square$

**8.1.5.** Матрицей размера $m \times n$ называется прямоугольная таблица из $m$ строк и $n$ столбцов, заполненная числами. Матрицу размера $m \times n$ можно умножить на матрицу размера $n \times k$ (ширина левого сомножителя должна равняться высоте правого), и получается матрица размером $m \times k$. Ценой такого умножения будем считать произведение $mnk$ (таково число умножений, которые нужно выполнить при стандартном способе умножения — но сейчас это нам не важно). Умножение матриц ассоциативно, поэтому произведение $s$ матриц можно вычислять в разном порядке. Для каждого порядка подсчитаем суммарную цену всех матричных умножений. Найдите минимальную цену вычисления произведения, если известны размеры всех матриц. Число действий должно быть ограничено многочленом от числа матриц.
**Пример.** Матрицы размером $2 \times 3$, $3 \times 4$, $4 \times 5$ можно перемножать двумя способами. В первом цена равна $2 \cdot 3 \cdot 4 + 2 \cdot 4 \cdot 5 = 24 + 40 = 64$, во втором цена равна $3 \cdot 4 \cdot 5 + 2 \cdot 3 \cdot 5 = 90$.

**Решение.** Представим себе, что первая матрица написана на отрезке $[0, 1]$, вторая — на отрезке $[1, 2]$, ..., $s$-я — на отрезке $[s-1, s]$. Матрицы на отрезках $[i-1, i]$ и $[i, i+1]$ имеют общий размер, позволяющий их перемножить. Обозначим его через $d[i]$. Таким образом, исходным данным в задаче является массив $d[0]...d[s]$.

Через $a(i, j)$ обозначим минимальную цену вычисления произведения матриц на участке $[i, j]$ (при $0 \le i < j \le s$). Искомая величина равна $a(0, s)$. Величины $a(i, i+1)$ равны нулю (матрица одна и перемножать ничего не надо). Рекуррентная формула будет такой:

$$a(i, j) = \min\{a(i, k) + a(k, j) + d[i]d[k]d[j]\}$$

где минимум берётся по всем возможных местам последнего умножения, то есть по всем $k = i+1, \dots, j-1$. В самом деле, произведение матриц на отрезке $[i, k]$ есть матрица размера $d[i]d[k]$, произведение матриц на отрезке $[k, j]$ имеет размер $d[k]d[j]$, и цена вычисления их произведения равна $d[i]d[k]d[j]$. $\square$

**Замечание.** Две последние задачи похожи. Это сходство станет яснее, если написать матрицы-множители на сторонах 1-2, 2-3, ..., $(s-1)-s$ многоугольника, а на каждой хорде $i-j$ написать произведение всех матриц, стягиваемых этой хордой.

**8.1.6.** Железная дорога с односторонним движением имеет $n$ станций. Известны цены билетов от $i$-й станции до $j$-й (при $i < j$ — в обратную сторону проезда нет). Найдите минимальную стоимость проезда от начала до конца (с учётом возможной экономии за счёт пересадок). $\square$

**8.1.7.** Задано конечное множество с бинарной операцией (вообще говоря, не коммутативной и даже не ассоциативной). Имеется $n$ элементов $a_1, \dots, a_n$ этого множества и ещё один элемент $x$. Проверьте, можно ли так расставить скобки в произведении $a_1 \times \dots \times a_n$, чтобы в результате получился $x$. Число операций должно не превосходить $Cn^3$ для некоторой константы $C$ (ависящей от числа элементов в выбранном конечном множестве).

**Решение.** Заполняем таблицу, в которой для каждого участка $a_i...a_j$ нашего произведения хранится список всех возможных его значений (при разной расстановке скобок). $\square$
По существу этот же приём применяется в полиномиальном алгоритме проверки принадлежности слова произвольному контекстно-свободному языку (см. главу 15).

Следующая задача (задача о рюкзаке) уже упоминалась в главе 3.

**8.1.8.** Имеется $n$ положительных целых чисел $x_1, \dots, x_n$ и число $N$. Выясните, можно ли получить $N$, складывая некоторые из чисел $x_1, \dots, x_n$. Число действий должно быть порядка $Nn$.

[Указание. После $i$ шагов хранится множество тех чисел на отрезке $0 \dots N$, которые представимы в виде суммы некоторых из $x_1 \dots x_i$.] ☐

**Замечание.** Мы видели, что замена рекурсивной программы на заполнение таблицы значений иногда позволяет уменьшить число действий. Примерно того же эффекта можно добиться иначе: оставить программу рекурсивной, но в ходе вычислений запоминать уже вычисленные значения, а перед очередным вычислением проверять, нет ли уже готового значения.

## 8.2. Стек отложенных заданий

Другой приём устранения рекурсии продемонстрируем на примере задачи о ханойских башнях.

**8.2.1.** Напишите нерекурсивную программу для нахождения последовательности перемещений колец в задаче о ханойских башнях.

**Решение.** Вспомним рекурсивную программу, перекладывающую $i$ верхних колец с $m$ на $n$:

```pascal
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$ дисками
и к одной задаче с единственным диском. Занимаясь этими задачами, важно не позабыть, что ещё осталось сделать.

Для этой цели заведём стек отложенных заданий, элементами которого будут тройки (i, m, n). Каждая такая тройка интерпретируется как заказ «переложить i верхних дисков с m-го стержня на n-й». Заказы упорядочены в соответствии с требуемым порядком их выполнения: самый срочный — вершина стека. Получаем такую программу:

```pascal
procedure move(i,m,n: integer);
begin
  сделать стек заказов пустым
  положить в стек тройку <i,m,n>
  {инвариант: осталось выполнить заказы в стеке}
  while стек непуст do begin
    удалить верхний элемент, переложив его в <j,p,q>
    if j = 1 then begin
      writeln ('сделать ход', p, '->', q);
    end else begin
      s:=6-p-q;
      {s - третий стержень: сумма номеров равна 6}
      положить в стек тройки <j-1,s,q>, <1,p,q>, <j-1,p,s>
    end;
  end;
end;
```

(Заметим, что первой в стек кладётся тройка, которую надо выполнять последней.) Стек троек может быть реализован как три отдельных стека. (Кроме того, в паскале есть специальный тип, называемый «запись» (record), который может быть применён.) ☐

### 8.2.2. (Сообщил А. К. Звонкин со ссылкой на Анджея Лисовского.)
Для задачи о ханойских башнях есть и другие нерекурсивные алгоритмы. Вот один из них: простаивающим стержнем (не тем, с которого переносят, и не тем, на который переносят) должны быть все стержни по очереди. Другое правило: поочерёдно перемещать наименьшее кольцо и не наименьшее кольцо, причём наименьшее — по кругу. ☐

### 8.2.3. Используйте замену рекурсии стеком отложенных заданий в рекурсивной программе печати десятичной записи целого числа.

**Решение.** Цифры добываются с конца и закладываются в стек, а за- тем печатаются в обратном порядке. ☐

### 8.2.4. Напишите нерекурсивную программу, печатающую все вер- шины двоичного дерева.
**Решение.** В этом случае стек отложенных заданий будет содержать заказы двух сортов: «напечатать данную вершину» и «напечатать все вершины поддерева с данным корнем» (при этом *nil* считается корнем пустого дерева). Таким образом, элемент стека есть пара: (тип заказа, номер вершины).

Вынимая элемент из стека, мы либо сразу исполняем его (если это заказ первого типа), либо помещаем в стек три порождённых им заказа — в одном из шести возможных порядков. ☐

**8.2.5.** Что изменится, если требуется не печатать вершины двоичного дерева, а подсчитать их количество?

**Решение.** Печатание вершины следует заменить прибавлением единицы к счётчику. Другими словами, инвариант таков: (общее число вершин) = (счётчик) + (сумма чисел вершин в поддеревьях, корни которых лежат в стеке). ☐

**8.2.6.** Для некоторых из шести возможных порядков возможны упрощения, делающие ненужным хранение в стеке элементов двух видов. Укажите некоторые из них.

**Решение.** Если требуемый порядок таков:

корень, левое поддерево, правое поддерево,

то заказ на печатание корня можно не закладывать в стек, а выполнять сразу.

Несколько более сложная конструкция применима для порядка

левое поддерево, корень, правое поддерево.

В этом случае все заказы в стеке, кроме самого первого (напечатать поддерево) делятся на пары:

напечатать вершину х, напечатать «правое поддерево» х

(= поддерево с корнем в правом сыне х). Объединив эти пары в заказы специального вида и введя переменную для отдельного хранения первого заказа, мы обойдёмся стеком однотипных заказов.

То же самое, разумеется, верно, если поменять местами левое и правое — получается ещё два порядка. ☐

**Замечание.** Другую программу печати всех вершин дерева можно построить на основе программы обхода дерева, разобранной в главе 3. Там используется команда «вниз». Поскольку теперешнее представление дерева с помощью массивов 1 и r не позволяет найти предка заданной вершины, придётся хранить список всех вершин на пути от корня к текущей вершине. См. также главу 9.
**8.2.7.** Напишите нерекурсивный вариант программы быстрой сортировки (см. с. 132). Как обойтись стеком, глубина которого ограничена $C \log n$, где $n$ — число сортируемых элементов?

**Решение.** В стек кладутся пары $(i, j)$, интерпретируемые как отложенные задания на сортировку соответствующих участков массива. Все эти заказы не пересекаются, поэтому размер стека не может превысить $n$. Чтобы ограничиться стеком логарифмической глубины, будем придерживаться такого правила: глубже в стек помещать больший из возникающих двух заказов. Пусть $f(n)$ — максимальная глубина стека, которая может встретиться при сортировке массива из не более чем $n$ элементов таким способом. Оценим $f(n)$ сверху таким способом: после разбиения массива на два участка мы сначала сортируем более короткий (храня в стеке более длинный про запас), при этом глубина стека не больше $f(n/2) + 1$, затем сортируем более длинный, так что

$$f(n) \le \max(f(n/2) + 1, f(n-1)),$$

откуда очевидной индукцией получаем $f(n) = O(\log n)$. $\square$

<figure><img src="image_70.png" /></figure>

## 8.3. Более сложные случаи рекурсии

Пусть функция $f$ с натуральными аргументами и значениями определена рекурсивно условиями

$$ \begin{aligned} f(0) &= a, \\ f(x) &= h(x, f(l(x))) \quad (x > 0) \end{aligned} $$

где $a$ — некоторое число, $a$ и $l$ — известные функции. Другими словами, значение функции $f$ в точке $x$ выражается через значение $f$ в точке $l(x)$. При этом предполагается, что для любого $x$ в последовательности

$$x, l(x), l(l(x)), \dots$$

рано или поздно встретится 0.

Если дополнительно известно, что $l(x) < x$ для всех $x$, то вычисление $f$ не представляет труда: вычисляем последовательно $f(0), f(1), f(2), \dots$.

**8.3.1.** Напишите нерекурсивную программу вычисления $f$ для общего случая.

**Решение.** Для вычисления $f(x)$ вычисляем последовательность

$$l(x), l(l(x)), l(l(l(x))), \dots$$
до появления нуля и запоминаем её, а затем вычисляем значения $f$ в точках этой последовательности, идя справа налево. □

Ещё более сложный случай из следующей задачи вряд ли встретится на практике (а если и встретится, то проще рекурсию не устранять, а оставить). Но тем не менее: пусть функция $f$ с натуральными аргументами и значениями определяется соотношениями

$$ 
\begin{aligned}
f(0) &= a, \\
f(x) &= h(x, f(l(x)), f(r(x))) \quad (x > 0),
\end{aligned}
$$

где $a$ — некоторое число, а $l, r$ и $h$ — известные функции. Предполагается, что если взять произвольное число и начать применять к нему функции $l$ и $r$ в произвольном порядке, то рано или поздно получится 0.

### 8.3.2. Напишите нерекурсивную программу вычисления $f$.

**Решение.** Можно было бы сначала построить дерево, у которого в корне находится $x$, а в сыновьях вершины $i$ стоят $l(i)$ и $r(i)$ — если только $i$ не равно нулю. Затем вычислять значения функции, идя от листвьев к корню. Однако есть и другой способ.

Обратной польской записью (или постфиксной записью) выражения называют запись, где знак функции стоит после всех её аргументов, а скобки не используются. Вот несколько примеров:

```
f(2)                 2 f
f(g(2))             2 g f
s(2, t(7))          2 7 t s
s(2, u(2, s(5, 3)))  2 2 5 3 s u s
```

Постфиксная запись выражения позволяет удобно вычислять его с помощью стекового калькулятора. Этот калькулятор имеет стек, который мы будем представлять себе расположенным горизонтально (числа вынимаются и кладутся справа), и клавиши — числовые и функциональные. При нажатии на клавишу с числом это число кладётся в стек. При нажатии на функциональную клавишу соответствующая функция применяется к нескольким аргументам у вершины стека. Например, если в стеке были числа

2 3 4 5 6

и нажата функциональная клавиша $s$, соответствующая функции от двух аргументов, то в стеке окажутся числа

2 3 4 $s(5, 6)$.
Перейдём теперь к нашей задаче. В процессе вычисления значения функции $f$ мы будем работать со стеком чисел, а также с последовательностью чисел и символов $f, l, r, h$, которую мы будем интерпретировать как последовательность нажатий клавиш на стековом калькуляторе. Инвариант такой:

если стек чисел представляет собой текущее состояние стекового калькулятора, то после нажатия всех клавиш последовательности в стеке останется единственное число, и оно будет искомым ответом.

Пусть нам требуется вычислить значение $f(x)$. Тогда вначале мы помещаем в стек число $x$, а последовательность содержит единственный символ $f$. (При этом инвариант соблюдается.) Далее с последовательностью и стеком выполняются такие преобразования:

<table><thead><tr><th>старый стек</th><th>старая последовательность</th><th>новый стек</th><th>новая последовательность</th></tr></thead><tbody><tr><td>X</td><td>x P</td><td>X x</td><td>P</td></tr><tr><td>X x</td><td>l P</td><td>X l(x)</td><td>P</td></tr><tr><td>X x</td><td>r P</td><td>X r(x)</td><td>P</td></tr><tr><td>X x y z</td><td>h P</td><td>X h(x, y, z)</td><td>P</td></tr><tr><td>X 0</td><td>f P</td><td>X a</td><td>P</td></tr><tr><td>X x</td><td>f P</td><td>X</td><td>x x l f x r f h P</td></tr></tbody></table>

Здесь $x, y, z$ — числа, $X$ — последовательность чисел, $P$ — последовательность чисел и символов $f, l, r, h$. В последней строке предполагается, что $x \neq 0$. Эта строка соответствует равенству

$$f(x) = h(x, f(l(x))), f(r(x))).$$

Преобразования выполняются, пока последовательность не станет пуста. В этот момент в стеке окажется единственное число, которое и будет ответом. ☐

**Замечание.** Последовательность по существу представляет собой стек отложенных заданий (вершина которого находится слева).
# 9. РАЗНЫЕ АЛГОРИТМЫ НА ГРАФАХ

## 9.1. Кратчайшие пути

В этом разделе рассматриваются различные варианты одной задач. Пусть имеется $n$ городов, пронумерованных числами от 1 до $n$. Для каждой пары городов с номерами $i$, $j$ в таблице $a[i][j]$ хранится целое число — цена прямого авиабилета из города $i$ в город $j$. Считается, что рейсы существуют между любыми городами, $a[i][i] = 0$ при всех $i$, $a[i][j]$ может отличаться от $a[j][i]$. Наименьшей стоимостью проезда из $i$ в $j$ считается минимально возможная сумма цен билетов для маршрутов (в том числе с пересадками), ведущих из $i$ в $j$. (Она не превосходит $a[i][j]$, но может быть меньше.)

В предлагаемых ниже задачах требуется найти наименьшую стоимость проезда для некоторых пар городов при тех или иных ограничениях на массив $a$ и на время работы алгоритма.

9.1.1. Предположим, что не существует замкнутых маршрутов, для которых сумма цен отрицательна. Докажите, что в этом случае маршрут с наименьшей стоимостью существует.

**Решение.** Маршрут длиной больше $n$ всегда содержит цикл, поэтому минимум можно искать среди маршрутов длиной не более $n$, а их конечное число. ☐

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

9.1.2. Найдите наименьшую стоимость проезда из 1-го города во все остальные за время $O(n^3)$.

**Решение.** Обозначим через $\text{МинСт}(1,s,k)$ наименьшую стоимость проезда из 1 в $s$ менее чем с $k$ пересадками. Тогда выполняется та-
кое соотношение:

$$ \text{МинСт}(1, s, k+1) = \min\left(\text{МинСт}(1, s, k), \min_{i=1..n} \text{МинСт}(1, i, k) + a[i][s]\right) $$

Как отмечалось выше, искомым ответом является МинСт(1, i, n) для всех i = 1...n.

```pascal
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;
end;
```

Приведённый алгоритм называют алгоритмом динамического про-
граммирования, или алгоритмом Форда – Беллмана.

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

Решение. Инвариант будет таков:

$$ \text{МинСт}(1, i, n) \le x[i] \le \text{МинСт}(1, i, k). \quad \square $$

Этот алгоритм может быть улучшен в двух отношениях: можно за
то же время $O(n^3)$ найти наименьшую стоимость проезда i → j для
всех пар i, j (а не только при i = 1), а можно сократить время работы
do $O(n^2)$. Правда, в последнем случае нам потребуется, чтобы все цены
a[i][j] были неотрицательны.

9.1.4. Найдите наименьшую стоимость проезда i → j для всех i, j
за время $O(n^3)$.
**Решение.** Для $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.** Как проверить за $O(n^3)$ действий, имеет ли граф с $n$ вершинами циклы с отрицательной суммой?

[Указание. Можно применять алгоритм Флойда, причём разрешать $i = j$ в $A(i,j,k)$, пока не появится первый отрицательный цикл.] ☐

**9.1.6.** Имеется $n$ валют и таблица обменных курсов (сколько флюринов дают за талер и т.п.). Коммерсант хочет неограниченно обогатиться, обменивая свой начальный капитал туда-сюда по этим курсам. Как проверить, возможно ли это?

[Указание. После логарифмирования деньги уподобляются расстояниям.] ☐

**9.1.7.** Известно, что все цены неотрицательны. Найдите наименьшую стоимость проезда $1 \to i$ для всех $i = 1...n$ за время $O(n^2)$.

**Решение.** В процессе работы алгоритма некоторые города будут выделенными (в начале — только город 1, в конце — все). При этом:

* для каждого выделенного города $i$ хранится наименьшая стоимость пути $1 \to i$; при этом известно, что минимум достигается на пути, проходящем только через выделенные города;

* для каждого невыделенного города $i$ хранится наименьшая стоимость пути $1 \to i$, в котором в качестве промежуточных используются только выделенные города.

Множество выделенных городов расширяется на основании следующего замечания: если среди всех невыделенных городов взять тот, для которого хранимое число минимально, то это число является истин-
ной наименьшей стоимостью. В самом деле, пусть есть более короткий путь. Рассмотрим первый невыделенный город на этом пути — уже до него путь длиннее! (Здесь существенна неотрицательность цен.)

Добавив выбранный город к выделенным, мы должны скорректировать информацию, хранимую для невыделенных городов. При этом достаточно учесть лишь пути, в которых новый город является последним пунктом пересадки, а это легко сделать, так как минимальную стоимость проезда в новый город мы уже знаем.

При самом бесхитростном способе хранения множества выделенных городов (в булевом векторе) добавление одного города к числу выделенных требует времени $O(n)$.
☐

Этот алгоритм называют алгоритмом Дейкстры.

9.1.8. Имеется $n$ городов, соединённых дорогами (с односторонним движением). Для любых городов $i, j$ известен максимальный вес груза, который можно везти из $i$ в $j$ (грузоподъёмность дороги). Найдите за время $O(n^2)$ для всех городов максимальный вес груза, который в них можно привезти из столицы.

[Указание. Действуйте аналогично алгоритму Дейкстры, заменив сумму на максимум.] ☐

Отыскание кратчайшего пути имеет естественную интерпретацию в терминах матриц. Пусть $A$ — матрица цен одной авиакомпании, а $B$ — матрица цен другой. Пусть мы хотим лететь с одной пересадкой, причём сначала самолётом компании $A$, а затем — компании $B$. Сколько нам придётся заплатить, чтобы попасть из города $i$ в город $j$?

9.1.9. Докажите, что эта матрица вычисляется по обычной формуле для произведения матриц, только вместо суммы надо брать минимум, а вместо умножения — сумму. ☐

9.1.10. Докажите, что таким образом определённое произведение матриц ассоциативно. ☐

9.1.11. Докажите, что задача о кратчайших путях эквивалентна вычислению $A^\infty$ для матрицы цен $A$: в последовательности $A, A^2, A^3, ...$ все элементы, начиная с некоторого, равны искомой матрице стоимости кратчайших путей. (Если нет отрицательных циклов!) ☐

9.1.12. Начиная с какого элемента можно гарантировать равенство в предыдущей задаче? ☐
Обычное (не модифицированное) умножение матриц тоже может оказаться полезным, только матрицы должны быть другие. Пусть есть не все рейсы (как раньше), а только некоторые, $a[i][j]$ равно 1, если рейс есть, и 0, если рейса нет. Возведём матрицу $a$ (обычным образом) в степень $k$ и посмотрим на её $(i-j)$-й элемент.

**9.1.13.** Чему он равен?

**Ответ.** Числу различных способов попасть из $i$ в $j$ за $k$ рейсов (с $k-1$ пересадками). ☐

При описании кратчайших путей случай, когда есть не все рейсы, можно свести к исходному, введя фиктивные рейсы с бесконечно большой (или достаточно большой) стоимостью. Тем не менее возникает такой вопрос. Число реальных рейсов может быть существенно меньше $n^2$, поэтому интересны алгоритмы, которые работают эффективно в такой ситуации. Исходные данные естественно представлять тогда в такой форме: для каждого города известно число выходящих из него рейсов, их пункты назначения и цены.

**9.1.14.** Докажите, что алгоритм Дейкстры можно изменить таким образом, чтобы для $n$ городов и $m$ рейсов (всего) он требовал не более $C(n+m) \log n$ операций.

[Указание. Что надо сделать на каждом шаге? Выбрать невыделенный город с минимальной стоимостью и скорректировать цены для всех городов, в которые из него есть маршруты. Если бы кто-то сообщил нам, для какого города стоимость минимальна, то хватило бы $C(n+m)$ действий. А поддержание сведений о том, какой элемент в массиве минимален (см. задачу на с. 115), обходится ещё в множитель $\log n$.] ☐

Иногда нам нужны не все города. Пусть, скажем, в графе дорог нужно найти кратчайший путь между двумя близкими посёлками — тогда города и дороги в другой части страны нас явно не интересуют. С точки зрения алгоритма, если нас интересует расстояние от $i$ до $j$, то алгоритм Дейкстры, вычисляющий расстояния от $i$ до всех городов, можно остановить, как только город $j$ станет выделенным.

**9.1.15.** Покажите, что в этот момент выделены могут быть только города, которые не дальше от $i$, чем $j$.

[Указание. Для невыделенного города с минимальной стоимостью расстояние до него равно его стоимости, а для любого другого невыделенного города $u$ расстояние не меньше (сравним с расстоянием до первого невыделенного города на кратчайшем пути в $u$).]
Если мы (как это часто делают на практике) храним отдельно выделенные города (как множество, см. главы 13 и 14), а также невыделенные города конечной стоимости (множество плюс приоритетная очередь, с. 115), предыдущая задача ограничивает количество хранимых городов: это города, отстоящие от i не больше, чем город j, а также все их соседи. Такой способ хранения полезен, если граф задан неявно — скажем, если мы ищем кратчайший путь из одной позиции какой-то головоломки в другую. (При реализации алгоритма Дейкстры от приоритетной очереди, помимо взятия наименьшего элемента, понадобится операция увеличения приоритета элемента, но её тоже легко реализовать при способе хранения, описанном в задаче 6.4.2.)

Предыдущие замечания особенно полезны в сочетании с методом потенциалов. Пусть есть некоторая функция $\varphi$ на вершинах графа, называемая потенциалом. Изменим длины всех рёбер графа, прибавив к длине ребра из $u$ в $v$ величину $\varphi(v) - \varphi(u)$.

**9.1.16.** Докажите, что при таком изменении графа кратчайшие пути сохранятся (кратчайший путь из одной вершины в другую останется кратчайшим), но их длины изменятся: к длине кратчайшего пути из $p$ в $q$ прибавится $\varphi(q) - \varphi(p)$.

[Указание. К длине любого пути из $p$ в $q$ прибавится как раз та же самая разность $\varphi(q) - \varphi(p)$ (при сложении добавок к длинам рёбер все промежуточные члены сократятся).]

Эта задача вместе с предыдущими используется в алгоритме, называемом А*-поиском. Пусть нам надо найти кратчайшее расстояние от i до j. Возьмём в качестве потенциала некоторую эвристическую оценку расстояния до j. Тогда рёбра, идущие в сторону уменьшения этой оценки, станут короче, и поэтому алгоритм будет рассматривать их в первую очередь. Нужно только, чтобы длина всех рёбер оставалась неотрицательной, то есть чтобы длина ребра uv была не меньше $\varphi(u) - \varphi(v)$.

**9.1.17.** Покажите, что если это свойство выполнено, то эвристическая оценка расстояния будет (гарантированно) нижней оценкой.

[Указание. Как она меняется вдоль кратчайшего пути?]

**9.1.18.** Пусть рёбра в графе — это дороги, а их длина измеряется вдоль дороги. Что тогда можно выбрать в качестве такой нижней оценки?

**Ответ.** Геометрическое расстояние (по поверхности Земли) до j.
## 9.2. Связные компоненты, поиск в глубину и ширину

Наиболее простой случай задачи о кратчайших путях — если все цены равны 0 или $+\infty$. Другими словами, мы интересуемся возможностью попасть из $i$ в $j$, но за ценой не постоим. В других терминах: мы имеем ориентированный граф (картинку из точек, некоторые из которых соединены стрелками) и нас интересуют вершины, доступные из данной.

Для этого случая задачи о кратчайших путях приведённые в предыдущем разделе алгоритмы — не наилучшие. В самом деле, более быстрая рекурсивная программа решения этой задачи приведена в главе 7, а нерекурсивная — в главе 6. Сейчас нас интересует такая задача: не просто перечислить все вершины, доступные из данной, но перечислить их в определённом порядке. Два популярных случая — поиск в ширину и в глубину.

### Поиск в ширину.

Надо перечислить все вершины ориентированного графа, доступные из данной, в порядке увеличения длины пути от неё. (Тем самым мы решим задачу о кратчайших путях, когда цены рёбер равны 1 или $+\infty$.)

**9.2.1.** Придумайте алгоритм решения этой задачи с числом действий не более $C$ (число рёбер, выходящих из интересующих нас вершин).

**Решение.** Эта задача рассматривалась в главе 6, с. 114. Здесь мы приведём подробное решение. Пусть $num[i]$ — количество рёбер, выходящих из $i$, $out[i][1], ..., out[i][num[i]]$ — вершины, куда ведут рёбра. Вот программа, приведённая ранее:

```pascal
procedure Доступные (i: integer);
  {напечатать все вершины, доступные из i, включая i}
  var X: подмножество 1..n;
     P: подмножество 1..n;
     q, v, w: 1..n;
     k: integer;
begin
  ...сделать X, P пустыми;
  writeln (i);
  ...Добавить i к X, P;
  {(1) P = множество напечатанных вершин; P содержит i;
   (2) напечатаны только доступные из i вершины;
```
(3) X - подмножество P;
(4) все напечатанные вершины, из которых выходит ребро в ненапечатанную вершину, принадлежат X}
while X непусто do begin
    ...взять какой-нибудь элемент X в v;
    for k := 1 to num [v] do begin
        w := out [v][k];
        if w не принадлежит P then begin
            writeln (w);
            добавить w в P;
            добавить w в X;
        end;
    end;
end;
end;

Тогда нам было безразлично, какой именно элемент множества X выбирается. Если мы будем считать X очередью (первым пришёл — первым ушёл), то эта программа напечатает все вершины, доступные из i, в порядке возрастания их расстояния от i (числа рёбер на кратчайшем пути из i). Докажем это.

Обозначим через $V(k)$ множество всех вершин, расстояние которых от i (в описанном смысле) равно k. Имеет место такое соотношение:

$$V(k + 1) = (\text{концы рёбер с началами в } V(k)) \setminus (V(0) \cup \dots \cup V(k))$$

Докажем, что для любого $k = 0, 1, 2, \dots$ в ходе работы программы будет такой момент (после очередной итерации цикла while), когда

в очереди стоят все элементы $V(k)$ и только они;
напечатаны все элементы $V(0), \dots, V(k)$.

(Для $k = 0$ это будет состояние перед циклом.) Рассуждая по индукции, предположим, что в очереди скопились все элементы $V(k)$. Они будут просматриваться в цикле, пока не кончатся (поскольку новые элементы добавляются в конец, они не перемешаются со старыми). Конпы ведущих из них рёбер, если они уже не напечатаны, печатаются и ставятся в очередь — то есть всё как в записанном выше соотношении для $V(k + 1)$. Так что когда все старые элементы кончатся, в очереди будут стоять все элементы $V(k + 1)$. □

### Поиск в глубину.

Рассматривая поиск в глубину, удобно представлять себе ориентированный граф как образ дерева. Более точно, пусть есть ориентированный граф, одна из вершин которого выделена. Будем предполагать,
что все вершины доступны из выделенной по ориентированным путям. Построим дерево, которое можно было бы назвать «универсальным накрытием» нашего графа. Его корнем будет выделенная вершина графа. Из корня выходят те же стрелки, что и в графе — их концы будут сыновьями корня. Из них в дереве выходят те же стрелки, что и в графе и так далее. Разница между графом и деревом в том, что пути в графе, ведущие в одну и ту же вершину, в дереве «расклеены». В других терминах: вершина дерева — это путь в графе, выходящий из корня. Её сыновья — это пути, продолженные на одно ребро. Заметим, что дерево бесконечно, если в графе есть ориентированные циклы.

Имеется естественное отображение дерева в граф (вершин в вершины). При этом каждая вершина графа имеет столько прообразов, сколько путей в неё ведёт. Поэтому обход дерева (посещение его вершин в том или ином порядке) одновременно является и обходом графа — только каждая вершина посещается многократно.

Будем предполагать, что для каждой вершины графа выходящие из неё рёбра упорядочены (например, пронумерованы). Тем самым для каждой вершины дерева выходящие из неё рёбра также упорядочены. Будем обходить дерево так: сначала корень, а потом поддеревья (в порядке ведущих в них рёбер). Такой обход дерева рассматривался нами в главе 7. Ему соответствует обход графа. Если выкинуть из этого обхода повторные посещения уже посещённых вершин, то получится то, что называется «поиск в глубину».

Другими словами, на путях, выходящих из выделенной вершины, введём порядок: путь предшествует своему продолжению; если два пути расходятся в некоторой вершине, то меньшим считается тот, который выходит из неё по меньшему ребру. Вершины теперь упорядочиваются в соответствии с минимальными путями, в них ведущими. Обход вершин графа в указанном порядке называется поиском в глубину.

### 9.2.2. Напишите программу поиска в глубину.

```
[Указание. Возьмём программу обхода дерева (корень → левое поддерево → правое поддерево) из главы 7 или из главы 8 и используем её применительно к обстоятельствам. Главное изменение: не надо посещать вершины повторно. Так что если мы попали в уже посещённую вершину, то можно с ней ничего не делать. (Если путь не минимален среди ведущих в данную вершину, то и все его продолжения не минимальны — их просматривать не надо).]
```

**Замечание.** Напомним, что в главе 8 упоминались две возможности устранения рекурсии в программе обхода дерева (с. 142). Оба варианта можно использовать для поиска в глубину.
Поиск в глубину лежит в основе многих алгоритмов на графах, порой в несколько модифицированном виде.

### 9.2.3. Неориентированный граф называется двудольным, если его вершины можно раскрасить в два цвета так, что концы любого ребра — разного цвета. Составьте алгоритм проверки, является ли заданный граф двудольным, в котором число действий не превосходит $C$ (число рёбер + число вершин).

[Указание. (а) Каждую связную компоненту можно раскрашивать отдельно. (б) Выбрав цвет одной вершины и обходя её связную компоненту, мы определяем единственно возможный цвет остальных.] ☐

**Замечание.** В этой задаче безразлично, производить поиск в ширину или в глубину.

### 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] \le num[vert[s]] $$

и равенство

$$ vert[s+1] = dest[vert[s]] [edge[s]]. $$

Заметим, что конец последнего ребра нашего пути (то есть вершина $dest[vert[l]] [edge[l]]$, не включается в массив $vert$. Кроме того,
для последнего ребра мы делаем исключение, разрешая ему указывать «в пустоту», т. е. разрешаем `edge[1]` равняться `num[vert[1]]+1`.

В процессе работы алгоритм будет печатать номера вершин, при этом соблюдая требование «вершина напечатана только после тех вершин, в которые из неё ведут рёбра». Кроме того, будет выполняться такое требование (И):

вершины пути, кроме последней (`vert[1]...vert[1]`) не напечатаны, но свернув с пути налево, мы немедленно упираемся в напечатанную вершину.

Вот что получается:

```c
1:=1; vert[1]:=0; edge[1]:=1;
while not( (1=1) and (edge[1]=n+1)) do begin
    if edge[1]=num[vert[1]]+1 then begin
        {путь кончается в пустоте, поэтому все вершины,
         следующие за vert[1], напечатаны - можно
         печатать vert[1]}
        writeln (vert[1]);
        1:=1-1; edge[1]:=edge[1]+1;
    end else begin
        {edge[1] <= num[vert[1]], путь кончается в
         вершине}
        lastvert:= dest[vert[1]][edge[1]]; {последняя}
        if lastvert напечатана then begin
            edge[1]:=edge[1]+1;
        end else begin
            1:=1+1; vert[1]:=lastvert; edge[1]:=1;
        end;
    end;
end;
{путь сразу же ведёт в пустоту, поэтому все вершины
левее, то есть 1..n, напечатаны}
```

**9.2.5.** Докажите, что если в графе нет циклов, то этот алгоритм заканчивает работу.

**Решение.** Пусть это не так. Каждая вершина может печататься только один раз, так что с некоторого момента вершины не печатаются. В графе без циклов длина пути ограничена (вершина не может входить в путь дважды), поэтому подождав ещёё, мы можем дождаться момента, после которого путь не удлиняется. После этого может разве что увеличиваться `edge[1]` — но и это не беспредельно. □
Тем самым мы построили искомый нерекурсивный алгоритм топологической сортировки графа. ☐

9.2.6. Докажите, что время работы этого алгоритма не превосходит $O(\text{число вершин} + \text{число рёбер})$. ☐

9.2.7. Как модифицировать алгоритм так, чтобы он отыскивал один из циклов, если таковые имеются, и производил топологическую сортировку, если циклов нет? ☐

## 9.3. Сети, потоки и разрезы

В этом разделе мы разберём алгоритм для решения ещё одного типа задач, связанных с графами.

9.3.1. В пункте А добывают нефть, а в пункте В её перерабатывают. Доставка от добычи до переработки происходит по трубам. Около каждой трубы показана её пропускная способность: сколько единиц нефти можно по ней прокачать за единицу времени. Какое максимальное количество нефти можно доставить из А в В за единицу времени и как это сделать?

<figure><img src="image_71.png" /></figure>

**Решение.** Сразу же ясно, что больше 10 из А не вывезти (потому что есть только трубы 4 и 6), да и в В не доставить по той же причине. Но даже и 10 не получится: пришедшие по верхней трубе 6 единиц некуда девать (максимум можно отправить $5 = 4 + 1$). Но 9 единиц пропустить по сети можно:

<figure><img src="image_72.png" /></figure>

Около каждой трубы указано направление потока и его величина (в квадратных скобках — максимально возможная величина).
Легко поверить, что это наилучший вариант и что больше 9 единиц пропустить по сети нельзя, но если кто сомневается, можно объяснить это так. Проведём в сети границу (пунктирная линия на рисунке), разделяющую А и B.

<figure><img src="image_73.png" /></figure>

Через неё ведут трубы пропускной способности 4, 1, 4, в сумме 9, так что больше не получится. ☐

В этом разделе мы увидим, что примерно так же обстоит дело и в общем случае: в любой сети максимально возможный поток ограничен минимальным разрезом той же величины, и разберём один (самый первый и самый простой) алгоритм поиска этого потока и этого разреза.

Но прежде чем это всё точно сформулировать и доказать, надо говориться об обозначениях. В нашем примере трубы были «неориентированные» — они могли работать в обе стороны, и пропускные способности туда и сюда были одинаковые. Но это не обязательно: будем считать, что по трубе из узла *i* в узел *j* можно прокачивать $c[i, j]$ единиц, а в обратную сторону $c[j, i]$ единиц, и эти границы в принципе могут быть разными (например, для односторонней трубы одно из этих чисел равно нулю). Мы предполагаем, что узлы сети ($=\text{вершины графа}$) пронумерованы от 1 до *n*, так что *c* будет двумерным массивом чисел.

Эти обозначения вызывают несколько естественных вопросов:

* Чему равно $c[i, j]$, если из *i* в *j* нет трубы? Ответ: отсутствующая труба — всё равно что труба с нулевой пропускной способностью, так что мы полагаем $c[i, j] = c[j, i] = 0$ в этом случае. (При оценке времени работы алгоритма нам будет важно, какие рёбра есть, а каких нет, но пока что можно считать так.)

* А если из *i* в *j* ведут две трубы? Ответ: такое не разрешается, но это не важно, потому что несколько труб можно всегда заменить одной, сложив их пропускные способности.

* Чему равны $c[i, i]$? Ответ: не имеет значения, но можно считать, что $c[i, i] = 0$.

Массив $c[i, j]$ задаёт сеть (по-английски network), значение $c[i, j]$ называют пропускной способностью (capacity) трубы из *i* в *j*. Теперь
надо договориться, как мы будем представлять и хранить в алгоритме поток (flow) в этой сети, то есть схему транспортировки. Тут полезна маленькая хитрость: поток из $j$ в $i$ мы будем считать потоком из $i$ в $j$, но с противоположным знаком. Другими словами, мы будем рассматривать массив $f[i,j]$ того же размера, у которого $f[i,j] = -f[j,i]$ при всех $i,j$ от 1 до $n$. Из этого условия следует, что $f[i,i] = 0$ (и это логично: нам не нужен поток из вершины в себя). Более формально, пусть фиксированы два разных числа $s$ (номер узла-источника) и $t$ (номер узла-потребителя). Иногда $s$ называют истоком (source), а $t$ называют стоком (sink). Массив $f$ называют потоком в сети $c$, если

* $f[i,j] = -f[j,i]$ для всех $i,j$ от 1 до $n$ (уже обсуждали);

* $f[i,j] \le c[i,j]$ для всех $i,j$ от 1 до $n$ (поток по ребру не превышает его пропускной способности);

* $\sum_{j=1}^{n} f[i,j] = 0$ при всех $i$, отличных от $s$ и $t$.

Последнее условие означает, что во всех вершинах, кроме $s$ и $t$, наша условная нефть не добывается и не теряется — сколько приходит, столько и уходит. Заметим, что наши соглашения о знаках позволяют записать это условие, не разделяя входящие и выходящие рёбра, и это удобно.

**9.3.2.** Как в этих обозначениях записать сеть и поток из нашего примера?

**Решение.** Обозначим верхнюю и нижнюю вершины через $C$ и $D$ (мы используем буквы вместо номеров, но понятно, что имеется в виду).

<table><thead><tr><th>c</th><th>A</th><th>B</th><th>C</th><th>D</th></tr></thead><tbody><tr><th>A</th><td>0</td><td>0</td><td>6</td><td>4</td></tr><tr><th>B</th><td>0</td><td>0</td><td>4</td><td>6</td></tr><tr><th>C</th><td>6</td><td>4</td><td>0</td><td>1</td></tr><tr><th>D</th><td>4</td><td>6</td><td>1</td><td>0</td></tr></tbody></table>

<table><thead><tr><th>f</th><th>A</th><th>B</th><th>C</th><th>D</th></tr></thead><tbody><tr><th>A</th><td>0</td><td>0</td><td>5</td><td>4</td></tr><tr><th>B</th><td>0</td><td>0</td><td>-4</td><td>-5</td></tr><tr><th>C</th><td>-5</td><td>4</td><td>0</td><td>1</td></tr><tr><th>D</th><td>-4</td><td>5</td><td>-1</td><td>0</td></tr></tbody></table>

☐

Обратите внимание, что матрица $f$, как говорят, кососимметрична (симметричные относительно главной диагонали клетки содержат противоположные числа), а матрица $c$ симметрична. Кососимметричность матрицы $f$ — это результат нашего соглашения, что поток из $i$ в $j$ в нашей бухгалтерии учитывается дважды, со знаком плюс в одной клетке и со знаком минус в симметричной. На всякий случай ещё раз подчеркнём, что нет двух отдельных потоков «из $i$ в $j$» и «из $j$ в $i$», которые можно менять независимо; есть только один поток, который
лишь записывается в двух клетках с противоположными знаками. (Победобно тому, как переток электричества из одной страны в другую одна страна записывает как экспорт, а другая как импорт.)

А матрица $c$ симметрична из-за того, что мы рассматриваем симметричные трубы — и это, в отличие от кососимметричности потока, не обязательно. Вполне можно было бы рассматривать одностороннюю трубу (см. ниже).

**9.3.3.** Какие условия накладываются на поток из $i$ в $j$, если $c[i, j] = 2$ и $c[j, i] = -2$?

**Решение.** Условия дают $f[i, j] \le 2$ и $f[j, i] = -f[i, j] \le -2$, то есть $f[i, j] \ge 2$. Таким образом, в этой сети требуется $f[i, j] = 2$, не больше и не меньше. (Можно представить себе трубу, в которой по каким-то технологическим причинам нельзя останавливать или даже уменьшать перекачку ниже максимального уровня.) ☐

**9.3.4.** Как отразить в наших обозначениях одностороннюю трубу, по которой можно перекачивать из $i$ в $j$ не более 2 единиц, а обратно ничего перекачивать нельзя?

**Ответ.** $c[i, j] = 2$, $c[j, i] = 0$. ☐

**9.3.5.** Как записать в терминах $c[i, j]$ условие «поток из $i$ в $j$ должен быть не меньше 2 и не больше 3»?

**Ответ.** $c[i, j] = 3$, $c[j, i] = -2$. ☐

**9.3.6.** Что можно сказать о потоке в сети, если $c[i, j] = 2$, $c[j, i] = -3$?

**Ответ.** Такого потока не существует. ☐

Если отрицательные значения $c[i, j]$ вас пугают, то можно договориться рассматривать только сети, где $c[i, j] \ge 0$ при всех $i, j$. В такой сети всегда есть поток (нулевой — все требования выполнены). Так мы и считаем в дальнейшем, если обратное не оговорено явно. Заметьте, что среди $f[i, j]$ отрицательные числа всё равно будут (если поток ненулевой) — в силу кососимметричности.

В следующей задаче требуется перевести очевидный факт на математический язык и доказать его.

**9.3.7.** Покажите, что для любого потока выполнено равенство

$$ \sum_{i} f[s, i] = \sum_{j} f[j, t]. $$

Что означает это равенство на человеческом языке?
**Решение.** Левая часть — это суммарный поток из истока (в принципе туда может что-то и втекать, тогда в этой сумме есть отрицательные члены), а правая часть — суммарный поток в сток. Равенство, таким образом, можно назвать «законом сохранения материи»; оно верно, если в сети нет утечек и дополнительных источников (одно из наших условий).

Общее значение левой и правой части называют суммарной величиной потока $f$.

Как это (очевидное) утверждение доказать формально? Вот как: рассмотрим сумму $\sum_{i,j=1}^{n} f[i,j]$. Эта сумма равна нулю, так как члены $f[i,j]$ и $f[j,i]$ сокращаются, а все $f[i,i]$ равны нулю. С другой стороны, её можно переписать как

$$ \sum_{i=1}^{n} \sum_{j=1}^{n} f[i, j]. $$

По определению потока внутренняя сумма равна нулю, кроме случаев $i = s$ и $i = t$, так что от всей суммы (равной нулю, напомним) остаётся

$$ 0 = \sum_{j=1}^{n} f[s, j] + \sum_{j=1}^{n} f[t, j]. $$

Поскольку $f[t,j] = -f[j,t]$, изменяем знаки во втором слагаемом и получаем искомое равенство. $\square$

Теперь мы должны перевести на тот же математический язык утверждение о разрезах. Будем называть разрезом разбиение всех чисел от 1 до $n$ (узлов сети) на два непересекающихся класса $S$ и $T$, в котором исток $s$ попадает в $S$, а сток $t$ попадает в $T$. Будем обозначать такой разрез $(S,T)$. Пусть, помимо этого, у нас есть поток $f$. Тогда можно посчитать поток через разрез, то есть сумму

$$ \sum_{u \in S, v \in T} f[u, v], $$

которую мы будем обозначать через $f(S,T)$.

Подсчёт потока через разрез — это именно то, что делает таможенную статистика с потоком товаров через границу. И если товары производятся в одной стране, а потребляются в другой (и только), то эта сумма равна производству в истоке и потреблению в стоке. Следующая задача предлагает доказать это формально.
**9.3.8.** Пусть $(S, T)$ — произвольный разрез сети, а $f$ — поток в этой сети. Докажите, что равенство предыдущей задачи можно дополнить:

$$ \sum_{i} f[s, i] = f(S, T) = \sum_{j} f[j, t]. $$

**Решение.** Будем действовать по аналогии с предыдущей задачей: рассмотрим сумму

$$ \sum_{i \in S, j \in \{1, \dots, n\}} f[i, j], $$

но ограничим суммирование только парами $(i, j)$, для которых $i \in S$. Теперь уже сокращения не получится: хотя рёбра, у которых оба конца в $S$, появляются с плюсом и с минусом и по-прежнему сокращаются, останутся рёбра, у которых $i \in S$, а $j \in T$, им сократиться не с кем, обратного ребра в сумме нет. Так что от всей суммы останется $f(S, T)$. С другой стороны, если переписать сумму как

$$ \sum_{i \in S} \sum_{j=1}^{n} f[i, j], $$

то все внутренние суммы равны нулю при $i \neq s$, так что останется как раз поток, выходящий из истока $s$. $\square$

**9.3.9.** Повторите рассуждение для потока, входящего в сток. $\square$

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

**9.3.10.** Как изменится поток через разрех, если мы поменяем $S$ и $T$ (а также исток $s$ и сток $t$) местами, не меняя массива $f$?

**Ответ.** Изменит знак. $\square$

Зная пропускные способности рёбер через разрез, можно ограничить суммарный поток через него:

**9.3.11.** Пусть дана сеть с пропускными способностями $c[i, j]$ и некоторый поток $f[i, j]$ в ней. Пусть, с другой стороны, в этой сети есть
некоторый разрез $(S, T)$. Докажите, что суммарная величина потока не превосходит пропускной способности разреза, определяемой как

$$ \sum_{u \in S, v \in T} c[u, v]. $$

**Решение.** Доказательство короче формулировки: мы знаем, что суммарная величина потока равна потоку через разрез, а он (очевидно) не превосходит пропускной способности этого разреза. □

Заметим, что в сумме, определяющей пропускную способность разреза, все слагаемые неотрицательны (напомним, что мы ограничиваемся случаем неотрицательных чисел $c[i, j]$) — для потоков это было не так.

### 9.3.12. Иногда вместо потоков рассматривают предпотоки, в которых разрешаются потери перекачиваемой жидкости (но она не может взяться из ниоткуда). Как изменится определение? Покажите, что несмотря на такое пренебрежение экологией, количество жидкости, подходящей в сток, всё равно не превосходит пропускной способности любого разреза.

Фиксируем некоторую сеть, и будем рассматривать в ней разные потоки (напомним, что мы считаем $c[i, j]$ неотрицательными, так что нулевой поток всегда существует) и разные разрезы. У каждого потока есть суммарная величина, а у каждого разреза — пропускная способность. Задача 9.3.11 утверждает, что все первые не превосходят всех вторых — по очевидным причинам. Оказывается — и это утверждение называют теоремой Форда-Фалкерсона, — что это неравенство обращается в равенство для некоторого потока (максимального потока) и некоторого разреза (минимального разреза). Другими словами, есть число, которое является одновременно суммарной величиной некоторого потока и пропускной способностью некоторого разреза. Это число ограничивает сверху любой поток (потому что любой поток ограничен сверху минимальным разрезом) и снизу любой разрез (потому что любой разрез ограничен снизу максимальным потоком). Так что действительно названия «максимальный» и «минимальный» для потоков и разрезов оправданы.

Мы докажем теорему Форда-Фалкерсона, но не сразу. Начнём с более слабого утверждения.

### 9.3.13. Пусть имеется сеть $c$ и некоторый поток $f$ в ней. Тогда выполнено одно из двух: либо в сети $c$ существует поток большей ве-
личины, либо в ней есть разрез, у которого пропускная способность равна величине потока $f$.

(Как мы видели, эти случаи исключают друг друга: если поток равен некоторому разрезу, то большего потока уже быть не может.)

Это утверждение очевидно следует из теоремы Форда – Фалкерсона: сравнивая поток с максимальным (который существует по этой теореме), мы либо можем его увеличить, либо замечаем, что он уже равен минимальному разрезу. Но обратное рассуждение так просто не проходит (см. обсуждение после решения задачи).

**Решение.** Основная идея состоит в рассмотрении остаточной сети (residual network). Представим себе, что по трубе с пропускной способностью 3 в каком-то направлении идёт поток величины 2. В этом случае при необходимости можно увеличить этот поток ещё на 1; как говорят, остаточная пропускная способность этой трубы (в том же направлении) равна 1. Более хитрый пример: пусть есть односторонняя труба пропускной способности 2, и она полностью использована. Тогда возникает «виртуальная» труба<fnref n="1" /> в обратную сторону с той же пропускной способностью 2: если мы захотим добавить поток в обратном направлении, нужно просто уменьшить исходный поток на соответствующую величину. Формально говоря, мы рассматриваем остаточную сеть $c'$, положив $c'[i, j] = c[i, j] - f[i, j]$. Заметим, что по определению потока все значения $c'[i, j]$ неотрицательны (и нулевой поток в остаточной сети соответствует неизменённому потоку исходной).

**9.3.14.** Если в двусторонней трубе с пропускной способностью 3 сейчас поток 2 в одну сторону, то каковы пропускные способности остаточной сети в ту и другую сторону? ☐

Продолжим решение задачи 9.3.13. Для данной сети $c$ и потока $f$ в ней рассмотрим остаточную сеть. Построим ориентированный граф, проведя рёбро из $u$ в $v$ в тех случаях, когда в остаточной сети ненулевая (положительная) пропускная способность $c[u, v]$. Этот остаточный граф отражает возможности дополнительных поставок. (Заметьте, что в нём вполне могут быть одновременно рёбра из $u$ в $v$ и обратно.) Теперь есть два случая:

* В остаточном графе есть путь из истока $s$ в сток $t$. Такой путь называют дополняющим путём (augmenting path), поскольку вдоль него можно пропустить дополнительный поток из $s$ в $t$.

<footnote n="1">¹В газотранспортной отрасли это называют «виртуальным реверсом» и много спорят о законности этого.</footnote>
Почему? Посмотрим на положительные остаточные пропускные способности вдоль этого пути. Возьмём наименьшую из них, пусть это какое-то $δ > 0$. Добавим к исходному потоку дополнительный поток величины $δ$, то есть увеличим исходный поток по рёбрам дополняющего пути на $δ$, а по другим рёбрам оставим как было. (Педантичный читатель или редактор справедливо укажет на неточность в последнем предложении: если в дополняющий путь входит ребро из $u$ в $v$, то мы увеличиваем $f[u, v]$ на $δ$ и уменьшаем $f[v, u]$ на $δ$ в соответствии с нашим соглашением о знаках.) Легко проверить, что это будет потоком (добавка $δ$ как вошла, так и выйдет), и суммарная величина потока увеличится на $δ$.

* В остаточном графе нет пути из $s$ в $t$. Другими словами, вершина $t$ не входит в число вершин, доступных в этом графе из $s$. Тогда понятно, где «узкое место», в котором надо провести разрез: пусть $S$ — вершины, доступные из $s$ в остаточном графе (включая сам исток $s$), а $T$ — все остальные (включая сток $t$). Из $S$ в $T$ не ведёт рёбер в остаточном графе (из доступной вершины нельзя попасть в недоступную, иначе она была бы доступной). Значит, для рёбер из $S$ в $T$ их пропускная способность $c[u, v]$ используется потоком $f[u, v]$ полностью, и потому пропускная способность разреза равна потоку $f(S, T)$ через разрез.

Эти два случая и соответствуют двум вариантам из условия задачи. ☐

### 9.3.15. В решении есть небольшая неточность: нужно было брать не просто путь в остаточном графе, а путь, не проходящий дважды по одному ребру (например, кратчайший). Почему это важно?

**Решение.** Если путь дважды проходит по ребру, то поток по этому ребру придётся увеличивать на $2δ$, а это может превзойти остаточную пропускную способность. ☐

### 9.3.16. Докажите, что во втором из рассмотренных случаев (когда пропускная способность равна величине потока) поток по всем рёбрам пересекает разрез в одну и ту же сторону, то есть $f[u, v] \ge 0$ для всех $u \in S, v \in T$.

**Решение.** Неравенство между потоком и пропускной способностью получается сложением неравенств $f[u, v] \le c[u, v]$; оно обращается в равенство, лишь если все складываемые неравенства обращаются в равенства, и в этом случае $f[u, v] = c[u, v] \ge 0$ по предположению.

Теперь попробуем доказать теорему Форда-Фалкерсона, то есть построить поток, равный разрезу (точнее: поток, суммарная величина
которого равна пропускной способности некоторого разреза). Будем рассуждать так. Начём с произвольного потока (например, нулевого). Мы только что доказали, что либо его можно увеличить, либо он уже равен некоторому разрезу. Во втором случае всё хорошо. В первом увеличим поток, и снова применим то же рассуждение. Либо поток можно ещё увеличить, либо есть равный ему разрез — если первое, увеличим ещё и так далее, пока это не станет невозможным. Когда это случится, мы получим максимальный поток, равный минимальному разрезу.

### 9.3.17. В чём ошибка в этом рассуждении?

**Решение.** Ниоткуда не следует, что этот процесс увеличения когда-то остановится, так что слова «когда это случится» неоправданно оптимистичны. ☐

И это не просто теоретическая возможность, такое реально бывает, если никак не ограничивать выбор дополняющего пути. Начальный пример Форда – Фалкерсона был довольно сложный, но потом были придуманы более простые (Цвик в статье 1995 года построил пример с 6 вершинами и 8 рёбрами и показал, что ни один из параметров нельзя уменьшить, *Theoretical Computer Science*, **148**(1), 165–170, 1995). Идею таких примеров понять не так сложно. Представим себе сеть, в которой есть три ребра небольшой пропускной способности, а кроме этого много рёбер большой пропускной способности, которые связывают все остальные пары вершин.

<figure><img src="image_74.png" /></figure>

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

<figure><img src="image_75.png" /></figure>

Что происходит при дополнении потока по таким путям? Если до этого рёбра были недогружены на a, b, c, то после этого в двух из них недогруз уменьшится, а в одном увеличится:

$$ (a, b, c) \rightsquigarrow (a-\delta, b-\delta, c+\delta) \text{ или } (a-\delta, b+\delta, c-\delta) \text{ или } (a+\delta, b-\delta, c-\delta) $$

При этом $\delta$ выбирается максимально возможным, чтобы при дальнейшем увеличении недогруз уже стал бы отрицательным — то есть одно из чисел станет равным нулю. Следующий шаг (указанного вида) определяется однозначно: надо уменьшать два положительных числа, увеличивая нулевое, до тех пор, пока наименьшее из двух не обратится в нуль, и так далее. Легко сообразить, что если после первого шага недогруз будет $(0, \alpha, \beta)$, где $\alpha$ и $\beta$ несоизмеримы (их отношение иррационально), то процесс будет продолжаться неограниченно.

**9.3.18.** Покажите, что если $\gamma$ обратно золотому сечению, то есть является (положительным) решением уравнения $\gamma + \gamma^2 = 1$, то начав с тройки $(0, 1, \gamma)$, мы получим тройки $(\gamma, \gamma^2, 0)$, $(\gamma^3, 0, \gamma^2)$ и так далее — так что процесс будет продолжаться бесконечно. $\square$

В приведённом выше рассуждении пропущен один момент: почему остальные рёбра (большой пропускной способности, как мы сказали) никогда не насытятся? Но видно (особенно в последнем примере), что увеличение общего потока ограничено, так что если пропускные способности остальных рёбер достаточно велики, то до их насыщения дело никогда не дойдёт.

Построенный пример существенным образом использует иррациональные числа.

**9.3.19.** Покажите, что в сети с целыми (или хотя бы рациональными) пропускными способностями аналогичная ситуация невозмож-
на: увеличение потока вдоль дополняющего пути, как его ни выбирать, рано или поздно даст поток, в котором дополняющего пути не будет.

Из этого утверждения (и ранее доказанного) следует теорема Форда-Фалкерсона для частного случая графов с целыми пропускными способностями.

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

В этом рассуждении число шагов может быть большим даже для маленького графа. Это видно на совсем простом примере.

<figure><img src="image_76.png" /></figure>

**9.3.20.** Покажите, что на графе на рисунке (где $N$ — большое целое число) при неудачном выборе дополняющих путей число итераций будет не меньше $N$.

**Решение.** Будем поочерёдно использовать $s-p-q-t$ и $s-q-p-t$ в качестве дополняющих путей, начав с нулевого потока. Тогда на первом шаге поток увеличится на 1, а на каждом следующем будет увеличиваться на 2. Максимальный поток (который вообще не использует ребро $p-q$) равен $2N$, так что до него надо сделать как минимум $N$ итераций. (Видно, как неудачный выбор дополняющего пути приводит к долгой работе в тривиальном примере.) ☐

**9.3.21.** Рассмотрим сеть с целыми пропускными способностями. Докажите, что максимальный поток в ней всегда можно выбрать целочисленным (нецелые потоки могут давать тот же результат, но не могут давать большего).
**Решение.** Описанный процесс увеличения даёт целые потоки — и когда он закончится, поток равен разрезу, а этого не может превзойти никакой поток, целый или нет. □

Как же найти максимальный поток и минимальный разрез для пропивольной сети? Самый простой алгоритм для этого, называемый алгоритмом Эдмондса—Карпа в честь его изобретателей, следует описанной схеме с единственным добавлением: в качестве дополняющего пути всегда берётся кратчайший путь из $s$ в $t$ в остаточном графе. Мы уже знаем, как быстро искать кратчайший путь, так что это не проблема. Осталось только доказать, что при этом процесс сойдётся, и оценить число итераций. Начнём с первого. Вот простое (но неверное!) рассуждение: на каждом шаге одно из рёбер дополняющего пути используется полностью, и тем самым больше по нему ничего пропустить нельзя. Значит, количество рёбер в остаточном графе каждый раз уменьшается, и бесконечно так продолжаться не может.

**9.3.22.** Что неверно в этом рассуждении? (Оно не может быть верным, так как мы не используем, что дополняющий путь кратчайший.)

**Решение.** Хотя одно из рёбер дополняющего пути действительно пропадает, но общее число рёбер может не уменьшиться или даже увеличиться, поскольку возникают реверсные рёбра. (Мы видели на примерах, что одно и то же ребро может входить в дополняющий путь то в одну сторону, то в другую.)

Но тем не менее что-то в таком роде (что остаточный граф постепенно «прореживается») сказать можно.

**9.3.23.** Выберем какую-то вершину $u$ графа и будем следить за расстоянием в остаточном графе от $s$ до $u$. Докажите, что в ходе алгоритма это расстояние не может уменьшаться (а может оставаться неизменным или увеличиваться).

Аналогичное утверждение верно и для расстояния от $u$ до $t$ (симметрия).

**Решение.** Пусть мы сделали несколько шагов алгоритма, и имеется остаточная сеть (и соответствующий остаточный граф). Расклассифицируем все вершины по длине кратчайшего пути из $s$ в этом графе: в $S_0$ входит сама вершина $s$, в $S_1$ — вершины, куда из $s$ ведёт ребро, в $S_2$ — вершины на расстоянии 2, и так далее. (Эта классификация не зависит от выбора вершины $u$.) Если расстояние от $s$ до $u$ было равно какому-то $i$, то вершина $u$ попадёт в класс $S_i$.
Заметим, что кратчайший путь из $s$ в $u$ должен проходить по очереди через вершины в классах $S_0, S_1, ..., S_i$: пропустить класс он не может, так как на каждом шаге расстояние меняется на 1, а оставаться в том же классе или идти назад нельзя, тогда путь не будет кратчайшим. То же самое можно сказать и про рёбра дополняющего пути. После увеличения потока вдоль дополняющего пути добавятся обратные рёбра этого пути (если их не было) — все эти рёбра будут идти из класса с большим номером в класс с меньшим номером. И потому их добавление не сократит путь из $s$ в $u$: даже если вообще добавить все рёбра, ведущие из класса с большим номером в класс с меньшим номером, путь не сократится — какой смысл идти в точку, которая ближе к началу пути, чем текущая?

Так что расстояние или останется прежним, или увеличится (ведь одно из рёбер дополняющего пути пропало, и другого пути той же длины может не быть).

Формально говоря, мы не рассмотрели случай, когда расстояние уже было бесконечным (пути из $s$ в $u$ не было) и не доказали, что оно останется бесконечным. Тут надо сказать так: новые рёбра могут вести только в вершины, доступные из $s$, потому новых доступных вершин не появится. ☐

Как мы уже говорили, на каждом шаге работы алгоритма (увеличение потока вдоль дополняющего пути) одно из рёбер дополняющего пути (то, где пропускная способность минимальна — его ещё называют критическим ребром) исчезает, заменяясь на противоположное. Если мы оценим сверху, сколько раз это может происходить с каждым ребром, то получим и верхнюю оценку для числа шагов (умножив на общее число рёбер).

**9.3.24.** Докажите, что одно и то же ребро не может быть критическим (в ту и в другую сторону) более чем $O(n)$ раз. (Напомним, что $n$ — число вершин.)

**Решение.** Пусть нас интересует ребро $u-v$. Оно может быть критическим лишь поочерёдно в ту и в другую сторону. Будем следить, как меняются расстояния от истока до $u$ и до $v$. Мы уже знаем, что они могут только возрастать (и не превосходят $n$, раз у нас всего $n$ вершин). При этом, когда ребро критическое, одно из расстояний превышает другое ровно на 1, как мы видели. Остаётся заметить, что если есть два пешехода, которые идут по дороге в $n$ километров, не поворачивая назад, и в какой-то момент первый обгонял второго на километр, потом второй первого, потом снова первый второго и так далее, общее число таких моментов не больше $n$ (потому что между соседними моментами
один из пешеходов должен пройти как минимум два километра, а всего они проходят $2n$). $\square$

Отсюда следует, что алгоритм Эдмондса – Карпа всегда завершает работу, и тем самым мы доказали теорему Форда – Фалкерсона в общем случае (не только для целых пропускных способностей).

Можно попробовать оценить время работы этого алгоритма. Сразу видно, что он, как говорят, полиномиальный (время работы ограничено полиномом от $n$), никакого перебора экспоненциального числа вариантов в нём нет. При практической реализации полезно хранить данные (значения $c$ и $f$) не про все пары вершин, а только для тех пар, которые в изначальной сети соединены ребром (и у каждой вершины иметь спиксок соседей в исходном графе) — для всех остальных пар и в массиве $c$, и в массиве $f$ стоят только нули, которые так и остаются нулями. Если, следуя традиции, обозначать число вершин за $V$, а число рёбер за $E$, то при таком способе хранения данных

* поиск кратчайшего пути (поиск в ширину) требует $O(E)$ шагов;

* коррекция вдоль дополняющего пути требует $O(V)$ шагов (что поглощается $O(E)$ шагами поиска);

* число итераций есть $O(EV)$, потому что каждое из $E$ рёбер является критическим $O(V)$ раз.

**9.3.25.** Какое общее число шагов дают эти оценки?

**Ответ.** Всего получается $O(E^2V)$.

<figure><img src="image_77.png" /></figure>

Есть много более эффективных алгоритмов (построенных на разных идеях), это большой раздел информатики, но мы ограничимся приведённым простым алгоритмом, и в заключение приведём два примера, когда этот алгоритм можно использовать для решения других задач. Первый пример совсем простой.

**9.3.26.** Рассмотрим сеть без стока и истока, и будем искать в ней циркуляции (жидкость циркулирует по трубам, $\sum_j f[i,j] = 0$ при всех $i$). Будем разрешать отрицательные значения функции $c[i,j]$ (что означает, что в некоторых трубах указано минимальное допустимое значение потока). Как проверить, возможна ли в данной сети циркуляция?

**Решение.** Добавим к сети отдельные вершины стока и истока, и соединим их со всеми вершинами исходной сети трубами пропускной способности $c$, где $c$ — достаточно большая константа.
<figure><img src="image_78.png" /></figure>

Построим в полученной сети некоторый поток. Для этого пустим по каждой трубе какое-то разрешённое количество жидкости (предполагаем, что для каждой трубы условия на $f[i, j]$ и $f[j, i]$ не противоречат друг другу, иначе задача тривиальна), беря эту жидкость при необходимости по трубе из истока и сливая её по трубе в сток. Проблем не возникнет, поскольку мы предположили, что $c$ достаточно велико.

Итак, у нас есть некоторый поток в результирующей сети. Теперь используем алгоритм Эдмондса – Карпа для его максимизации. Ясно, что не может получиться больше $cV$, где $V$ — число вершин, и что ровно $cV$ получится в том и только том случае, когда в исходной сети существует циркуляция. $\square$

Второй пример — эта задача о максимальном паросочетании в двудольном графе. В адаптированном для школьников варианте её можно сформулировать так. Есть несколько школьников, каждый из них решил несколько задач. Надо организовать разбор максимального числа задач, при этом один и тот же школьник не может выступать дважды, и нельзя дважды рассказывать одну и ту же задачу.

**9.3.27.** Схема «кто что решил» показана на рисунке (слева школьники $a, b, c, d, e$, справа задачи 1, 2, 3, 4, 5). Какое максимальное число задач можно разобрать, соблюдая ограничения?

<figure><img src="image_79.png" /></figure>
**Решение.** Можно организовать разбор трёх задач (паросочетание $a-2, b-1, e-5$, см. рисунок).

<figure><img src="image_80.png" /></figure>

Как убедиться, что больше нельзя, не перебирая варианты? Заметим, что школьники $a, c, d, e$ не решили ничего, кроме задач 2 и 5 (а школьник $d$ даже и задачу 2 не решил, но это не важно). Поэтому из них могут выступить только двое — а двое других останутся не у дел. $\square$

**Терминология:** двудольный граф на рисунках состоит из левой доли (школьники) и правой доли (задачи). Паросочетание (способ разбора) — набор рёбер, у которых все левые концы разные (ни один школьник не выступает дважды) и все правые концы разные (ни одну задачу не рассказывают дважды). Аналогичную задачу о максимальном паросочетании можно поставить для произвольного двудольного графа (произвольной схемы соединения вершин слева и справа).

**9.3.28.** Найдите максимальное паросочетание в произвольном двудольном графе, сведя эту задачу к отысканию максимального потока.

**Решение.** Будем считать рёбра графа идущими слева направо и имеющими неограниченную пропускную способность, и добавим исток слева и сток справа, соединив их с вершинами односторонними рёбрами с пропускной способностью 1.

<figure><img src="image_81.png" /></figure>

Целочисленный поток в таком графе — это в точности паросочетание. В самом деле, приходящая из истока единица потока должна куда-то направиться. Поскольку поток целый, то она может пойти только по одному ребру. И если два таких использованных ребра при-
ведут в одну вершину справа, то из неё уже поток не сможет выйти. А как искать максимальный целочисленный поток, мы знаем, для этого даже алгоритм Эдмондса – Карпа не нужен, можно использовать любые дополняющие пути. □

В этой задаче дополняющие пути в остаточной сети имеют ясный смысл: из левой доли мы идём вправо по неиспользованным рёбрам графа, потом влево по использованным, потом снова вправо по неиспользованным и так далее, поэтому этот алгоритм называют иногда «поиск максимального паросочетания с помощью чередующихся цепей».

<figure><img src="image_82.png" /></figure>

Мы поняли, что (целочисленные) потоки в построенной сети соответствуют паросочетаниям. А чему соответствуют разрезы и что можно извлечь из совпадения максимального потока и минимального разреза? Вспомним объяснение про школьников: поток не может быть большим, потому что есть четыре школьника, которые решили одни и те же две задачи. Оказывается, что именно такого рода препятствие есть всегда, и это как раз соответствует разрезу в сети.

Представим себе, что в левой доле, где всего $m$ вершин, есть набор $U$ из $u$ вершин, у которых все их соседи входят в какой-то набор $V$ из меньшего числа вершин $v$ в правой доле.

<figure><img src="image_83.png" /></figure>

Это означает, что как минимум $u-v$ вершин слева останутся без дела, так что максимальное паросочетание не превосходит

$$m - (u - v) = m - u + v.$$

Оказывается, что такую оценку всегда можно сделать точной.
**9.3.29.** Пусть в двудольном графе (слева *m* вершин, справа *n* вершин) не существует паросочетания размера *k* > 0. Тогда в левой доле есть набор *U* из *u* вершин, а в правой доле есть набор *V* из *v* вершин, для которых (1) все соседи вершин из *U* попадают в *V*; (2) *m* - *u* + *v* < *k*.

(Поскольку исходная задача симметрична, можно сформулировать и симметричное утверждение о вершинах в правой доле и их соседях в левой доле; это эквивалентно переходу от множеств *U* и *V* к их дополнениям.)

**Решение.** Рассмотрим максимальный разрез — по теореме Форда – Фалкерсона он меньше *k*. Левая его компонента *S* содержит исток, какие-то вершины левой доли (назовём их *U*), и какие-то вершины правой доли (назовём их *V*).

<figure><img src="image_84.png" /></figure>

Заметим, что вершина в *U* не может быть соединена ребром с вершиной не из *V*, потому что тогда это ребро попадает в разрез, а такие рёбра имеют неограниченную (очень большую) пропускную способность. Пусть в *U* попало *u* вершин, а в *V* попало *v* вершин. Какие рёбра пересекают разрез? Это *m* - *u* рёбер, которые из истока ведут в вершины не из *U*, а также *v* рёбер, которые из *V* ведут в сток. Все они имеют пропускную способность 1, поэтому минимальный разрез равен *m* - *u* + *v* и меньше *k* (мы с этого начали). □

То же самое утверждение в чуть другой форме:

**9.3.30.** В школе работает несколько кружков. Требуется в каждом кружке выбрать старосту из числа участников этого кружка, причём один человек не может быть старостой двух кружков. Докажите, что это невозможно в том и только том случае, когда при некотором *u* найдётся *u* кружков, в которых вместе занимается меньше *u* человек.

**Решение.** Кружки — точки в левой доле, школьники — в правой, а рёбра ведут от кружка ко всем его участникам. □
В такой форме это утверждение называют теоремой Холла о пред-
ставителях (староста представляет свой кружок). В одну сторону оно
очевидно: если в *u* кружках всего занимаются меньше *u* человек, то
старост выбрать не удастся. В обратную сторону оно, как мы видели,
следует из теоремы Форда – Фалкерсона. Но можно доказать его и без
неё.

9.3.31. Докажите это обратное утверждение индукцией по числу кружков, рассмотрев два случая: (1) есть набор из некоторого числа *u* кружков, в которых вместе занимаются ровно *u* школьников, и (2) всегда есть запас: для любого семейства кружков общее число школьников в них больше числа кружков в семействе.

Вот ещё одна переформулировка того же утверждения, называемая теоремой Кёнига; её преимущество в том, что обе доли графа входят в неё симметричным образом.

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

Следующую задачу можно найти в сборниках олимпиадных задач для школьников, но, по-видимому, её решение по существу требует теоремы Холла в том или ином виде (а особенно просто её решить, зная о потоках и разрезах).

9.3.33. На контрольной каждый школьник решил 5 задач, и каждую задачу решило 5 школьников. Докажите, что можно организовать разбор так, чтобы каждый школьник рассказал одну из решённых им задач и все задачи были бы разобраны.

[Указание. Число задач равно числу школьников (посчитаем реше-
ния двумя способами), обозначим его за *n*. В соответствующем графе
есть дробный поток величины *n*, в котором каждая задача рассказы-
вается с весом 1/5, значит, есть и целый поток такой величины. (Если
избегать упоминания потоков, то можно заметить, что препятствие к
разбору всех задач из теоремы Холла невозможно, потому что в этом
случае из *U* выходит больше рёбер, чем может зайти в *V*.)]
# 10. СОПОСТАВЛЕНИЕ С ОБРАЗЦОМ

## 10.1. Простейший пример

**10.1.1.** Имеется последовательность символов х[1]...х[n]. Определите, имеются ли в ней идущие друг за другом символы abcd. (Другими словами, требуется выяснить, есть ли в слове х[1]...х[n] подслово abcd.)

**Решение.** Имеется примерно n (если быть точным, n-3) позиций, на которых может находиться искомое подслово в исходном слове. Для каждой из позиций можно проверить, действительно ли там оно находится, сравнив четыре символа. Однако есть более эффективный способ. Читая слово х[1]...х[n] слева направо, мы ожидаем появления буквы a. Как только она появилась, мы ищем за ней букву b, затем с, и, наконец, d. Если наши ожидания оправдываются, то слово abcd обнаружено. Если же какая-то из нужных букв не появляется, мы оказываемся у разбитого корыта и начинаем всё сначала. ☐

Этот простой алгоритм можно описать в разных терминах. Используя терминологию так называемых **конечных автоматов**, можно сказать, что при чтении слова х слева направо мы в каждый момент находимся в одном из следующих состояний: «начальное» (0), «сразу после a» (1), «сразу после ab» (2), «сразу после abc» (3) и «сразу после abcd» (4). Читая очередную букву, мы переходим в следующее состояние по правилу, указанному в таблице (см. следующую страницу). Как только мы попадём в состояние 4, работа заканчивается.

Наглядно выполнение алгоритма можно представить себе так: фишка двигается из кружка в кружок по стрелкам; стрелка выбирается так, чтобы надпись на ней соответствовала очередной букве входного слова. Чтобы этот процесс был успешным, нужно, чтобы для каждой буквы
<table><thead><tr><td>Текущее состояние</td><td>Очередная буква</td><td>Новое состояние</td></tr></thead><tbody><tr><td>0</td><td>a</td><td>1</td></tr><tr><td>0</td><td>кроме a</td><td>0</td></tr><tr><td>1</td><td>b</td><td>2</td></tr><tr><td>1</td><td>a</td><td>1</td></tr><tr><td>1</td><td>кроме a,b</td><td>0</td></tr><tr><td>2</td><td>c</td><td>3</td></tr><tr><td>2</td><td>a</td><td>1</td></tr><tr><td>2</td><td>кроме a,c</td><td>0</td></tr><tr><td>3</td><td>d</td><td>4</td></tr><tr><td>3</td><td>a</td><td>1</td></tr><tr><td>3</td><td>кроме a,d</td><td>0</td></tr></tbody></table>

Правила перехода для конечного автомата

была ровно одна подходящая стрелка из любого кружка.

<figure><img src="image_85.png" /></figure>

Соответствующая программа очевидна (мы указываем новое состояние, даже если оно совпадает со старым; эти строки можно опустить):

```pascal
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;
```
```pascal
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 своим подсловом. Эта функция не является индуктивной, но имеет индуктивное расширение

$x \mapsto$ длина максимального начала слова abcd, являющегося концом х.
## 10.2. Повторения в образце — источник проблем

**10.2.1.** Можно ли в предыдущих рассуждениях заменить слово abcd на произвольное слово?

**Решение.** Нет, и проблемы связаны с тем, что в образце могут быть повторяющиеся буквы. Пусть, например, мы ищем вхождения слова ababc. Вот появилась буква a, за ней идёт b, за ней идёт a, затем снова b. В этот момент мы с нетерпением ждём буквы с. Однако — к нашему разочарованию — вместо неё появляется другая буква, и наш образец ababc не обнаружен. Однако нас может ожидать утешительный приз: если вместо с появилась буква a, то не всё потеряно: за ней могут последовать буквы b и с, и образец-таки будет найден. ☐

Вот картинка, поясняющая сказанное:

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). Таблица перехода показана на следующей странице.
<table><thead><tr><td>Текущее состояние</td><td>Очередная буква</td><td>Новое состояние</td></tr></thead><tbody><tr><td>0</td><td>a</td><td>1 (a)</td></tr><tr><td>0</td><td>кроме a</td><td>0</td></tr><tr><td>1 (a)</td><td>b</td><td>2 (ab)</td></tr><tr><td>1 (a)</td><td>a</td><td>1 (a)</td></tr><tr><td>1 (a)</td><td>кроме a,b</td><td>0</td></tr><tr><td>2 (ab)</td><td>a</td><td>3 (aba)</td></tr><tr><td>2 (ab)</td><td>кроме a</td><td>0</td></tr><tr><td>3 (aba)</td><td>b</td><td>4 (abab)</td></tr><tr><td>3 (aba)</td><td>a</td><td>1 (a)</td></tr><tr><td>3 (aba)</td><td>кроме a,b</td><td>0</td></tr><tr><td>4 (abab)</td><td>c</td><td>5 (ababc)</td></tr><tr><td>4 (abab)</td><td>a</td><td>3 (aba)</td></tr><tr><td>4 (abab)</td><td>кроме a,c</td><td>0</td></tr></tbody></table>

Для проверки посмотрим, к примеру, на вторую снизу строку. Если прочитанная часть кончалась на `abab`, а затем появилась буква `a`, то теперь прочитанная часть кончается на `ababa`. Наибольшее начало образца (`ababc`), являющееся её концом — это `aba`. ☐

**Философский вопрос:** мы говорили, что трудность состоит в том, что есть несколько возможных положений образца, каждое из которых может оказаться истинным. Им соответствуют несколько начал образца, являющихся концами входного слова. Но конечный автомат помнит лишь самое длинное из них. Как же остальные?

**Философский ответ.** Дело в том, что самое длинное из них определяет все остальные — это его концы, одновременно являющиеся его началами.

Не составляет труда для любого конкретного образца написать программу, осуществляющую поиск этого образца описанным способом. Однако хотелось бы написать программу, которая ищет произвольный образец в произвольном слове. Это можно делать в два этапа: сначала по образцу строится таблица переходов конечного автомата, а затем читается входное слово и состояние преобразуется в соответствии с этой таблицей. Подобный метод часто используется для более сложных задач поиска (см. далее), но для поиска подслова существует более простой и эффективный алгоритм, называемый алгоритмом Кнута-Морриса-Пратта. (Ранее сходные идеи были предложены Ю. В. Матиясевичем.) Но прежде нам понадобятся некоторые вспомогательные утверждения.
## 10.3. Вспомогательные утверждения

Для произвольного слова $X$ рассмотрим все его начала, одновременно являющиеся его концами, и выберем из них самое длинное. (Не считая, конечно, самого слова $X$.) Будем обозначать его $l(X)$.

Примеры: $l(aba) = a$, $l(abab) = ab$, $l(ababa) = aba$, $l(abc) =$ пустое слово.

**10.3.1. Докажите, что все слова $l(X)$, $l(l(X))$, $l(l(l(X)))$ и т. д. являются началами слова $X$**.

**Решение.** Каждое из них (согласно определению) является началом предыдущего. ☐

По той же причине все они являются концами слова $X$.

**10.3.2. Докажите, что последовательность предыдущей задачи обрывается (на пустом слове).**

**Решение.** Каждое слово короче предыдущего. ☐

**10.3.3. Докажите, что любое слово, одновременно являющееся началом и концом слова $X$ (кроме самого $X$) входит в последовательность $l(X), l(l(X)), \dots$**

**Решение.** Пусть слово $Y$ есть одновременно начало и конец $X$. Слово $l(X)$ — самое длинное из таких слов, так что $Y$ не длиннее $l(X)$. Оба эти слова являются началами $X$, поэтому более короткое из них является началом более длинного: $Y$ есть начало $l(X)$. Аналогично, $Y$ есть конец $l(X)$. Рассуждая по индукции, можно предполагать, что утверждение задачи верно для всех слов короче $X$, в частности, для слова $l(X)$. Так что слово $Y$, являющееся концом и началом $l(X)$, либо равно $l(X)$, либо входит в последовательность $l(l(X)), l(l(l(X))), \dots$, что и требовалось доказать. ☐

## 10.4. Алгоритм Кнута–Морриса–Пратта

Алгоритм Кнута–Морриса–Пратта (КМП) получает на вход слово

$$X = x[1]x[2]\dots x[n]$$

и просматривает его слева направо буква за буквой, заполняя при этом массив натуральных чисел $1[1]\dots1[n]$, где

$$1[i] = \text{длина слова } l(x[1]\dots x[i])$$
(функция `l` определена в предыдущем пункте). Словами: `l[i]` есть длина наибольшего начала слова `x[1]...x[i]`, одновременно являющегося его концом.

**10.4.1.** Какое отношение всё это имеет к поиску подслова? Другими словами, как использовать алгоритм КМП для определения того, является ли слово А подсловом слова В?

**Решение.** Применим алгоритм КМП к слову `A#B`, где `#` — специальная буква, не встречающаяся ни в А, ни в В. Слово А является подсловом слова В тогда и только тогда, когда среди чисел в массиве `1` будет число, равное длине слова А. □

**10.4.2.** Опишите алгоритм заполнения таблицы `1[1]...1[n]`.

**Решение.** Предположим, что первые `i` значений `1[1]...1[i]` уже найдены. Мы считаем очередную букву слова (т.е. `x[i+1]`) и должны вычислить `1[i+1]`.

<figure><img src="image_86.png" /></figure>

Другими словами, нас интересуют начала `Z` слова `x[1]...x[i+1]`, одновременно являющиеся его концами — из них нам надо выбрать самое длинное. Откуда берутся эти начала? Каждое из них (не считая пустого) получается из некоторого слова `Z'` приписыванием буквы `x[i+1]`. Слово `Z'` является началом и концом слова `x[1]...x[i]`. Однако не любое слово, являющееся началом и концом слова `x[1]...x[i]`, годится — надо, чтобы за ним следовала буква `x[i+1]`.

Получаем такой рецепт отыскания слова `Z`. Рассмотрим все начала слова `x[1]...x[i]`, являющиеся одновременно его концами. Из них выберем подходящие — те, за которыми идёт буква `x[i+1]`. Из подходящих выберем самое длинное. Приписав в его конец `x[i+1]`, получим искомое слово `Z`.

Теперь пора воспользоваться сделанными нами приготовлениями и вспомнить, что все слова, являющиеся одновременно началами и концами данного слова, можно получить повторными применениями к нему функции `l` из предыдущего раздела. Вот что получается:

```pascal
i:=1; l[1] := 0;
{таблица l[1]..l[i] заполнена правильно}
while i <> n do begin
  len := l[i]
```
```pascal
{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.** Докажите, что число действий в приведённом только что алгоритме не превосходит $C_n$ для некоторой константы $C$.

**Решение.** Это не вполне очевидно: обработка каждой очередной бу- квы может потребовать многих итераций во внутреннем цикле. Однако каждая такая итерация уменьшает $len$ по крайней мере на 1, и в этом случае $l[i+1]$ окажется заметно меньше $l[i]$. С другой стороны, при увеличении $i$ на единицу величина $l[i]$ может возрасти не более чем на 1, так что часто и сильно убывать она не может — иначе убывание не будет скомпенсировано возрастанием.

Более точно, можно записать неравенство

$$1[i+1] \le l[i] - (\text{число итераций на i-м шаге}) + 1$$

или

$$(\text{число итераций на i-м шаге}) \le l[i] - l[i+1] + 1.$$

Остаётся сложить эти неравенства по всем $i$ и получить оценку сверху для общего числа итераций. $\square$

**10.4.4.** Будем использовать этот алгоритм, чтобы выяснить, явля- ется ли слово $X$ длины $n$ подсловом слова $Y$ длины $m$. (Как это делать с помощью специального разделителя #, описано выше.) При этом чи- сло действий будет не более $C(n+m)$, и используемая память тоже. Придумайте, как обойтись памятью не более $C_n$ (что может быть су- щественно меньше, если искомый образец короткий, а слово, в котором его ищут — длинное).
**Решение.** Применяем алгоритм КМП к слову A#B. При этом вычисление значений 1[1], ..., 1[n] проводим для слова Х длины n и запоминаем эти значения. Дальше мы помним только значение 1[i] для текущего i — кроме него и кроме таблицы 1[1]...1[n], нам для вычислений ничего не нужно. ☐

На практике слова Х и У могут не находиться подряд, поэтому просмотр слова Х и затем слова У удобно оформить в виде разных циклов. Это избавляет также от хлопот с разделителем.

**10.4.5.** Напишите соответствующий алгоритм (проверяющий, является ли слово Х = x[1]...x[n] подсловом слова Y = y[1]...y[m]).

**Решение.** Сначала вычисляем таблицу 1[1]...1[n] как раньше. Затем пишем такую программу:

```pascal
j:=0; len:=0;
{len - длина максимального начала слова Х, одновременно
  являющегося концом слова y[1]..y[j]}
while (len <> n) and (j <> m) do begin
    while (x[len+1] <> y[j+1]) and (len > 0) do begin
        {начало не подходит, применяем к нему функцию 1}
        len := 1[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, слово Х встретилось; иначе мы дошли до конца
  слова Y, так и не встретив Х}
```

## 10.5. Алгоритм Бойера – Мура

Этот алгоритм делает то, что на первый взгляд кажется невозможным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Как так может быть? Идея проста. Пусть, например, мы ищем образец abcd. Посмотрим на четвёртую букву слова: если, к примеру, это буква e, то нет никакой необходи
димости читать первые три буквы. (В самом деле, в образце буквы 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;

<figure><img src="image_87.png" /></figure>

В процессе поиска мы будем хранить в переменной `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$.
Возможны разные модификации этого алгоритма. Например, можно строку `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]];`

<figure><img src="image_88.png" /></figure>

Приведённый нами упрощённый вариант алгоритма Бойера–Мура в некоторых случаях требует существенно больше `n` действий (число действий порядка `mn`), проигрывая алгоритму Кнута–Морриса–Пратта.

**10.5.3.** Приведите пример ситуации, в которой образец не входит в слово, но алгоритму требуется порядка `mn` действий, чтобы это установить.

**Решение.** Пусть образец имеет вид `baaa...aa`, а само слово состоит только из букв `a`. Тогда на каждом шаге несоответствие выясняется лишь в последний момент. ☐

<figure><img src="image_89.png" /></figure>

Настоящий (не упрощённый) алгоритм Бойера–Мура гарантирует, что число действий не превосходит $C(m+n)$ в худшем случае. Он использует идеи, близкие к идеям алгоритма Кнута–Морриса–Пратта. Представим себе, что мы сравнивали образец со входным словом, идя справа налево. При этом некоторый кусок $Z$ (являющийся концом образца) совпал, а затем обнаружилось различие: перед $Z$ в образце стоит не то, что во входном слове. Что можно сказать в этот момент о входном слове? В нём обнаружен фрагмент, равный $Z$, а перед ним стоит не та буква, что в образце. Эта информация может позволить сдвинуть образец на несколько позиций вправо без риска пропустить его вхождение. Эти сдвиги следует вычислить заранее для каждого конца $Z$ нашего образца. Как говорят знатоки, всё это (вычисление таблицы сдвигов и её использование) можно уложить в $C(m+n)$ действий.

## 10.6. Алгоритм Рабина

Этот алгоритм основан на простой идее. Представим себе, что в слове длины `m` мы ищем образец длины `n`. Вырежем окошечко размера `n`
и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в окошечке с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию, определённую на словах длины $n$. Если значения этой функции на слове в окошечке и на образце различны, то совпадения нет. Только если значения одинаковы, нужно проверять совпадение по буквам.

Что мы выигрываем при таком подходе? Казалось бы, ничего — ведь чтобы вычислить значение функции на слове в окошечке, всё равно нужно прочесть все буквы этого слова. Так уж лучше их сразу сравнить с образцом. Тем не менее выигрыш возможен, и вот за счёт чего. При сдвиге окошечка слово не меняется полностью, а лишь добавляется буква в конце и убирается в начале. Хорошо бы, чтобы по этим данным можно было рассчитать, как меняется функция.

### 10.6.1. Приведите пример удобной для вычисления функции.

**Решение.** Заменим все буквы в слове и образце их номерами, представляющими собой целые числа. Тогда удобной функцией является сумма цифр. (При сдвиге окошечка нужно добавить новое число и вычесть пропавшее.) ☐

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

### 10.6.2. Приведите пример семейства удобных функций.

**Решение.** Выберем некоторое число $p$ (желательно простое, см.далее) и некоторый вычет $x$ по модулю $p$. Каждое слово длины $n$ будем рассматривать как последовательность целых чисел (заменив буквы кодами). Эти числа будем рассматривать как коэффициенты многочлена степени $n-1$ и вычислим значение этого многочлена по модулю $p$ в точке $x$. Это и будет одна из функций семейства (для каждой пары $p$ и $x$ получается, таким образом, своя функция). Сдвиг окошка на 1 соответствует вычитанию старшего члена $(x^{n-1}$ следует вычислить заранее), умножению на $x$ и добавлению свободного члена. ☐

Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число $p$ фиксировано и к тому же простое, а $X$ и $Y$ — два различных слова длины $n$. Тогда им соответствуют различные многочлены (мы предполагаем, что коды всех букв различны —
это возможно, если $p$ больше числа букв алфавита). Совпадение значений функции означает, что в точке $x$ эти два различных многочлена совпадают, то есть их разность обращается в 0. Разность есть многочлен степени $n-1$ и имеет не более $n-1$ корней. Таким образом, если $n$ много меньше $p$, то случайному $x$ мало шансов попасть в неудачную точку.

## 10.7. Более сложные образцы и автоматы

Мы можем искать не конкретное слово, а подслова заданного вида. Например, можно искать слова вида $a?b$, где вместо ? может стоять любая буква (иными словами, нас интересует буква $b$ на расстоянии 2 после буквы $a$).

**10.7.1.** Укажите конечный автомат, проверяющий, есть ли во входном слове фрагмент вида $a?b$.

**Решение.** Читая слово, следует помнить, есть ли буква $a$ на последнем месте и на предпоследнем — пока не встретим искомый фрагмент. Автомат имеет состояния 00, 01, 10, 11, их смысл таков:

00 на предпоследнем и последнем местах нет $a$

01 на предпоследнем нет, на последнем есть

10 не предпоследнем есть, на последнем нет

11 есть и там, и там

Таблица переходов автомата:

<table><thead><tr><th>Текущее состояние</th><th>Очередная буква</th><th>Новое состояние</th></tr></thead><tbody><tr><td>00</td><td>a</td><td>01</td></tr><tr><td>00</td><td>не a</td><td>00</td></tr><tr><td>01</td><td>a</td><td>11</td></tr><tr><td>01</td><td>не a</td><td>10</td></tr><tr><td>10</td><td>a</td><td>01</td></tr><tr><td>10</td><td>b</td><td>найдено</td></tr><tr><td>10</td><td>не a и не b</td><td>00</td></tr><tr><td>11</td><td>a</td><td>11</td></tr><tr><td>11</td><td>b</td><td>найдено</td></tr><tr><td>11</td><td>не a и не b</td><td>10</td></tr></tbody></table>

<figure><img src="image_90.png" /></figure>

Другой стандартный знак в образце — это звёздочка ($*$), на место которой может быть подставлено любое слово. Например, образец
ab*cd означает, что мы ищем подслово ab, за которым следует что угодно, а затем (на любом расстоянии) идёт cd.

**10.7.2.** Укажите конечный автомат, проверяющий, есть ли во входном слове образец ab*cd (в описанном только что смысле).

Решение.

<table><thead><tr><th>Текущее<br>состояние</th><th>Очередная<br>буква</th><th>Новое<br>состояние</th></tr></thead><tbody><tr><td>начальное</td><td>a</td><td>a</td></tr><tr><td>начальное</td><td>не a</td><td>начальное</td></tr><tr><td>a</td><td>b</td><td>ab</td></tr><tr><td>a</td><td>a</td><td>a</td></tr><tr><td>a</td><td>не a и не b</td><td>начальное</td></tr><tr><td>ab</td><td>c</td><td>abc</td></tr><tr><td>ab</td><td>не c</td><td>ab</td></tr><tr><td>abc</td><td>d</td><td>найдено</td></tr><tr><td>abc</td><td>c</td><td>abc</td></tr><tr><td>abc</td><td>не с и не d</td><td>ab</td></tr></tbody></table>

<figure><img src="image_91.png" /></figure>

Ещё один вид поиска — это поиск любого из слов некоторого списка.

**10.7.3.** Дан список слов X₁, ..., Xₖ и слово Y. Как определить, входит ли хотя бы одно из слов Xᵢ в слово Y (как подслово)? Количество действий не должно превосходить константы, умноженной на суммарную длину всех слов (из списка и того, в котором происходит поиск).

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

Посмотрим на дело с другой стороны. Каждому образцу из списка соответствует конечный автомат с некоторым множеством состояний. Эти автоматы можно объединить в один, множеством состояний которого будет произведение множеств состояний всех тех автоматов. Это — очень большое множество. Однако на самом деле большинство его элементов недоступны (не могут появиться при чтении входного слова) и за счёт этого получается экономия. Примерно эту идею (но в изменённом виде) мы и будем использовать.

Вспомним алгоритм Кнута-Морриса-Пратта. В нём, читая входное слово, мы хранили наибольшее начало образца, являющееся концом прочитанной части. Теперь нам следует хранить для каждого из
образцов наибольшее его начало, являющееся концом прочитанной части. Решающим оказывается такое замечание: достаточно хранить самое длинное из них — все остальные по нему восстанавливаются (как наибольшие начала образцов, являющиеся его концами).

Склеим все образцы в дерево, объединив их совпадающие начальные участки. Например, набору образцов

{aaa, aab, abab}

соответствует дерево

<figure><img src="image_92.png" /></figure>

Формально говоря, вершинами дерева являются все начала всех образцов, а сыновья вершины получаются приписыванием буквы.

Читая входное слово, мы двигаемся по этому дереву: текущая вершина — это наибольшая (самая правая) из вершин, являющихся концом прочитанной части (= наибольший конец прочитанной части, являющийся началом одного из образцов).

Определим функцию $l$, аргументами и значениями которой являются вершины дерева. Именно, $l(P) = $ наибольшая вершина дерева, являющаяся концом $P$. (Напомним, вершины дерева — это слова.) Нам понадобится такое утверждение:

**10.7.4.** Пусть $P$ — вершина дерева. Докажите, что множество всех вершин, являющихся концами $P$, равно $\{l(P), l(l(P)), \dots\}$

**Решение.** См. доказательство аналогичного утверждения для алгоритма Кнута–Морриса–Пратта. $\square$

<figure><img src="image_93.png" /></figure>

Теперь ясно, что нужно делать, находясь в вершине $P$ и читая букву $z$ входного слова. Надо просматривать последовательно вершины $P, l(P), l(l(P)), \dots$, пока не обнаружится такая, из которой выходит стрелка с буквой $z$. Та вершина, в которую эта стрелка ведёт, и будет нашим следующим положением.

Остаётся понять, как для каждой вершины дерева вычислить указатель на значение функции $l$ в этой вершине. Это делается как раньше, при этом значения $l$ для более коротких слов используются при вычислении очередного значения функции $l$. Это означает, что вершины дерева следует просматривать в порядке возрастания их длины. Нетрудно понять, что всё это можно уложить в требуемое число действий (хотя
константа зависит от числа букв в алфавите). Относящиеся к этому подробности см. в главе 9. ☐

Можно поинтересоваться, какие свойства слов распознаются с помощью конечных автоматов. Оказывается, что существует просто описываемый класс образцов, задающий все такие свойства — класс регулярных выражений.

**Определение.** Пусть фиксирован конечный алфавит Γ, не содержащий символов Λ, ε, (, ), * и | (они будут использоваться для построения регулярных выражений и не должны перемешиваться с буквами). Регулярные выражения строятся по таким правилам:

(а) буква алфавита Γ — регулярное выражение;

(б) символы Λ, ε — регулярные выражения;

(в) если А, В, С, ..., Е — регулярные выражения, то (АСС...Е) — регулярное выражение;

(г) если А, В, С, ..., Е — регулярные выражения, то (А|В|С|...|Е) — регулярное выражение;

(д) если А — регулярное выражение, то А* — регулярное выражение.

Каждое регулярное выражение задаёт множество слов в алфавите Γ по таким правилам:

(а) букве соответствует одноэлементное множество, состоящее из одногобуквенного слова, состоящего из этой буквы;

(б) символу ε соответствует пустое множество, а символу Λ — одноэлементное множество, единственным элементом которого является пустое слово;

(в) регулярному выражению (АСС...Е) соответствует множество всех слов, которые можно получить, если к слову из А приписать слово из В, затем из С, ..., затем из Е (конкатенация множеств);

(г) регулярному выражению (А|В|С|...|Е) соответствует объединение множеств, соответствующих выражениям А, В, С, ..., Е;

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

<table>
   <thead>
    <tr>
     <td>
      Выражение
     </td>
     <td>
      Множество
     </td>
    </tr>
   </thead>
   <tbody>
    <tr>
     <td>
      (a|b)*
     </td>
     <td>
      все слова из букв a и b
     </td>
    </tr>
    <tr>
     <td>
      (aa)*
     </td>
     <td>
      слова из чётного числа букв a
     </td>
    </tr>
    <tr>
     <td>
      (Λ|a|b|aa|ab|ba|bb)
     </td>
     <td>
      все слова длины не более 2 из букв a, b
     </td>
    </tr>
   </tbody>
  </table>

10.7.5. Напишите регулярное выражение, которому соответствует множество всех слов из букв a и b, в которых число букв a чётно.

Решение. Выражение b* задаёт все слова без буквы a, а выражение (b*ab*ab*) — все слова ровно с двумя буквами a. Остаётся объединить эти множества, а потом применить итерацию:

$$
((b*ab*ab*) | b*)*
$$

Другой вариант ответа:

$$
(b*ab*a)*b*
$$

<figure><img src="image_94.png" /></figure>

10.7.6. Напишите регулярное выражение, которое задаёт множество всех слов из букв a, b, c, в которых слово **bас** является подсловом.

Решение. ((a|b|c)*bac (a|b|c)*)

<figure><img src="image_95.png" /></figure>

10.7.7. Напишите регулярное выражение, которое задаёт множество всех слов из букв a, b, c, в которых слово **bас** не является подсловом.

[Указание. Эта задача сложнее предыдущей; видимо, самый простой способ её решить — перейти к конечным автоматам и вернуться обратно (см. ниже задачу 10.7.14).]

<figure><img src="image_96.png" /></figure>

Теперь задачу о поиске образца в слове можно переформулировать
так: проверить, принадлежит ли слово множеству, соответствующему
данному регулярному выражению.

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)*)
$$

<figure><img src="image_97.png" /></figure>
**10.7.9.** Докажите, что для всякого регулярного выражения можно построить конечный автомат, который распознаёт соответствующее этому выражению множество слов.

**Решение.** Нам потребуется новое понятие — понятие источника, или недетерминированного конечного автомата. Представим себе ориентированный граф — картинку из нескольких точек (вершин) и некоторых стрелок, соединяющих эти точки (рёбер). Пусть на некоторых рёбрах написаны буквы (не обязательно на всех). Пусть также среди вершин выбраны две — начальная Н и конечная К. Такая картинка называется источником.

Будем двигаться различными способами из Н в К, читая буквы по дороге (на тех стрелках, где они есть). Каждому пути из Н в К, таким образом, соответствует некоторое слово. А источнику в целом соответствует множество слов — тех слов, которые можно прочесть на путях из Н в К.

**Замечание.** Если нарисовать состояния конечного автомата в виде точек, а переходы при чтении букв изобразить в виде стрелок, то станет ясно, что конечный автомат — это частный случай источника. (С дополнительными требованиями: (а) на всех стрелках, за исключением ведущих в К, есть буквы; (б) для любой точки на выходящих из неё стрелках каждая буква встречается ровно один раз.)

Мы будем строить конечный автомат по регулярному выражению в два приёма. Сначала мы построим источник, которому соответствует то же самое множество слов. Затем для произвольного источника построим автомат, который проверяет, принадлежит ли слово соответствующему множеству.

**10.7.10.** По регулярному выражению постройте источник, задающий то же множество.

**Решение.** Индукция по построению регулярного выражения. Буквам соответствуют графы из одной стрелки. Объединение реализуется так:

<figure><img src="image_98.png" /></figure>
Нарисована картинка для объединения трёх множеств, прямоугольни-
ки — это источники, им соответствующие; указаны начальные и ко-
нечные вершины. На новых стрелках (их 6) букв не написано.

Конкатенации соответствует картинка

<figure><img src="image_99.png" /></figure>

Наконец, итерации соответствует картинка

<figure><img src="image_100.png" /></figure>

<figure><img src="image_101.png" /></figure>

10.7.11. Дан источник. Постройте конечный автомат, проверяю-
щий, принадлежит ли входное слово соответствующему множеству (то
есть можно ли прочесть это слово, идя из Н в К).

**Решение.** Состояниями автомата будут множества вершин источника. Именно, прочтя некоторое начало X входного слова, мы будем помнить множество всех вершин источника, в которые можно пройти из начальной, прочитав на пути слово X. ☐

<figure><img src="image_102.png" /></figure>

Тем самым задача 10.7.9 решена.

<figure><img src="image_103.png" /></figure>

Оказывается, что регулярные выражения, автоматы и источники
распознают одни и те же множества. Чтобы убедиться в этом, нам
осталось решить такую задачу:

10.7.12. Дан источник. Постройте регулярное выражение, задаю-
щее то же множество, что и этот источник.

**Решение.** Пусть источник имеет вершины 1, ..., k. Будем считать, что 1 — это начало, а k — конец. Через $D_{i,j,s}$ обозначим множество всех слов, которые можно прочесть на пути из i в j, если в качестве промежуточных пунктов разрешается использовать только вершины 1, ..., s. Согласно определению, источнику соответствует множество $D_{1,k,k}$.

Индукцией по s будем доказывать регулярность всех множеств $D_{i,j,s}$ при всех i и j. При $s = 0$ это очевидно (промежуточные вершины запрещены, поэтому каждое из множеств состоит только из букв).
Из чего состоит множество $D_{i,j,s+1}$? Отметим на пути моменты, в которых он заходит в $(s+1)$-ю вершину. При этом путь разбивается на части, каждая из которых уже не заходит в неё. Поэтому легко сообразить, что

$$D_{i,j,s+1} = D_{i,j,s} | (D_{i,s+1,s} \ D_{s+1,s+1,s} * \ D_{s+1,j,s})$$

(вольность записи: мы используем для операций над множествами обозначения как для регулярных выражений). Остаётся воспользоваться предположением индукции. ☐

**10.7.13.** Где ещё используется то же самое рассуждение?

**Ответ.** В алгоритме Флойда вычисления цены кратчайшего пути, см. главу 9 (Разные алгоритмы на графах). ☐

**10.7.14.** Докажите, что класс множеств, задаваемых регулярными выражениями, не изменился бы, если бы мы разрешили использовать не только объединение, но и отрицание (а следовательно, и пересечение — оно выражается через объединение и отрицание).

**Решение.** Для автоматов переход к отрицанию очевиден. ☐

**Замечание.** На практике важную роль играет число состояний автомата. Оказывается, что тут всё не так просто, и переход от источника к автомату требует экспоненциального роста числа состояний. Подробное рассмотрение связанных с этим теоретических и практических вопросов — дело особое (см. книгу Ахо, Ульмана и Сети о компиляторах).

## 10.8. Суффиксные деревья

До сих про наши программы сначала получали образец, который надо искать, а потом текст, в котором надо искать. В следующих задачах всё наоборот.

**10.8.1.** Программа получает на вход слово $Y$ длины $m$ и может его обрабатывать (пока без ограничений на время и память). Затем она получает слово $X$ длины $n$ и должна сообщить, является ли оно подсловом слова $Y$. При этом число операций при обработке слова $X$ должно быть порядка $n$ (не превосходить $cn$, где константа $c$ может зависеть от размера алфавита). Как написать такую программу?

**Решение.** Пока не накладывается никаких ограничений на время и память при обработке $Y$, это не представляет труда. Именно, надо склеить все подслова слова $Y$ в дерево, объединив слова с общими нача-
лами (как мы это делали, распознавая вхождения нескольких образцов). Например, для $Y = ababc$ получится такое дерево подслов (на ребре написана буква, которая добавляется при движении по этому ребру; вершины находятся во взаимно однозначном соответствии с подсловами слова $Y$):

<figure><img src="image_104.png" /></figure>

Пусть такое дерево построено. После этого, читая слово $X$ слева направо, мы прослеживаем $X$ в дереве, начав с корня; слово $X$ будет подсловом слова $Y$, если при этом мы не выйдем за пределы дерева. ☐

Заметим, что аналогичная конструкция годится для любого множества слов $U$, а не только для множества всех подслов данного слова: после того как соответствующее дерево построено, мы можем про любое слово $X$ определить его принадлежность к $U$ за время, пропорциональное длине $X$. (Надо только дополнительно хранить в вершине дерева информацию, принадлежит ли соответствующее ей слово множеству $U$ или лишь является началом другого слова, принадлежащего $U$.)

**10.8.2.** Решите предыдущую задачу с дополнительным ограничением: объём используемой памяти пропорционален длине слова $Y$.

**Решение.** Прежний способ не годится: число вершин дерева равно числу подслов слова $Y$, а у слова длины $m$ число подслов может быть порядка $m^2$, а не $m$. Однако мы можем «сжать» наше дерево, оставив вершинами лишь точки ветвления (где больше одного сына). Тогда на рёбрах дерева надо написать уже не буквы, а куски слова $Y$.

Вот что получится при сжатии нашего примера:

<figure><img src="image_105.png" /></figure>

Будем считать (здесь и далее), что последняя буква слова $Y$ больше в нём не встречается. (Этого всегда можно достичь, дописав дополнительный фиктивный символ.) Тогда листья сжатого дерева соответствуют концам слова $Y$, а внутренние вершины (точки ветвления) —
таким подсловам *s* слова *Y*, которые встречаются в *Y* несколько раз, и притом с разными буквами после *s*.

У каждой внутренней вершины (не листа) сжатого дерева есть не менее двух сыновей. В деревьях с такими свойствами число внутренних вершин не превосходит числа листьев. (В самом деле, при движении слева направо в каждой точке ветвления добавляется новый путь к листу.) Поскольку листьев *m*, всего вершин не более 2*m*, и мы уложимся в линейную по *m* память, если будем экономно хранить пометки на ребрах. Каждая такая пометка является подсловом слова *Y*, и потому достаточно указывать координату её начала и конца в *Y*. Это не помешает впоследствии прослеживать произвольное слово *X* в этом дереве буква за буквой, просто в некоторые моменты мы будем находиться внутри рёбер (и должны помнить, внутри какого ребра и в какой позиции мы находимся). При появлении новой буквы слова *X* её нужно сравнить с соответствующей буквой пометки этого ребра (что можно сделать за *O*(1) действий, так как координату этой буквы мы знаем.) ☐

Построенное нами сжатое дерево называют сжатым суффиксным деревом слова *Y* (концы слова называют «суффиксами»).

**10.8.3.** Покажите, что построение сжатого суффиксного дерева можно выполнить за время *O*(*m*²) с использованием *O*(m) памяти.

**Решение.** Будем добавлять в суффиксное дерево суффиксы по очереди. Добавление очередного суффикса делается так же, как и проверка принадлежности: мы считаем его буква за буквой и прокладываем путь в дереве. В некоторый момент добавляемый суффикс выйдет за пределы дерева (напомним, что мы считаем, что последний символ слова уникален).

Если это произойдёт посередине ребра, то ребро придётся в этом месте разрезать. Ребро превратится в два, его пометка разрежется на две, появится новая вершина (точка ветвления) и её новый сын-лист. Если точка ветвления совпадёт с уже имевшейся в дереве, то у неё появится новый сын-лист. В любом случае после обнаружения места ветвления требуется *O*(1) операций для перестройки дерева (в частности, разрезание пометки на две выполняется легко, так как пометки хранятся в виде координат начала и конца в слове *Y*). ☐

Гораздо более сложной задачей является построение сжатого суффиксного дерева за линейное время (вместо квадратичного, как в предыдущей задаче). Чтобы изложить алгоритм Маккрейта, который решает эту задачу, нам понадобятся некоторые приготовления.

Для начала опишем более подробно структуру дерева, которое мы используем, и операции с ним.
Мы рассматриваем деревья с корнем, на рёбрах которых написаны слова (пометки); все пометки являются подсловами некоторого заранее фиксированного слова Y. При этом выполнены такие свойства:

* каждая внутренняя вершина имеет хотя бы двух сыновей;

* пометки на рёбрах, выходящих из данной вершины, начинаются на разные буквы.

Каждой вершине v такого дерева соответствует слово, которое за-
писано на пути от корня r к вершине v. Будем обозначать это слово s(v).
Обозначим пометку на ребре, ведущем к v, через l(v), а отца верши-
ны v — через f(v). Тогда s(r) = Λ (пустое слово), а

$$
s(v) = s(f(v)) + l(v)
$$

для любой вершины $v \neq r$ (знак «+» обозначает соединение строк).

Помимо вершин дерева, мы будем рассматривать позиции в нём, ко-
торые могут быть расположены в вершинах, а также «внутри рёбер»
(разделяя пометку этого ребра на две части). Формально говоря, по-
зиция представляет собой пару (v, k), где v — вершина (отличная от
корня), а k — целое число в промежутке [0, |l(v)|), указывающее, на
сколько букв надо вернуться от v к корню. Здесь |l(v)| — длина по-
метки l(v); значение k = l(v) соответствовало бы предыдущей вершине
и потому не допускается. К числу позиций мы добавляем также па-
ру (r, 0), соответствующую корню дерева. Каждой позиции p = (v, k)
соответствует слово s(p), которое получается удалением k последних
символов из s(v).

Пусть *p* — произвольная позиция в дереве, а *w* — слово. Пройти
вдоль *w*, начиная с *p*, означает найти другую позицию *q*, для которой
*s*(*q*) = *s*(*p*) + *w*. Если такая позиция есть, то (при описанном способе
хранения пометок, когда указываются координаты их начала и конца
внутри *Y*) её можно найти за время, пропорциональное длине слова *w*.
Если такой позиции нет, то в какой-то момент мы «свернём с пути»;
в этот момент можно пополнить дерево, сделав отсутствующую в де-
реве часть слова *w* пометкой на пути к новому листу. Надо только,
чтобы эта пометка была подсловом слова *Y* (при нашем способе хране-
ния пометок); это будет гарантировано, если прослеживаемое слово *w*
является подсловом слова *Y*.

Заметим, что при этом может образоваться новая вершина (если
развилка оказалась внутри ребра), а может и не образоваться (если раз-
вилка оказалась в вершине). Число действий при такой модификации
пропорционально длине пройденной части слова (длина непройденной не важна).

Оказывается, что навигацию в дереве можно ускорить, если заранее известно, что она будет успешной.

**10.8.4.** Пусть для данной позиции *p* и слова *w* заранее известно, что в дереве есть позиция *q*, для которой $s(q) = s(p) + w$. Покажите, что позицию *q* можно найти за время, пропорциональное числу рёбер дерева на пути от *p* к *q*. (Это число может быть значительно меньше длины слова *w*, если пометки на рёбрах длинные.)

**Решение.** В самом деле, при навигации нужно ориентироваться лишь в вершинах (выбирать исходящее ребро в зависимости от очередной буквы); в остальных местах путь однозначный и потому можно сдвигаться сразу к концу ребра. ☐

Подведём итоги. Рассмотренный способ хранения деревьев позволяет (для фиксированного слова *Y*)

* создать дерево из одного корня $[O(1)]$;

* найти отца любой вершины (кроме корня) $[O(1)]$;

* узнать пометку любой вершины (кроме корня), то есть пометку ведущего к ней ребра $[O(1)]$;

* пройти из любой позиции *p* вдоль любого слова *w*, если заранее известно, что мы не выйдем из дерева; результат — позиция *q* в дереве, для которой $s(q) = s(p) + w$ [$O$(число рёбер на пути]);

* добавить слово *w* (некоторое подслово слова *Y*), начав с позиции *p*; если при этом в дереве нет позиции *q*, для которой $s(q) = s(p) + w$, то дерево меняется и такая позиция *q* создаётся (она будет листом) [$O$(число букв в *w*, не вошедших в *l(q)*]);

* наконец, для любого слова *X* можно выяснить, найдётся ли в дереве позиция *q*, для которой $s(q) = X$ [$O(|X|)$].

В квадратных скобках указано число действий при выполнении соответствующих операций.

Ещё мы будем хранить в вершинах дерева «суффиксные ссылки» (в каждой вершине будет не более одной ссылки на другую вершину), но сначала надо объяснить, что это такое.

Начнём с полного (не сжатого) суффиксного дерева для слова *Y*. Каждой его вершине (кроме корня) отвечает некоторое непустое подслово слова *Y*. Если мы отрезем у этого подслова последнюю букву,
то в дереве спустимся на один шаг к корню. Но что будет, если мы отрежем первую букву? Снова получится подслово, но оно уже будет совсем в другом месте дерева.

Вот как выглядят эти переходы в нашем примере (отрезание первой буквы соответствует пунктирной стрелке):

<figure><img src="image_106.png" /></figure>

Эти стрелки мы будем называть суффиксными ссылками, поскольку они соответствуют переходу от слова к его суффиксу на единицу меньшей длины. Они определены для всех вершин, кроме корня.

Формально можно сказать так. Пусть $w'$ означает слово $w$ без первой буквы ($w'$ определено для любого непустого слова $w$). Тогда суффиксная ссылка ведёт из вершины $p$ в вершину $q$, если $s(q) = s(p)'$ (напомним, что $s(u)$ — слово, соответствующее вершине $u$).

**10.8.5.** Как связаны суффиксные ссылки двух соседних вершин (отца и сына)?

**Ответ.** Они указывают на соседние вершины, и буква на соединяющем их ребре та же самая. ☐

**10.8.6.** Докажите, что при переходе к сжатому суффиксному дереву ссылки по-прежнему идут из вершины в вершину (не внутрь рёбер).

**Решение.** В самом деле, по нашему предположению последняя буква слова больше в нём не встречается, поэтому из листа ссылка ведёт в лист. А если вершина (отличная от корня) является точкой ветвления, то соответствующее ей слово $s$ встречается с различными буквами после него. Другими словами, для некоторых букв $a$ и $b$ слова $sa$ и $sb$ являются подсловами слова $Y$. Отрезав от них первую букву, получим слова $s'a$ и $s'b$, которые также являются подсловами слова $Y$, поэтому и $s'$ является точкой ветвления. ☐

Вот что получится для нашего примера:

<figure><img src="image_107.png" /></figure>
Теперь мы уже готовы к изложению алгоритма Маккрейта. Сжатое суффиксное дерево строим постепенно, добавляя к нему суффиксы по мере уменьшения их длины. Обозначим через $Y_i$ суффикс, начинающийся с $i$-й буквы слова $Y$. (Таким образом, $Y_1 = Y$, а $Y_m$ состоит из одной буквы.) После $i$ шагов построения наше дерево будет хранить $Y_1, \dots, Y_i$.

**10.8.7. Покажите, что суффиксные ссылки в таком дереве определены корректно (ведут в другую вершину того же дерева) для всех вершин, кроме, возможно, последнего добавленного листа (соответствующего слову $Y_i$) и его отца.**

**Решение.** В самом деле, суффиксная ссылка из листа $Y_j$ ведёт в лист $Y_{j+1}$, и потому ей есть куда вести. Рассмотрим теперь внутреннюю вершину $v$, не являющуюся отцом последнего листа. Пусть в ней разветвляются два пути в листья $Y_j$ и $Y_k$. Без ограничения общности можно считать, что $j, k < i$ (если один из путей ведёт в $Y_i$, то его можно заменить другим, ведь вершина $v$ по предположению не последняя развилка на этом пути). Отрезав от этих путей первый символ, получим пути в листья $Y_{j+1}$ и $Y_{k+1}$; эти пути присутствуют в дереве (поскольку $j+1$ и $k+1$ не превосходят $i$), а точка их развилки будет концом суффиксной ссылки вершины $v$. $\square$

Суффиксные ссылки для листьев нам не понадобятся, и вычислять мы их не будем, а для всех остальных вершин дерева мы их будем вычислять и хранить. Более точно, после $i$ шагов алгоритма

* в дереве хранятся слова $Y_1, \dots, Y_i$ (и все их начала);

* адрес листа, соответствующего последнему добавленному суффиксу ($Y_i$) хранится в переменной *last*;

* для всех внутренних вершин дерева, кроме, быть может, отца вершины *last*, хранится правильная суффиксная ссылка.

Надо понять, как поддерживать это при добавлении очередного суффикса. Можно, не мудрствуя лукаво, добавлять $Y_{i+1}$ буква за буквой, начиная с корня дерева. (Именно так мы раньше и делали, и это требовало квадратичного времени.)

Какие тут возможны оптимизации? Первая связана с тем, что мы можем двигаться по дереву быстрее, если знаем, что заведомо из него не выйдем. Вторая связана с использованием суффиксных ссылок.

Оба варианта предполагают, что отец $u$ листа *last* не совпадает с корнем. (Если совпадает, нам придётся добавлять $Y_{i+1}$ от корня.)
Пусть tail — пометка листа last, а head = s(u); другими словами, слово head соответствует вершине u. Тогда

$$Y_i = head + tail.$$

Отрезая первую букву, получаем

$$Y_{i+1} = head' + tail.$$

Заметим, что head' заведомо не выходит за пределы дерева. В са-
мом деле, u было точкой ветвления, поэтому помимо листа $Y_i$ через
точку u проходил и листу $Y_j$ с $j < i$. Тогда $Y_j$ начинается на head, а $Y_{j+1}$
начинается на head' и уже есть в дереве.

Поэтому мы можем сначала проследить head' (найти позицию v, для которой s(v) = head'), а потом уже добавить tail, начиная с v.

<figure><img src="image_108.png" /></figure>

Первый способ оптимизации: head' заведомо есть в дереве.

Эта оптимизация никак не использует суффиксных ссылок. Второй способ оптимизации их использует и позволяет (в том случае, когда применим) обойтись без прослеживания $Y_{i+1}$ от корня (как ускоренного, так и обычного). Пусть на пути к листу last, представляющему суффикс $Y_i$, имеется вершина v, у которой суффиксная ссылка указывает на вершину w, так что $s(w) = s(v)'$. Пусть p — слово на пути от v к last. Тогда

$$Y_i = s(v) + p, \quad Y_{i+1} = Y_i' = s(v)' + p = s(w) + p,$$

и для добавления $Y_{i+1}$ в дерево достаточно добавить слово p, начиная с вершины w.

Второй способ оптимизации сочетается с первым: отрезок слова p от v до отца листа last можно проходить с уверенностью, что мы не выйдем за пределы дерева.

Итак, мы можем описать действия, выполняемые при добавлении очередного суффикса $Y_{i+1}$ в дерево, следующим образом.
<figure><img src="image_109.png" /></figure>

Второй способ оптимизации: пользуемся суффиксной ссылкой вершины на пути к last.

Пусть $u$ — отец листа last, соответствующего последнему уже добавленному суффиксу $Y_i$.

Случай 1: $u$ есть корень дерева. Тогда ни одна из оптимизаций не применима, и мы добавляем $Y_{i+1}$, начиная от корня.

Случай 2: $u$ не есть корень дерева, но отец $u$ есть корень дерева (лист last находится на высоте 2). Тогда $Y_i = head + tail$, где head и tail — пометки вершин $u$ и last. Мы применяем первую оптимизацию и прослеживаем $head'$ с гарантией до некоторой позиции $z$, а потом добавляем tail от z.

Случай 3: $u$ не есть корень дерева и его отец $v$ также не есть корень дерева. Тогда для $v$ имеется суффиксная ссылка на некоторую вершину $w$, и $s(w) = s(v)'$. Пусть pretail — пометка вершины $u$, а tail — пометка листа last, при этом $Y_i = s(v) + pretail + tail$ и потому $Y_{i+1} = Y'_i = s(w) + pretail + tail$. Остаётся проследить pretail от вершины $w$ с гарантией, получив некоторую позицию $z$, а потом добавить tail от вершины $z$.

Остаётся ещё понять, как поддерживать структуру суффиксных ссылок (адрес нового листа у нас получается при добавлении сам собой, так что с ним проблем нет) и оценить число действий при выполнении этих процедур последовательно для всех суффиксов.

Начнём с суффиксных ссылок. По правилам они должны быть у всех внутренних вершин, кроме отца только что добавленного листа. Поэтому нам надо заботиться об отце листа last, соответствующего $Y_i$ (этот лист перестал быть «только что добавленным»; напротив, единственная новая вершина как раз является отцом только что добавленного листа и в ней суффиксная ссылка не нужна). Это актуально в случаях 2 и 3, но в этих случаях по ходу дела была найдена нужная вершина $z$, куда и будет направлена суффиксная ссылка из $u$. Строго говоря, $z$ могла быть не вершиной, а позицией, но тогда после добавления она станет вершиной (отцом только что добавленного листа) — ведь в новом де-
реве $u$ уже не является отцом последнего листа, и потому суффиксная
сылка из $u$, как было доказано, должна вести в вершину. (Другими
словами, в случаях 2 и 3, если позиция $z$ была внутри ребра, то в ней
ребро разрезается.)

Всё сказанное можно условно записать в виде такого алгоритма до-
бавления суффикса $Y_{i+1}$:
Осталось оценить число действий, которые выполняются при последовательном добавлении суффиксов $Y_1, ..., Y_m$. При добавлении каждого следующего суффикса выполняется ограниченное количество действий, если не считать действий при «прослеживании» и «добавлении». Нам надо установить, что общее число действий есть $O(m)$; для этого достаточно отдельно доказать, что суммарное число действий при всех прослеживаниях есть $O(m)$ и суммарное число действий при всех добавлениях есть $O(m)$. (Заметим, что некоторые прослеживания или добавления могут быть долгими — но это компенсируется другими.)

**Прослеживания.** Длительность прослеживания пропорциональна числу $k$ задействованных в нём рёбер, но при этом высота последнего добавленного листа (число рёбер на пути к нему) увеличивается на $k - O(1)$ (по сравнению с предыдущим добавленным листом). Чтобы убедиться в этом, достаточно заметить, что в третьем случае высота вершины $s(w)$ может быть меньше высоты вершины $s(v)$ разве что на единицу, поскольку суффиксные ссылки из всех вершин на пути к $v$ (не считая корня, где нет суффиксной ссылки) ведут в вершины на пути к $w$. Поскольку высота любого листа ограничена числом $m$, заключаем, что общая длительность всех прослеживаний есть $O(m)$.

**Добавления.** Рассуждаем аналогично, но следим не за высотой последнего листа, а за длиной его пометки. При добавлении слова *tail* (или *tail*') число действий пропорционально числу просмотренных букв, но каждая просмотренная буква (кроме, быть может, одной) уменьшает длину пометки хотя бы на единицу: в пометке остаются лишь непросмотренные буквы (не считая первой). Поэтому на все добавления уходит в общей сложности $O(m)$ действий.

Тем самым мы доказали, что описанный алгоритм строит сжатое суффиксное дерево слова $Y$ длины $m$ за $O(m)$ действий. После этого для любого слова $X$ длины $n$ можно за $O(n)$ действий выяснить, является ли $X$ подсловом слова $Y$.

**10.8.8.** Как модифицировать алгоритм построения суффиксного дерева, чтобы не только узнавать, является ли данное слово $X$ подсловом слова $Y$, но и (если является) указывать место, где оно встречается (одно из таких мест, если их несколько)? Время построения должно оставаться $O(|Y|)$, время поиска подслова — $O(|X|)$.

**Решение.** Каждая вершина сжатого суффиксного дерева соответствует некоторому подслову слова $Y$; в момент, когда эта вершина была добавлена в дерево, известно, в каком месте есть такое подслово, и можно записать в вершине, где соответствующее подслово кончается. ☐
**10.8.9.** Как модифицировать этот алгоритм, чтобы для каждого подслова можно было бы указывать его первое (самое левое) вхождение?

[Указание. При возникновении новой вершины на ребре нужно брать её первое вхождение (информация о котором есть на конце ребра), а не второе, только что обнаруженное.] ☐

**10.8.10.** Как модифицировать этот алгоритм, чтобы для каждого подслова можно было бы указывать его последнее (самое правое) вхождение?

[Указание. Если при каждом проходе корректировать информацию вдоль пути, это будет долго; быстрее построить дерево, затем вновь его обойти и для каждой вершины вычислить момент последнего появления соответствующего подслова.] ☐

**10.8.11.** Как использовать сжатое суффиксное дерево, чтобы для данного слова Y за время $O(|Y|)$ найти самое длинное подслово, которое входит в Y более одного раза?

**Решение.** Такое подслово является внутренней вершиной сжатого суффиксного дерева, поэтому достаточно из всех его вершин взять ту, которой соответствует самое длинное слово. Для этого достаточно обойти все его вершины (длину можно вычислять по мере обхода, складывая длины пометок на рёбрах). ☐

На практике можно использовать также и другой способ нахождения самого длинного подслова, входящего дважды, — так называемый *массив суффиксов*. А именно, будем рассматривать число *i* как «код» конца слова, начинающего с *i*-й буквы. Введём на кодах порядок, соответствующий лексикографическому (словарному) порядку на словах: код *i* предшествует коду *j*, если конец слова, начинающийся с *i*, в лексикографическом порядке идёт раньше конца слова, начинающегося с *j*. После этого отсортируем коды в соответствии с этим порядком, получив некоторую перестановку массива 1, 2, 3, ..., *m* (где *m* — длина исходного слова Y). Если какое-то слово X входит в слово Y дважды, то оно является началом двух концов слова Y. При этом эти концы можно выбрать соседними в лексикографическом порядке, поскольку все промежуточные слова тоже начинаются на X. Значит, достаточно для всех соседних концов посмотреть, сколько начальных букв у них совпадает, и взять максимум.

Этот способ требует меньше памяти (нам нужен лишь один массив из целых чисел той же длины, что исходное слово), но может требовать большого времени: во-первых, сортировка сама по себе требует
порядка $m \log m$ сравнений, во-вторых, каждое сравнение может длиться долго, если совпадающий кусок большой. Но в случаях, когда длинных совпадающих кусков мало, такой алгоритм работает неплохо.

**10.8.12.** Примените один из таких алгоритмов к любимой книге и объясните результат.

[Указание. Длинные повторяющиеся куски могут быть художественным приёмом (как в известном стишке про дом, который построил Джек) или следствием забывчивости автора. Для современных автомобилей возможно также неумеренное использование функций вырезания и вставки (заливки текста в мышь и выливания из мыши, если использовать графический интерфейс) в текстовом редакторе.] ☐
# 11. АНАЛИЗ ИГР

## 11.1. Примеры игр

11.1.1. Двое играют в такую игру: на столе лежит 20 спичек; играющие по очереди могут взять от 1 до 4 спичек; кто не может сделать хода (спичек не осталось) — проигрывает. Кто выигрывает при правильной игре?

**Решение.** Второй выигрывает, если будет дополнять ход первого до 5 спичек (если первый берёт одну, второй должен взять четыре и так далее). Тогда после четырёх раундов спичек не останется и первый проиграет. ☐

11.1.2. Кто выиграет — первый или второй — если спичек не 20, а 23?

**Решение.** Первый: если он возьмёт три спички, то станет вторым в уже разобранной игре и потому сможет выиграть. ☐

Аналогично получается ответ и для произвольного числа спичек $N$: если $N$ кратно пяти, то выигрывает второй, а если нет, то первый.

11.1.3. Изменим условия игры: пусть взявший последнюю спичку проигрывает. Кто теперь выигрывает при правильной игре? ☐

11.1.4. Пусть теперь игрокам разрешено брать 1, 2 или 4 спички, а кто не может сделать ход, проигрывает. Кто выигрывает при правильной игре, если вначале было 20 спичек?

**Решение.** Здесь уже не так просто сразу указать выигрышную статегию для первого или второго. Начнём с небольшого числа спичек, изобразив разрешённые ходы в виде стрелок (рис. 11.1). Игрок, оказавшийся в позиции 0, проигрывает (таковы правила), поэтому соответствующий кружок пометим буквой П. Игрок, оказавшийся в позициях 1, 2 или 4, выигрывает, поскольку он может забрать все спички и перевести противника по стрелке в позицию 0. Поэтому мы пометим
<figure><img src="image_110.png" /><figcaption>Рис. 11.1. Игра со спичками.</figcaption></figure>

эти позиции буквой В. Теперь ясно, что позиция 3 является проигрышной: из неё можно пойти только в 1 и 2, и тогда противник (как мы уже знаем) выиграет. Пометим её буквой П. Далее замечаем, что позиции 4, 5 и 7 будут выигрышными (поскольку из них можно попасть в проигрышную для противника позицию 3; заметим, что из позиции 4 можно выиграть и быстрее, пойдя в 0). Теперь видно, что позиция 6 проигрышная (все стрелки из неё ведут в выигрышные для противника позиции), 8 — выигрышная, 9 — проигрышная и так далее с периодом 3.

Таким образом, если число спичек делится на 3, то позиция проигрышная, если нет — то выигрышная. Поэтому в игре с 20 спичками первый игрок выигрывает. ☐

### 11.1.5. Как он для этого должен играть?

**Решение.** Ставить противника в проигрышную позицию, то есть следить, чтобы после его хода число спичек было кратно трём (в частности, в начале игры взять 2 спички, чтобы осталось 18). ☐

### 11.1.6. На столе лежат две кучки спичек: в одной $m$, в другой $n$. За один ход разрешается взять любое (ненулевое) число спичек, но только из одной кучки (можно взять все спички в ней); кто не может сделать ход, проигрывает. Кто выигрывает при правильной игре?

**Ответ:** при $m=n$ выигрывает второй, при $m \neq n$ — первый. ☐

### 11.1.7. На шахматной доске стоит ладья, которую игроки по очереди двигают, при этом разрешено сдвигать её влево и вниз (оставлять на месте нельзя); кто не может сделать ход, проигрывает. Кто выигрывает при правильной игре?

**[Указание.** Как эта игра связана с предыдущей?] ☐

### 11.1.8. (Игра «ним») Имеется $k$ кучек из $n_1, \dots, n_k$ спичек; за один ход можно взять любое (ненулевое) число спичек, но только из одной кучи (можно взять все спички в ней); кто не может сделать ход, проигрывает. Кто выигрывает при правильной игре?
**Решение.** Запишем числа $n_1, ..., n_k$ в двоичной системе счисления друг под другом, как если бы мы собирались их складывать. Если в каком разряде при этом оказалось чётное число единиц, то выигрывает второй, в остальных случаях — первый. В самом деле, если во всех разрядах чётное число единиц, то после уменьшения одного из чисел какой-то из его разрядов изменится и в этом разряде получится нечётное число единиц. (Это соответствует тому, что из проигрышной позиции любой ход ведёт в выигрышную.) Если же в некоторых («плохих») разрядах нечётное число единиц, возьмём старший плохой разряд и то из чисел, которое содержит в этом разряде единицу. Тогда, изменив в этом числе все плохие разряды, получим меньшее число, которое поставит противника в проигрышную позицию. (См. правила для выигрышных и проигрышных позиций в следующем разделе.) ☐

**11.1.9.** В ряд лежат N ящиков, в каждом из них по монете. За один ход игрок может взять любую монету или любые две монеты из соседних ящиков; кто не может сделать ход, проигрывает. Кто выигрывает при правильной игре?

**Решение.** Первый: он должен взять одну или две монеты в центре, а потом симметрично повторять ходы второго. ☐

## 11.2. Цена игры

Анализируя игры в предыдущем разделе, мы использовали следующие (очевидные) правила:

1. Если из некоторой позиции *p* можно пойти (по стрелкам) в некоторую проигрышную (для попавшего в неё игрока) позицию, то позиция *p* является выигрышной (для попавшего в неё).

2. Если из некоторой позиции *p* можно пойти только в выигрышные позиции, то позиция *p* является проигрышной.

**11.2.1.** Докажите, что если число позиций в игре конечно, нет циклов (нельзя вернуться в однажды пройденную позицию) и про все заключительные позиции (где нельзя сделать хода) известно, кто выигрывает, то правила 1 и 2 однозначно разбивают все позиции на выигрышные и проигрышные.

**Решение.** Будем применять эти правила, пока это возможно. Ясно, что никакая позиция не будет объявлена одновременно выигрышной и проигрышной (для попавшего в неё). Надо лишь доказать, что не останется «сомнительных» позиций (не отнесённых ни к выигрышным,
ни к проигрышным). Заметим, что из каждой сомнительной позиции ведёт стрелка хотя бы в одну сомнительную позицию. (В самом деле, если все стрелки ведут в несомненные позиции, то либо все они выигрышные, либо есть хоть одна проигрышная, и можно было бы воспользоваться одним из двух правил.) Значит, идя по стрелкам в сомнительные позиции, мы рано или поздно получим цикл, что противоречит предположению. ☐

11.2.2. Сформулируйте и докажите аналогичное утверждение для игр, допускающих ничьи. ☐

Игры с ничейным исходом являются частными случаями конечных игр с полной информацией и нулевой суммой, рассматриваемых в теории игр. Чтобы задать такую игру, необходимо:

1) указать конечное множество, элементы которого называются позициями;

2) для каждой позиции указать, является ли она заключительной (игра закончена) или нет;

3) для каждой заключительной позиции указать результат игры (число); это число понимается как сумма денег, которую один игрок платит другому;

4) для каждой незаключительной позиции указать, кто из игроков должен делать ход в этой позиции и какие разрешены ходы (в какие позиции этот игрок может перейти);

5) указать начальную позицию игры.

При этом требуется, чтобы не было циклов (нельзя было вернуться в уже пройденную позицию после нескольких ходов).

Позиции игры удобно рассматривать как вершины графа и изображать точками; возможные ходы при этом становятся рёбрами графа и изображаются стрелками. Игру можно рассматривать как передвижение фишки, обозначающей текущую позицию игры, по этому графу. В каждой вершине написано, кто должен делать ход (если игра не кончилась) или кто и сколько выиграл (если игра кончилась). Одна из вершин указана как начальная позиция.

Будем называть игроков Макс и Мин и считать, что результат игры определяет, сколько Мин платит Максу. (Мотивировка: Макс хочет, чтобы это число было максимальным, а Мин — минимальным — а лучше всего отрицательным, поскольку тогда он получает деньги!) Кто
из игроков делает первый ход, определяется начальной позицией. Заметим, что мы теперь не предполагаем, что игроки ходят по очереди: один и тот же игрок может делать несколько ходов подряд.

(Тем самым, например, в игре со спичками каждый кружок на рисунке 11.1 теперь превращается в две позиции: с ходом Макса и с ходом Мина.)

Игра, в которой один из игроков выигрывает, а другой проигрывает, соответствует значениям $±1$ в заключительных вершинах ($+1$ означает выигрыш Макса, $-1$ означает выигрыш Мина). Игры с ничейными исходами получатся, если приписать число 0 ничейным позициям.

Определим теперь понятие стратегии. Стратегия для Макса (или Мина) определяет, как он должен ходить в каждой из позиций (где ход за ним); формально это функция $s$, определённая на множестве позиций, где ход за ним. Значениями этой функции являются позиции, при этом ходы должны быть допустимыми, то есть из $p$ в $s(p)$ должна вести стрелка.

Стратегии такого типа называют в теории игр позиционными, подчёркивая, что выбор хода зависит лишь от текущей позиции, но не от истории игры (как мы в эту позицию попали). (Другие стратегии нам не понадобятся, так что слово «позиционная» мы будем опускать.)

Если фиксировать стратегии для Макса и Мина, то исход игры предопределен: эти стратегии однозначно определяют последовательность позиций («партию») и результат игры.

### 11.2.3. Докажите, что для любой игры $G$ можно найти число $c$ и стратегии $M$ и $m$ для Макса и Мина, при которых:

(1) Макс, пользуюясь стратегией $M$, гарантирует себе выигрыш не менее $c$, как бы ни играл Мин;

(2) Мин, пользуюясь стратегией $m$, гарантирует себе проигрыш не более $c$, как бы ни играл Макс.

Число $c$ называют ценой игры $G$. Заметим, что цена игры определяется однозначно: из условий (1) и (2) следует, что у Макса нет стратегии, гарантирующей ему выигрыш больше $c$ (поскольку она не может это сделать против стратегии $m$), а у Мина нет стратегии, гарантирующей ему проигрыш меньше $c$.

Для игр с двумя исходами утверждение задачи (называемое теоремой Цермело) означает, что ровно у одного из игроков имеется выигрышная стратегия. Если разрешить и ничьи, то либо у одного из игроков есть выигрышная стратегия, либо у обоих есть стратегия, гарантирующая ничью.
**Решение.** Пусть $p$ — произвольная позиция игры $G$. Рассмотрим игру $G_p$, которая отличается от $G$ лишь начальной позицией, и эта начальная позиция есть $p$. (Если $p$ — заключительная вершина, то игра $G_p$ тривиальна: игра кончается, не начавшись, и игрокам сообщается результат игры.) Как мы сейчас увидим, цену игры $G_p$ (как функцию от $p$) можно определить рекурсивно, начиная с заключительных позиций.

Более точно, рассмотрим следующее рекурсивное определение некоторой функции $c$, определённой на вершинах графа:

* $c(p)$ равно выигрышу Макса ($=\text{проигрышу Мина}$) в позиции $p$, если позиция $p$ является заключительной;

* $c(p) = \max\{c(p')\}$, если в вершине $p$ ходит Макс; максимум берётся по всем вершинам $p'$, в которые Макс может пойти из $p$ по правилам игры;

* $c(p) = \min\{c(p')\}$, если в вершине $p$ ходит Мин; минимум берётся по всем вершинам $p'$, в которые Мин может пойти из $p$ по правилам игры.

**Лемма.** Это определение корректно: существует и единственна функция $c$ (аргументы — вершины графа, значения — числа), удовлетворяющая указанным требованиям.

Доказательство леммы. Назовём рангом вершины максимальное число ходов, которое можно сделать из этой вершины. Поскольку по предположению в игре нет циклов, то ранг любой вершины не больше числа вершин. Докажем индукцией по $k$, что существует и единственна функция $c$, определённая на вершинах ранга не больше $k$ и удовлетворяющая рекурсивному определению. Для $k=0$ это очевидно. Шаг индукции использует такое (очевидное) замечание: если из вершины $p$ можно сделать ход в вершину $p'$, то ранг вершины $p'$ меньше ранга вершины $p$. Поэтому рекурсивное определение однозначно задаёт значения на вершинах ранга $k$, если известны значения на вершинах меньших рангов. Лемма доказана.

Осталось доказать, что значение $c(p)$ является ценой игры $G_p$. Рассмотрим следующую (позиционную) стратегию для Макса: из вершины $p$ ходить в ту вершину $p'$, для которой значение $c(p')$ максимально (и равно $c(p)$). Если Макс следует этой стратегии, то независимо от ходов Мина значение $c(q)$ для текущей вершины $q$ не убывает в ходе игры (при ходах Мина оно убывать вообще не может, при ходах Макса оно не убывает по построению стратегии). Тем самым в вершине $p$
Максу гарантирован выигрыш не меньше $c(p)$. Аналогичным образом, если Мин ходит в ту вершину $p'$, где достигается минимум $c(p')$ (равный $c(p)$), то значение $c(q)$ не возрастает в ходе игры и потому Мин проигрывает не более $c(p)$.

Теорема Цермело доказана. ☐

**11.2.4. Игра в крестики-нолики состоит в следующем: на большом квадратном поле два игрока по очереди ставят крестики и нолики в ещё не занятые клетки (начинают крестики). Выигрывает тот, кто первым поставит пять своих знаков подряд (по вертикали, горизонтали или диагонали). Если всё поле заполнено, а такого не случилось, партия считается ничейной. Докажите, что у крестиков есть стратегия, гарантирующая им ничью или выигрыш.**

**Решение.** Согласно теореме Цермело, в противном случае у ноликов есть стратегия, гарантирующая им выигрыш. Покажем, что крестики могут использовать по существу ту же стратегию, забыв о своём первом ходе. А именно, представим себе, что крестики делают произвольный первый ход (карандашом), а затем отвечают (чернилами) на ходы ноликов по выигрышной стратегии для ноликов (считая ходы ноликов крестиками и забыв о своём первом ходе).

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

Кроме того, игра может кончиться раньше времени, если карандашный крестик образует выигрышный ряд с чернильными — но это нам только лучше.

Таким образом, мы доказали, что если у ноликов есть выигрышная стратегия, то и у крестиков есть выигрышная стратегия — и если дать этим стратегиям играть друг против друга, получится противоречие. ☐

**11.2.5. Докажите, что цена любой игры равна выигрышу в одной из заключительных вершин.** ☐

**11.2.6. Покажите, что теорема Цермело вытекает из своего частного случая игр с двумя исходами (выигрыш первого и второго).**

[Указание. Для каждого $c$ будем считать выигрыш меньше $c$ проигрышем, а больше $c$ — выигрышем.] ☐
**11.2.7.** Пусть дана некоторая игра *G*. Выберем одну из заключительных вершин и будем менять выигрыш в этой вершине: положив его равным *c*, получим игру *G[c]*. Рассмотрим цену этой игры как функцию от *c*. Что это может быть за функция?

**Ответ.** Цена игры *G[c]* равна ближайшей к *c* точке некоторого отрезка [*a*, *b*] (зависящего от игры *G*). ☐

Вот ещё один пример игры, где теорема Цермело позволяет доказать существование выигрышной стратегии для первого игрока. Эта игра названа в книгах М. Гарднера («Математические досуги», М.: Мир, 1972; «Математические головоломки и развлечения», М.: Мир, 1971) игрой Гейла или «бридж-ит». Рассмотрим прямоугольную сеть из пунктирных линий высоты *n* и ширины *n* + 1 (рис. 11.2); вершины

<figure><img src="image_111.png" /><figcaption>Рис. 11.2. Игра Гейла.</figcaption></figure>

сети соединены пунктирными отрезками длины 1. Первый игрок каздым своим ходом обводит (сплошной линией) один из отрезков. Его задача — соединить сплошными линиями левую и правую стороны прямоугольника. Задача второго игрока — ему помешать; каждым своим ходом он стирает один из отрезков (лишая первого возможности впоследствии его обвести). Игра заканчивается, когда все отрезки обведены или стёрты; первый выиграл, если при этом левая и правая стороны прямоугольника соединены.

**11.2.8.** Используя теорему Цермело, докажите, что первый игрок имеет выигрышную стратегию.

[Указание. Игру можно представить в более симметричном виде, если добавить сетку для второго игрока (рис. 11.3) и считать, что второй хочет соединить верхнюю и нижнюю стороны своей сетки, а линиям первого и второго игроков запрещено пересекаться (тем самым проведя свою линию, второй игрок как бы стирает пересекающую её линию
первого). Если игра закончилась (в каждой возможной точке пересечения проведена вертикальная или горизонтальная линия), то ровно один из игроков выиграл: можно пройти по линиям или слева направо, или сверху вниз, но не одновременно. Аккуратное доказательство этого интуитивно ясного топологического факта, впрочем, не так просто.) ☐

<figure><img src="image_112.png" /><figcaption>Рис. 11.3. Игра Гейла, симметричный вариант.</figcaption></figure>

Как пишет Гарднер, Клод Шеннон (создатель теории информации) пришел для этой игры любопытную «физическую» стратегию, которая легко обобщается на любую сеть линий. Представим себе, что все стороны всех клеток сети (для первого игрока) представляют собой резисторы одинакового сопротивления, кроме левой и правой сторон прямоугольника, которые сделаны из провода нулевого сопротивления. Первый игрок своим ходом закорачивает эти сопротивления, а второй игрок разрывает их (делает бесконечными). Стратегия первого игрока состоит в том, что надо подключить напряжение между левой и правой сторонами прямоугольника, и закорачивать (обводить) то сопротивление, через которое идёт максимальный ток (или, что то же самое, на котором падает наибольшая разность потенциалов). Если таких сопротивлений оказалось несколько, можно закорачивать любое из них.

Из книг Гарднера не ясно, является ли эта стратегия выигрышной. Зато там приведена явная выигрышная стратегия (со ссылкой на О.Гросса). Чтобы объяснить её, будем считать, что целью первого игрока является не дать второму соединить верх и низ. (Мы уже упоминали, что эта цель равносильна исходной.) Начальный ход первого игрока показан на рис. 11.4; этот ход запрещает одно из рёбер второго игрока. Разделим остальные рёбра второго игрока на пары соседних, как показано на том же рисунке. Первый игрок препятствует второму провести оба ребра какой-либо пары: если второй провёл одно из рёбер пары, первый не даст провести второе ребро этой пары (прове-
<figure><img src="image_113.png" /><figcaption>Рис. 11.4. Игра Гейла: выигрышная стратегия.</figcaption></figure>

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

**11.2.9.** Докажите, что любой путь по линиям пунктирной сетки, соединяющий верх и низ рисунка 11.4, обязательно покрывает два ребра одной пары.

**Решение.** Для ясности оставим на рисунке только пунктирные линии и соответствующие вершины (рис. 11.5). Отметим серую область, как показано на рисунке; тем самым ребра делятся на серые и белые.

<figure><img src="image_114.png" /><figcaption>Рис. 11.5. Игра Гейла: анализ выигрышной стратегии.</figcaption></figure>

Предположим, что имеется путь снизу вверх, который не покрывает ни одной пары рёбер. Можно считать, что этот путь не проходит дважды через одну вершину (выбросим циклы). Каждый шаг на этом пути может относиться к одной из восьми категорий: четыре направления (север, восток, юг и запад) комбинируются с двумя цветами (серым
и белым). Как видно из рисунка, путь должен начинаться с серого ша-
га на север, а заканчиваться белым шагом на север.

Покажем, что это невозможно в силу наших ограничений (нельзя
использовать два ребра одной пары и нельзя дважды проходить через
одну вершину). Что, к примеру, может следовать за серым шагом на
север? Ещё один серый шаг на север, серый шаг на запад или белый
шаг на восток. За серым шагом на запад может следовать серый шаг
на запад или серый шаг на север. Разбирая поочерёдно все варианты,
легко убедиться, что путь, начавшись серым шагом на север, никогда
не выйдет (если не нарушит правил) за пределы множества

{серый шаг на север, серый шаг на запад,
белый шаг на восток, белый шаг на юг}.

Поэтому белый шаг на север (который должен быть последним в пути) невозможен, и мы доказали, что верх и низ рисунка нельзя соединить путём, не проходящим по двум рёбрам одной пары. ☐

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

[Указание. Он может помешать первому, например, повернуть с за-
пада на север, разбив все стороны клеток на пары и не давая покрыть
оба члена пары.] ☐

11.2.11. (Для знакомых с теорией вероятностей) На поле для игры Гейла (рис. 11.2) каждая из пунктирных линий обведена с вероятностью 1/2 независимо от других. Докажите, что путь от левой до правой стороны (по обведённым линиям) существует с вероятностью 1/2. ☐

11.3. Вычисление цены: полный обход

Как видно из доказательства теоремы Цермело, для нахождения
оптимальной стратегии достаточно уметь вычислять цены всех вер-
шин. В этом разделе мы рассмотрим случай, когда позиции игры обра-
зуют дерево (ведущие вверх рёбра дерева соответствуют возможным
в данной позиции ходам) и покажем, как применить программу обхода
дерева (глава 3).
Напомним, что мы рассматривали Робота, который в каждый момент находится в одной из вершин дерева и умеет выполнять команды `вверх_налево`, `вправо` и `вниз`. Робот начинает работу в корне дерева (роль которого теперь играет начальная позиция игры). Раньше Робот умел ещё обрабатывать вершины; теперь мы предполагаем, что он может определить тип текущей вершины (один из трёх: `max`, `min` и `final`, что соответствует вершинам Макса, Мина и заключительным) и может определить стоимость текущей вершины, если она является заключительной.

### 11.3.1. Напишите программу, которая управляет Роботом и вычисляет цену игры.

**Решение.** Напишем рекурсивную процедуру, которая, начав с некоторой вершины, обходит поддерево этой вершины, возвращает Робота на место и сообщает цену вершины (где она начала и кончила):

```pascal
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. Напишите нерекурсивную программу для вычисления цены игры (заданной деревом, по которому ходит Робот).
**Решение.** Как обычно, рекурсию можно устранить, используя стек. В данном случае каждый элемент стека будет хранить информацию об одном из предков текущей вершины (чем дальше, тем глубже — на дне стека будет информация о корне). Когда мы находимся в корне, стек пуст, при движении вверх по дереву он удлиняется, при движении вниз — укорачивается.

Каждый элемент стека представляет собой пару; первый элемент — тип соответствующей вершины (min/max), а второй элемент — минимум/максимум значений всех её сыновей левее текущего. В программе из главы 3 существенную роль играли два утверждения: ОЛ означало, что обработаны все вершины левее текущей (те, путь в которые отклоняется налево от пути в текущую); ОЛН означало, что обработаны все вершины левее и над текущей (это бывало, когда мы проходили вершину второй раз).

Помимо стека (который всегда будет хранить данные, указанные выше) программа использует ещё переменную с. В ситуации ОЛ эта переменная не используется, а в ситуации ОЛН она хранит цену текущей вершины. Покажем, как можно поддерживать это, описав действия с переменной и стеком для каждого варианта движения Робота (ср. с. 64):

* {ОЛ, не есть_сверху} обработать {ОЛН}:
  в переменную с записываем цену текущего листа;

* {ОЛ, есть_сверху} вверх_налево {ОЛ}:
  перед тем, как идти вверх, добавляем в стек тип текущей вершины (max/min) и значение $-∞/+∞$ соответственно, имея в виду, что максимум пустого множества равен $-∞$, а минимум равен $+∞$;

* {есть_справа, ОЛН} вправо {ОЛ}:
  обновляем значение в вершине стека, беря максимум или минимум (в зависимости от типа вершины стека) со значением переменной с;

* {не есть_справа, есть_снизу, ОЛН} вниз {ОЛН}:
  в переменную с помещаем максимум/минимум (в зависимости от типа вершины стека) её прежнего значения и значения на вершине стека (оно забирается из стека, и стек укорачивается).

Легко видеть, что при этом утверждения о содержании стека и значении переменной с не нарушаются, и по окончанию работы программы стек будет пуст, а значение переменной с будет равно цене игры. ☐
**11.3.3.** Как изменить эту программу, чтобы вычислить цены всех вершин?

[Указание. В состоянии ОЛН мы знаем цену текущей вершины, и такое случается для всех вершин.] ☐

## 11.4. Альфа-бета-процедура

Мы видели, как можно вычислить цену игры, обойдя все вершины её дерева. Однако иногда можно сэкономить и часть дерева не посещать. Пусть, например, игра имеет два исхода (выигрыш и проигрыш) и мы обнаружили (после просмотра части дерева), что некоторый ход является для нас выигрышным. Тогда нет смысла рассматривать остальные ходы. Более общо, если мы нашли ход, гарантирующий нам максимальный выигрыш (допускаемый правилами игры), то нет смысла искать дальше.

Подобная оптимизация возможна не только в тех случаях, когда мы знаем максимально возможный выигрыш. Пусть, например, дерево игры имеет такой вид, как на рис. 11.6, причём $a \ge b$ и мы обходим вершины дерева слева направо. Тогда после просмотра вершины a мы

<figure><img src="image_115.png" /><figcaption>Рис. 11.6. Оптимизация возможна при $a \ge b$.</figcaption></figure>

знаем, что цена корневой вершины не меньше a. Перейдя к min-вершине и просмотров её первого сына b, мы определяем, что цена min-вершины не больше b и (при $b \le a$) она не может повлиять на цену корня. Поэтому следующие вершины (серая область на рисунке) и их поддеревья нам просматривать не нужно.

Применённую в обоих случаях оптимизацию можно описать так. Приступая к оценке некоторой вершины, мы знаем некоторый промежуток $[m, M]$, в пределах которого нас интересует цена этой вершины — либо потому, что она заведомо не может выйти за пределы
промежутка (как в первом случае, когда лучше выигрыша ничего не бывает), либо потому, что это нам ничего не даёт (как во втором случае, когда все цены меньше a для нас неотличимы от a).

Более формально, введём обозначение $x_{[a,b]}$, где $x$ — число, а $[a, b]$ — промежуток:

$$x_{[a,b]} = \begin{cases} a, & \text{если } x \le a; \\ x, & \text{если } a \le x \le b; \\ b, & \text{если } b \le x. \end{cases}$$

Другими словами, $x_{[a,b]}$ — ближайшая к $x$ точка промежутка $[a, b]$, которую можно назвать «приведённым к $[a, b]$ значением $x$». Теперь можно сказать, что после просмотра вершины $a$ на рисунке 11.6 нас интересует приведённая к $[a, +\infty)$ цена min-вершины (все значения, меньшие $a$, безразличны), а после просмотра вершины $b$ эта приведённая цена уже известна (равна $a$). Аналогичным образом цена игры с двумя исходами $\pm 1$ равна её приведённой к отрезку $[-1, +1]$ цене, и после обнаружения выигрышного хода становится ясным, что эта цена равна $+1$.

Используя это соображение, напишем оптимизированный алгоритм, в котором рекурсивно определяется приведённая к промежутку $[a, b]$ цена игры в текущей вершине:

```pascal
procedure find_reduced_cost (a,b: integer; var c: integer)
begin
  var x: integer;
  c:= стоимость, приведённая к [a,b]
end
if тип = final then begin
  find_reduced_cost (a,b,c);
  {c = максимум цены вершины и братьев слева,
   приведённый к [a,b]
  }
  while есть_справа and (c<b) do begin
    вправо;
    find_reduced_cost (c,b,x);
    c := x;
  end;
  {c=цена вершины под текущей, приведённая к [a,b]}
  вниз;
end else begin {тип = мин}
  ...симметрично
end;
end;
```
Этот алгоритм часто называют а-б-процедурой по историческим причинам (границы интервала обозначались буквами а и б). Подробно (запутанная) история этого алгоритма описана в статье Кнута и Мура в журнале *Artificial Intelligence*, **6**(4), 293–326 (1975). В частности, они пишут, что этот алгоритм переоткрывался несколько раз, вначале воспринимался как эвристический (т.е. сокращающий перебор, но не гарантирующий точного ответа), а опубликован он был впервые в статье Брудно 1963 года «с довольно сложным доказательством» (как пишут Кнут и Мур).

Естественный вопрос: насколько такого рода оптимизация помогает уменьшить перебор? Мы рассмотрим простейший пример. Пусть игра имеет фиксированную длину, из каждой позиции возможны два хода, игроки ходят по очереди, каждый делает *n* ходов и цены листьев равны 0 или 1. Дерево такой игры — полное двоичное дерево, min- и max-уровни чередуются, в листьях написаны нули и единицы, и нужно вычислить значение в корне. (Если считать, что $1 = истина, 0 = ложь$, то максимум и минимум соответствуют операциям OR (ИЛИ) и AND (И), поэтому иногда говорят об AND-OR-дереве.)

Сколько листьев нужно посетить, чтобы вычислить значение в корне? Напомним, что всего листьев $2^{2n}$ для дерева с $2n$ уровнями (каждый из игроков делает *n* ходов).

### 11.4.1. Докажите, что для любых значений в листьях описанный нами оптимизированный алгоритм просматривает не менее $2^n$ листьев.

**Решение.** На уровне 2 находятся четыре вершины. В ходе работы алгоритм должен узнать цену игры хотя бы в двух из них. В самом деле, пусть нижняя вершина есть min-вершина. Если в ней нуль, то в одном из её сыновей тоже нуль. А раз это max-вершина, то для установления этого факта нужно знать цену обоих сыновей (равную нулю). Второй случай: в корне единица. Тогда в обеих его сыновьях должна быть единица, и чтобы быть в этом уверенным, нужно в каждом из них посмотреть как минимум одного сына.

Аналогично ради каждого значения на уровне 2 нужны два значения на уровне 4 и так далее — в конце концов на уровне $2^n$ нужно знать $2^n$ значений. ☐

Для наглядности мы говорили о конкретном алгоритме, описанном выше. Но справедлив и более общий факт: любой набор значений в листьях, который однозначно определяет значение в корне, содержит не менее $2^n$ значений.

### 11.4.2. Проведите аккуратное доказательство этого утверждения.
[Указание. По существу уже всё доказано, надо только это оформить.] ☐

Только что полученная оценка относилась к самому благоприятному случаю. Утверждение следующей задачи, напротив, говорит о наихудшем случае.

**11.4.3.** Пусть у нас спрашивают значения в листьях AND-OR-дерева в заранее неизвестном нам порядке, и мы можем называть эти значения по собственному усмотрению. Докажите, что мы можем действовать так, чтобы до последнего момента (пока есть хоть одно не названное значение) цена корня оставалось бы неизвестной (то есть могла быть и нулём, и единицей в зависимости от ещё не названных значений).

Эта задача показывает, что любой алгоритм отыскания цены корня в наиболее неблагоприятном случае вынужден обходить все листья (в частности, наш оптимизированный алгоритм никакого выигрыша не даёт).

**Решение.** Будем доказывать это индукцией по высоте дерева. Пусть корень является AND-вершиной. Тогда будем оттягивать (по предположению индукции) определение значений в детях корня, а когда дальше оттягивать будет нельзя (последний лист поддерева становится известным), сделаем так, чтобы это поддерево было истинным. Тем самым значение в корне совпадает со значением в другом поддереве и может оставаться неопределённым до последнего момента. ☐

Более интересной является оценка среднего числа опрошенных листьев. Будем считать, что алгоритм *findreduced_cost* применяется к некоторому фиксированному AND-OR-дереву (с фиксированными значениями в листьях), но для каждой вершины порядок просмотра двух её детей выбирается случайно. Тогда общее число просмотренных листьев становится случайной величиной.

**11.4.4.** Докажите, что математическое ожидание этой случайной величины (среднее по всем порядкам просмотров) для любого AND-OR-дерева высоты $2n$ (с $4^n$ вершинами) не превосходит $3^n$.

**Решение.** Рассмотрим сначала случай $n=1$, то есть дерево глубин 2. Пусть его корень является AND-вершиной. Если в корне находится 0, то на первом уровне 0, 0 или 0, 1. В первом случае нам достаточно просмотреть две вершины (найдя первый нуль, мы не ищем второй). Во втором случае с вероятностью $1/2$ нам хватит двух, а с вероятностью $1/2$ понадобится три или четыре. Если же в AND-корне находится 1, то в обеих OR-вершинах первого уровня находится единица, и на
каждую из них нужно в среднем не больше $3/2$ просмотров листьев (с вероятностью не менее $1/2$ мы сразу попадаем в лист с единицей и второй лист не смотрим).

Дальнейшее рассуждение легко происходит по индукции. Пусть среднее значение числа запрашиваемых листьев для любого дерева глубины $2k$ не превосходит $3^k$. Рассмотрим дерево глубины $2k+2$ с фиксированными значениями в листьях. Для каждого выбора порядка на первых двух уровнях известно, какие из четырёх вершин высоты 2 будут рассмотрены. По предположению среднее число использованных листьев при рассмотрении каждой вершины высоты 2 (усреднение по всем порядкам обхода) не больше $3^k$. Дополнительно усредняем по порядкам на двух первых уровнях и замечаем, что в среднем рассматривается не больше трёх вершин высоты 2. ☐

11.4.5. Получите более точную оценку для числа просмотренных листьев в предыдущей задаче. [Указание. Используйте разные оценки в зависимости от значения в корне; это позволит заменить $\sqrt{3}$ в оценке на меньшее число $(1 + \sqrt{33})/4$.] ☐

11.4.6. Покажите, что для любого набора значений в листьях AND-OR-дерева существует такой порядок просмотра сыновей, при котором потребуется просмотреть не более $2^n$ листьев. ☐

## 11.5. Ретроспективный анализ

Существенно ли описанное в прошлом разделе улучшение алгоритма (переход от полного перебора к $\alpha-\beta$-процедуре)? С одной стороны, да: в нашем примере переход от $4^n$ к $3^n$ даёт выигрыш в $(4/3)^n$ раз, а $(4/3)^n$ экспоненциально растёт с ростом $n$. С другой стороны, экспонента остаётся экспонентой, даже если её показатель уменьшается с 4 до 3, поэтому надежды полностью проанализировать даже не очень сложную и долгую игру таким способом почти нет.

Поэтому на практике обычно выбирают некоторую оценку позиции — легко вычислимую функцию, которая по мнению практиков как-то отражает преимущество того или иного игрока (скажем, материальный перевес в шахматах). Затем вместо настоящей игры рассматривают ограниченную игру, в которой делается сравнительно небольшое число $k$ ходов, а затем результатом игры считается оценка полученной позиции, и в этой игре выполняют перебор (применяя $\alpha-\beta$-оптимизацию). Конечно, это ничего не гарантирует в настоящей игре, но что поделаешь.
Бывают, однако, и ситуации, когда удаётся определить цену данной позиции точно. Это удаётся сделать для шахматных эндшпилей с небольшим числом фигур — например, можно рассчитать, за какое минимальное число ходов можно поставить мат королём, слоном и конём против одинокого короля в заданных начальных условиях. Заметим, что при этом число ходов может измеряться десятками, а каждый ход имеет десятки вариантов, поэтому о полном переборе (или даже о несколько сокращённом) не может идти и речи.

**11.5.1.** Придумайте другой подход, использующий ограниченность общего числа возможных позиций (скажем, для четырёх упомянутых фигур на шахматной доске это $64^4 = 2^{24} = 16$ «мегапозиций»; с учётом очередности хода будет 32 мегапозиции; массив такого размера помечается в память современных компьютеров без труда).

**Решение.** Заведём массив, отведя ячейку для каждой позиции. Просмотрим его один раз и отметим все матовые позиции (записав туда число 0 в знак того, что позиция проиграна и больше ходить нельзя). Затем просмотрим массив ещё раз и пометим как выигрышные все позиции, из которых можно пойти в матовые (напишем там 1 в знак того, что можно выиграть за 1 ход). Затем отметим все (ещё не отмеченные) позиции, из которых все ходы ведут в позиции с меткой 1, написав там -2; они проигрываются в два хода. Затем — позиции, из которых есть ход в позиции с меткой -2 (написав там 3), после этого — позиции, из которых все ходы ведут в 1- или 3-позиции (написав там -4) и т. п. Так будем делать до тех пор, пока будут появляться новые пометки. Как только это кончится, для каждой позиции будет известно, можно ли в ней выиграть и сколько ходов для этого нужно. ☐

Фактически эта процедура повторяет доказательство теоремы Цермело (но дополнительно мы получаем информацию о том, сколько ходов до выигрыша или проигрыша при наилучшей игре).

**11.5.2.** Могут ли при этом остаться неотмеченные позиции и чему они соответствуют?

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

Использование таблицы описанного типа можно считать применением метода динамического программирования (мы не вычисляем цену игры для одной и той же позиции снова и снова, обходя дерево, а заполняем таблицу цен систематически).
# 12. ОПТИМАЛЬНОЕ КОДИРОВАНИЕ

## 12.1. Коды

Имея $2^n$ символов, мы можем кодировать каждый из них $n$ битами, поскольку существует $2^n$ комбинаций из $n$ битов. Например, можно закодировать $4 = 2^2$ символа А, Г, Т, Ц (используемые при записи геномов) двухбитовыми комбинациями 00, 01, 10 и 11. Другой пример: последовательностями из 8 битов (байтами) можно закодировать 256 символов (и этого хватает на латинские и русские буквы, знаки препинания и др.).

Более формально: пусть нам дан алфавит, то есть конечное множество, элементы которого называются символами или буквами этого алфавита. Кодом для алфавита А называется функция (таблица) $\alpha$, которая для каждого символа $a$ из А указывает двоичное слово $\alpha(a)$, называемое кодовым словом, или просто кодом этого символа. (Двоичное слово — конечная последовательность нулей и единиц.) Не требуется, чтобы коды всех символов имели равные длины.

Мы допускаем, чтобы разные символы имели одинаковые коды. Согласно нашему определению, разрешается все буквы алфавита закодировать словом 0 (и даже пустым словом) — но, конечно, такой код будет бесполезен. Хороший код должен позволять декодирование (восстановление последовательности символов по её коду).

Формально это определяется так. Пусть фиксирован алфавит А и код $\alpha$ для этого алфавита. Для каждого слова $P$ в алфавите А (то есть для любой конечной последовательности букв алфавита А) рассмотрим двоичное слово $\alpha(P)$, которое получается, если записать подряд коды всех букв из $P$ (без каких-либо разделителей). Код $\alpha$ называется однозначным, если коды различных слов различны: $\alpha(P) \neq \alpha(P')$ при $P \neq P'$.

12.1.1. Рассмотрим трёхбуквенный алфавит $\{a, b, c\}$ и код $\alpha(a) = 0$, $\alpha(b) = 01$ и $\alpha(c) = 00$. Будет ли этот код однозначным?
**Решение.** Нет, поскольку слова *aa* и *c* кодируются одинаково. ☐

**12.1.2.** Для того же алфавита рассмотрим код $\alpha(a) = 0$, $\alpha(b) = 10$ и $\alpha(c) = 11$. Будет ли этот код однозначным?

**Решение.** Будет. Чтобы доказать это, достаточно объяснить, как можно восстановить слово *P* по его коду $\alpha(P)$. Если $\alpha(P)$ начинается с нуля, то ясно, что слово *P* начинается с *a*. Если $\alpha(P)$ начинается с единицы, то слово *P* начинается с *b* или с *c* — чтобы узнать, с чего именно, достаточно посмотреть на второй бит слова $\alpha(P)$. Восстановив первую букву слова *P*, мы забываем о ней и о её коде, и продолжаем всё сначала. ☐

Верно и более общее утверждение. Назовём код **префиксным**, если коды букв не являются началами друг друга (слово $\alpha(p)$ не является началом слова $\alpha(q)$, если буквы *p* и *q* различны).

**12.1.3.** Докажите, что любой префиксный код является однозначным.

**Решение.** Декодирование можно вести слева направо. Первая буква восстанавливается однозначно: если для двух букв *p* и *q* слова $\alpha(p)$ и $\alpha(q)$ являются началами кода, то одно из слов $\alpha(p)$ и $\alpha(q)$ является началом другого, что невозможно для префиксного кода. И так далее. ☐

**12.1.4.** Приведите пример однозначного кода, не являющегося префиксным.

[Указание. Пусть $\alpha(a) = 0$, $\alpha(b) = 01$, $\alpha(c) = 11$. Этот код является «суффиксным», но не префиксным.] ☐

**12.1.5.** Найдите таблицу для азбуки Морзе. Объясните, почему её можно использовать на практике, хотя она не является ни префиксным, ни даже однозначным кодом. ☐

## 12.2. Неравенство Крафта – Макмиллана

Зачем вообще нужны коды с разной длиной кодовых слов? Дело в том, что на практике разные символы алфавита встречаются с разной частотой, и выгодно законодавить частые символы короткими словами. (Это соображение, кстати, учитывалось при составлении азбуки Морзе.)

Пусть для каждой буквы *a* алфавита А фиксирована её частота $p(a)$ — положительное число, причём суммы частот всех букв равны
единице. Тогда для любого кода $\alpha$ можно определить среднюю длину этого кода как сумму

$$E = \sum p(a)|\alpha(a)|$$

по всем буквам $a \in A$, где $|\alpha(a)|$ — длина кодового слова $\alpha(a)$ буквы $a$. (Смысл этого определения: если в слове длины $N$ буква $a$ встречается с частотой $p(a)$, то таких букв будет $Np(a)$ и на их кодирование уйдёт $Np(a)|\alpha(a)|$ битов; общая длина кода будет $\sum Np(a)|\alpha(a)|$ и в среднем на кодирование каждой буквы уйдёт $E$ битов.)

Теперь возникает задача: для данных частот построить однозначный код минимальной средней длины. Теоретически это можно сделать перебором (если в коде есть хотя бы одно очень длинное кодовое слово, то его средняя длина велика, поэтому такие коды можно не рассматривать; остаётся конечное число вариантов). Но можно обойтись и без перебора, и в этом разделе мы научимся это делать.

Для начала поймём, что мешает нам выбирать кодовые слова короткими. Оказывается, что есть ровно одно препятствие: длины $n_1, \dots, n_k$ кодовых слов должны удовлетворять неравенству

$$2^{-n_1} + 2^{-n_2} + \dots + 2^{-n_k} \le 1,$$

называемому в теории кодирования неравенством Крафта – Макмиллана.

**12.2.1.** Проверьте, что оно выполнено для рассмотренных выше примеров однозначных кодов. $\square$

**12.2.2.** Докажите, что для всякого префиксного кода выполняется неравенство Крафта – Макмиллана.

**Решение.** Отрезок $[0, 1]$ можно разбить на две половины. Назовём левую $I_0$, а правую $I_1$. Каждую из них разобьём пополам: отрезок $I_0$ разделится на левую половину $I_{00}$ и правую $I_{01}$, аналогично $I_1$ делится на $I_{10}$ и $I_{11}$. И так далее: любому двоичному слову $x$ соответствует отрезок $I_x$. Длина этого отрезка есть $2^{-|x|}$, где $|x|$ — длина слова $x$. Если слово $x$ является началом слова $y$, то отрезок $I_x$ содержит отрезок $I_y$; если ни одно из слов $x$ и $y$ не является началом другого, то отрезки $I_x$ и $I_y$ не перекрываются (на том знаке, где $x$ и $y$ впервые расходятся, $I_x$ и $I_y$ попадают в разные половины).

Рассмотрим теперь отрезки, соответствующие словам префиксного кода. Они не перекрываются. А значит, сумма их длин не больше единицы, что и даёт неравенство Крафта – Макмиллана. $\square$
**12.2.3.** Пусть даны $k$ целых положительных чисел $n_1, \dots, n_k$, удовлетворяющие неравенству Крафта–Макмиллана. Докажите, что можно построить префиксный код для $k$-буквенного алфавита с длинами кодовых слов $n_1, \dots, n_k$.

**Решение.** И здесь полезно использовать соответствие между словами и отрезками и представлять себе дело так: у нас есть единичный отрезок $[0, 1]$, и мы выделяем его части пользователям по требованию. Если пользователь приходит с числом $n_i$, то это значит, что ему надо выдать в пользование один из отрезков длиной $2^{-n_i}$, соответствующих кодовым словам длины $n_i$. (Тем самым годятся не любые отрезки такой длины, а лишь «правильно расположенные».) Код должен быть префиксным, это значит, что отрезки разных пользователей не должны перекрываться. Нам дано, что суммарная длина всех требований не больше единицы. Как их удовлетворить? Можно отводить место слева направо, при этом рассматривать требования в порядке убывания длин (тогда более короткие отрезки будут правильно расположены после предыдущих более длинных). ☐

**12.2.4.** Покажите, что выделять кодовые слова (место на отрезке) можно и в порядке поступления требований (как иногда говорят, в «режиме on-line»): пользователь приходит с числом $n_i$ и уходит с правильно расположенным отрезком длины $2^{-n_i}$, причём если выполнено неравенство Крафта–Макмиллана, то никто не уйдёт обиженным (всем хватит места, и перераспределять его не придётся).

[Указание. Нужно поддерживать свободное пространство как объединение правильно расположенных отрезков попарно различных длин, выделяя каждому пользователю кусок из кратчайшего подходящего отрезка и доразбивая остаток.] ☐

**12.2.5.** Покажите, что неравенство Крафта–Макмиллана выполняется не только для любого префиксного кода, но и вообще для любого однозначного кода. (Именно это доказал Макмиллан; Крафт доказал неравенство для префиксных кодов.)

**Решение.** Есть разные способы решить эту задачу; мы приведём простое и красивое, хотя и несколько загадочное, решение. Пусть имеется однозначный код с $k$ кодовыми словами $P_1, \dots, P_k$. Нам надо доказать, что их длины $n_i = |P_i|$ удовлетворяют неравенству Крафта–Макмиллана. Представим себе, что вместо нулей и единиц используются символы $a$ и $b$ (какая разница, из чего составлять коды?). Запишем
формально сумму всех кодовых слов как алгебраическое выражение

$$P_1 + P_2 + \dots + P_k$$

(многочлен от $a$ и $b$, в котором одночлены записаны как произведения переменных $a$ и $b$, без возведения в степень). Теперь (ещё более странное на первый взгляд действие) возведём это выражение в степень $N$ (произвольное натуральное число) и раскроем скобки, сохраняя порядок переменных (не собирая вместе одинаковые переменные) в одночленах:

$$(P_1 + P_2 + \dots + P_k)^N = \text{сумма одночленов.}$$

Напимер, для кода со словами 0, 10, 11 (которые теперь записываются как $a, ba, bb$) и для $N = 2$ получаем

$$(a + ba + bb)^2 = (a + ba + bb)(a + ba + bb) = \\ = aa + aba + abb + baa + baba + babb + bba + bbba + bbbb.$$

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

Теперь подставим $a = b = 1/2$ в наше равенство (если оно верно для букв, то оно верно и для любых их числовых значений). Слева получится

$$(2^{-n_1} + 2^{-n_2} + \dots + 2^{-n_k})^N$$

(в скобке как раз выражение из неравенства Крафта – Макмиллана). Правую часть мы оценим сверху, группировав слова по длининам: имеется не более $2^l$ слагаемых длины $l$, каждое из которых равно $2^{-l}$, и потому слагаемые данной длины в сумме не превосходят единицы, а правая часть не превосходит максимальной длины слагаемых, то есть $N \max n_i$. Итак, получаем, что

$$(2^{-n_1} + 2^{-n_2} + \dots + 2^{-n_k})^N < N \max n_i,$$

и это верно при любом $N$. Если основание степени в левой части больше единицы, то при больших $N$ это неравенство нарушится (показательная функция растёт быстрее линейной). Поэтому для однозначного кода выполняется неравенство Крафта – Макмиллана. $\square$
## 12.3. Код Хаффмана

Теперь задача о коде минимальной средней длины приобретает такую форму: для данных положительных $p_1, \dots, p_k$, равных в сумме единице, найти целые положительные $n_1, \dots, n_k$, для которых выполнено неравенство Крафта – Макмиллана, а сумма

$$ \sum_{i=1}^{k} p_i n_i $$

является минимально возможной (среди наборов $n_1, \dots, n_k$, удовлетворяющих неравенству). Задача 12.2.5 показывает, что средняя длина однозначного кода не меньше этого минимума, а задача 12.2.3 говорит, что этот минимум достигается, причём даже для префиксного кода. Как же найти числа $n_1, \dots, n_k$, доставляющие этот минимум?

**12.3.1. Докажите, что для двух букв оптимальный код состоит из двух слов длины 1, независимо от частот букв.** ☐

Чтобы решить задачу в общем случае, начнём с нескольких простых замечаний.

**12.3.2. Пусть частоты расположены в убывающем порядке: $p_1 > p_2 > \dots > p_k$. Докажите, что тогда длины слов оптимального кода идут в неубывающем порядке: $n_1 \le n_2 \le \dots \le n_k$**.

**Решение.** Если бы более редкая буква имела бы более короткое кодовое слово, то, обменяв кодовые слова, мы сократили бы среднюю длину кода. ☐

**12.3.3. Останется ли утверждение предыдущей задачи в силе, если частоты расположены в невозрастающем порядке (возможны равные)?**

**Решение.** Нет: если, скажем, имеются три буквы с частотой $1/3$, то оптимальный код будет иметь длины слов $1, 2, 2$ (если бы два кодовых слова имели длину $1$, то на третье уже не осталось бы места), и они могут идти в любом порядке. ☐

Заметим, однако, что при поиске оптимального кода (для невозрастающих частот) мы вправе ограничиваться лишь кодами, в которых длины кодовых слов неубывают (поскольку кодовые слова для букв одинаковых частот можно переставлять без изменения средней длины кода).
**12.3.4.** Пусть частоты расположены в невозрастающем порядке $(p_1 \ge p_2 \ge \dots \ge p_k)$, а длины слов в оптимальном коде расположены в непубывающем порядке $n_1 \le n_2 \le \dots \le n_k$. Докажите, что $n_{k-1} = n_k$ (при $k \ge 2$).

**Решение.** Предположим, что это не так, и что есть единственное самое длинное кодовое слово длины $n_k$. Тогда неравенство Крафта – Макмиллана не может обращаться в равенство, поскольку все слагаемые, кроме наименьшего (последнего), кратны удвоенному последнему слагаемому. Значит, в этом неравенстве есть запас, причём не меньший последнего слагаемого. А тогда можно уменьшить $n_k$ на единицу, не нарушая неравенства, что противоречит предположению об оптимальности исходного кода. $\square$

Эта задача показывает, что при поиске оптимального кода можно рассматривать лишь коды, в которых две самые редкие буквы имеют коды одинаковой длины.

**12.3.5.** Как свести задачу отыскания длин кодовых слов оптимального кода для $k$ частот

$$p_1 \ge p_2 \ge \dots \ge p_{k-2} \ge p_{k-1} \ge p_k$$

к задаче поиска длин оптимального кода для $k-1$ частот

$$p_1, p_2, \dots, p_{k-2}, p_{k-1} + p_k$$

(частоты двух самых редких букв объединены)?

**Решение.** Мы уже знаем, что можно рассматривать лишь коды с $n_{k-1} = n_k$. Неравенство Крафта – Макмиллана тогда запишется как

$$2^{-n_1} + 2^{-n_2} + \dots + 2^{-n_{k-2}} + 2^{-n_{k-1}} + 2^{-n_k} = 2^{-n_1} + 2^{-n_2} + \dots + 2^{-n_{k-2}} + 2^{-n} \le 1,$$

если положить $n_{k-1} = n_k = n+1$. Таким образом, числа $n_1, \dots, n_{k-2}, n$ должны удовлетворять неравенству Крафта – Макмиллана для $k-1$ букв. Средняя длины этих двух кодов будут связаны:

$$p_1 n_1 + \dots + p_{k-2} n_{k-2} + p_{k-1} n_{k-1} + p_k n_k = p_1 n_1 + \dots + p_{k-2} n_{k-2} + (p_{k-1} + p_k)n + [p_{k-1} + p_k].$$

Последнее слагаемое (квадратная скобка) не зависит от выбираемого кода, поэтому минимизировать надо остальное, то есть как раз среднюю длину кода с длинами слов $n_1, \dots, n_{k-2}, n$ для частот $p_1, p_2, \dots, p_{k-2}, p_{k-1} + p_k$. После этого надо положить $n_{k-1} = n_k = n+1$, и это даст оптимальный код для исходной задачи. $\square$