Алгоритми із поверненням
Особливо інтригуюча область програмування — завдання так званого штучного інтелекту. Тут ми маємо справу з алгоритмами, що шукають рішення не за заданими правилами обчислень, а шляхом проб і помилок. Зазвичай процес проб і помилок поділяється на окремі завдання (прийом"Поділяй і володарюй" ). Часто ці завдання найбільше природно виражаються в термінах рекурсії і вимагають дослідження кінцевого числа підзавдань. У загальному вигляді весь процес можна оформити як процес пошуку, що будує (і обрізає) дерево підзадач. У багатьох проблемах таке дерево пошуку росте дуже швидко, зростання залежить від параметрів задачі та часто буває експонентним. Відповідно зростає і вартість пошуку. Іноді, використовуючи деякі евристики, дерево пошуку вдається скоротити і звести витрати на обчислення до розумних меж.
З принципу, що завдання штучного інтелекту розбивається на подзадачи, продемонструємо застосування у своїй рекурсії. Почнемо з демонстрації основних методів на добре відомому прикладі - задачі прохід коня.
Дана дошка розміром n 'nтобто. міститьn2 полів. Спочатку на полі з координатамиx0,y0 міститься кінь - фігура, що переміщається за звичайними шаховими правилами. Завдання полягає у пошуку послідовності ходів (якщо вона існує), коли він кінь точно один раз побуває на всіх полях дошки (обійде дошку), тобто. Необхідно обчислитиn2 - 1 ходів.
Очевидний прийом спростити завдання обходуn2 полів - вирішувати простішу, а саме виконати черговий хід, або довести, що ніякий хід не можливий. Тому розпочнемо з визначення алгоритму виконання чергового ходу. Перший його варіант виглядає так:
BEGINініціалізація вибору ходу;
REPEATвибір чергового кандидата зі списку ходів;
IFпідходитьTHEN
IFдошка не заповненаTHEN
IFневдачаTHENзнищення попереднього ходу
UNTILудачаORкандидатів більше немає
Для детальнішого опису алгоритму потрібно вибрати деяке уявлення даних. Дошку, найпростіше, можна як матрицю, назвемо її h. Введемо, крім того, тип індексуючих значень:
TYPE index = ARRAY [1..n, 1..n] OF INTEGER; (25)
Внаслідок того, що ми хочемо знати історію просування по дошці, поля її представлятимемо цілими числами, а не булевськими значеннями, що дозволяють лише визначати зайнятість поля. Відповідно до цього можна зупинитися на таких угодах:
Тепер потрібно вибрати відповідні параметри. Вони повинні визначати початкові умови наступного ходу та результат (якщо хід зроблено). У першому випадку достатньо задавати координати поля (х,у), звідки слідує хід, і числоi, що вказує номер ходу (для фіксації). Для результату потрібен булевський параметр; якщо він - "істина", то хід був можливий.
Крім того, умовудошка не заповненаможна переписати якi2 . Якщо ввести ще дві локальні змінніuіvдля можливого ходу, що визначається відповідно до правил “стрибка” коня, то предикатпідходитьможна подати як логічну кон'юнкцію умов , що нове поле знаходиться в межах дошки (1 £u£nі 1 £v£n) і ще не відвідувалося (huv= 0). Фіксація допустимого ходу виконується за допомогою наданняhuv:=i, а скасування - за допомогоюhuv:= 0. Якщо ввести локальну зміннуq1 тавикористовувати її як параметр-результат при рекурсивних зверненнях до цього алгоритму, тоq1 можна підставити замістьудача.Відповідно до цього отримуємо наступну процедуру:
PROCEDURE Try (i: INTEGER; x, у: index; VAR q: BOOLEAN);
VAR u, v: INTEGER; q1: BOOLEAN;
BEGINініціація вибору ходу;(27)
REPEAT- координати наступного ходу,
визначається правилами шахів;
ELSE WriteLn('no path');
Не можна упускати ще одну деталь. Зміннаhuvіснує тільки в тому випадку, якщо іu, іvлежать у діапазоні індексів 1…n. Отже, вираз у (27), підставлений замістьпідходитьз (24), осмислено, тільки якщо його чотири перші складові істинні. Саме тому важливо, щоб складова huv = 0 була останньою. У табл. 1 наводяться рішення для трьох вихідних позицій: приn= 5 і приn= 6.
Таблиця 1. Три можливі обходи конем
Характерна властивість таких алгоритмів (алгоритмів з поверненням) полягає в тому, що в них робляться кроки в напрямку загального рішення, але вони фіксуються (записуються) таким чином, що пізніше можна повернутися назад, відкидаючи тим самим кроки, які ведуть у глухий кут, а не до спільного рішення. Такий процес називаєтьсяповерненнямабовідкатом(backtracking). Якщо припустити, що кількість потенційних кроків звісно, то з алгоритму (24) можна вивести універсальну схему:
BEGINініціація вибору кандидата;
REPEATвибір чергового кандидата;
IFпідходитьTHEN BEGINйого запис;
IFрішення неповнеTHEN BEGIN Try; (28)
IFневдачаTHEN BEGINстирання записуEND
UNTILудачаORкандидатів більше немає
У реальних програмах можуть зустрічатися й інші варіанти, що виходять із схеми (28). Часто, наприклад, зустрічається побудова з явним параметром рівня, коли вказується глибина рекурсії. Це призводить до простих умов закінчення роботи. Більше того, якщо на кожному кроці число досліджуваних шляхів фіксоване (нехай воно дорівнюєm), можна застосовувати ще одну виведену схему (до неї треба звертатися за допомогою оператора Try(1):
PROCUDURE Try(i: INTEGER);
REPEAT k := k+1;вибір k-го кандидата;
IFпідходитьTHEN BEGINйого запис;