Различные стратегии поиска вывода.

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

    Возможна и другая стратегия. В ней зависимость «если - то» используется в другом смысле. Пусть нам нужно вывести утверждение из консеквента некоторой продукции. Тогда проверяем, доказаны ли утверждения из антецедента этой продукции. Если доказаны, то вывод найден. В противном случае потребуется применить то же рассуждение для недоказанных утверждений из антецедента и т.д., пока все утверждения из А не будут доказаны, доказывая тем самым утверждения из В. Таким образом, активизируются те продукции, консеквенты которых содержат утверждения, подлежащие выводу. Эта стратегия поиска логического вывода называется обратной.

    Как прямая, так и обратная стратегии, в свою очередь, делятся на параллельную и последовательную. Они отличаются друг от друга методами перебора. При параллельной стратегии все возможные варианты вывода рассматриваются параллельно. Этот способ не требует возвратов, реализации «бектрекинга». Напротив, последовательная стратегия предусматривает последовательный перебор вариантов с использованием бектрекинга. Эта стратегия, по сути, эквивалентна обходу дерева. Приведем пример, иллюстрирующий два варианта стратегий: прямой параллельный и обратный последовательный.

 

Пример 6.

    Пусть в нашей БЗ используются утверждения

R, s, t, u, v, w, x, y, z.

Правила вывода, представленные в виде продукций, таковы:

 

1) r –> t          4) s –> u         7) w, x --> y

2) u –> t       5) r, t, v –> w 8) u, w, x --> z

3) r, u –> v     6) u, y –> w          9) r, w –> z

    Будем считать, что установленными являются утверждения r  и s и нашей задачей является установить, выводимо ли утверждение z.

Прямая стратегия.

 

    Результаты работы алгоритма, реализующего прямую стратегию, можно представить в виде таблицы, состоящей из следующих столбцов: № шага, номера активизированных продукций, и факты, попадающие в базу данных в процессе работы алгоритма. Перед началом работы (шаг 0) в базу данных заносятся факты, считающиеся доказанными a priori, т.е. начальные условия. Затем активизируются все продукции, антецеденты которых состоят только из фактов, находящихся в БД. Консеквентны активизированных продукций заносятся в БД. Работа алгоритма прекращается, когда на очередном шаге в БД не будет занесен ни один новый факт. Возможен и другой вариант окончания работы: если требуется вывести указанные утверждения, работу можно закончить, когда все они попадут в БД. Ниже приведена таблица вывода утверждения z при указанных выше начальных условиях.

   

№№ шагов	акт. п-ла	база данных
0	-	r, s
1	1,4	r, s, t, u
2	2,3	r, s, t, u, v
3	5	r, s, t, u, v, w
4	9	r, s, t, u, v, w, z

Вывод получен.

 

Обратная стратегия.

 

    Алгоритм, реализующий обратную стратегию, осуществляет построение специального дерева вывода. Построение дерева начнем с корня, который пометим утверждением, истинность которого требуется установить. Остальные вершины будем помечать левыми частями продукций (заметим, что при необходимости вывести несколько утверждений, понадобится сформировать «лес» – т.е. по одному дереву для каждого утверждения). Дуги дерева будем помечать номерами в соответствии с порядком их построения и номерами продукций в скобках. На каждом шаге требуется найти продукцию, в правой части которой находится анализируемое утверждение. На первом шаге выберем утверждение, помечающее корень. Дальнейшие шаги алгоритма проиллюстрируем выводом утверждения z в БЗ примера:

              

 Поясним работу алгоритма. Его начальным условием является установленные a priori факты r и s. На первом шаге ищем первую продукцию, в правой части которой находится z. Это продукция 8. В стеке возвратов запоминаем, что дальнейший просмотр продукций при возврате на этот шаг следует начинать с продукции 9. Формируем вершину u,w,x и строим в нее дугу из вершины z. Из вершины u,w,x необходимо построить три вершины и три дуги по продукциям, в правых частях которых находятся утверждения u, w и x. Сначала строим первую пару – вершину s и дугу 2(4). Дуга 2(4) позволяет вывести утверждение u и занести его в список установленных фактов (БД). Затем строим пару r,t,v и дугу 3(5). r – установленный факт, а построение вершин r и r,u и дуг 4(1) и 5(3) позволяет считать выведенными факты t, v и w. Однако утверждение х в правых частях продукций отсутствует. Поэтому продолжение вывода невозможно – возник тупик и данный вариант вывода оказался непродуктивным.

Используя стек возвратов, ищем другое правило для z. Это правило 9. Применив его, завершаем вывод. В таблице в правой части рисунка 2 содержатся списки установленных фактов (содержимое БД) после каждого шага вывода.