3.4. Алгоритмы с возвратом

Рис. 3.7. Кривые Серпинского Si,----St.

3.4. алгоритмы с возвратом

Особенно интересный раздел программирования - это задачи из области искусственного интеллекта . Здесь нужно строить алгоритмы, которые находят решение определенной Задачи не по фиксированным правилам вычисления, а методом проб и ошибок. Обычно процесс проб и ошибок разделяется на отдельные подзадачи. Часто эти подзадачи наиболее естественно описываются с помощью рекурсии. Процесс пробки ошибок можно рассматривать в общем виде как попсовый процесс, который постепенно строит и просматривает Также обрезает) дерево подзадач. Во многих случаях та-деревья поиска растут очень быстро, обычно экспоненциально, в зависимости от заданного параметра. Соответ-венно увеличивается стоимость поиска. Часто дерево по-можно обрезать, используя только эвристические сооб-Р^зкения, и тем' самым сводить количество вычислений к ja-УЧным пределам.

Здесь МЫ не собираемся обсуждать общие эвристическ правила. Предмет этой главы - общий принцип разбиец * таких задач на подзадачи и использование в них peKypcj. Вначале мы продемонстрируем основные принципы на v рощо известном примере - задаче о ходе коня.

Дана доска п X . содержащая полей; Конь, котопщ ходит согласно щахматным правилам, помещается на пол с начальными координатами хо, уо- Нужно покрыть всю дос^1. ходами коня, т. е. вычислить обход доски, если он сущ^ ствует, из - 1 ходов, такой, что каждое поле посещается ровно один раз.

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

procedure попытка следующего хода; begin инициация выборки ходов;

repeat выбор следующего возможного хода из списка с редных ходов; if он приемлем then begin запись хода;

if доска не заполнена then (3.24)

begin попытка следующего хода;

if неудача then стирание предыдущего хода end

until {ход был удачным) V {нэт других возможных ходой\ end

Если мы хотим более точно описать этот алгоритм, то должны выбрать некоторое представление для данных. Очевидно, что доску можно представить в виде матрицы, скажем, А. Введем также тип индексирующих значений:

type index = 1.. n; 25)

var А: &тт&у[1пйех, index] of integer

Так как мы хотим сохранять историю последовательного з^ хвата доски, то мы будем представлять каждое поле floeij целым числом, а не булевским значением, которое отража бы просто факт занятия поля. Очевидно, можно остановитьс i на таких соглащениях:

h [х, у] = 0: поле (х, у) не посещалось,

h[x, y] = i: поле (х, у) посещалось на i-м ходу (1 f I

Теперь нужно выбрать подходящие параметры. Онидол ны определять начальные условия для следующего хода.

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

Рь пора обратить на них внимание. Вос задана начальная пара координат <х, уУ, то имеется возможных координат <и, v} следующего хода. На . 3-8 они пронумерованы от 1 до 8.

сообщать о его удаче или неудаче. Первая задача вы- няется заданием координат поля х, у, с которого делается а также номером хода / (для его фиксации). Для реше-ffi рторой задачи нужен булевский параметр-результат:

true означает удачу, q = false - неудачу. Какие операторы можно теперь уточнить на основе этих

щений? Разумеется, доска не заполнена можно выразить < г-Кроме того, если ввести две локальные пере- нны^ м и у для обозначения координат возможного хода, поеделяемых по правилам хода коня, то предикат приемлем можно выразить как логическую конъюнкцию двух условий: чтобы новое поле находилось на доске, т. е. 1 и п

J у п, и чтобы оно ранее не посещалось, т. е. h\u, h\ = 0. Фиксация допустимого хода выполняется с помощью 1исваивания у]: = i, а отмена хода (стирание)-как jj у] 0. Если при рекурсивном вызове этого алгоритма в качестве параметра-результата передается локальная переменная q\, то вместо ход был удачным можно подставить q\. Таким образом, мы приходим к программе (3.27):

procedure try (i: integer; x,y: index; var g: boolean); varw, : integer; ql: boolean; begin инициация выбора ходов;

repeat пусть и, v - координаты следующего хода, определяемого шахматными правилами; if (1<м<и) Л (!< < ) Л (A[ ,w]=0) then begin h[u,v] := i;

if i < sqr(n) then (3.27)

begin try{i-{-\,u,v,q\);

if -11 then h[u,v\ := 0 end else qi : = true

until 1 Y {нет других ходов); q := ql