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

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

Разбить на страницы
Показывать лекцию целиком

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

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

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

Решение. Очевидно, на каждой из $$n$$ горизонталей должно стоять по ферзю. Будем называть k-позицией (для $$k = 0, 1,\ldots,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}\Rightarrow {ОЛ}\\ {state} = {WLU}\Rightarrow {ОЛН}$$

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

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

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

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

    (а) быть частью пути из корня в $$x$$ ( $$\text{y ниже x}$$ );

    (б) свернуть налево с пути в $$x$$ ( $$\text{y левее x}$$ );

    (в) пройти через $$x$$ ( $$\text{y над x}$$ );

    (г) свернуть направо с пути в $$x$$ ( $$\text{y правее x}$$ );

    В частности, сама вершина $$x$$ относится к категории (в). Условия теперь будут такими:

    (ОНЛ) обработаны все вершины ниже и левее;

    (ОНЛН) обработаны все вершины ниже, левее и над.

    Вот как будет выглядеть программа:

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

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

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

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

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

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

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

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

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

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

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

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

    Указание. Примерно каждое второе действие при исполнении этой программы - обработка вершины, а каждая вершина обрабатывается максимум дважды.

    Вернемся теперь к нашей задаче о ферзях (где из всех программ обработки дерева понадобится лишь первая, самая простая). Реализуем операции с деревом позиций. Позицию будем представлять с помощью переменной 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_down := (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.8.Приведенная программа тратит довольно много времени на выполнение проверки есть_сверху (проверка, находится ли верхний ферзь под боем, требует числа действий порядка n ). Изменить реализацию операций с деревом позиций так, чтобы все три проверки есть_сверху/справа/снизу и соответствующие команды требовали бы количества действий, ограниченного не зависящей от n константой.

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

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

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

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

    Замечание. По сравнению с полным перебором всех $${2}^{n}$$ подмножеств тут есть некоторый выигрыш. Можно также предварительно отсортировать массив a в убывающем порядке, а также считать недопустимыми те позиции, в которых сумма отброшенных членов больше, чем разность суммы всех членов и s. Последний прием называют "методом ветвей и границ". Но принципиального улучшения по сравнению с полным перебором тут не получается (эта задача, как говорят, $$NP$$ -полна, подробности см. в книге Ахо, Хопкрофта и Ульмана "Построение и анализ вычислительных алгоритмов", Мир, 1979, а также в книге Гэри и Джонсона "Вычислительные машины и труднорешаемые задачи", Мир, 1982). Традиционное название этой задачи - "задача о рюкзаке" (рюкзак общей грузоподъемностью s нужно упаковать под завязку, располагая предметами веса $${a[1]}\ldots{a[n]}$$ ). См. также в лекции 8 (Как обойтись без рекурсии) алгоритм ее решения, полиномиальный по $${n}+{s}$$ (использующий "динамическое программирование").

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

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

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

    Страницы:

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

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

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

    Решение. Очевидно, на каждой из $$n$$ горизонталей должно стоять по ферзю. Будем называть k-позицией (для $$k = 0, 1,\ldots,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}\Rightarrow {ОЛ}\\ {state} = {WLU}\Rightarrow {ОЛН}$$

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

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

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

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

    (а) быть частью пути из корня в $$x$$ ( $$\text{y ниже x}$$ );

    (б) свернуть налево с пути в $$x$$ ( $$\text{y левее x}$$ );

    (в) пройти через $$x$$ ( $$\text{y над x}$$ );

    (г) свернуть направо с пути в $$x$$ ( $$\text{y правее x}$$ );

    В частности, сама вершина $$x$$ относится к категории (в). Условия теперь будут такими:

    (ОНЛ) обработаны все вершины ниже и левее;

    (ОНЛН) обработаны все вершины ниже, левее и над.

    Вот как будет выглядеть программа:

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

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

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

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

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

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

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

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

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

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

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

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

    Указание. Примерно каждое второе действие при исполнении этой программы - обработка вершины, а каждая вершина обрабатывается максимум дважды.

    Вернемся теперь к нашей задаче о ферзях (где из всех программ обработки дерева понадобится лишь первая, самая простая). Реализуем операции с деревом позиций. Позицию будем представлять с помощью переменной 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_down := (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.8.Приведенная программа тратит довольно много времени на выполнение проверки есть_сверху (проверка, находится ли верхний ферзь под боем, требует числа действий порядка n ). Изменить реализацию операций с деревом позиций так, чтобы все три проверки есть_сверху/справа/снизу и соответствующие команды требовали бы количества действий, ограниченного не зависящей от n константой.

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

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

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

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

    Замечание. По сравнению с полным перебором всех $${2}^{n}$$ подмножеств тут есть некоторый выигрыш. Можно также предварительно отсортировать массив a в убывающем порядке, а также считать недопустимыми те позиции, в которых сумма отброшенных членов больше, чем разность суммы всех членов и s. Последний прием называют "методом ветвей и границ". Но принципиального улучшения по сравнению с полным перебором тут не получается (эта задача, как говорят, $$NP$$ -полна, подробности см. в книге Ахо, Хопкрофта и Ульмана "Построение и анализ вычислительных алгоритмов", Мир, 1979, а также в книге Гэри и Джонсона "Вычислительные машины и труднорешаемые задачи", Мир, 1982). Традиционное название этой задачи - "задача о рюкзаке" (рюкзак общей грузоподъемностью s нужно упаковать под завязку, располагая предметами веса $${a[1]}\ldots{a[n]}$$ ). См. также в лекции 8 (Как обойтись без рекурсии) алгоритм ее решения, полиномиальный по $${n}+{s}$$ (использующий "динамическое программирование").

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

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

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

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^