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




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


Существует много различных подходов к проблеме поиска решающего пути для задач, сформулированных в терминах пространства состояний. Основные две стратегии поиска - это поиск в глубину и поиск в ширину. В настоящем разделе мы реализуем первую из них.

Мы начнем разработку алгоритма и его вариантов со следующей простой идеи:

line();

Для того, чтобы найти решающий путь Реш из заданной вершины В в некоторую целевую вершину, необходимо:

  • если В - это целевая вершина, то положить Реш = [В], или
  • если для исходной вершины В существует вершина-преемник В1, такая, что можно провести путь Реш1 из В1 в целевую вершину, то положить Реш = [В | Peш1].
line();

fig11_4.gif (1753 bytes)

Рис. 11. 4.  Пример простого пространства состояний:  а   -  стартовая
вершина,   f    и   j   -  целевые вершины. Порядок, в которой происходит
проход по вершинам пространства состояний при поиске в глубину:
а, b, d, h, e, i, j. Найдено решение [a, b, e, j]. После возврата
обнаружено другое решение: [а, с, f].

На Пролог это правило транслируется так:

        решить( В, [В] ) :-
                цель( В).

        решить( В, [В | Реш1] ) :-
                после( В, В1 ),
                решить( В1, Реш1).

Эта программа и есть реализация поиска в глубину. Мы говорим "в глубину", имея в виду тот порядок, в котором рассматриваются альтернативы в пространстве состояний. Всегда, когда алгоритму поиска в глубину надлежит выбрать из нескольких вершин ту, в которую следует перейти для продолжения поиска, он предпочитает самую "глубокую" из них. Самая глубокая вершина - это вершина, расположенная дальше других от стартовой вершины. На рис. 11.4 мы видим на примере, в каком порядке алгоритм проходит по вершинам.


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