Методы поиска и переборные алгоритмы

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

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

Постановка задачи.

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

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

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

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

Перебор с возвратом

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

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

if <есть клетка-сосед Neighbor отсутствующая в Way, в которую на этом пути еще не ходили> thenbegin <добавить Neighbor в Way>; текущая клетка:= Neighbor;end else <извлечь из Way>;

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

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

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

Finish:= False;<сделать пустым Way>;<добавить в Way (1, 1)><сделать OptimalWay бесконечно длинным>;repeat if <есть клетка-сосед Neighbor отсутствующая в Way, в которую на этом пути еще не ходили> then begin <добавить Neighbor в Way>; текущая клетка:= Neighbor; if (<текущая клетка – (M, N)>)and (<длина OptimalWay больше длины Way>) then OptimalWay:= Way; end else begin if <Way пуст> then Finish:= True else <извлечь из Way>; end;until Finish;

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

Посмотрим работу алгоритма с указанным усовершенствованием на примере лабиринта, изображенного на рисунке (строки нумеруются снизу вверх, столбцы – слева направо). Фиксируем порядок посещения соседних клеток: левая, верхняя, правая, нижняя. В таблице будем фиксировать лишь содержимое Way и OptimalWay в моменты переходов от движения вперед к возврату назад и наоборот от возвратов назад к движению вперед.

Содержимое Way	Содержимое OptimalWay
<(1,1)>	Бесконечно длинный путь
…“движение вперед”…	/– то же –/
<(1,1), (1,2), (2,2), (3,2), (3,1), (4,1), (5,1), (5,2), (5,3), (5,4), (5,5)> (причина возврата: найден вариант)	<(1,1), (1,2), (2,2), (3,2), (3,1), (4,1), (5,1), (5,2), (5,3), (5,4), (5,5)>
…“возврат”…	/– то же –/
<(1,1), (1,2), (2,2), (3,2), (3,1), (4,1), (5,1), (5,2), (5,3), (5,4)>	/– то же –/
…“движение вперед”…	/– то же –/
<(1,1), (1,2), (2,2), (3,2), (3,1), (4,1), (5,1), (5,2), (5,3), (5,4), (4,4)> (причина возврата: вариант заведомо неоптимален)	/– то же –/
…“возврат”…	/– то же –/
<(1,1), (1,2), (2,2)>	/– то же –/
…“движение вперед”…	/– то же –/
<(1,1), (1,2), (2,2), (2,3), (2,4), (3,4), (4,4), (5,4), (5,3), (5,2), (5,1)> (причина возврата: вариант заведомо неоптимален)	/– то же –/
…“возврат”…	/– то же –/
<(1,1), (1,2), (2,2), (2,3), (2,4), (3,4), (4,4), (5,4)>	/– то же –/
…“движение вперед”…	/– то же –/
<(1,1), (1,2), (2,2), (2,3), (2,4), (3,4), (4,4), (5,4), (5,5)> (причина возврата: найден вариант)	<(1,1), (1,2), (2,2), (2,3), (2,4), (3,4), (4,4), (5,4), (5,5)>
…“возврат”…	/– то же –/
<(1,1), (1,2), (2,2), (2,3), (2,4)>	/– то же –/
…“движение вперед”…	/– то же –/
<(1,1), (1,2), (2,2), (2,3), (2,4), (1,4), (1,5)> (причина возврата: некуда идти)	/– то же –/
…“возврат”…	/– то же –/
<> (конец перебора: некуда идти, некуда возвращаться)	/– то же –/

В рассмотренном примере оптимальным оказался путь длиной 8 ходов, проходящий через клетки (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4), (5, 4), (5, 5).

Волновой алгоритм

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

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

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

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

Рассмотрим метод на примере:

Распространение волны отображено на рисунке и в таблице. Цифра на рисунке означает шаг метода (номер фронта волны), на котором клетка посещается.

Шаг метода
Клетки	(1,1)	(1,2)	(2,2)	(3,2) (2,3)	(3,1) (2,4)	(4,1) (3,4) (1,4)	(5,1) (4,4) (1,5)	(5,2) (5,4)	(5,3) (5,5)

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

В данном примере при обратном ходе мы получим путь, проходящий через клетки (1, 1), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4), (5, 4), (5, 5). Этот результат совпадает с полученным перебором с возвратом.

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

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

Лабораторная работа выполняется на ПЭВМ.

Для получения результата необходимо сделать следующее:

1. Проанализировать исходные данные.

2. Разработать алгоритм решения задачи

3. Разработать и отладить программу

4. Создать отчет

 

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Что такое граф? Что такое ребро и дуга графа?

2. Что такое ориентированный граф и неориентированный граф?

3. Какие вершины называют смежными? Какие ребра называют смежными? Что означает слово инцидентные?

4. Что такое вес вершины, вес ребра? Привести примеры из реальных задач.

5. Каковы сложности в среднем и лучшем случае алгоритма поиска в глубину?

6. В чем разница между алгоритмами поиска в ширину и поиска в глубину?

7. Согласны ли Вы с хранением графа в виде списков смежности в алгоритмах поиска? Почему?

8. Назовите два основных этапа волнового алгоритма. Что происходит на каждом из этапов?