Введение в экспертные системы
Прямая и обратная цепочки рассуждений
5.3.2. Прямая и обратная цепочки рассуждений
На глобальном уровне управления последовательностью применения правил можно выделить две стратегии поведения — применять правила в прямом и обратном порядке. Прямой порядок означает, что цепь рассуждений строится, отталкиваясь от данных (условий, о которых известно, что они удовлетворяются), к гипотезам (состоянию проблемы, вытекающему из этих условий). Обратная цепочка означает, что рассуждения строятся, отталкиваясь от заданной цели (гипотезы, представляющие целевое состояние системы) к условиям, при которых возможно достижение этой цели. Здесь явно чувствуется аналогия с прямой и обратной стратегиями доказательства теорем (см. об этом в главе 8).
CLIPS представляет собой систему, в которой строится прямая цепочка рассуждений, а порождающие правила в системе MYCIN используются в большинстве случаев для построения обратной цепочки рассуждений, как было показано в главе 3. В CLIPS всегда сопоставляются состояние рабочей памяти и левые части правил, а затем выполняются действия, предусмотренные правой частью выбранного правила. А в MYCIN ведущей в рассуждениях является правая часть правила. Если мы задались целью установить природу некоторого микроорганизма, то отбираются все правила, в правой части которых дается соответствующее заключение, и затем анализируется, предпосылки какого из них удовлетворяются текущими данными.
Проще всего представить отличие между прямой и обратной цепочками рассуждений в терминах грамматических правил, аналогичных представленным в разделе 5.1. Как было показано, набор правил
(Р1) $ -> а$а
(Р2) $ -> b$b
(РЗ) $ -> с$с
Во-первых, их можно использовать для формирования палиндромов. Если задаться некоторым начальным символом из имеющегося алфавита, то любая последовательность применения правил приведет к формированию палиндрома. Так, применение правил Р1, Р1, РЗ, Р2, Р3 к исходному символу с приведет к формированию строк
аса, aacaa, caacaac, bcaacaacb, cbcaacaacbc.
Это пример прямой цепочки, поскольку с и каждая последующая сформированная строка сопоставляются с левой частью правила, а затем означивается правая часть правила.
Во-вторых, можно использовать этот же набор правил не для формирования, а для распознавания палиндромов. Мы уже видели ранее, что, задавшись некоторой строкой, например ЬасаЬ, можно проследить, в какой последовательности применялись правила при построении этой строки. Строка bасаb соответствует правой части правила Р2; можно сказать, что правая часть правила Р2 "допускает" строку bacab. Означенная левая часть правила Р2 — это строка аса, которая соответствует правой части правила PI, a означенная левая часть этого правила — аксиома с. Таким образом, процесс распознавания успешно завершился — мы доказали, что bacab представляет собой палиндром. Описанный процесс распознавания — это пример применения обратной цепочки рассуждений. Начальная строка bacab и каждая очередная подстрока анализируются на соответствие с правыми частями имеющихся правил, а результатом является означивание левой части выбранного правила. Если в качестве исходной мы зададимся строкой acbcb, то для нее не удастся найти в имеющемся наборе правил такое, правая часть которого "допускала" бы эту строку, а значит, исходная строка не может быть палиндромом.
В литературе по теории доказательства теорем прямая цепочка рассуждений, как правило, ассоциируется с "восходящим" процессом, т.е. рассуждениями от фактов к целям, а обратная цепочка — с "нисходящим" процессом, рассуждением от целей к фактам. Но, строго говоря, в отношении продукционных систем эти термины не являются синонимами. Например, вполне возможно реализовать нисходящий процесс в продукционной системе с прямой цепочкой рассуждений, если должным образом настроить локальный режим управления, например задать явное указание целей.
В листинге 5.4 показана простая программа построения башни из блоков. Эта программа переключается между двумя задачами: выбором очередного блока и установкой блока в башню.
В разделе шаблонов блоки представлены объектами, обладающими такими свойствами, как цвет, размер и положение. Если положение блока не определено, предполагается, что он находится в куче блоков (heap), еще не уложенных в башню. Шаблон on предоставляет в наше распоряжение средство, позволяющее описать размещение блоков одного (upper) на другом (lower). Информацию о текущей фазе решения проблемы (поиск или установка) несет шаблон goal.
