Аса, aacaa, caacaac, bcaacaacb, cbcaacaacbc.

Это пример прямой цепочки, поскольку с и каждая последующая сформированная строка сопоставляются с левой частью правила, а затем означивается правая часть правила.

Во-вторых, можно использовать этот же набор правил не для формирования, а для распознавания палиндромов. Мы уже видели ранее, что, задавшись некоторой строкой, например ЬасаЬ, можно проследить, в какой последовательности применялись правила при построении этой строки. Строка bасаb соответствует правой части правила Р2; можно сказать, что правая часть правила Р2 "допускает" строку bacab. Означенная левая часть правила Р2 — это строка аса, которая соответствует правой части правила PI, a означенная левая часть этого правила — аксиома с. Таким образом, процесс распознавания успешно завершился — мы доказали, что bacab представляет собой палиндром. Описанный процесс распознавания — это пример применения обратной цепочки рассуждений. Начальная строка bacab и каждая очередная подстрока анализируются на соответствие с правыми частями имеющихся правил, а результатом является означивание левой части выбранного правила. Если в качестве исходной мы зададимся строкой acbcb, то для нее не удастся найти в имеющемся наборе правил такое, правая часть которого "допускала" бы эту строку, а значит, исходная строка не может быть палиндромом.

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

В листинге 5.4 показана простая программа построения башни из блоков. Эта программа переключается между двумя задачами: выбором очередного блока и установкой блока в башню.

В разделе шаблонов блоки представлены объектами, обладающими такими свойствами, как цвет, размер и положение. Если положение блока не определено, предполагается, что он находится в куче блоков (heap), еще не уложенных в башню. Шаблон on предоставляет в наше распоряжение средство, позволяющее описать размещение блоков одного (upper) на другом (lower). Информацию о текущей фазе решения проблемы (поиск или установка) несет шаблон goal.

Листинг 5.4. Набор правил для построения башни из блоков

;; СТРАТЕГИЯ РАЗРЕШЕНИЯ КОНФЛИКТОВ

(declare (strategy mea))

;; Шаблоны

;; Объект block характеризуется цветом, размером и положением,

(deftemplate block

(field color (type SYMBOL))

(field size (type INTEGER))

(field place (type SYMBOL)))

;; Вектор 'on' указывает, что блок <upper>

;; находится на блоке <lower>. (deftemplate on

(field upper (type SYMBOL»

(field lower (type SYMBOL))

(field place (type SYMBOL) (default heap)])

;; Текущая цель (goal) может быть либо 'найти' (find),

;; либо 'уложить' (build), (deftemplate goal

(field task (type SYMBOL)))

;; ИНИЦИАЛИЗАЦИЯ

;; Имеются три блока разных цветов и размеров.

;; Предполагается, что они находятся в куче.

(deffacts the-facts

(block (color red) (size 10))

(block(color yellow) (size 20))

(block (color blue) (size 30))

)

;; ПРАВИЛА

;; Задать первую цель: найти первый блок,

(defrule begin

(initial-fact) =>

(assert (goal (task find))))

;; Взять самый большой блок в куче (heap),

(defrule pick-up

?my-goal <- (goal (task find))

?my-block <- (block (size?S1) (place heap))

(not (block (color?C2) (size?S2&:(>-?S2?S1))

(place heap))) =>

(modify?my-block (place hand))

(modify?my-goal (task build)))

;; Установить первый блок в основание башни (tower).

;; Этот блок не имеет под собой никакого другого,

(defrule place-first

?my-goal <- (goal (task build))

?my-block <- (block (place hand))

(not (block (place tower)))

=>

(modify?my-block (place tower))

(modify?my-goal (task find)))

;; Установить последующие блоки на тот,

;; что лежит в основании башни,

(defrule put-down

?my-goal <- (goal (task build))

?my-block <- (block (color?C0)

(place hand))

(block (color?C1) (place tower)))

(not (on (upper?C2) (lower?C1)

(place tower)))

=>

(modify?my-block (place tower))

(assert (on (upper?CO) (lower?C1)

(place tower)))

(modify?my-goal (task find)))

;; Если в куче больше нет блоков, прекратить процесс,

(defrule stop

?my-goal <- (goal (task find))

(not (block (place heap)))

=>

(retract?my-goal))

Обратите внимание на то, что порядок перечисления правил в программе не имеет значения. В программе управления роботом, представленной в листинге 5.3, правило прекращения выполнения стояло в списке первым, а в этой программе оно стоит в самом конце списка. Трассировку выполнения приведенной программы и некоторые комментарии вы найдете во врезке 5.4.