Особенно интригующая область программирования — задачи так называемого искусственного интеллекта. Здесь мы имеем дело с алгоритмами, ищущими решение не по заданным правилам вычислений, а путем проб и ошибок. Обычно процесс проб и ошибок разделяется на отдельные задачи (прием “Разделяй и властвуй”). Часто эти задачи наиболее естественно выражаются в терминах рекурсии и требуют исследования конечного числа подзадач. В общем виде весь процесс можно оформить как процесс поиска, строящий (и обрезающий) дерево подзадач. Во многих проблемах такое дерево поиска растет очень быстро, рост зависит от параметров задачи и часто бывает экспоненциальным. Соответственно увеличивается и стоимость поиска. Иногда, используя некоторые эвристики, дерево поиска удается сократить и тем самым свести затраты на вычисления к разумным пределам.
Исходя из принципа, что задача искусственного интеллекта разбивается на подзадачи, продемонстрируем применение при этом рекурсии. Начнем с демонстрации основных методов на хорошо известном примере — задаче о ходе коня.
Дана доска размером n´n т.е. содержащая n2полей. Вначале на поле с координатами x0, y0помещается конь — фигура, перемещающаяся по обычным шахматным правилам. Задача заключается в поиске последовательности ходов (если она существует), при которой конь точно один раз побывает на всех полях доски (обойдет доску), т.е. нужно вычислить n2 - 1 ходов.
Очевидный прием упростить задачу обхода n2полей — решать более простую, а именно либо выполнить очередной ход, либо доказать, что никакой ход не возможен. Поэтому начнем с определения алгоритма выполнения очередного хода. Первый его вариант выглядит следующим образом:
PROCEDURE TryNextMove;
BEGIN инициализация выбора хода;
REPEAT выбор очередного кандидата из списка ходов;
IF подходит THEN
BEGIN
запись хода;
IF доска не заполнена THEN
BEGIN (24)
TryNextMove;
IF неудача THEN уничтожение предыдущего хода
END
END
UNTIL удача OR кандидатов больше нет
END;
Для более детального описания алгоритма нужно выбрать некоторое представление для данных. Доску, самое простое, можно представить как матрицу, назовем ее h. Введем, кроме того, тип для индексирующих значений:
TYPE index = ARRAY [1..n, 1..n] OF INTEGER; (25)
VAR h: index;
Вследствие того, что мы хотим знать историю продвижения по доске, поля ее будем представлять целыми числами, а не булевскими значениями, позволяющими лишь определять занятость поля. В соответствии с этим можно остановиться на таких соглашениях:
h[x, y] = 0: поле (х, у)еще не посещалось; (26)
h[x, y] = i:поле (х, у)посещалось на i-мходу.
Теперь нужно выбрать соответствующие параметры. Они должны определять начальные условия следующего хода и результат (если ход сделан). В первом случае достаточно задавать координаты поля (х, у), откуда следует ход, и число i, указывающее номер хода (для фиксации). Для результата же требуется булевский параметр; если он — "истина", то ход был возможен.
Кроме того, условие доска не заполнена можно переписать как i < n2. Если ввести еще две локальные переменные u и v для возможного хода, определяемого в соответствии с правилами “прыжка” коня, то предикат подходит можно представить как логическую конъюнкцию условий, что новое поле находится в пределах доски (1 £ u £ n и 1 £ v £ n) и еще не посещалось (huv= 0). Фиксация допустимого хода выполняется с помощью присваивания huv:= i, а отмена — с помощью huv:= 0. Если ввести локальную переменную q1 и использовать ее в качестве параметра-результата при рекурсивных обращениях к этому алгоритму, то q1 можно подставить вместо удача. В соответствии с этим получаем следующую процедуру:
PROCEDURE Try(i: INTEGER; х, у: index; VAR q: BOOLEAN);
VAR u, v: INTEGER; q1: BOOLEAN;
BEGIN инициация выбора хода; (27)
REPEAT <u, v> - координаты следующего хода,
определяемого правилами шахмат;
IF (((1 <= u) AND (u <= n)) AND ((1 <= v) AND (v<= n))) AND (h[u, v] =0) THEN
BEGIN
h[u,v]:= i;
IF i < n*n THEN
BEGIN Try(i+1, u, v, q1);
IF NOT q1 THEN h[u,v]:= 0 ELSE q1:= TRUE;
END;
END;
UNTIL q1 OR других ходов нет;
q:= q1;
END;
Еще один шаг детализации — и получим уже полностью написанную программу. До этого момента программа создавалась совершенно независимо от правил, управляющих движением коня. Уточним и эту частную особенность задачи.
Рис. 8.Восемь возможных ходов коня
Если задана начальная пара координат х, у, то для следующего хода u, v существует восемь возможных кандидатов. На рис. 8 они пронумерованы от 1 до 8. Получать u, v из х, у довольно просто. Достаточно к последним добавлять разности между координатами, хранящиеся либо в массиве разностей, либо в двух массивах, хранящих отдельные разности. Обозначим эти массивы через dx и dy и будем считать, что они соответствующим образом инициализированы. Для нумерации очередного хода-кандидата можно использовать индекс k (подробности показаны в листинге 3). Первый раз к рекурсивной процедуре обращаются с параметрами x0 и y0 — координатами поля, с которого начинается обход. Этому полю должно быть присвоено значение 1, остальные поля маркируются как свободные:
h [х0,у0] := 1; Тгу(2, x0, y0, q);
Листинг 3. Обход поля ходом коня
PROGRAM KnightsTour;
VAR i, j, n, Nsqr: INTEGER;
q: BOOLEAN;
dx, dy: ARRAY [1..8] OF INTEGER;
h: ARRAY [1..8,1..8] OF INTEGER;
PROCEDURE Try(i, x, y: INTEGER; VAR q: BOOLEAN);
VAR k, u, v: INTEGER; q1: BOOLEAN;
BEGIN k:= 0;
REPEAT k:= k+1; q1:= FALSE;
u:= x+dx[k]; v:= y+dy[k];
IF (((1 <= u) AND (u <= n)) AND ((1 <= v) AND (v <= n))) AND (h[u, v] = 0) THEN
FOR j := 1 TO n DO Write(' ',i,':',j,'->',h[i,j]:2,'; ');
WriteLn;
END;
END
ELSE WriteLn('no path');
ReadLn;
END.
Нельзя упускать еще одну деталь. Переменная huvсуществует только в том случае, если и u, и v лежат в диапазоне индексов 1…n. Следовательно, выражение в (27), подставленное вместо подходит из (24), осмысленно, только если его четыре первые составляющие истинны. Именно поэтому важно, чтобы составляющая huv= 0 была последней. В табл. 1 приводятся решения для трех исходных позиций: <3,3> и <2,4> при n = 5 и <1,1> при n = 6.
Таблица 1. Три возможных обхода конем
Характерное свойство таких алгоритмов (алгоритмов с возвратами) заключается в том, что в них делаются шаги в направлении общего решения, но все они фиксируются (записываются) таким образом, что позже можно вернуться вспять, отбрасывая тем самым шаги, которые ведут в тупик, а не к общему решению. Такой процесс называется возвратом или откатом (backtracking). Если предположить, что число потенциальных шагов конечно, то из алгоритма (24) можно вывести универсальную схему:
PROCEDURE Try;
BEGIN инициация выбора кандидата;
REPEAT выбор очередного кандидата;
IF подходит THEN BEGIN его запись;
IF решение неполное THEN BEGIN Try; (28)
IF неудача THEN BEGIN стирание записи END
END
END
UNTIL удача OR кандидатов больше нет
END;
В реальных программах могут встречаться и другие варианты, получающиеся из схемы (28). Часто, например, встречается построение с явным параметром для уровня, когда указывается глубина рекурсии. Это приводит к простым условиям окончания работы. Более того, если на каждом шаге число исследуемых путей фиксировано (пусть оно равно m), то можно применять еще одну выведенную схему (к ней надо обращаться с помощью оператора Try(1):
