Глава 3. Обход дерева. Перебор с возвратами.

     3.1. Ферзи, не бьющие друг друга: обход дерева позиций

     В  предыдущей главе мы рассматривали несколько задач одного
и того же типа: "перечислить все элементы  некоторого  множества
A". Схема решения была такова: на множестве A вводился порядок и
описывалась  процедура  перехода  от произвольного элемента мно-
жества A к следующему за ним (в этом порядке).  Такую  схему  не
всегда  удается  реализовать  непосредственно, и в этой главе мы
рассмотрим другой полезный прием перечисления всех элементов не-
которого множества. Его называют "поиск  с  возвратами",  "метод
ветвей  и границ", "backtracking". На наш взгляд наиболее точное
название этого метода - обход дерева.

     3.1.1. Перечислить все способы расстановки n ферзей на шах-
матной доске n на n, при которых они не бьют друг друга.

     Решение. Очевидно, на каждой из n горизонталей должно  сто-
ять  по  ферзю.  Будем  называть k-позицией (для k = 0, 1,...,n)
произвольную расстановку k ферзей на k нижних горизонталях (фер-
зи могут бить друг друга). Нарисуем "дерево позиций": его корнем
будет единственная 0-позиция, а из каждой  k-позиции  выходит  n
стрелок  вверх в (k+1)-позиции. Эти n позиций отличаются положе-
нием ферзя на (k+1)-ой горизонтали. Будем считать, что  располо-
жение  их  на рисунке соответствует положению этого ферзя: левее
та позиция, в которой ферзь расположен левее.

                                        Дерево позиций для
                                           n = 2








Среди позиций этого дерева нам надо отобрать те n-позиции, в ко-
торых ферзи не бьют друг друга. Программа будет "обходить  дере-
во" и искать их. Чтобы не делать лишней работы, заметим вот что:
если  в  какой-то  k-позиции  ферзи  бьют друг друга, то ставить
дальнейших ферзей смысла нет. Поэтому, обнаружив это,  мы  будем
прекращать построение дерева в этом направлении.

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




                                         Дерево допустимых
                                         позиций для n = 3









     Разобьем задачу на две части: (1) обход произвольного дере-
ва и (2) реализацию дерева допустимых позиций.
     Сформулируем задачу обхода произвольного дерева. Будем счи-
тать, что у нас имеется Робот, который в каждый момент находится
в одной из вершин дерева (вершины изображены на рисунке  кружоч-
ками). Он умеет выполнять команды:

                              вверх_налево  (идти по самой левой
                                 из выходящих вверх стрелок)

                              вправо (перейти в соседнюю  справа
                                 вершину)

                              вниз (спуститься вниз на один уро-
                                 вень)

            вверх_налево
            вправо
            вниз

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


                                    Так команда "вправо"
                                    НЕ действует!



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

     Доказательство  правильности приводимой далее программы ис-
пользует такие определения. Пусть фиксировано положение Робота в
одной из вершин дерева. Тогда все листья дерева  разбиваются  на
три  категории: над Роботом, левее Робота и правее Робота. (Путь
из корня в лист может проходить через вершину с Роботом,  свора-
чивать  влево,  не доходя до нее и сворачивать вправо, не доходя
до нее.) Через (ОЛ) обозначим условие "обработаны все листья ле-
вее Робота", а через (ОЛН) - условие "обработаны все листья  ле-
вее и над Роботом".












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

  procedure вверх_до_упора_и_обработать
  | {дано: (ОЛ), надо: (ОЛН)}
  begin
  | {инвариант: ОЛ}
  | while есть_сверху do begin
  | | вверх_налево
  | end
  | {ОЛ, Робот в листе}
  | обработать;
  | {ОЛН}
  end;

Основной алгоритм:

  дано: Робот в корне, листья не обработаны
  надо: Робот в корне, листья обработаны

  {ОЛ}
  вверх_до_упора_и_обработать
  {инвариант: ОЛН}
  while есть_снизу do begin
  | if есть_справа then begin {ОЛН, есть справа}
  | | вправо;
  | | {ОЛ}
  | | вверх_до_упора_и_обработать;
  | end else begin
  | | {ОЛН, не есть_справа, есть_снизу}
  | | вниз;
  | end;
  end;
  {ОЛН, Робот в корне => все листья обработаны}

Осталось  воспользоваться  следующими  свойствами  команд Робота
(сверху записаны условия, в которых выполняется команда, снизу -
утверждения о результате ее выполнения):

   (1) {ОЛ, не есть_сверху}  (2) {ОЛ}
       обработать                вверх_налево
       {ОЛН}                     {ОЛ}

   (3) {есть_справа, ОЛН}    (4) {не есть_справа, ОЛН}
       вправо                    вниз
       {ОЛ}                      {ОЛН}

     3.1.2. Доказать, что приведенная программа завершает работу
(на любом конечном дереве).
     Решение. Процедура вверх_налево  завершает  работу  (высота
Робота  не может увеличиваться бесконечно). Если программа рабо-
тает бесконечно, то, поскольку листья не обрабатываются  повтор-
но, начиная с некоторого момента ни один лист не обрабатывается.
А  это  возможно,  только  если Робот все время спускается вниз.
Противоречие. (Об оценке числа действий см. далее.)

     3.1.3. Доказать правильность следующей программы обхода де-
рева:

  var state: (WL, WLU);
  state := WL;
  while есть_снизу or (state <> WLU) do begin
  | if (state = WL) and есть_сверху then begin
  | | вверх;
  | end else if (state = WL) and not есть_сверху then begin
  | | обработать; state := WLU;
  | end else if (state = WLU) and есть_справа then begin
  | |  вправо; state := WL;
  | end else begin {state = WLU, not есть_справа, есть_снизу}
  | |  вниз;
  | end;
  end;

     Решение. Инвариант цикла:
        state = WL  => ОЛ
        state = WLU => ОЛН
Доказательство завершения работы: переход из состояния ОЛ в  ОЛН
возможен  только  при  обработке вершины, поэтому если программа
работает бесконечно, то с некоторого момента значение  state  не
меняется, что невозможно.

    3.1.4.  Решить задачу об обходе дерева, если мы хотим, чтобы
обрабатывались все вершины (не только листья).

    Решение. Пусть x - некоторая вершина. Тогда любая вершина  y
относится к одной из четырех категорий. Рассмотрим путь из корня
в y. Он может:
    (а) быть частью пути из корня в x (y ниже x);
    (б) свернуть налево с пути в x (y левее x);
    (в) пройти через x (y над x);
    (г) свернуть направо с пути в x (y правее x);
В  частности,  сама вершина x относится к категории (в). Условия
теперь будут такими:
    (ОНЛ) обработаны все вершины ниже и левее;
    (ОНЛН) обработаны все вершины ниже, левее и над.
Вот как будет выглядеть программа:

  procedure вверх_до_упора_и_обработать
  | {дано: (ОНЛ), надо: (ОНЛН)}
  begin
  | {инвариант: ОНЛ}
  | while есть_сверху do begin
  | | обработать
  | | вверх_налево
  | end
  | {ОНЛ, Робот в листе}
  | обработать;
  | {ОНЛН}
  end;

Основной алгоритм:

  дано: Робот в корне, ничего не обработано
  надо: Робот в корне, все вершины обработаны

  {ОНЛ}
  вверх_до_упора_и_обработать
  {инвариант: ОНЛН}
  while есть_снизу do begin
  | if есть_справа then begin {ОНЛН, есть справа}
  | | вправо;
  | | {ОНЛ}
  | | вверх_до_упора_и_обработать;
  | end else begin
  | | {ОЛН, не есть_справа, есть_снизу}
  | | вниз;
  | end;
  end;
  {ОНЛН, Робот в корне => все вершины обработаны}

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

    Решение.  Под "обработано ниже и левее" будем понимать "ниже
обработано по разу, слева обработано полностью (листья по  разу,
останые по два)". Под "обработано ниже, левее и над" будем пони-
мать "ниже обработано по разу, левее и над - полностью".

Программа будет такой:

  procedure вверх_до_упора_и_обработать
  | {дано: (ОНЛ), надо: (ОНЛН)}
  begin
  | {инвариант: ОНЛ}
  | while есть_сверху do begin
  | | обработать
  | | вверх_налево
  | end
  | {ОНЛ, Робот в листе}
  | обработать;
  | {ОНЛН}
  end;

Основной алгоритм:

  дано: Робот в корне, ничего не обработано
  надо: Робот в корне, все вершины обработаны

  {ОНЛ}
  вверх_до_упора_и_обработать
  {инвариант: ОНЛН}
  while есть_снизу do begin
  | if есть_справа then begin {ОНЛН, есть справа}
  | | вправо;
  | | {ОНЛ}
  | | вверх_до_упора_и_обработать;
  | end else begin
  | | {ОЛН, не есть_справа, есть_снизу}
  | | вниз;
  | | обработать;
  | end;
  end;
  {ОНЛН, Робот в корне => все вершины обработаны полностью}

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

     Теперь реализуем операции с деревом позиций. Позицию  будем
представлять  с помощью переменной k: 0..n (число ферзей) и мас-
сива c: array [1..n] of 1..n (c [i] - координаты ферзя  на  i-ой
горизонтали; при i > k значение c [i] роли не играет). Предпола-
гается,  что  все позиции допустимы (если убрать верхнего ферзя,
остальные не бьют друг друга).

  program queens;
  | const n = ...;
  | var
  |   k: 0..n;
  |   c: array [1..n] of 1..n;
  |
  | procedure begin_work; {начать работу}
  | begin
  | | k := 0;
  | end;
  |
  | function danger: boolean; {верхний ферзь под боем}
  | | var b: boolean; i: integer;
  | begin
  | | if k <= 1 then begin
  | | | danger := false;
  | | end else begin
  | | | b := false; i := 1;
  | | | {b <=> верхний ферзь под боем ферзей с номерами < i}
  | | | while i <> k do begin
  | | | | b := b or (c[i]=c[k]) {вертикаль}
  | | | |     or (abs(c[[i]-c[k]))=abs(i-k)); {диагональ}
  | | | | i := i+ 1;
  | | | end;
  | | | danger := b;
  | | end;
  | end;
  |
  | function is_up: boolean {есть_сверху}
  | begin
  | | is_up := (k < n) and not danger;
  | end;
  |
  | function is_right: boolean {есть_справа}
  | begin
  | | is_right := (k > 0) and (c[k] < n);
  | end;
  | {возможна ошибка: при k=0 не определено c[k]}
  |
  | function is_down: boolean {есть_снизу}
  | begin
  | | is_up := (k > 0);
  | end;
  |
  | procedure up; {вверх_налево}
  | begin {k < n}
  | | k := k + 1;
  | | c [k] := 1;
  | end;
  |
  | procedure right; {вправо}
  | begin {k > 0,  c[k] < n}
  | | c [k] := c [k] + 1;
  | end;
  |
  | procedure down; {вниз}
  | begin {k > 0}
  | | k := k - 1;
  | end;
  |
  | procedure work; {обработать}
  | | var i: integer;
  | begin
  | | if (k = n) and not danger then begin
  | | | for i := 1 to n do begin
  | | | | write ('<', i, ',' , c[i], '> ');
  | | | end;
  | | | writeln;
  | | end;
  | end;
  |
  | procedure UW; {вверх_до_упора_и_обработать}
  | begin
  | | while is_up do begin
  | | | up;
  | | end
  | | work;
  | end;
  |
  begin
  | begin_work;
  | UW;
  | while is_down do begin
  | | if is_right then begin
  | | | right;
  | | | UW;
  | | end else begin
  | | | down;
  | | end;
  | end;
  end.

     3.1.7. Приведенная программа тратит довольно много  времени
на  выполнение  проверки  есть_сверху  (проверка,  находится  ли
верхний ферзь под боем, требует числа действий порядка n). Изме-
нить реализацию операций с деревом позиций так,  чтобы  все  три
проверки есть_сверху/справа/снизу и соответствующие команды тре-
бовали  бы  количества действий, ограниченного не зависящей от n
константой.

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

     3.2.  Обход дерева в других задачах.

     3.2.1. Использовать метод обхода дерева для решения  следу-
ющей   задачи:   дан  массив  из  n  целых  положительных  чисел
a[1]..a[n] и число s; требуется узнать, может ли  число  s  быть
представлено  как  сумма  некоторых  из чисел массива a. (Каждое
число можно использовать не более чем по одному разу.)

     Решение. Будем задавать k-позицию последовательностью из  k
булевских  значений,  определяющих,  входят  ли  в  сумму  числа
a[1]..a[k] или не входят. Позиция допустима, если  ее  сумма  не
превосходит s.

     Замечание. По сравнению с полным перебором всех (2 в степе-
ни  n) подмножеств тут есть некоторый выигрыш. Можно также пред-
варительно отсортировать массив a в убывающем порядке,  а  также
считать  недопустимыми  те  позиции, в которых сумма отброшенных
членов больше, чем разность суммы всех  членов  и  s.  Последний
приём  называют  "методом  ветвей  и границ". Но принципиального
улучшения по сравнению с полным перебором тут не получается (эта
задача, как говорят, NP-полна,  см.  подробности  в  книге  Ахо,
Хопкрофта и Ульмана "Построение и анализ вычислительных алгорит-
мов").  Традиционное  название  этой задачи - "задача о рюкзаке"
(рюкзак общей грузоподъемностью s нужно упаковать  под  завязку,
располагая  предметами  веса  a[1]..a[n]).  См.  также в главе 7
(раздел о динамическом программировании)  алгоритм  её  решения,
полиномиальный по n+s.

     3.2.2.  Перечислить все последовательности из n нулей, еди-
ниц и двоек, в которых никакая группа цифр  не  повторяется  два
раза подряд (нет куска вида XX).

     3.2.3.  Аналогичная  задача для последовательностей нулей и
единиц, в которых никакая группа цифр не  повторяется  три  раза
подряд (нет куска вида XXX).

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