дб. Четвертое издание джозеф Джарратано Университет Хьюстон клиэрЛэйк Гари Райли People5oft, Издательский дом "Вильямс" Москва СанктПетербург Киев 2007 ббк 32. 973. 26 018 75 Д
 Скачать 3.73 Mb.
|
(export ?NONE) (export deftemplate ?ALL) (export deftemplate ?Применительно к конструкциям, которые рассматривались до сих пор в настоящей книге, этот формат совпадает с первым форматом. Аналогичным образом, четвертый формат позволяет указать, что никакие конструкции deftemplate не подлежат экспорту. Второй и четвертый форматы предусмотрены в основном для того, чтобы конструкции, экспортируемые некоторым модулем, могли быть явно заданы. Наконец, пятый формат позволяет задать конкретный список конструкций deftemplate, экспортируемых модулем. Атрибут export может быть задан больше одного раза в определении defmodule для указания экспортируемых конструкций различных типов, но до сих пор в качестве единственных экспортируемых конструкций мы рассматривали только конструкции deftemplate, поэтому не было необходимости использовать больше одного оператора с атрибутом export. Как показано ниже, атрибут import также может иметь пять допустимых форматов. (import (import (import (import (import deftemplate ?NONE) deftemplate предназначенный для экспорта, если не считать того, что сих помощью обеспечивается импорт указанных конструкций. Кроме того, должен быть указан модуль, из которого импортируются конструкции. Как и атрибут export., определение defmodule может иметь несколько атрибутов import. Прежде чем любая конструкция может быть задана в списке импорта, она должна быть определена, но такое требование, чтобы конструкция была определена, прежде чем ее можно будет указать в списке экспорта, не является обязательным (чтобы можно было поместить конструкцию в модуль, необходимо определить сам модуль, поэтому в действительности невозможно определить конструкцию до определения модуля, в котором она экспортируется. В связи с наличием этого ограничения невозможна такая ситуация, в которой два модуля взаимно импортируют конструкции, заданные в другом модуле (например, если модуль A импортирует конструкции из модуля В, то невозможно добиться того, чтобы модуль В импортировал конструкции из модуля А. В качестве иллюстрации импорта и экспорта фактов предположим, что в модуль RECOVERY необходимо импортировать конструкцию de f template с именем fault из модуля DETECTION, а из модуля ISOLATION конструкцию. Импорт и экспорт фактов 725 de f template с именем possible — failure. В отличие от других конструкций, конструкцию de fmodule невозможно переопределить после того, как она определена в программе. Таким образом, для того чтобы заменить атрибуты import и export конструкции необходимо вначале выполнить команду clear. Это ограничение распространяется на все модули, за исключением модуля который определяется заранее этот модуль может быть переопределен один раз для включения других атрибутов import и export (по умолчанию модуль MAIN ничего не экспортирует и не импортирует. Следует также отметить, что в применяемом по умолчанию определении модуля MAIN не экспортируется конструкция deftemplate с именем initial — fact. Как было указано в главе 8, при определенных обстоятельствах клевой части некоторых правил добавляется шаблон ( initial — fact ), в частности, это действие выполняется, если первым условным элементом правила является условный элемент not. Если такое правило помещается в модуль, в котором не импортируется конструкция deftemplate с именем initial — fact из модуля то это правило не может быть активизировано. Следует также отметить, что при определении такого правила не возникает даже ошибка, поскольку введение шаблона ( initial — вызывает создание подразумеваемой конструкции de f template с именем initial — fact в текущем модуле. Ниже приведены новые определения для модулей DETECTION, ISOLATION и наряду сих конструкциями deftemplate (все эти определения должны быть введены после выполнения команды clear). (defmodule DETECTION (export deftemplate fault)) (deftemplate DETECTION::fault (slot component)) (defmodule ISOLATION (export deftemplate possible-failure)) (deftemplate ISOLATION::possible-failure (slot component)) (deйтобы1е RECOVERY (import DETECTION deftemplate fault) (import ISOLATION deftemplate possible- failure)) Теперь, после того как определены конструкции de f module и de f template, появляется возможность вводить факты йап11 в списки фактов модулей и RECOVERY, а факты possible — failure — в списки фактов модулей RECOVERY и ISOLATION, как показано ниже (deffacts DETECTION::start (fault (component А) 726 Глава 9. Модульное проектирование, управление выполнением. CLIPS> (deffacts ISOLATION: 81аг1 (possible- failure (component B)))J CLIPS> (deffacts RECOVERY::start (fault (component С) (possible-failure (component D)))J CLIPS> (reset)J CLIPS> (facts DETECTION)J f — 0 (fault (component A)) f — 2 (fault (component С) For а total of 2 facts. CLIPS> (facts ISOLATION)J f — 1 (possible-failure (component В) f — 3 (possible-failure (component D)) For а total of 2 facts. CLIPS> (Хасае RECOVERY)J f — 0 (fault (component A)) f — 1 (possible- failure (component В) f — 2 (fault (component С) f — 3 (possible- failure (component D)) For а total of 4 facts. CLIPS> 9.8 Модули и управление выполнением программы Конструкция defmodule может использоваться не только для управления тем, какие конструкции de f template могут импортироваться и экспортироваться модулем, но и для управления исполнением правил. В языке CLIPS каждый определяемый модуль не получает лишь часть одного общего рабочего списка правила имеет свой собственный рабочий список правил. Благодаря этому появляется возможность управлять выполнением программы и принимать решение о том, в каком модуле должен быть выбран рабочий список правил для исполнения правил. Например, все следующие конструкции defrule должны быть Обратите внимание на то, что после вставки фактов fault в список фактов любого из модулей DETECTION и RECOVERY эти факты становятся видимыми в обоих модулях. Такой же принцип соблюдается и по отношению к фактам possible-failure, вставляемым в список фактов модулей RECOVERY и. Модули и управление выполнением программы активизированы с помощью фактов fault и possible — введенных в список фактов в предыдущем примере (defrule DETECTION::rule-1 (fault (component АС ВАС В D)) =>) Если бы после загрузки всех этих правил команда agenda была вызвана следующим образом, то отобразился бы рабочий список правил модуля поскольку последнее заданное правило было помещено в этот модуль CLIPS> (get-current-module)J RECOVERY CLIPS> (agenda)J 0 rule-3: f-O,f-3 0 rule-3: f-O,f-1 0 rule-3: f-2,f-3 0 rule-3: f- 2,f-1 For а total of 4 activations. CLIPS> Команда agenda, как и команды list — defrules и facts, принимает необязательный параметр, который в случае его определения отображает тот модуль, для которого должен быть выведен рабочий список правила 3 0 rule-2: f-1 For а total of 2 activations. CLIPS> (agenda RECOVERY)J 0 rule-3: f-O,f-3 0 rule-3: f-O,f-1 0 rule-3: f-2,f-3 728 Глава 9. Модульное проектирование, управление выполнением. О rule-3: For а total of 4 CLIPS> (agenda *) MAIN: f — 2,f — 1 activations. DETECTION: ООО ООО ООО а total of 8 CLIPS> f-3 О, f — 3 О, f — 1 f- 2, f-3 f-2, f — 1 activations ° Команда focus Итак, теперь все правила распределены потрем отдельным рабочим спискам правил. Что же произойдет после выдачи команды run таким образом CLIPS> (unwatch all)J CLIPS> (watch rules)J CLIPS> (run)J CLIPS> (focus запускается Дело в том, что в системе CLIPS сопровождается не только информация о текущем модуле, который используется для определения того, в какие списки должны вводиться новые конструкции и какие конструкции применяются или подвергаются воздействию командно и текущий фокус, который определяет, какой рабочий список правил должен использоваться вовремя выполнения команды run. Команды reset и clear автоматически переводят текущий фокус на модуль MAIN. А после смены текущего модуля текущий фокус не изменяется. Таким образом, по условиям рассматриваемого примера после выдачи команды run для выбора правил, подлежащих исполнению, применяется рабочий список правил, связанный с модулем MAIN. Тем не менее этот рабочий список правил пуст, поэтому запуск правил не происходит. Для смены текущего фокуса используется команда focus. Команда focus имеет следующий синтаксис. Модули и управление выполнением программы 729 В том простом случае, когда в этой команде задается только одно имя модуля, текущий фокус устанавливается на указанный модуль. После переустановки текущего фокуса в модуль DETECTION и выдачи команды run происходит запуск правил из рабочего списка правил модуля DETECTION: CLIPS> (focus DETECTION) J TRUE CLIPS> (run)J FIRE 1 rule — 1: f — 2 FIRE CLIPS> 2 rule — 1: О При использовании команды focus не только происходит смена текущего фокуса, но и возвращается предыдущее значение текущего фокуса. Текущий фокус в действительности является верхним значением структуры в стековой структуре данных, называемой стеком фокусов. После каждой смены текущего фокуса с помощью команды focus фактически новый текущий фокус задвигается в верхнюю часть стека фокусов, смещая вниз все предыдущие текущие фокусы. А после того как в результате исполнения всех правил рабочий список правил модуля, находящегося в текущем фокусе, становится пустым, текущий фокус выталкивается (удаляется) из стека фокусов, и текущим фокусом становится следующий модуль. Затем исполняются правила из рабочего списка правил нового текущего фокуса до тех пор, пока фокус не перейдет на новый модуль или в рабочем списке правил текущего модуля больше не останется правил. Правила продолжают исполняться до тех пор, пока в стеке фокусов не остается больше модулей или не вызывается команда halt. Продолжая рассматриваемый пример, укажем, что если вначале фокус будет переведен на модуль ISOLATION, а затем на модуль RECOVERY, то это вызовет запуск всех правил из рабочего списка правил модуля, аза этим последует запуск правил из рабочего списка правил модуля ISOLATION. Для отображения перечня модулей, находящихся в стеке фокусов, применяется команда list4îmÿ-stack (которая не принимает параметров CLIPS> (focus ISOLATION)J TRUE CLIPS> (focus RECOVERY)J TRUE CLIPS> (list-focus-stack)J RECOVERY ISOLATION 730 Глава 9. Модульное проектирование, управление выполнением. (run) ! 1 rule-3: f-l,f-4 2 rule — 3: f— - 1,f — 2 3 rule-3: f-3, f-4 4 rule — 3: f— - З — 2 5 rule-2: f-4 б rule-2: f — 2 (list-focus-stack)J CLIPS> FIRE FIRE FIRE FIRE FIRE FIRE CLIPS> CLIPS> Следует отметить, что один и тот же модуль может быть представлен в стеке фокусов больше одного раза, но перевод фокуса на модуль, который уже находится в текущем фокусе, не приводит к получению каких-либо результатов. Манипулирование стеком фокусов и его изучение В языке предусмотрено несколько команд и функций для манипулирования текущим фокусом и стеком фокусов. Команда clear-focus-stack позволяет Использование двух команд позволяющих задвинуть в стек фокусов модули ISOLATION и, вызовет то, что правила RECOVERY будут исполняться прежде, чем правила ISOLATION. Но предусмотрена также возможность задать водной команде focus сразу несколько модулей в таком случае модули задвигаются в стек фокусов справа налево, например, как показано ниже (focus ISOLATION RECOVERY)J TRUE CLIPS> (list-focus- stack) J ISOLATION RECOVERY CLIPS> (focus ISOLATION)J TRUE CLIPS> (list-focus-stack) J ISOLATION RECOVERY CLIPS> (focus RECOVERY)J TRUE CLIPS> (list-focus-stack)J RECOVERY ISOLATION RECOVERY CLIPS> 9.8. Модули и управление выполнением программы удалить все модули из стека фокусов. Функция get-focus возвращает имя модуля, находящегося в текущем фокусе, или символ если стек фокусов пуст. Функция pop-focus удаляет текущий фокус из стека фокусов (и возвращает имя модуля, который был в текущем фокусе, или символ FALSE, если стек фокусов пуст). Функция деМоспя-stack возвращает многозначное значение, содержащее имена модулей, находящихся в стеке фокусов. Примеры применения этих команд и функций приведены ниже (get-focus-stack)J (RECOVERY ISOLATION RECOVERY) CLIPS> (get-focus)J RECOVERY CLIPS> (рор-focus)J RECOVERY CLIPS> (clear-focus-stack)J CLIPS> (get-focus-stack)J () CLIPS> (get-focus)J FALSE CLIPS> (рор-focus)J FALSE CLIPS> Для контроля над изменениями в стеке фокусов может использоваться команда watch, в вызове которой в качестве параметра применяется ключевое слово focus: CLIPS> (watch focus) J CLIPS> (focus DETECTION ISOLATION RECOVERY)J > Focus RECOVERY > Focus ISOLATION from RECOVERY > Focus DETECTION from ISOLATION TRUE CLIPS> (run)J < Focus DETECTION to ISOLATION <- Focus ISOLATION to RECOVERY < Focus RECOVERY CLIPS> 732 Глава 9. Модульное проектирование, управление выполнением. В рабочем списке правил имеется правило example-2, нов стеке фокусов отсутствуют какие-либо модули. А после выдачи команды run в стек фокусов помещается модуль МАХИ, поэтому так или иначе появляется возможность запуска правила example — 2: CLIPS> (гшь) — > Focus MAIN FIRE 1 example2: f 0 с Focus MAIN CLIPS> Команда return Один из недостатков способа управления потоком выполнения с использованием управляющих фактов для представления фаз, который описан в разделе 9.4, состоит в том, что он не позволяет выполнить запуск некоторых активизированных правил в конкретной фазе, выйти из этой фазы, а затем еще развернуться в туже фазу и исполнить остальные активизированные правила из рабочего списка правил. Это происходит потому, что после извлечения управляющего факта, В том случае, если выдана команда run, а стек фокусов пуст, в стек фокусов автоматически задвигается модуль MAIN. Такая возможность предусмотрена в основном для удобства, на тот случай, что ко времени завершения программы добавляются новые активизации, а в стеке фокусов не остается больше модулей, например, как показано ниже. CLIPS> (clear)J CLIPS> (watch focus)J CLIPS> (watch rules)J CLIPS> (defrule ezample-1 >)J CLIPS> (reset) J с Focus MAIN — > Focus MAIN CLIPS> (run) J FIRE 1 example-1: f-0 с Focus MAIN CLIPS> (defrule ezample-2 >)J CLIPS> (agenda)J 0 example-2: f-0 For а total of 1 activation. CLIPS> (list- focus-stack) J CLIPS> 9.8. Модули и управление выполнением программы 733 который представляет данную фазу, из рабочего списка правил удаляются все активизированные правила, относящиеся к соответствующей фазе. А после того как в дальнейшем в список фактов вновь будет вставлен управляющий факт, повторно активизируются все ранее активизированные правила, относящиеся к данной фазе, а не только те правила, которые небыли запущены (разумеется, это происходит лишь притом условии, что вставляется или удаляется только управляющий факт, ноне какие-либо другие факты. Если для управления потоком выполнения используются модули, то появляется возможность преждевременно прекратить исполнение активизированных правил из рабочего списка правил определенного модуля (в данном случае преждевременно означает — до того, как рабочий список правил модуля станет пустым. Для немедленного прекращения выполнения правой части правила и удаления текущего фокуса из стека фокусов (и передачи управления над выполнением правил в следующий модуль в стеке фокусов) может применяться команда return. В команду return при ее использовании в правой части правила не должны передаваться параметры (команда return может также применяться в конструкциях процедурного программирования, предусмотренных в языке CLIPS). Использование команды return иллюстрируется в следующем примере CLIPS> (clear)J CLIPS> (defmodule MAIN (export deftemplate initial-fact))J CLIPS> (defmodule DETECTION (import MAIN deftemplate initial-fact))J CLIPS> (defrule MAIN::start (focus DETECTION))J CLIPS> (defrule DETECTION::example-1 ф (return) (printout t "No printout!" crlf))J CLIPS> (defrule DETECTION::example-2 > (return) (printout t "No printout!" crlf))J CLIPS> (watch rules)J 734 Глава 9. Модульное проектирование, управление выполнением. CLIPS> (watch focus)J CLIPS> (reset 1 < Focus MAIN — > Focus MAIN CLIPS> (run)J FIRE 1 start: f-0 — > Focus DETECTION from MAIN FIRE 2 example-1: f-0 < Focus DETECTION to MAIN < Focus MAIN CLIPS> Средство auto- В языке CLIPS не только предоставляется возможность явно переводить фокус нате или иные модули с помощью команды focus, но и обеспечивается автоматический перевод фокуса на конкретный модуль при активизации конкретных правил из этого модуля. По умолчанию на модуль правила при активизации этого правила фокус автоматически не переводится. Такое положение дел можно изменить с использованием атрибута auto-f0ñïÿ. Атрибут auto — Гостя должен быть задан в операторе declare наряду с атрибутом salience. В этом случае задается ключевое слово auto — focus, за которым следует либо символ (который позволяет разрешить средство auto-focus), либо символ FALSE (запрещающий это средство. Для обеспечения использования средства auto — focus в некоторых правилах модуля необязательно, чтобы это средство В этом примере заслуживают внимания две важные особенности. Во-первых, активизация правил в модуле DETECTION с использованием заданного по умолчанию шаблона initial — fact становится возможной, только если конструкция deftemplate с именем initial — fact будет экспортирована модулем MAIN и импортирована модулем DETECTION. Во-вторых, важно то, что команда return немедленно останавливает выполнение правой части правила. Об этом свидетельствует то, что в правиле example — 1 не выполняется команда printout, которая следует за командой return (тоже касается правила example — 2, поскольку это правило не получает возможности запуска. Следует отметить, что по своим функциональным возможностям команда return аналогична, ноне идентична команде pop-focus, поскольку последняя удаляет текущий фокус из стека фокусов, но допускает продолжение выполнения действий в правой части правила. Если бы в рассматриваемом примере вместо команды return использовалась команда pop-focus, то вовремя выполнения действий правила example — 1 на внешнее устройство была бы выведена строка "No printout!". 735 9.8. Модули и управление выполнением программы было разрешено для всех правил модуля. Аналогичным образом, если для правила применяется оператор declare, необязательно объявлять и атрибут salience, и атрибут auto — Использование средства auto- focus иллюстрируется в следующем примере CLIPS> (clear)J CLIPS> (defmodule MAIN (export deftemplate initial-fact))J CLIPS> (defmodule DETECTION (import MAIN deftemplate initial-fact))J CLIPS> (defrule DETECTION::example (declare (auto-focus TRUE)) ;)) ] CLIPS> (watch focus)J CLIPS> (reset)J < Focus MAIN > Focus MAIN > Focus DETECTION from MAIN CLIPS> После выдачи команды reset фокус автоматически переводится на модуль поскольку стек фокусов пуст. Затем в результате ввода факта initial— fact в список фактов активизируется правило Поскольку для этого правила разрешен атрибут auto — focus, тов стек фокусов автоматически задвигается модуль этого правила модуль DETECTION. Средство auto — focus особенно удобно при использовании правил, которые обнаруживают нарушения ограничений. Оно позволяет немедленно перевести текущий фокус на модуль ограничивающего правила и поэтому дает возможность предпринять необходимые действия сразу после обнаружения соответствующего нарушения. При этом отсутствует необходимость явно предусматривать отдельную фазу, на которой обнаруживались бы нарушения. Отказ от фаз и управляющих фактов Благодаря использованию конструкций de fmodule, команд focus и return, а также средства auto — focus появилась возможность отказаться от применения фаз и управляющих фактов и создать гораздо более явно выраженный механизм управления потоком выполнения правил. В таком случае вместо описанных враз Глава 9. Модульное проектирование, управление выполнением. деле 9.4 конструкций, применяемых для управления выполнением, могут использоваться следующие конструкции (defmodule DETECTION) (defmodule ISOLATION) (defmodule RECOVERY) (deffacts MAIN::control-information (phase-sequence DETECTION ISOLATION RECOVERY)) (defrule MAIN::change-phase ?list <- (phase-sequence ?next-phase $?other- phases) — > (focus ?next-phase) (retract ?list) (assert (phase- sequence ?other-phases ?next-phase))) Управление выполнением передается по циклу от модуля DETECTION к модулю, затем к модулю RECOVERY и возвращается в начало. Происходит запуск всех правил каждого модуля, прежде чем появляется возможность запуска правил в следующем модуле (при условии, что не выдается команда return или фокус не переходит на новый модуль в результате применения средства auto — Гостя, как показано ниже. CLIPS> (unwatch all)J CLIPS> (reset)J CLIPS> (watch rules)J CLIPS> (watch focus)J CLIPS> (run 5) 1 FIRE 1 change-phase: f-1 > Focus DETECTION from MAIN < Focus DETECTION to MAIN FIRE 2 change-phase: f-2 > Focus ISOLATION from MAIN < Focus ISOLATION to MAIN FIRE 3 change-phase: f-3 > Focus RECOVERY from MAIN < Focus RECOVERY to MAIN FIRE 4 change-phase: f-4 > Focus DETECTION from MAIN < Focus DETECTION to MAIN 9.9. алгоритм сопоставления с шаблонами 737 FIRE 5 change-phase: f-5 > Focus ISOLATION from МАХИ ( Focus ISOLATION to MAIN CLIPS> 9.9 алгоритм сопоставления с шаблонами В таких языках, основанных на правилах, как CLIPS, Jess, Eclipse и OPS5, используется очень эффективный алгоритм сопоставления фактов с шаблонами правили определения того, условия каких правил удовлетворены. Этот алгоритм называется алгоритмом сопоставления с шаблонами [12], [27], [28]. Для написания эффективных правил на языке CLIPS не требуется понимание работы rete-алгоритма. Тем не менее понимание основополагающих алгоритмов, образующих фундамент языка CLIPS и других языков, основанных на правилах, позволяет разобраться в том, почему правила, написанные водной форме, являются более эффективными, чем написанные в другой форме. Чтобы разобраться в том, почему алгоритм является таким эффективным, целесообразно рассмотреть проблему согласования фактов с правилами в целом, а затем ознакомиться с другими алгоритмами, которые не являются столь же эффективными. На рис. 9.6 показано, какую задачу решает алгоритм. Рис. 9.6. Сопоставление с шаблонами правила и факты Если бы процесс согласования должен был произойти только один раз, то решение задачи согласования было бы несложным. Машина логического вывода может исследовать каждое правило, а затем выполнить поиск во множестве 738 Глава 9. Модульное проектирование, управление выполнением. Рис. 9.7. Принцип поиска фактов удовлетворяющих правилам Тем не менее в языках, основанных на правилах, процесс согласования должен осуществляться неоднократно. Обычно состав списка фактов изменяется вовремя каждого цикла выполнения. При этом в список фактов могут быть добавлены новые факты или из этого списка могут быть удалены старые факты. Может оказаться, что в результате таких изменений станут удовлетворяться те шаблоны, проверка условий которых перед этим оканчивалась неудачей, или наоборот. Теперь процесс решения задачи согласования становится осуществляемым неоднократно. При этом вовремя каждого цикла приходится сопровождать и обновлять множество правил, проверка условий которых завершена успешно, в связи с добавлением и удалением фактов. Простой и незамысловатый метод решения указанной проблемы мог бы состоять в обеспечении того, чтобы машина логического вывода проверяла каждое правило, позволяя снова осуществить поиск фактов, после каждого цикла выполнения. Но основным недостатком такого подхода является то, что он может показывать очень низкое быстродействие. В большинстве экспертных систем, основанных на правилах, обнаруживается свойство, называемое временной избыточностью. Это свойство заключается в том, что обычно в результате выполнения действий любого правила изменяется лишь немного фактов в списке фактов. Иными словами, состав фактов в экспертной системе изменяется со временем довольно медленно. Может оказаться, что в каждом цикле выполнения добавляется фактов, чтобы определить, удовлетворяются ли шаблоны данного правила. Если проверка условий, заданных шаблонами правила, завершается успешно, то правило можно поместить в рабочий список правил. Этот подход показан на рис. 9.7. 9.9. алгоритм сопоставления с шаблонами 739 или удаляется лишь небольшая процентная доля фактов, и поэтому изменения в списке фактов обычно затрагивают лишь небольшую процентную долю правил. Иначе говоря, подход требующий повторного просмотра всех правил для поиска необходимых фактов, связан с использованием большого объема ненужных вычислений, поскольку с наибольшей вероятностью для большинства правил в текущем цикле будут найдены те же факты, что ив предыдущем цикле. Причины неэффективности этого подхода иллюстрируются на рис. Затененная область представляет те изменения, которые произошли в списке фактов. Ненужных повторных вычислений можно избежать, передавая результаты уже выполненных согласований из одного цикла в другой, а затем проводя только применительно к изменениям вычисления, необходимые в связи с наличием вновь добавленных или вновь удаленных фактов (рис. 9.9). Правила остаются неизменными, изменяется только состав фактов, поэтому не правила должны применяться для поиска фактов, а факты — для поиска правил. Рис. Ненужные вычисления, осуществляемые при использовании правил для поиска фактов алгоритм сопоставления с шаблонами позволяет воспользоваться свойством временной избыточности, которым обладают экспертные системы, основанные на правилах. В алгоритме такая цель достигается за счет сохранения состояния процесса согласования от цикла к циклу, а затем проведения повторных вычислений в связи с изменениями в этом состоянии, с учетом только тех изменений, которые произошли в списке фактов. Иначе говоря, если водном цикле обнаружены два из трех необходимых фактов для множества шаблонов, тона следующем цикле нет необходимости выполнять проверку для тех двух фактов, которые уже были найдены, поскольку теперь интерес представляет только тре- Глава 9. Модульное проектирование, управление выполнением. 740 Рис. 9.9. Применение подхода, в котором факты служат для поиска правил тий факт. Состояние процесса согласования модифицируется лишь в результате добавления и удаления фактов. Это означает, что если количество добавляемых и удаляемых фактов невелико по сравнению с общим количеством фактов и шаблонов, то процесс согласования протекает очень быстро. В наихудшем случае, если происходят изменения во всех фактах, то процесс согласования действует так, как если бы все факты должны быть сопоставлены со всеми шаблонами. При использовании подхода, в котором обрабатываются только обновления в списке фактов, необходимо предусмотреть хранение в памяти информации о том, какие сопоставления фактов с шаблонами уже были выполнены успешно в каждом правиле. Иными словами, если окажется, что новый факт согласуется с третьим шаблоном правила, то информация о сопоставлениях, относящаяся к первым двум шаблонам, должна быть доступной, чтобы можно было завершить процесс согласования. Информация о состоянии такого типа, которая указывает на факты, сопоставленные ранее с шаблонами правила, называется частичным соответствием. Частичным соответствием для правила является любое множество фактов, которые были успешно сопоставлены с шаблонами правила, начиная с первого шаблона правила и заканчивая любым другим шаблоном, включая последний. Таким образом, правило стремя шаблонами может иметь частичное соответствие с первым шаблоном, с первыми вторым шаблонами, а также с первым, вторыми третьим шаблонами. Частичное соответствие со всеми шаблонами правила становится также активизацией правила. Еще одним типом хранимой информации о состоянии является так называемое сопоставление с шаблонами. Сопоставление с шаблоном возникает, если факт удовлетворяет единственному. Сеть шаблонов 741 9.10 Сеть шаблонов Процесс согласования фактов с шаблонами правил можно разделить на два этапа. Во-первых, после добавления и удаления фактов необходимо определить, с какими шаблонами должно быть выполнено сопоставление. Во-вторых, необходимо провести сравнение связываний переменных в различных шаблонах, чтобы определить частичные соответствия для группы шаблонов. Процесс определения того, какие факты согласуются с шаблонами, осуществляется в сети шаблонов. В целях сокращения изложения ограничимся описанием процесса сопоставления с шаблонами в однозначных слотах фактов de f template. Все операции согласования, в которых не участвуют операции сравнения с переменными, связанными в других шаблонах, могут быть выполнены в сети шаблонов. Сеть шаблонов имеет структуру, подобную дереву, в котором ограничениями первого слота всех шаблонов являются узлы, соединенные с корнем дерева, ограничениями второго слота всех шаблонов — узлы, соединенные с этими узлами, и т.д. Ограничениями последнего слота в шаблоне являются листовые узлы дерева. Узлы в сети шаблонов называются одновходовыми узлами, поскольку каждый из них получает информацию только из узла, находящегося над ним. Узлы в сети шаблонов иногда называют также узлами шаблонов, а листовые шаблону любого правила и рассматривается без учета того, что переменные других шаблонов могут ограничивать процесс согласования. Основной недостаток алгоритма сопоставления с шаблонами состоит в том, что этот алгоритм требует большого объема памяти. Если осуществляется сравнение всех фактов со всеми шаблонами, то память не требуется. Если же приходится хранить информацию о состоянии системы, представленную в виде результатов сопоставлений с шаблонами и частичных соответствий, то потребность в памяти становится существенной. Вообще говоря, чем больший объем памяти занимает заранее подготовленная информация, тем выше быстродействие, но объем потребляемой памяти невозможно увеличивать до бесконечности, поэтому приходится искать компромиссный вариант. Тем не менее важно помнить, что плохо написанные правила не только работают медленно, но и расходуют значительный объем памяти. алгоритм позволяет также повысить эффективность систем, основанных на правилах, благодаря тому, что в нем используется свойство структурного подобия правил. Структурное подобие часто характеризуется тем, что во многих правилах содержатся одинаковые шаблоны или группы шаблонов. Это свойство используется в алгоритме для повышения эффективности по такому принципу, что одинаковые компоненты объединяются в пулы для того, чтобы вычисления значений этих компонентов не приходилось проводить больше одного раза Глава 9. Модульное проектирование, управление выполнением. узлы — терминальными узлами. Каждый узел шаблона содержит спецификацию, используемую для определения того, согласовано ли значение слота факта с ограничением слота некоторого шаблона. Например, следующий шаблон был бы представлен только одним узлом, поскольку в нем имеется лишь одно ограничение слота (data (x 27)) В таком случае спецификация согласования для первого узла была бы выражена следующим образом The slot x value is equal to the constant 27 В действительности необходимо также проверить, правильно ли определено то, что факт имеет имя отношения, соответствующее данному шаблону (например, нельзя допускать, чтобы факты f oobar согласовывались с шаблонами data лишь потому, что в них имеются те же имена слотов. В системе CLIPS для проведения такой проверки сопровождается отдельная сеть шаблонов для каждой конструкции de f чтобы можно было выполнять проверку имени отношения ко времени создания факта, но до проведения сопоставления с шаблонами. Спецификации согласования включают всю информацию, необходимую для согласования отдельного слота. Несколько проверок могут проводиться одновременно. Например, такой шаблон (data (х -red&-green)) может применяться для выработки следующей спецификации согласования для слотах Обычно в сети шаблонов связывание переменных проверяется, только если переменная используется в шаблоне больше одного раза. Например, применение показанного ниже шаблона не приводит к формированию спецификаций согласования ни для слотах, ни для слота у, поскольку первое связывание переменной со значением слота не влияет на то, будет ли успешно выполнено согласование шаблона с фактом. (data (х х) (у у) (z ?x)) Но слот должен иметь такое же значение, как и слот х, поэтому спецификация согласования для слота z должна быть следующей The z slot value is equal to the x slot value В сети шаблонов могут быть проверены такие выражения, которые содержат переменные, полностью находящиеся внутри шаблона. Например, использование приведенного ниже шаблона не приведет к формированию спецификации. Сеть шаблонов 743 согласования для слотах, поскольку переменная у не содержится в шаблоне (разумеется, применение такого шаблона возможно, только если переменная ?у определена водном из предыдущих шаблонов. (data (х х х у) Тем не менее слот х в следующем шаблоне (data (х х х 4))) имел бы показанную ниже спецификацию согласования, поскольку единственная переменная, находящаяся в выражении х, содержится также в данном шаблоне. The x slot value is greater than the constant 4 Как уже было сказано выше, сеть шаблонов имеет иерархическую организацию, в которой узлы шаблона, соответствующие ограничениям первого слота шаблонов, находятся в верхней части. После внесения любого факта в список фактов проверяются узлы шаблонов для поиска ограничений первого слота в сети шаблонов. Любой узел шаблона, для которого проверка спецификации согласования завершается успешно, активизирует находящиеся непосредственно под ним узлы шаблонов. Этот процесс продолжается до тех пор, пока не достигаются терминальные узлы в сети шаблонов. Достижение терминальных узлов в сети шаблонов соответствует окончанию проверки шаблона и успешному согласованию шаблона. С каждым терминальным узлом связана альфа-память, или правая часть памяти. Альфа-память содержит множество всех фактов, согласованных с шаблоном, который ассоциирован сданным терминальным узлом. Иными словами, альфа- память хранит множество сопоставлений с шаблоном для конкретного шаблона. В сети шаблонов используется преимущество структурного подобия, поскольку общие узлы шаблонов применяются совместно в разных шаблонах. Дело в том, что хранение узлов шаблонов организовано иерархически, поэтому два шаблона могут совместно использовать свои первые узлов шаблонов, если спецификации согласования для их первых N ограничений слота являются идентичными. Например, следующие шаблоны могут совместно использовать общие узлы шаблонов для слотах (х red) уху) Обратите внимание на то, что идентичными должны быть спецификации согласования, ноне обязательно ограничения слота, находящиеся в шаблоне. Например, в приведенных ниже шаблонах может совместно использоваться узел шаблона для слота у, даже несмотря на то, что переменные, применяемые в этих двух шаблонах, являются разными. (data (х х) (ух) (х у) (у у Глава 9. Модульное проектирование, управление выполнением. 744 Для слотов хне формируется спецификация согласования и поэтому они игнорируются сточки зрения обеспечения совместного использования. Тем не менее изменение порядка следования слотов на противоположный привело бык тому, что в шаблонах нельзя было совместно использовать узлы, поскольку первый шаблон формировал бы спецификацию согласования для слота у, а второй шаблон— спецификацию согласования для слотах, как показано ниже (х х) уху уху) На рис. 9.10 показана сеть шаблонов, сформированная с приведенными ниже правилами. Сеть шаблонов данных Сеть шаблонов согласования Рис. Сеть шаблонов для двух правилах х) уха х) (b red)) (data (х -green) ух (х х) ух Сеть соединений После определения того, какие шаблоны согласованы с фактами, необходимо проверить результаты сравнения связываний переменных в различных шаблонах, чтобы убедиться в том, что переменные, используемые более чем водном Л. Сеть соединений 745 шаблоне, имеют совместимые значения. Такое сравнение выполняется в сети соединений. Каждый терминальный узел в сети шаблонов действует в качестве входа в узел соединения, или в двухвходовой узел сети соединений. Каждое соединение содержит спецификацию согласования для согласований в альфа-памяти, ассоциированной с этим терминальным узлом, и для множества частичных соответствий, которое было согласовано с предыдущими шаблонами. Частичные соответствия для предыдущих шаблонов хранятся в бета-памяти, или в левой части памяти соединения. Таким образом, для правила с шаблонами требуется N-1 соединение (нов системе CLIPS для упрощения алгоритма фактически используется всего соединений, что позволяет вводить в действие каждое соединение только с помощью одного шаблона. В первом соединении сравниваются первые два шаблона, а в оставшихся соединениях сравнивается шаблон, дополнительный по отношению к частичным соответствиям предыдущего соединения. Например, если дано такое правило Rete — используемое в приведенном выше примере (defrule Rete — rule 2 (match ах (х -green) ух (х х) ух) то первое соединение должно содержать следующую спецификацию согласования а slot value of the fact bound to the first pattern is equal to the y slot value of the fact bound to the second pattern. В таком случае во втором соединении было бы получено в качестве входных данных множество частичных соответствий из первого соединения, поэтому второе соединение содержало бы следующую спецификацию согласования The x slot value of the fact bound to the third pattern is equal to the y slot value of the fact bound to the second Обратите внимание на то, что можно было бы сравнить значение переменной х в третьем шаблоне со значением переменной х в первом шаблоне, а нес переменной х во втором шаблоне. Второе вхождение переменной х в третьем шаблоне в этой сети соединений проверять не требуется, поскольку ее значение можно проверить в сети шаблонов. Сети шаблонов и соединений для правила Rete — rule-2 показаны на рис. 9.11. Глава 9. Модульное проектирование, управление выполнением. 746 Сеть шаблонов Сеть шаблонов согласования Сеть шаблонов данных Шаблон сопоставлен Шаблон сопоставлен Шаблон сопоставлен Значение слота а факта, связанного со вторым шаблоном, равно слотуу факта, связанного с первым шаблоном Значение слотах факта, связанного со вторым шаблоном, равно слотуу факта, связанного с третьим шаблоном Сеть соединений Активизировано Рис. 9.11. Сети шаблонов и соединений для правила Rete-rule-2 (defrule sharing-1 (match ах) В сети соединений можно воспользоваться преимуществом структурного подобия для совместного использования соединений в различных правилах. Соединения в сети соединений могут совместно использоваться в двух правилах, если они имеют идентичные шаблоны и результаты сравнения соединений для двух или нескольких шаблонов, начиная с первого шаблона. Например, в приведенных ниже правилах можно было совместно использовать все их шаблоны в сети шаблонов, а также соединения, созданные для их первых трех шаблонов в сети соединений. Сеть соединений 747 (data (х -green) ух (х х) уха уху уху) (у у) (other (q у) =>) Но соединение для четвертого шаблона нельзя совместно использовать в сети соединений, поскольку спецификации согласования для двух рассматриваемых правил являются разными. В спецификации согласования для четвертого шаблона правила sharing — 1 не требуется выполнять какие-либо сравнения, поскольку переменная ? z не применяется в других шаблонах. Нов спецификации согласования для четвертого шаблона правила sharing — 2 необходимо предусмотреть сравнение переменной ус переменной ? у другого шаблона для обеспечения того, чтобы связывания этих переменных являлись совместимыми. Еще раз отметим, что для использования преимущества структурного подобия не требуется, чтобы имена переменных были идентичными. Имеет значение лишь то, являются ли идентичными спецификации согласования. После выдачи команды watch compilations система CLIPS предоставляет полезную информацию о совместном использовании соединений. Например, ниже приведены команды, которые показывают, как отображается информация о совместном использовании соединений. В данном случае предполагается, что правила sharing — 1 и sharing — 2 хранятся в файле "rules clp". CLIPS> (watch compilations)J CLIPS> (load "rules.clp")J Defining бей sharing — 1 +j+j+j+j Пей й sharing — 2 =j=j=j+j TRUE CLIPS> Знаки +j в этом выводе указывают, что добавляется некоторое соединение, а знаки =j говорят о том, что соединение используется совместно. Таким образом, после введения правила sharing — 1 создаются четыре новых соединения. С другой стороны, после введения правила sharing — 2 в нем совместно с правилом sharing — 1 используются первые три соединения, а для последнего шаблона создается новое соединение. Обратите внимание на то, что в системе для представления данного правила использовались четыре соединения, а не три, что Глава 9. Модульное проектирование, управление выполнением. 9.12 Важность правильного выбора порядка расположения шаблонов Программисты, впервые осваивающие языки, основанные на правилах, часто не представляют себе, насколько важно добиться должного упорядочения шаблонов в правилах сточки зрения быстродействия и эффективного использования памяти. Поскольку алгоритм предусматривает сохранение информации о состоянии от одного цикла к другому, очень важно добиться того, чтобы правила не вырабатывали большого количества частичных соответствий. Например, рассмотрим следующую простую программу (deffacts information (find-match асе асе х уху х у ?z ?w))) Сброс этой программы (переустановка в исходное состояние) происходит очень быстро. В этом позволяет убедиться команда watch йасз, которая непосредственно следует за командой reset. А теперь рассмотрим следующую программу (deffacts information (find- match асе а) потребовалось бы при обычных обстоятельствах. В целях упрощения реализации удобнее иметь только по одному шаблону в расчете на каждое соединение, поэто- му вместо применения одного соединения для первых двух шаблонов в системе CLIPS используется два соединения. Важность правильного выбора порядка расположения шаблонов 749 (item b) (item се х) (item уху х у ?z ?w))) Команда Гася, которая следует за командой reset, при выполнении данной программы демонстрирует значительное увеличение продолжительности сброса. По мере выполнения сброса быстро происходит внесение первых нескольких фактов из конструкции de f f acts в список фактов. Но для внесения последующих фактов в список фактов требуется все более и более продолжительное время. И правило match — 1, и правило match — 2 имеют одинаковые шаблоны, но сброс правила match — 2 занимает гораздо больше времени. А в действительности на некоторых компьютерах выполнение сброса правила match — может вызвать то, что система CLIPS исчерпает доступную память. Еще более значительное различие в быстродействии может быть продемонстрировано путем добавления большего количества фактов item в конструкцию de f f acts с именем information (а на некоторых компьютерах нельзя будет обнаружить заметного различия, не введя дополнительные факты item в конструкцию def facts с именем information). Учет характеристик правила match-1 Полезная информация может быть получена с помощью подсчета количества сопоставлений с шаблонами и частичных соответствий для правила match-1. Для иллюстрации выполняемых при этом действий в данном и следующих разделах используются листинги согласований с шаблонами и частичных соответствий. Для удобства чтения в этих листингах вместо полного текста всего факта применяются идентификаторы фактов. Кроме того, частичные соответствия обозначаются фигурными скобками. Идентификаторы фактов показаны в следующем списке f-1 (find-match асе а (item b) 750 Глава 9. Модульное проектирование, управление выполнением. f-4 (item с) f-5 (item d) бед) Правило match — 1 имеет такие сопоставления с шаблонами 1 f — 1 2: 3: 4 ° 5: Правило match — 1 имеет следующие частичные соответствия Pattern 1: [f-1] Patterns 1-2: [f-1, f-2] Patterns 1-3: [f-l,f-2,f-4] Patterns 1-4: [f-1, f-2, f-4, б 1-5: [f-1, f-2, f-4, б, f-8] В целом правило match — имеет 29 сопоставлений с шаблонами и 5 частичных соответствий. Учет характеристик правила match-2 Правило match — 2 имеет следующие сопоставления с шаблонами 2: 3: 4: 5: Правила match — 1 и match — 2 имеют одинаковое количество сопоставлений с шаблонами. А теперь рассмотрим только частичные соответствия для шаблона 1: й Шаблон 1 имеет семь частичных соответствий, и это неудивительно, поскольку для первого шаблона частичные соответствия и сопоставления с шаблонами должны быть одинаковыми. Но, как показано ниже, количество частичных соответствий для шаблонов 1 и 2 является довольно значительным. [f-2, f-2],[f-2, f-3],[f-2, f-4],[f-2, f-5], [f — 2, f — 6],[f — 2, f — 7],[f — 2, й, [f-3, f-2],[f-3, f-3],[f-3, f-4],[f-3, f-5], Pattern Pattern Pattern Pattern Pattern Pattern Pattern Pattern Pattern Pattern f — 2, f — 2, f — 2, f — 2, f — 2, f — 2, f — 2, f — 2, f — 1 f — 3, f — 3, f — 3, f — 3, f — 3, f — 3, f — 3, f — 3, f — 4, f — 4, f — 4, f — 4, f — 4, f — 4, f — 4, f — 4, f — 5, f — 5, f — 5, f — 5, f — 5, f — 5, f — 5, f — 5, f — б, f — 6, f — б, f — б, f — б, f — б, f — б, f — 6, f — 7, f-8 f — 7, f — 8 f — 7, f-8 f — 7, f-8 f — 7, f — 8 f — 7, f- 8 f — 7, f-8 f — 7, f — 8 9.12. Важность правильного выбора порядка расположения шаблонов 751 [f Ç,f á], [f З 7], [f Ç,f 8], [f-4, f-2],[f-4, З, f-4],[f- 4, f-5], [f-4, f-6],[f-4, f-7],[f-4, f-8], [f-5, f-2],[f-5, f-3],[f-5, f-4],[f-5, й, f — й, й-7],[й-5, й, б, б, б, б, й, [f — á, f — á], [f — 6, f — 7], [f — á, f — 8], [f-7, f-2],[f-7, З, f-4], [f-7, й, й, f — á], й, f — 7] й, f — 8], [f-8, f-2],[f-8, З, f-5], й, f — á], й, f — 7], й, f — 8] Общее количество частичных соответствий для шаблонов 1 и 2 равно сорока девяти (семь сопоставлений с шаблонами для шаблона умножаются на семь сопоставлений с шаблонами для шаблона. Из-за резкого увеличения потребности в памяти дальнейший рост количества частичных соответствий, которые можно ввести в список применительно к другим шаблонам, вскоре ограничивается, поскольку для шаблонов с 1 по 3 необходимо предусмотреть 343 частичных соответствия, а для шаблонов с по 4 2401 частичное соответствие. Как ив случае правила match — 1, для шаблонов с 1 по 5 имеется только одночастичное соответствие [f — 2,f — 4,f — б — 8,f — 1] Важно отметить, что количество сопоставлений с шаблонами и количество активизаций для правили одинаково, но правило match — 1 имеет только пять частичных соответствий, а правило match — 2 имеет 2801 частичное соответствие, причем разница между этими значениями количества продолжает расти по мере дальнейшего добавления фактов item. Факт (item h) не создает новые частичные соответствия для правила match — а для правила match — 2 создает 1880 новых частичных соответствий. Этот пример показывает, что из-за большого количества создаваемых частичных соответствий может резко снизиться производительность программы. При выборе эффективного набора правил необходимо стремиться не только к тому, чтобы свести к минимуму количество создаваемых новых частичных соответствий, но и количество удаляемых старых частичных соответствий. В действительности следует стремиться к тому, чтобы изменения состояния системы от одного цикла к другому были сведены к минимуму. Конкретные методы минимизации изменений состояния рассматриваются ниже в этой главе Глава 9. Модульное проектирование, управление выполнением. Команда В языке CLIPS предусмотрена команда отладки, называемая matches, которая позволяет отобразить данные о количестве сопоставлений с шаблонами, частичных соответствий и активизаций некоторого правила. Эта команда позволяет находить правила, при использовании которых вырабатывается большое количество частичных соответствий, а также упрощает отладку в тех ситуациях, когда на первый взгляд проверка всех шаблонов правила завершается успешно, но несмотря на это, правило не активизируется. Команда matches имеет следующий синтаксис (matches для которого должно быть отображено количество сопоставлений и соответствий. Пример вывода команды matches показан в следующем диалоге CLIPS> (clear)J CLIPS> (defrule match-3 (find-match х ?y) (item х) (item у) ш) (assert (found-match ха с d) (find-match e f) (item а) (item Ь) ( tern с) (item f))J б CLIPS> (facts)J f — О (find-match асе ас б (item f) For а total of 7 facts. 9.12. Важность правильного выбора порядка расположения шаблонов 753 CLIPS> (matches match-3)J Matches for Pattern 1 f — Об Pattern 3 f — 3 f — 4 f — 5 f — б Partial matches for CEs 1 — 2 f — 1, f-5 f — ООО CLIPS> Первый шаблон правила match — 3 имеет три сопоставления с шаблонами, по одному для каждого факта find — Аналогичным образом, и второй и третий шаблоны имеют четыре сопоставления с шаблонами, по одному для каждого факта item. Первые два шаблона имеют два частичных соответствия одинотноситсякфактам (find — match си с),авторой кфактам (find-match си с. С фактом (find — match е f) не связано ни одного частичного соответствия, поскольку факте) не существует. Для всех трех шаблонов имеется только одночастичное соответствие — частичное соответствие для фактов (fact — match а b), (item аи Для этого частичного соответствия имеется также одна активизация. А после запуска правила match — применительно к этой активизации в выводе команды matches соответствующая информация больше не отображается Глава 9. Модульное проектирование, управление выполнением. Наблюдение за изменяющимся состоянием m1-pm-1 "Partial matches for (find-match х уху (х) =>) (defrule m1-pm-1-to-3 "Partial matches for (find-match х уху х уху х уху г) (item ?w) => pattern ?w) patterns 1 and 2" ?w) 1 to 3 patterns ?w) patterns 1 to 4" ?w) tions for the match rule" ?w) (assert (found-match х у ?z ?w))) Команда matches предоставляет удобный способ исследования частичных соответствий, относящихся к некоторому правилу. Еще одним способом слежения за частичными соответствиями является способ, в котором такие соответствия рассматриваются как частичные активизации правил. Если правило match — 1 будет рассматриваться как несколько отдельных правил, в каждом из которых предпринимается попытка вычисления частичных соответствий, то для просмотра этих частичных соответствий по мере их формирования может использоваться команда watch Правило match — 1 может быть разбито на несколько правил следующим образом. Упорядочение шаблонов в целях повышения эффективности 755 После загрузки приведенных выше правили конструкции def facts с именем information можно организовать отслеживание частичных соответствий входе их создания с помощью команд, показанных в следующем примере диалогового выполнения команда се ас б (item е) > Activation 0 > f — 7 (item f) > f-8 (item g) > Activation 0 CLIPS> ml-pm-1-to-2: f-l,f-2 ml-pm-1-to-3: f-l,f-2,f-4 ml- pm-1-to-4: б match-1: f-l, f-2, f-4, б, f-8 Упорядочение шаблонов в целях повышения эффективности При решении задачи упорядочения шаблонов в целях ограничения количества создаваемых частичных соответствий следует руководствоваться несколькими ре- После применения такого же метода для контроля над выполнением правила matches — 2 вырабатываются сотни частичных активизаций. Теперь должно быть ясно, что если речь идет о повышении эффективности, толевую часть правила нельзя рассматривать как единое целое. Каждую левую часть каждого правила следует считать несколькими отдельными правилами и предпринимать предположение, что каждое из этих правил вырабатывает множество частичных соответствий для всего правила в целом. Поэтому задача написания эффективных правил связана с ограничением не только общего количества активизаций для правила, но и количества частичных соответствий для каждого из отдельных субправил, которые формируют левую часть правила Глава 9. Модульное проектирование, управление выполнением. комендациями. Иногда бывает нелегко найти наилучший способ упорядочения шаблонов, поскольку одни рекомендации противоречат другим. Вообще говоря, эти рекомендации по упорядочению должны использоваться для предотвращения возникновения наиболее существенных неэффективностей, которые могут проявляться в системе, основанной на правилах. Входе настройки производительности экспертной системы может потребоваться применить значительное количество вариантов переупорядочения шаблонов по методу проб и ошибок, чтобы определить, в результате каких изменений система будет действовать быстрее. Часто бывает также, что намного лучшие результаты могут быть достигнуты после опробования полностью другого подхода, а не осуществления попыток точной настройки шаблонов. Первоочередное размещение наиболее конкретных шаблонов Наиболее конкретные шаблоны должны размещаться ближе к началу левой части правила. Наиболее конкретный шаблон, вообще говоря, характеризуется тем, что к нему относится меньшее количество согласующихся фактов в списке фактов и наибольшее количество связываний переменных, ограничивающих другие шаблоны. Например, конкретным является шаблон (match х у ? z ?w), показанный в правилах match — 1 и match — 2, поскольку он ограничивает значения фактов, разрешающие вырабатывать частичные соответствия для четырех других шаблонов правила. Размещение в последнюю очередь шаблонов, согласующихся с непостоянными фактами Шаблоны, которые согласуются с фактами, часто добавляемыми и удаляемыми из списка фактов, должны размещаться ближе к концу левой части правила. Благодаря этому количество изменений в частичных соответствиях для данного правила становится наименьшим. Важно отметить, что шаблоны, согласующиеся с непостоянными фактами, часто бывают наиболее конкретными шаблонами в правиле. В связи с этим может возникнуть противоречие при осуществлении попытки переупорядочить шаблоны в правиле для достижения максимальной эффективности. Например, обычно лучше всего размещать управляющие факты в качестве начального шаблона правила, поскольку при отсутствии управляющего факта не будут вырабатываться частичные соответствия для этого правила. Но если внесение управляющих фактов и их извлечение из списка фактов происходят весьма часто, в связи с чем приходится то и дело повторно вычислять большое количество частичных соответствий, то размещение управляющего факта ближе к концу правила может стать более эффективным. Многозначные переменные и эффективность Первоочередное размещение шаблонов, сопоставляющихся с наименьшим количеством фактов Размещение ближе к началу правила таких шаблонов, которые сопоставляются лишь с немногими фактами в списке фактов, позволяет уменьшить количество частичных соответствий, которые могут быть выработаны. Еще раз отметим, что эта рекомендация может конфликтовать с другими рекомендациями. Шаблон, сопоставляющийся лишь с немногими фактами, необязательно является наиболее конкретным шаблоном еще одна особенность этого шаблона может состоять в том, что он согласуется с непостоянными фактами. 9.14 Многозначные переменные и эффективность Благодаря использованию многозначных подстановочных символов и многозначных переменных возможности сопоставления с шаблонами значительно возрастают. Но непродуманное применение этих возможностей часто приводит к снижению эффективности. Прибегая к использованию многозначных подстановочных символов и переменных, необходимо руководствоваться двумя рекомендациями, описанными в этом разделе. Во-первых, эти конструкции должны применяться, только если они действительно необходимы. Во-вторых, при использовании указанных конструкций нужно следить затем, чтобы количество многозначных подстановочных символов и переменных в единственном слоте шаблона было ограничено. Ниже приведено правило, которое показывает, что многозначные подстановочные символы и переменные могут оказаться полезными, но вместе стем весьма дорогостоящими сточки зрения производительности. (defrule produce-twoplets (list (Ь $?m ее) После внесения в список фактов такого факта, как (items а 4 z 2 ) ), данное правило вырабатывает факты, представляющие начальную ( front ), среднюю (middle) и конечную (back) части списка. Значения длины этих различных частей изменяются от нуля до длины списка. Безусловно, данное правило легко сформулировать с помощью многозначных переменных, но операция его согласования с шаблонами является чрезвычайно дорогостоящей. В табл. показаны все согласования, попытки выполнения которых были предприняты, а также продемонстрировано, что многозначные подстановочные символы и переменные способны выполнить значительную часть работы в составе процесса сопоставления с шаблонами. Вообще говоря, для этого правила produce — twoplets происходит (N2 + 3N + 2) / согласований в расчете на N полей, содержащихся в факте items. Таблица 9.1. Анализ попыток согласования для трех многозначных переменных Попытка согласования Поля, Поля согласующиеся согласующиеся с переменной Ь с переменной $2в Поля, согласующиеся с переменной е a4z2 4z2 z2 2 а a4z2 4z2 z2 4 4z 4z2 z2 2 а z2 а a4z a4z a4z2 Условный элементе и эффективность программы Любой условный элемент test, находящийся в правиле, должен размещаться как можно ближе к началу правила. Например, рассмотрим следующее правило, в котором осуществляются проверки для поиска трех различных точек (defrule three-distinct- points ?point-1 <- (point (х х) (у ух х) (у ?у2)) ?point-3 <- (point (х х) (у у) (test (and (neq ?point-1 ? point-2) (neq ?point-2 ?point-3) (neq ?point — 1 ?point — 3))) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Глава 9. Модульное проектирование, управление выполнением. Условный элемент test и эффективность программы 759 |