Глава 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-позиции, в которых ферзи не бьют друг друга. Программа будет "обходить дерево" и искать их. Чтобы не делать лишней работы, заметим вот что: если в какой-то k-позиции ферзи бьют друг друга, то ставить дальнейших ферзей смысла нет. Поэтому, обнаружив это, мы будем прекращать построение дерева в этом направлении.

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

      Разобьем задачу на две части: (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 относится к категории (в). Условия теперь будут такими: Вот как будет выглядеть программа:
      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_down := (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, not danger}
      | | 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-полна, см. подробности в книге Ахо, Хопкрофта и Ульмана "Построение и анализ вычислительных алгоритмов", Мир, 1979, а также в книиге Гэри и Джонсона "Вычислительные машины и труднорешаемые задачи", Мир, 1982). Традиционное название этой задачи - "задача о рюкзаке" (рюкзак общей грузоподъемностью s нужно упаковать под завязку, располагая предметами веса a[1]..a[n]). См. также в главе 7 (раздел о динамическом программировании) алгоритм её решения, полиномиальный по n+s.

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

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

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