Алгоритмы с возвратом

Игорь БОБАК mailto:ibobak@torba.com

Наверное, нет из вас, уважаемые читатели, таких, кто не игрывал в игру Lines (или по крайней мере не видел как кто-то другой в нее играет). А задумывались ли вы когда-нибудь над тем, как Lines мгновенно определяет путь, который должен проделать перекатываемый шарик из одного места в другое? Думаете, для машины это просто? Это нам с вами это просто, так как мы все-таки обладаем неким эмпирическим интеллектом. Для машины, конечно же, это тоже несложно, но в таких ситуациях ей часто приходится прибегать к методу проб и ошибок. В этой статье пойдет речь об отдельном классе алгоритмов, позволяющим машине решать подобные задачи. Должен сразу предупредить: если вы считаете себя гуру в алгоритмическом программировании — можете смело переходить к следующей статье, так как для себя вы вряд ли найдете что-то новое.

Этот тип алгоритмов в американской литературе фигурирует под названием backtracking algorithms, что в переводе означает «алгоритмы с откатом». Как правило, такие алгоритмы строятся на основе рекурсии, потому перед тем как читать эту статью рекомендую ознакомиться с тем, что это такое (см. статью «Ее Величество Рекурсия» в предыдущем номере). Эти алгоритмы отличаются от других тем, что ищут решения методом проб и ошибок, перебирая все или почти все варианты. Bаcktracking не является чем-либо особо изощренным, есть намного более продвинутые классы алгоритмов (например, динамическое программирование, «разделяй и властвуй», «жадные» алгоритмы и т. д) но речь о них пойдет в следующих статьях, так как они намного сложнее для понимания.

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

• первый пример — поиск оптимума с полным перебором всех вариантов;

• второй пример — поиск любого решения с выходом при его отыскании;

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

Пример первый: выйти из лабиринта

Нахождение пути в игре Lines (о ней шла речь в вступлении) — это задача именно такого класса. Задан лабиринт в виде матрицы проходимых и непроходимых участков. Нужно найти кратчайший путь от точки (x[1], y[1]) к Рис. 1 точке (x[2], y[2]) по проходимым участкам, или сообщить, что такого пути не существует. Пример: допустим, желтый шарик из положения (2, 10) (на рис. 1 в правом верхнем углу) мы хотим передвинуть в положение (9, 4) (обозначенное черной стрелкой):

Очевидно, что вариантов перемещения шарика из (2, 10) в (9, 4) много. Нам надо найти кратчайший.

Данные представим следующим образом:

Элемент массива а равен отрицательному числу (-1, -2, … в соответствии со цветом шарика) и равен нулю, если поле незанято. Полю шарика, который мы собираемся переместить, присвоим значение 1. Для того чтобы путь, который мы будем искать, не выходил за пределы доски, мы расширим массив в каждую сторону на 1 колонку/столбец и заполним эти колонки любым отрицательным значением (например, –10). В результате матрица для указанного примера будет выглядеть так (рис. 2):

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

Условия <можно пройти…> разберем позже, а сейчас давайте посмотрим на принцип работы такой процедуры. Вначале мы вызываем ее для начальной точки (в нашем примере — для точки (2,10)), передавая параметр L равным единице. Процедура опробует направление вправо от точки (вызывая себя же), вернется назад, потом попытается пройти налево, опять вернется назад и т. д. во всех направлениях. В этом и состоит суть метода проб и ошибок: пробуем каждый вариант прохода и возвращаемся.

Осталось лишь определить условия <можно пройти…>. Условие <можно пройти направо> эквивалентно следующему:

Для остальных условий все выглядит так же, только разница состоит в смещении по координате. Первая его часть очевидна — можно пробовать двигаться направо, если там еще не занята клетка. А вторая часть несет такой смысл: если в клетку [x+1,y] мы уже когда-то приходили, причем за большее количество шагов (a[x+1,y]), чем мы можем придти сейчас (a[x,y]+1), то лучше мы пройдем в нее отсюда еще раз и заново определим к ней путь, кратчайший прежнего.

Произведя вызов Paint(1, x, y), мы получим «закрашенную» матрицу, из которой легко найдем требуемый путь, двигаясь назад от целевой точки [x_aim, y_aim]. Значение a[x_aim, y_aim] и будет длиной самого короткого пути, если же один из ее соседей имеет метку на единицу меньше, чем a[x_aim, y_aim] — значит, отсюда-то мы и пришли в [x_aim, y_aim]. Тогда перемещаемся в эту соседнюю точку, и т. д., пока не придем в начало — место, где метка равна единице). Искомый путь найден.

Пример второй: обход шахматной доски конем

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

Данные будем представлять таким же образом, как и в предыдущем примере: значение поля массива равно 0, если на этом поле конь еще не побывал, и равно длине пути в противном случае (значение начальной клетки равно 1). В начале главной части программы выставляем значение булевой переменной Path_Found в false и вызываем TryNextMove(x0, y0, 1), где (х0, y0) — клетка, с которой начинается обход. Далее рекурсивная процедура начинает строить дерево решений (рис. 3), часть которого мы рассмотрим на примере доски размером 4*4 и начальной точки с координатами (1, 1). Текущее положение коня показано зеленым цветом.

Каждая стрелка соответствует вызову процедуры TryNextMove для следующего кандидата. Если на какой-то глубине все поле было полностью заполнено, глобальная переменная Path_Found Рис. 3 установится в true и в каждом вызове рекурсивной процедуры цикл repeat ... until прекратит свою работу — то есть условно мы возвратимся на самый верх нашего дерева.

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

const
const
 MAX = 100;
 MAX = 100;
{в этих массивах записаны все возможные ходы коня}
{в этих массивах записаны все возможные ходы коня}
 dx : array[1..8] of integer = (1,2,2,1,-1,-2,-2,-1);
 dx : array[1..8] of integer = (1,2,2,1,-1,-2,-2,-1);
 dy : array[1..8] of integer = (-2,-1,1,2,2,1,-1,-2);
 dy : array[1..8] of integer = (-2,-1,1,2,2,1,-1,-2);
var
var
 n,n2: integer; {размер доски}
 n,n2: integer; {размер доски}
 a: array[1..MAX,1..MAX] of integer;
 a: array[1..MAX,1..MAX] of integer;
 Path_found: boolean;
 Path_found: boolean;
{эта функция определяет, попадают ли координаты точки в середину доски}
{эта функция определяет, попадают ли координаты точки в середину доски}
function Valid(x,y: integer): boolean;
function Valid(x,y: integer): boolean;
begin
begin
 if (x>=1) and (x<=n) and (y>=1) and (y<=n) then
 if (x>=1) and (x<=n) and (y>=1) and (y<=n) then
  Valid := true
  Valid := true
 else Valid := false;
 else Valid := false;
end;
end;
{а эта процедура выводит доску на экран}
{а эта процедура выводит доску на экран}
procedure PrintBoard;
procedure PrintBoard;
var i,j: integer;
var i,j: integer;
begin
begin
 for i:=1 to n do begin
 for i:=1 to n do begin
  for j:=1 to n do write(a[i,j]:3,' ');
  for j:=1 to n do write(a[i,j]:3,' ');
  writeln;
  writeln;
 end;
 end;
end;
end;
{рекурсивная процедура, проделывающая всю работу}
{рекурсивная процедура, проделывающая всю работу}
procedure TryNextMove(x,y: integer; Level: integer);
procedure TryNextMove(x,y: integer; Level: integer);
var i, new_x, new_y: integer;
var i, new_x, new_y: integer;
begin
begin
 a[y,x] := Level; {ставим коня в (x,y)}
 a[y,x] := Level; {ставим коня в (x,y)}
 if Level = n2 then begin {если доска заполнена,}
 if Level = n2 then begin {если доска заполнена,}
  Path_Found := true; {то отмечаем, что путь найден}
  Path_Found := true; {то отмечаем, что путь найден}
  PrintBoard; {и выводим решение на экран}
  PrintBoard; {и выводим решение на экран}
  exit; {выход из процедуры}
  exit; {выход из процедуры}
 end;
 end;
 i:=1;
 i:=1;
 repeat
 repeat
  new_x := x + dx[i]; {находим координаты, откуда можно...}
  new_x := x + dx[i]; {находим координаты, откуда можно...}
  new_y := y + dy[i]; {попасть из (x,y)}
  new_y := y + dy[i]; {попасть из (x,y)}
  if Valid(new_x, new_y) and {если эта точка — в пределах поля...}
  if Valid(new_x, new_y) and {если эта точка— в пределах поля...}
    (a[new_y, new_x] = 0) then {и туда еще не ходили,}
    (a[new_y, new_x] = 0) then {и туда еще не ходили,}
   TryNextMove(new_x, new_y, Level+1); {то делаем следующий ход туда}
   TryNextMove(new_x, new_y, Level+1); {то делаем следующий ход туда}
  inc(i); 
  inc(i); 
 until (i>8) or (Path_Found); {выход из этого цикла появится тогда, когда мы переберем все 8 точек, в которые можно попасть из (x,y)}
 until (i>8) or (Path_Found); {выход из этого цикла появится тогда, когда мы переберем все 8точек, в которые можно попасть из (x,y)}
 a[y,x] := 0; {снимаем коня из (x,y)}
 a[y,x] := 0; {снимаем коня из (x,y)}
end;
end;
begin
begin
 Path_Found := false;
 Path_Found := false;
 read(n); n2 := n*n; {читаем размер доски}
 read(n); n2 := n*n; {читаем размер доски}
 TryNextMove(1,1, 1); {ищем обход конем, начиная с позиции (1, 1) и давая ей метку 1}
 TryNextMove(1,1, 1); {ищем обход конем, начиная с позиции (1,1) и давая ей метку 1}
end.
end.

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

Пример третий: коммивояжер

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

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

Как именно осуществить такое сокращение — опишем после приведения псевдокода backtrack-процедуры. Данные представим так:

Здесь массив а — это расстояния между каждой парой городов, массив taken служит для определения, встречался ли на пути город k (taken[k] = true) или нет (taken[k] = false), в массиве path запоминаются индексы городов в порядке их следования по маршруту.

Процедура выглядит так:

procedure Take(town: integer; index: integer);
procedure Take(town: integer; index: integer);
begin
begin
 <заходим в город town>;
 <заходим в город town>;
 if <обошли все N городов> then
 if <обошли все N городов> then
 begin
 begin
  if <длина этого пути меньше длины минимального,> then
  if <длина этого пути меньше длины минимального,> then
   <запомним этот путь и его длину как минимальные>
   <запомним этот путь и его длину как минимальные>
 end
 end
 else
 else
 for <все города k, в которых мы не были> do
 for <все города k, в которых мы не были> do
  if <есть смысл идти в город k (***) > then
  if <есть смысл идти в город k (***) > then
  begin
  begin
   <прибавить к длинне пути расстояние между town и k>;
   <прибавить к длинне пути расстояние между town и k>;
   Take(k, index+1); {зайти в город k}
   Take(k, index+1); {зайти в город k}
   {здесь мы вернулись из k}
   {здесь мы вернулись из k}
   <отнять от длинны пути расстояние между town и k>;
   <отнять от длинны пути расстояние между town и k>;
  end;
  end;
 <покидаем город town>
 <покидаем город town>
end;
end;

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

А теперь приведем сам код программы:

program voyger(input, output);
program voyger(input, output);
var
var
 n,i,j: integer;
 n,i,j: integer;
 MinL,L: longint;
 MinL,L: longint;
 a: array[1..100,1..100] of longint;
 a: array[1..100,1..100] of longint;
 taken: array[1..100] of boolean;
 taken: array[1..100] of boolean;
 MinPath, path: array[1..100] of integer;
 MinPath, path: array[1..100] of integer;
procedure Take(town: integer; index: integer);
procedure Take(town: integer; index: integer);
var k: integer;
var k: integer;
begin
begin
 path[index] := town; {заходим в город town}
 path[index] := town; {заходим в город town}
 taken[town] := true;
 taken[town] := true;
 if index=N then {обошли все города}
 if index=N then {обошли все города}
 begin { не забывайте, что еще нужно вернуться в первый}
 begin { не забывайте, что еще нужно вернуться в первый}
  if L + a[town,1] < MinL then {проверка на оптимальность}
  if L + a[town,1] < MinL then {проверка на оптимальность}
  begin
  begin
   MinL := L + a[town,1]; {запоминаем минимальную длину}
   MinL := L + a[town,1]; {запоминаем минимальную длину}
   move(path, MinPath, N*sizeof(integer)); {запоминаем путь}
   move(path, MinPath, N*sizeof(integer)); {запоминаем путь}
  end;
  end;
 end
 end
 else
 else
 for k:=1 to N do
 for k:=1 to N do
  if (not taken[k]) and {если там не были и...}
  if (not taken[k]) and {если там не были и...}
    (L + a[town, k] < MinL) then {есть смысл туда идти,}
    (L + a[town, k] < MinL) then {есть смысл туда идти,}
  begin
  begin
   inc(L, a[town, k]);
   inc(L, a[town, k]);
   Take(k, index+1); {рекурсивно делаем обход остальных вершин}
   Take(k, index+1); {рекурсивно делаем обход остальных вершин}
   dec(L, a[town, k]);
   dec(L, a[town, k]);
  end;
  end;
 taken[town] := false; {покидаем город town}
 taken[town] := false; {покидаем город town}
end;
end;
begin
begin
 assign(input, 'voyger.dat'); reset(input);
 assign(input, 'voyger.dat'); reset(input);
 {читаем данные из файла; во входном файле сначала идет число n, за ним построчно массив a[] длин между городами}
 {читаем данные из файла; во входном файле сначала идет число n, за ним построчно массив a[] длин между городами}
 fillchar(taken, sizeof(taken), 0);
 fillchar(taken, sizeof(taken), 0);
 read(n);
 read(n);
 for i:=1 to n do
 for i:=1 to n do
  for j:=1 to n do read(a[i,j]);
  for j:=1 to n do read(a[i,j]);
 L := 0;
 L := 0;
 MinL := 1 shl 30; {2^30 — заглушка. Это затем, чтобы прошла проверка «есть смысл...» в рекурсивной процедуре}
 MinL := 1 shl 30; {2^30— заглушка. Это затем, чтобы прошла проверка «есть смысл...» в рекурсивной процедуре}
 {делаем обход}
 {делаем обход}
 Take(1,1);
 Take(1,1);
 {выводим результат}
 {выводим результат}
 writeln('Minimum length: ', MinL);
 writeln('Minimum length: ', MinL);
 write('The path is: ');
 write('The path is: ');
 for i:=1 to n do write (MinPath[i],' ');
 for i:=1 to n do write (MinPath[i],' ');
 close(input);
 close(input);
end.
end.

Обобщение и выводы

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

procedure Try(next_element);
procedure Try(next_element);
begin
begin
 <включить next_element в искомое множество>;
 <включить next_element в искомое множество>;
 if <достигнут нужный результат> then
 if <достигнут нужный результат> then
 begin
 begin
  <запомнить этот результат> и/или 
  <запомнить этот результат> и/или 
  <вывести его на печать> и/или
  <вывести его на печать> и/или
  <проверить на оптимальность>;
  <проверить на оптимальность>;
  <выйти из процедуры, возможно исключив next_element из этого множества>;
  <выйти из процедуры, возможно исключив next_element из этого множества>;
 end;
 end;
 <цикл перебора всех оставшихся или допустимых элементов rest_element, который может быть реализован не обязательно в виде цикла for, while или repeat>
 <цикл перебора всех оставшихся или допустимых элементов rest_element, который может быть реализован не обязательно в виде цикла for, while или repeat>
 begin {в цикле}
 begin {в цикле}
  <подсчет необходимых локальных величин (*), если надо>;
  <подсчет необходимых локальных величин (*), если надо>;
  if <условие усечения дерева перебора, которого может и не быть>
  if <условие усечения дерева перебора, которого может и не быть>
   then Try(rest_element);
   then Try(rest_element);
  <обратные действия к (*), если (*) имели место>;
  <обратные действия к (*), если (*) имели место>;
 end;
 end;
 <исключить next_element из искомого множества>;
 <исключить next_element из искомого множества>;
end;
end;

В литературе иногда под алгоритмами с возвратом (backtracking algorithms) подразумевают все алгоритмы полного перебора вглубь, а класс более интеллектуальных, уменьшающих рост потенциального дерева поиска, выделяют особо и называют этот подкласс алгоритмами ветвей и границ (branch and bound algorithms). Но все-таки мне кажется, что последние нельзя считать отдельным классом, так как принцип их работы тот же, что и у backtracking’а, только с отсечением дерева.

Напоследок позволю себе дать несколько советов:

1) если вы видите, что дерево поиска можно сократить — обязательно это сделайте; рассмотрите все варианты сокращения перед написанием кода;

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

3) делайте включение элемента в искомое множество в начале процедуры, а его исключение — в конце. Типичная ситуация, которая часто приводит к ошибкам — это включение элемента в искомое множество не вначале процедуры, а в цикле перед вызовом Try. И тогда начинаются неприятности: код проверки оптимальности мигрирует в середину цикла, а там надо сделать выход, а перед выходом надо исключить элемент из множества — и понеслось… Плохая читабельность кода сопровождается более серьезными недостатками — как правило, что-то теряется, и в результате программа не работает.

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

5) не забывайте, что цикл может быть необязательно явным for/while/repeat-циклом; например, в первом примере нам надо было рассмотреть 4 направления движения, и мы сделали их по отдельности. Еще один пример — задача об обмене валют из моей статьи о рекурсии в прошлом номере. Это типичный backtracking, только не с циклом, а с перебором двух вариантов: кого из клиентов (+1 или -1) ставим в очередь на текущем шаге рекурсии.

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