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

Логический вывод по существу сводится к достижению цели G на основе последовательного процесса доказательства истинности (или ложности) частичных целей через механизм унификации и возвратов.

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

Пространство состояний – это граф, вершины которого соответствуют ситуациям, встречающимся в задаче, а решение задачи сводится к поиску пути на графе. Вершины графа соответствуют проблемным ситуациям, дуги – разрешенным переходам из одних состояний в другие. Задача отыскания плана решения задачи эквивалентна задаче построения пути между заданной начальной ситуацией и некоторой указанной заранее конечной ситуацией, называемой целевой вершиной. В терминах пространства ситуаций основными стратегиями поиска являются стратегии поиска в глубину и в ширину. Рассмотрим сначала первую из них (рис. 1.1).

В терминах логического программирования вычисление цели j приводит к полному обходу в глубину конкретного дерева поиска цели j, в котором выбирается самая левая цель. По существу здесь декларирован некоторый порядок извлечения целей. Действительно, говоря о поиске в глубину, мы имеем в виду тот порядок, в котором рассматриваются альтернативы в пространстве состояний. В соответствии с этим порядком запоминается одна альтернативная вершина и связанные с ней потомки. Сама система Prolog при выполнении цели проверяет цели по принципа поиска в глубину.

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

Рассмотрим программу поиска на графе в глубину на языке Prolog:

after – состояние дуг исходного графа

but – целевые вершины.

After(a,b).

After(a,c).

After(b,d).

After(b,e).

After(c,f).

After(c,g).

After(d,h).

After(e,i).

After(e,j).

After(f,k).

But(f).

But(j).

Solve(N,S):-

long([],N,S).

long(P,N,[N|P]):-

But(N).

Long(P,N,S):-

After(N,N1),

Not(member(N1,P)),

long([N|P],N1,S).

member(X,[X|Q]).

member(X,[H|Q]):-member(X,Q).

Для поиска пути из вершины а в целевые вершины необходимо ввести вопрос ?-solve(a,X).

В ответ будет выдано 2 ответа:

X=[j,e,b,a]->;

X=[f,c,a]->;

False.