5.6.2 Переборные алгоритмы

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

Лабиринт, состоящий из проходимых и непроходимых клеток, задан матрицей A размером mn. Элемент матрицы A[i,  j]=0, если клетка (i,  j) проходима. В противном случае A[i,  j]=.

Требуется найти кратчайший путь из клетки (1, 1) в клетку (m, n).

Фактически дана инвертированная матрица смежности (в ней нули заменены , а единицы – нулями). Лабиринт представляет собой граф.

Метод перебора с возвратом (по-английски называемый backtracking) основан на методе поиска в глубину. Перебор с возвратом – это метод проб и ошибок («попробуем сходить в эту сторону: не получится – вернемся и попробуем в другую»). Поскольку речь идет о переборе вариантов методом поиска в глубину, то во время работы алгоритма надо хранить текущий путь в дереве. Этот путь представляет собой стек Way. Кроме того, необходим массив Dest, размерность которого соответствует количеству вершин графа, хранящий для каждой вершины расстояние от нее до исходной вершины.

Вернемся к нашей задаче. Пусть текущей является некоторая клетка (в начале работы алгоритма – клетка (1, 1)).

if для текущей клетки есть клетка-сосед Neighbor, такая что:

(отсутствует в Way) and

(Dist[Neighbor]=0 or (Dist[Neighbor] > Length(Way))) then begin

добавить Neighbor в Way;

текущая клетка := Neighbor;

end else

извлечь из Way;

Листинг 5.15 – Переборный алгоритм прохождения лабиринта

Из приведенного выше фрагмента ясно, почему этот метод называется перебором с возвратом. Возврату здесь соответствует операция «извлечь из Way», которая уменьшает длину Way на 1.

Перебор заканчивается, когда Way пуст и делается попытка возврата назад. В этой ситуации возвращаться уже некуда.

Way – это путь текущий, но в процессе работы необходимо хранить еще и оптимальный путь OptimalWay.

Заметим, что алгоритм можно усовершенствовать, если не позволять, чтобы длина Way была больше или равна длине OptimalWay. В этом случае если и будет найден какой-то вариант большей длины, он заведомо не будет оптимальным. Такое усовершенствование в общем случае означает, что как только текущий путь станет заведомо неоптимальным, надо вернуться назад. В некоторых случаях это улучшение алгоритма позволяет сильно сократить перебор.

Рисунок 5.14 – Поиск выхода из лабиринта методом поиска в глубину

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

1. Распространение волны;

2. Обратный ход.

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

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

Рисунок 5.15 – Поиск выхода из лабиринта методом поиска в ширину

В качестве ещё одного примера рассмотрим игры двух лиц, которые обычно описываются множеством «позиций» и совокупностью правил перехода из одной позиции в другую, причем предполагается, что игроки ходят по очереди. Будем считать, что правилами разрешены лишь конечные последовательности позиций и что в каждой позиции имеется лишь конечное число разрешенных ходов. Тогда для каждой позиции p найдется число N(p) такое, что никакая игра, начавшаяся в p, не может продолжаться более N(p) ходов.

Терминальными называются позиции, из которых нет разрешенных ходов. На каждой из них определена целочисленная функция f(p), задающая выигрыш того из игроков, которому принадлежит ход в этой позиции; выигрыш второго игрока считается равным -f(p).

Рисунок 5.16 – Дерево игры «крестики-нолики»

Если из позиции p имеется d разрешенных ходов p1, …, pd, возникает проблема выбора лучшего из них. Будем называть ход наилучшим, если по окончании игры он приносит наибольший возможный выигрыш при условии, что противник выбирает ходы, наилучшие для него (в том же смысле). Пусть f(p) есть наибольший выигрыш, достижимый в позиции p игроком, которому принадлежит очередь хода, против оптимальной защиты. Так как после хода в позицию p_i выигрыш этого игрока равен -f(pi), имеем

Эта формула позволяет индуктивно определить f(p) для каждой позиции p.

Функция f(p) равна тому максимуму, который гарантирован, если оба игрока действуют оптимально. Следует, однако, заметить, что она отражает результаты весьма осторожной стратегии, которая не обязательно хороша против плохих игроков или игроков, действующих согласно другому принципу оптимальности. Пусть, например, имеются два хода в позиции p₁ и p₂, причем p₁ гарантирует ничью (выигрыш 0) и не дает возможности выиграть, в то время, как p₂ дает возможность выиграть, если противник просмотрит очень тонкий выигрывающий ход. В такой ситуации можно предпочесть рискованный ход в p₂, если только нет уверенности в том, что противник всемогущ и всезнающ. Очень возможно, что люди выигрывают у шахматных программ таким именно образом.

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

function BackSearch(p: position): integer;

{оценивает и возвращает выигрыш f(p) для позиции p}

var

m,i,t,d: integer;

begin

Определить позиции p1,...,pd, подчиненные p;

if d = 0 then BackSearch := f(p)

else begin

m := -;

for i:= 1 to d do begin

t := - BackSearch(pi);

if t > m then m:= t;

end;

BackSearch := m;

end;

end;

Листинг 5.16 – Алгоритм поиска с возвратом

Здесь + обозначает число, которое не меньше abs(f(p)) для любой терминальной позиции p; поэтому - не больше f(p) и -f(p) для всех p. Этот алгоритм вычисляет f(p) на основе «грубой силы» – для каждой позиции он оценивает все возможные продолжения.

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

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