Расстановка ферзей

Var

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

Рекурсия

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

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

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

o решение найдено;

o имеется некоторое число возможных путей к решению;

o тупиковая ситуация — все возможные пути исчерпаны, никакие действия невозможны.

В первом случае алгоритм можно считать завершенным, если только нужно было найти хотя бы одно решение, а не все множество решений. Во втором случае алгоритм должен выбрать один из возможных путей для дальнейшего поиска решений. Третий случай — это необходимость вернуться назад к последнему этапу, на котором остались возможные пути, и попробовать снова, если только все возможные альтернативы не были исчерпаны на всех предыдущих этапах (тогда придется признать, что решения нет).

Схема алгоритма с возвратом представлена в листинге 10.9:

Листинг 10.9. Схема алгоритма с возвратом

procedure Attemt(i: integer; удача: Boolean);

k: integer;

begin

k:=0;

repeat

выбор k-того возможного хода

if ход удачен then begin

обработка хода;

if i<n then begin

Attemt(i+1, удача);

if not удача then вернуться назад

end;

end;

until удача or (k=m)

end;

Эта схема предполагает фиксированное число путей на каждом шаге — это значение m, глубина рекурсии — n. В конкретных программах эта схема может воплощаться различными способами.

Задача о "восьми ферзях" — хорошо известный пример использования метода проб и ошибок и алгоритмов с возвратом. Этой задачей в 1780 г. занимался К. Ф. Гаусс, но полного ее решения не дал, и это не удивительно. Для подобного класса задач характерно отсутствие аналитического решения, но они требуют большого объема изнурительных вычислений, терпения, аккуратности. Поэтому такие задачи отдают для решения вычислительным машинам, обладающим вышеперечисленными достоинствами в полной мере.

Задача о восьми ферзяхформулируется так: нужно расставить восемь ферзей на шахматной доске размером 8×8 таким образом, чтобы ни один ферзь не угрожал другому, то есть чтобы ни один из них не находился на одной и той же горизонтали, вертикали или диагонали, что и любой другой.

Исследуем два варианта этой задачи:

o найти некоторое решение;

o найти все решения задачи, то есть все правильные конфигурации восьми ферзей, не бьющих друг друга на шахматной доске.

Для решения первого варианта данной задачи воспользуемся схемой, приведенной в листинге 10.9:

procedure Attemt(i: integer);