Рекурсія в Delphi: Пошук шляху
Механізм рекурсії вельми ефективний при програмуванні задач пошуку. В якості ще одного прикладу розглянемо задачу пошуку шляху між двома містами. Якщо кілька міст з'єднані дорогами, то очевидно, що потрапити з одного міста в інший можна різними маршрутами. Завдання полягає в знаходженні всіх можливих маршрутів.
Карта доріг між містами може бути зображена у вигляді графа - набору вершин, що означають міста, і ребер, що позначають дороги (рис. 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 відповідає значенню map [i, j].
Крім масиву тар нам будуть потрібні масив road (дорога) і масив incl (від include - включати). У road ми будемо записувати номера пройдених міст. У момент досягнення кінцевої точки він буде містити номери всіх пройдених точок, т. Е. Опис маршруту.
У incl будемо записувати true, якщо точка з номером i включена в маршрут. Робиться це для того, щоб не включати в маршрут вже пройдену точку (не ходити по колу).
Так як ми використовуємо рекурсивную процедуру, то треба звернути особливу увагу на умову завершення рекурсивного процесу. Процедура повинна припинити викликати сама себе, якщо поточна точка збіглася із заданою кінцевою точкою.
На рис. 12.11 приведена блок-схема алгоритму процедури вибору черговий точки формованого маршруту, а діалогове вікно - на рис. 12.12.
Для введення масиву, що представляє опис карти, використовується компонент stringGridl (значення його властивостей приведені в таблиці 12.1), для виведення результату (знайденого маршруту) - поле мітки Label1. Початкова і кінцева точки маршруту задаються введенням значень в поля редагування Edit1і Edit2. Процедура пошуку запускається клацанням кнопки Пошук (Button1). Поля міток Label2, Label3 і Label4 використовуються для виведення поясняющего тексту.
Мал. 12.11. Блок-схема процедури вибору точки маршруту
Мал. 12.12. Вікно програми Пошук маршруту
Таблиця 12.1. Значення властивостей компонента stringGrid1
Лістинг 12.5. Пошук маршруту