Краткие теоретические сведения. Механизм рекурсии весьма эффективен при программировании задач поиска

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

Карта дорог между городами может быть изображена в виде графа – набора вершин, обозначающих города, и ребер, обозначающих дороги (рис. 15).

 

 

 

Рис. 15

 

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

Например, пусть надо найти все возможные пути из точки 1 в точку 5. Согласно принятому правилу, сначала выберем точку 2. на следующем шаге выясняем, что точка 2 тупиковая, поэтому возвращаемся в точку 1 и делаем шаг в точку 3. Из точки 3 в точку 4, из 4 – в 6 и из точки 6 в точку 5. Один маршрут найден. После этого возвращаемся в точку 6 и проверяем, возможен ли шаг в точку, отличную от 5. Так как это возможно, то делаем шаг в 7 и затем в 5. найден еще один путь. Таким образом, процесс поиска состоит из шагов вперед и возвратов назад. Поиск завершается, если из узла начала движения уже некуда идти.

Алгоритм поиска имеет рекурсивный характер: чтобы сделать шаг, мы выбираем точку и опять делаем шаг, до тех пор пока не достигаем цели.

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

Граф можно представить двумерным массивом, который назовем map (карта). Значение элемента массива map[i, j] – единица, если города i и j соединены прямой дорогой, или ноль, если города не соединены дорогой. Для приведенного графа массив map можно изобразить в виде таблицы так:

 

 

1 2 3 4 5 6 7

 

Содержимое ячейки таблицы на пересечении строки i и столбца j соответствует значению map[i, j].

Помимо массива map нам потребуется массив road (дорога) и массив incl (от слова include – включать).

В road[i] мы будем записывать номера пройденных городов. В момент достижения конечной точки он будет содержать номера всех пройденных точек, т. е. описание маршрута.

В incl[i] будем записывать TRUE, если точка с номером i включена в маршрут. Делается это для того, чтобы не включать в маршрут уже пройденную точку (не ходить по кругу).

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

Точка, откуда начинается движение на данном шаге, совпадает с точкой, в которую надо попасть?

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

 

 

Да Нет

	Есть точка, соединения с точкой начала движения на данном шаге, еще не включенная в маршрут?

Да Нет Нет

 

 

 

 

 

 

Рис. 16

 

 

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

Program all_road;

const

N=7; {кол-во вершин графа}

Var

map: array[1..N, 1..N] of integer; {Карта: map[i, j] не 0, если точки i и j соединены}

road: array[1..N] of integer; {Маршрут – номера точек карты}

incl: array[1..N] of Boolean; {incl[i]=TRUE, если точка с номером i включена в road}

start, finish: integer; {Начальная и конечные точки}

i, j: integer;

procedure step (s, f, p: integer); {s – точка, из которой делается шаг}

{f – конечная точка маршрута}

{p – номер искомой точки маршрута}

var

c: integer; {Номер точки, в которую делается очередной шаг}

begin

if s=f then begin

{точки s и f совпали! }

write (‘Путь: ’);

for i: =1 to p-1 do write (road[i], ‘ ‘);

writeln;

end

else begin

{Выбираем очередную точку}

for c: =1 to N do begin {Проверяем все вершины}

if (map[s, c]< > 0) and (NOT incl[c])

{Точки соединения с текущей и не включена в маршрут}

then begin

road[p]: =c; {Добавим вершину в путь}

incl[c]: =TRUE; {Пометим вершину как включенную}

step (c, f, p+1);

incl[c]: =FALSE;

road[p]: =0;

end;

end;

end;

end; {конец процедуры step}

{Основная программа}

begin

{инициализация массивов}

for i: =1 to N do road[i]: =0;

for i: =1 to N do incl[i]: =FALSE;

for i: =1 to N do for j: =1 to N do map[i, j]: =0;

{Ввод значений элементов карты}

map[1, 2]: =1; map[2, 1]: =1;

map[1, 3]: =1; map[3, 1]: =1;

map[1, 4]: =1; map[4, 1]: =1;

map[3, 4]: =1; map[4, 1]: =1;

map[3, 7]: =1; map[7, 3]: =1;

map[4, 6]: =1; map[6, 4]: =1;

map[5, 6]: =1; map[6, 5]: =1;

map[5, 7]: =1; map[7, 5]: =1;

map[6, 7]: =1; map[7, 6]: =1;

write (‘Введите через пробел номера начальной и конечной точек -> ’);

readln (start, finish);

road[1]: =start; {Внесем точку в маршрут}

incl[start]: =TRUE; {Пометим ее как включенную}

step (start, finish, 2); {Ищем вторую точку маршрута}

writeln (‘Для завершения нажмите < Enter> ’);

readln;

end.

Пример работы программы:

Введите через пробел номера начальной и конечной точек -> 1 5

Путь: 1 3 4 6 5

Путь: 1 3 4 6 7 5

Путь: 1 3 7 5

Путь: 1 3 7 6 5

Путь: 1 4 3 7 5

Путь: 1 4 3 7 6 5

Путь: 1 4 6 5

Путь: 1 4 6 7 5

Для завершения нажмите < Enter>