Программирование на языке ПРОЛОГ для искуственного интеллекта




Стратегия поиска в глубину - часть 2


Этот порядок в точности соответствует результату трассировки процесса вычислений в пролог-системе при ответе на вопрос

        ?-  решить( а, Реш).

Поиск в глубину наиболее адекватен рекурсивному стилю программирования, принятому в Прологе. Причина этого состоит в том, что, обрабатывая цели, пролог-система сама просматривает альтернативы именно в глубину.

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

  • вершины пространства состояний - позиции, в которых поставлено 0 или более ферзей на нескольких последовательно расположенных горизонтальных линиях доски;
  • вершина-преемник данной вершины может быть получена из нее после того, как в соответствующей позиции на следующую горизонтальную линию доски будет поставлен еще один ферзь, причем таким образом, чтобы ни один из уже поставленных ферзей не оказался под боем;
  • стартовая вершина - пустая доска (представляется пустым списком);
  • целевая вершина - любая позиция с восемью ферзями (правило получения вершины-преемника гарантирует, что ферзи не бьют друг друга).

Позицию на доске будем представлять как список Y-координат поставленных ферзей. Получаем программу:

        после( Ферзи, [Ферзь | Ферзи] ) :-
                принадлежит( Ферзь, [1, 2, 3, 4, 5, 6, 7, 8] ),

                                % Поместить ферзя на любую вертикальную линию
                небьет( Ферзь, Ферзи).




Содержание  Назад  Вперед