Пошук шляху

Механізм рекурсії вельми ефективний при програмуванні задач пошуку. В якості ще одного прикладу розглянемо задачу пошуку шляху між двома містами. Якщо кілька міст з’єднані дорогами, то очевидно, що потрапити з одного міста в інший можна різними маршрутами. Завдання полягає в знаходженні всіх можливих маршрутів.

Карта доріг між містами може бути зображена у вигляді графа – набору вершин, що означають міста, і ребер, позначають дороги (рис. 12.9).

Рис. 12.9. Подання карти доріг у вигляді графа

Процес пошуку може бути представлений як послідовність кроків. На кожному кроці з використанням деякого критерію вибирається точка, в яку можна потрапити з поточної. якщо чергова обрана точка збіглася із заданою кінцевою точкою, то маршрут знайдений. Якщо не збіглася, то робимо з цієї точки ще крок. Так як поточна точка може бути з’єднана з декількома іншими, то потрібен якийсь формальний критерій вибору. У найпростішому випадку можна вибрати точку з найменшим номером.

Нехай, наприклад, треба знайти всі можливі шляхи з точки 1 в точку 5. Відповідно до прийнятого правилом, спочатку вибираємо точку 2. На наступному кроці з’ясовуємо, що точка 2 тупикова, тому повертаємося в точку 1 і робимо крок в точку 3. З точки 3 – в точку 4, з 4 – в 6 і з точки 6 – в точку 5. Один маршрут знайдений. Після цього повертаємося в точку 6 і перевіряємо, чи можливий крок в точку, відмінну від 5. Так як це можливо, то робимо крок в точку 7, і потім – в 5. Знайдений ще один шлях. Таким чином, процес пошуку складається з кроків вперед і повернень назад. Пошук завершується, якщо з вузла початку руху вже нікуди йти.

Алгоритм пошуку має рекурсивний характер: щоб зробити крок, ми вибираємо точку і знову робимо крок, і так продовжуємо до тих пір, поки не досягнемо мети.

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

Граф можна уявити двовимірним масивом, який назвемо тар (карта). Значення елемента масиву map [i, j] – це відстань між містами i та j, якщо міста з’єднані дорогою, або нуль, якщо міста не з’єднані прямою дорогою. Для наведеного графа масив тар можна зобразити у вигляді таблиці, представленої на рис. 12.10.

Рис. 12.10. Масив тар

Вміст комірки таблиці на перетині рядка i та стовпця j соответcтвует значенням map [i, j].
Крім масиву тар нам будуть потрібні масив road (дорога) і масив incl (від include – включати). В road ми будемо записувати номера пройдених міст. У момент досягнення кінцевої точки він буде містити номери всіх пройдених точок, т. е. опис маршруту.
У inci [i] будемо записувати true, якщо точка з номером i включена в маршрут. Робиться це для того, щоб не включати в маршрут вже пройдену точку (не ходити по колу).
Так як ми використовуємо рекурсивную процедуру, то треба звернути особливу увагу на умову завершення рекурсивного процесу. Процедура повинна припинити викликати сама себе, якщо поточна точка збіглася із заданою кінцевою точкою.
На рис. 12.11 приведена блок-схема алгоритму процедури вибору черговий точки формованого маршруту, а діалогове вікно – на рис. 12.12.
Для введення масиву, представляє опис карти, використовується компонент stringGridl (значення його властивостей приведені в таблиці 12.1), для виведення результату (знайденого маршруту) – поле мітки Label 1. Початкова і кінцева точки маршруту задаються введенням значень в поля редагування Edit1 і Edit2. Процедура пошуку запускається клацанням кнопки Пошук (Buttonl). Поля міток Label2, Label3 і Label4 використовуються для виведення пояснювального тексту.

Рис. 12.11. Блок-схема процедури вибору точки маршруту

Рис. 12.12. Вікно програми Пошук маршруту

Таблиця 12.1. Значення властивостей компонента stringGrid1

Текст програми приведений в лістингу 12.5.
Лістинг 12.5. Пошук маршруту

unit road _;
interface
uses
Windows, Messages, SysUtils, Classes,

Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids;
type
TForml = class (TForm)
StringGridl: TStringGrid;
Edit1: TEdit;
Edit2: TEdit;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Button1: TButton;
Label4: TLabel;
procedure FormActivate (Sender: TObject);
procedure ButtonlClickfSender: TObject);

private
{ Private declarations} public
{ Public declarations} end;
var
Form1: TForm1;
implementation
{$ R * .DFM}
procedure TForml.FormActivate (Sender: TObject);

var
i: integer; begin
// нумерація рядків

for i: = 1 to 10 do
StringGridl.Cells [0, i]: = IntToStr (i); // нумерація колонок
for i: = l to 10 do
StringGridl.Cells [1,0]: = IntToStr (i);

// опис зумовленої карти StringGridl.Cells [1,2]: = '1' StringGridl.Cells [2, l]: = '1'

StringGridl.Cells [1,3]: = '1'

StringGridl.Cells [3,1]: = '1'

StringGridl.Cells [1,4]: = '1'

StringGridl.Cells [4,1]: = '1'

StringGridl.Cells [3,7]: = '1'

StringGridl.Cells [7,3]: = '1'

StringGridl.Cells [4,6]: = '1'

StringGridl.Cells [6,4]: = '1'

StringGridl.Cells [5,6]: = '1'

StringGridl.Cells [6,5]: = '1'

StringGridl.Cells [5,7]: = '1'

StringGridl.Cells [7,5]: = '1'

StringGridl.Cells [6,7]: = '1'

StringGridl.Cells [7,6]: = '1'

end;
procedure TForml.ButtonlClick (Sender: TObject);

const
N = 10; // кол-во вершин графа var
map: array [1..N, 1..N] of integer; // Карта.map [i, j] ne 0,
// якщо точки i і j з'єднані
road: array [1..N] of integer;

// Дорога - номери точок карти

incl: array [1..N] of boolean; // incl [1] дорівнює TRUE, якщо точка
// з номером i включена в road
start, finish: integer; // Початкова і кінцева точки

found: boolean; i, j: integer;
procedure step (s, f, p: integer);

var
з: integer; // Номер точки, в яку робимо черговий крок

i: integer;

begin
if s = f then begin
// Точки s і f збіглися!
found: = TRUE;
Labell.caption: = Labell.caption + # 13 + 'Шлях:';
for i: = l to p-1 do
Labell.caption: = Labell.caption + ' '

+ IntToStr (road [i]); end
else begin
// вибираємо чергову точку for c: = l to N do
begin // перевіряємо всі вершини

if (map [s, c] <> 0) and (NOT incite1)
// точка з'єднана з поточної і не включена в маршрут

then begin
road [p]: = c; // додамо вершину в шлях

incl [c]: = TRUE; // пометим вершину як включену

step (c, f, p + l); incite]: = FALSE; road [p]: = 0;

end;

end;

end;

end; // кінець процедури step
begin
Label1.caption: = '';
// ініціалізація масивів
for i: = l to N do road [i]: = 0;
for i: = l to N do incl [i]: = FALSE;
// введення опису карти з SrtingGrid.Cells

for i: = l to N do
for j: = 1 to N do
if StringGrid1.Cells [i, j] <> ''
then map [i, j]: = StrToInt (StringGridl.Cells [i, j];

else map [i, j]: = 0;
start: = StrToInt (Editl.text);

finish: = StrToInt (Edit2.text);
road [l]: = start; // внесемо точку в маршрут
incl [start]: = TRUE; // пометим її як включену
step (start, finish, 2); // шукаємо другу точку маршруту
// перевіримо, чи знайдений хоча б один шлях

if not found
then Labell.caption: = 'Зазначені крапки не з'єднані!';
end;
end.

При запуску програми в момент активізації форми додатка відбувається подія onActivate, процедура обробки якого заповнює масив StringGridl.cells значеннями, представляють опис карти. Поверсі процедура нумерує рядки і стовпці таблиці, заповнюючи зафіксовані осередки першого шпальти і першого рядка StringGridl.

Пошук маршруту ініціює процедура TFormi.Buttoniciick, яка запускається клацанням на кнопці Пошук. Дана процедура для пошуку точки, з’єднаної з вихідною точкою, викликає процедуру step, яка після вибору першої точки, з’єднаної з початкової, і включення її в маршрут викликає сама себе. При цьому в якості початкової точки задається вже не вихідна, а поточна, тільки що включена в маршрут.