Применение поиска в пространстве состояний при реализации автоматизированного логического вывода.

Пусть дан простой ориентированный граф G=(V,E), и пусть существует некоторая вершина S, не имеющая предков (в эту вершину не входит ни одна дуга). Эта вершина называется начальным состоянием. Все остальные вершины имеют хотя бы одного предка. Также существует Term – подмножество терминальных вершин (состояний). Такой граф называется или пространством состояний или пространством решений, его вершины называются состояниями, а его дуги – правилами.

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

Раскрытием вершины или состояния называется определение исходящих из неё дуг.

В случае построения пространства состояний для задачи OL-опровержения вершины раскрываются следующим образом:

A) На (C_i,B_j) строится множество резольвент R.

B) Производится отождествление влево во всех клозах из R, где это возможно.

C) Заменяем все редуцируемые клозы в R на их редукции.

D) Определяем всевозможные боковые клозы для всех клозов из R.

Замечание: терминальными будут те пары, которые при резолюции дают пустой клоз.

Приведем для простоты пример из логики высказываний.

S={pÚq,ùpÚq, pÚùq, ùpÚùq}

(pÚq, -)

 

(pÚq, pÚùq) (pÚq,ùpÚùq)

 

(pÚqÚp=p,ùpÚq) (p, ùpÚùq)

 

(pÚq, pÚùq) (pÚq, ùpÚùq)

 

(pÚqÚp, ùpÚq) (pÚqÚp, ùpÚùq)

 

(pÚqÚpÚq=pÚqÚq, pÚùq) (pÚqÚq, ùpÚùq)

 

 

(pÚqÚqÚp=pÚqÚ) (pÚqÚqÚùp=p ÚqÚùp =)

ПОВТОР

 

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

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

Алгоритм поиска в пространстве состояний в формальном виде выглядит следующим образом:

G:={S}; T:={S}; // - вначале пространство решений G и дерево решений T состоит из одной начальной вершины S.

OPEN:={S}; // - список вершин, которые требуется раскрыть.

CLOSED:=Æ; // - список уже раскрытых вершин.

while true do begin // - начинаем бесконечный цикл.

if Null (OPEN) then return (NO); // - если список OPEN пуст, то ответ отрицательный

n:=First (OPEN); // - берём за n первую вершину в списке OPEN.

OPEN:= Tail (OPEN); // - список OPEN без первой вершины.

ADD (n, CLOSED); // - добавляем вершину n в список CLOSED.

if Term (n) then return (YES, T); // - если вершина терминальная, то ответ утвердительный с деревом решений T. При этом в случае необходимости мы можем продолжить поиск.

M={M_i}:=раскрыть (n); // - получаем в M список вершин, получившихся при раскрытии вершины n.

for mÎM do begin

ADD (G, n, m); // - добавляем дуги (n, m) в пространстве решений.

if (not (mÎOPEN)) and (not (mÎCLOSED)) then begin

ADD (T, n, m); // - добавляем правило (n, m) к дереву решений.

end;

else begin

Rebuild (T); // - перестраиваем дерево решений.

end;

end;

OPEN:=Reorder (OPEN); // - переупорядочиваем список OPEN

end.

Примечание. 1: Процедура переупорядочивания, то есть Reorder иногда зависит от конкретной задачи. В этом случае, алгоритм называется информированным. Существует три класса информированных алгоритмов: A, A*, OA*. Неинформированные алгоритмы бывают двух классов: поиск в ширину, поиск в глубину. В случае поиска в ширину верхняя вершина в списке OPENодна из самых ближних к начальной, а при поиске в глубину – одна из самых дальних от начальной. Тип поиска в пространстве состояний полностью соответствует соответствующему типу обхода графа (см. []).

2. Процедура Rebuild может отсутствовать. Она обязательна в случаях поиска оптимального решения.

Задача поиска в пространстве состояний может ставиться в четырех различных вариациях:

A) Определить существует ли решение вообще?

B) Найти любое решение задачи.

C) Найти всевоможные решения задачи.

D) Найти из множеств решений оптимальное в каком-либо смысле. В простейшем случае под оптимальным понимается решение, которому соответствует минимальное количество ребер от начальной до терминальной вершины. В случае OL-опровержения, таким образом, оптимальность означает минимизацию количества проведенных резолюций. В более сложных случаях могут вводиться весовые коэффициенты дуг.

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