Логический вывод по существу сводится к достижению цели 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.