Методы поиска решений на основе знаний

4.1. Вывод заключений в логических моделях [4, 5, 6, 9, 18]

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

Префиксная нормальная форма. Приведение формулы ИП к префиксной нормальной форме является первым этапом на пути к освобождению выражения от кванторов. Для приведения формулы ИП к этому виду используется ряд равносильных в исчислении предикатов формул.

Имеем (при условии, что P не содержит свободно x и, значит, не подвержено действию кванторов) следующие пары равносильных формул:

;

;

;

.

Необходимы также следующие пары равносильных формул:

;

.

Однако следует иметь в виду неравносильность следующих формул:

;

.

Поэтому в последних двух случаях для обеспечения равносильности необходимо произвести переименование связанных переменных, используя в качестве y переменную, отсутствующую в :

,

.

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

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

Шаг 1. Выражение логических связок импликации и эквиваленции через связки отрицания, дизъюнкции и конъюнкции с помощью известных правил алгебры высказываний.

Шаг 2. Продвижение связки отрицания до атомарных предикатов с использованием законов де Моргана. В результате выполнения этого шага получается формула, в которой знаки отрицания могут стоять только перед атомарными предикатами.

Шаг 3. Переименование связных переменных с использованием символов переменных, еще не встречавшихся в выражении.

Шаг 4. Вынесение кванторов в префикс с использованием приведенных выше отношений равносильности формул. После выполнения этого шага формула приобретает префиксный вид.

Рассмотрим простой пример. Пусть дано утверждение «Каждый программист имеет свой пароль». Формула ИП, соответствующая этому предложению, имеет вид

,

где программист (х), пароль (у) – одноместные, а имеет (х, у) – двухместный атомарные предикаты.

Шаг 1 выполняется для исключения импликации с помощью отношения равносильности формул . В итоге получим выражение

.

Шаг 2 и Шаг 3 для данной формулы выполнять не требуется.

Шаг 4 применительно к полученной формуле связан с использованием отношения равносильности формул , на основании которого можно вынести $ у в префикс и получить предложение требуемого вида: .

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

Для иллюстрации процесса сколемизации предикатных выражений продолжим рассмотрение примера, использованного для получения префиксной нормальной формы:

.

Как уже говорилось, если все переменные в некотором выражении подвергнуты квантификации, то мы можем опустить кванторы общности. Однако в данном случае квантор общности относится только к х, но не к у (т. е. не все у удовлетворяют высказыванию). Эта проблема решается путем введения функциональной зависимости у от х вида у = g (x), называемой функцией Сколема. В нашем примере g (x) – это принцип присвоения пароля у каждому программисту х. Учитывая, что у = g (x), перепишем наше выражение:

.

Теперь квантор общности распространяет свое действие на всё выражение и, следовательно, знак квантора общности можно опустить:

.

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

Приоритетность действия кванторов, имеющихся в префиксной форме представления, определяется слева направо. Например, формулу можно переписать в следующем виде: , так как переменной, влияющей на связанную квантором $ переменную y, является только x. Если же исходная логическая формула имеет вид , то переменными, влияющими на переменную с квантором существования, являются x и z и тогда получаем . Если исключаемый квантор существования не входит в область действия никакого из кванторов общности, то применяется сколемовская функция без аргументов, т. е. просто константа. Так становится , где символ константы A используется для ссылки на элемент, который, как известно, существует. Важно, чтобы A был новым символом константы и не совпадал с другими символами, взятыми для других формул.

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

Клаузальная форма (форма предложений). На данной стадии полученное для рассматриваемого примера выражение

может быть представлено в общем виде как .

Так как , то выражение на самом деле содержит два разных предложения со связкой или:

,

.

Поэтому полученное для рассматриваемого примера выражение может быть записано так:

,

.

О представленном в таком виде пропозициональном выражении говорят, что оно имеет клаузальную форм у. Любая, представленная в клаузальной форме, фраза состоит из серии высказываний (с отрицаниями или без них), соединенных связкой Ú (или).

В общем случае любое пропозициональное выражение можно привести к конъюнктивной нормальной форме (КНФ) многократным применением дистрибутивных правил. Чтобы затем преобразовать КНФ в клаузальную форму (в форму предложений), исключают символы &, заменяя конъюнкцию выражений на множество выражений . Результатом осуществления таких замен будет некоторое конечное множество выражений, каждое из которых является дизъюнкцией литералов (с отрицаниями или без них). Любая формула, состоящая только из дизъюнкций литералов, называется предложением. Множество предложений, полученных в результате исключения символа &, называется клаузальным множеством.

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

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

Решение задачи в исчислении предикатов равносильно доказательству (или опровержению) истинности формулы , где формулы считаются посылками, а формула С – требующим доказательства (или опровержения) заключением.

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

= .

В клаузальной форме формулы представляют собой дизъюнкции литералов (с отрицаниями или без них). Если формула С – не литерал, то формула тоже должна быть приведена к этому виду.

Итак, в последней формулировке мы должны, полагая истинными посылки, попытаться вывести истинность формулы . Отрицательный результат этой попытки будет свидетельствовать об истинности формулы С.

В основе метода резолюции лежит правило вывода обобщенное правило modus ponens: (), () ├ (), реализуемое как операция исключения высказываний из предложений, если эти высказывания в одних предложениях присутствуют без отрицаний, а в других – с отрицаниями.

Рассмотрим сначала абстрактный пример. Прежде всего предположим, что в клаузальной форме нам даны факты (посылки):

1) ;

2) ;

3) .

Далее предположим, что мы хотим доказать, что из истинности этих посылок следует истинность формулы С. Чтобы это сделать, дополним заданный набор предложений отрицанием С:

1) ;

2) ;

3) ;

4) .

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

1) ;

2) ;

3) .

После выполнения второй резолюции (например, исключением из первого предложения и В – из второго) останутся предложения:

2) А;

3) .

Наконец, исключив последние два предложения, получим пустое предложение, изображаемое символически (). В этом случае говорят, что получена пустая резольвента. Если удается вывести пустое предложение, то истинность заключения (в данном случае С) считается доказанной.

Теперь рассмотрим конкретное содержательное рассуждение.

Предположим установленной истинность двух утверждений:

1) если экономика развивается, то курс валюты не падает;

2) курс валюты падает.

Рассмотрим далее, как из этих утверждений сделать вывод, что экономика не развивается. Для этого представим сначала данные нам утверждения в виде формул исчисления предикатов:

1) ;

2) .

Переведя данные выражения в клаузальную форму и дополнив их отрицанием искомого заключения , получим:

1) ;

2) ;

3) .

Из полученных предложений видно, что использование в резолюции третьего и первого из них дает в итоге следующие два предложения:

1) ;

2) .

Резолюция этих предложений приводит к пустой резольвенте, что свидетельствует об истинности заключения .

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

4.2. Язык программирования логики (Пролог) [1, 4, 5, 6, 14]

Пролог и логика предикатов. Язык программирования логики (мы будем опираться на его версию, получившую название Турбо-Пролог) был разработан как язык программирования, предназначенный специально для представления логических моделей знания и решения задач на основе применения метода резолюции. При его создании в клаузальный синтаксис была введена логическая связка «импликация». Рассмотрим, как это может быть сделано. Напомним, что логическое выражение в клаузальной форме состоит из высказываний (или их отрицаний), соединенных связками или. Любой набор высказываний, соединенных связками или, благодаря коммутативности этой связки, может быть перестроен по нашему усмотрению. Чтобы ввести в клаузальный синтаксис связку импликация, сначала отделим отрицаемые высказывания от неотрицаемых, перенося их соответственно налево и направо. Так выражение

после перестройки приобретает следующий вид:

.

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

.

В результате рассматриваемому нами предложению будет эквивалентно следующее предложение:

.

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

.

В итоге рассматриваемое нами в качестве примера выражение в импликационной форме примет следующий вид:

.

Другими словами, набор условий, соединенных связкой и, имплицирует набор заключений, соединенных связкой или.

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

;

.

Выражения такого вида называются предложениями Хорна.

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

A:— B&D&E;

C:— B&D&E.

Факт представляется в обозначениях Пролога как предложение, не имеющее условий. Например, тот факт, что «Петр руководит Иваном», в Прологе запишется так (слова, начинающиеся с заглавных букв, в Прологе считаются именами переменных, поэтому имена персон, представляющие собой имена констант, начинаются в примере со строчных букв):

:—

Запрос (то, истинность чего мы стремимся установить), в соответствии с методом резолюции, отрицается (А запишется как ). Поскольку эквивалентно А → В (в нотации Пролога В:— А), то эквивалентно А → (в нотации Пролога:— А). Таким образом, запрос – это условие или набор условий без заключения. Следовательно, в Прологе запрос о том, «Отчитывается ли Федор перед Петром?» будет иметь вид:

:— .

Однако в Прологе тоже существует проблема выбора пары предложений для вывода очередной резольвенты. Для ее решения требуется иметь некоторую форму управляющей структуры. Способ ее решения в Прологе представляет собой поиск в пространстве состояний, имеющем вид дизъюнктивно-конъюнктивного дерева (ДК-дерева, дерева типа И/ИЛИ). Разобрать его проще на отвлеченном примере (рис. 4.1).

Крона дерева, изображенная на рис. 4.1, сформирована на основании приведенного там же списка правил, где фактам соответствуют терминальные вершины (листья дерева). Ветви дерева соединены либо связкой & (и – требование выполнения совокупности условий), либо связкой (или – требование выполнения хотя бы одного из условий).

ДК-дерево (дерево типа И/ИЛИ) можно рассматривать двояко: и как декларативное выражение, что обычно свойственно логическим выражениям, и как процедурное выражение, что характерно для программирования. Например, следуя логике, мы можем утверждать: для того, чтобы высказывание р было истинным, высказывания q и r должны быть истинны, а для того, чтобы q было истинным, достаточно истинности хотя бы одного из высказываний – либо s, либо t. С позиций процедурного представления правила языка Пролог можно интерпретировать как декомпозицию доказательства заданного высказывания: для доказательства р необходимо доказать q и r, а для доказательства q достаточно доказать или s, или t.

Представив набор предложений Пролога в виде ДК-дерева, можно применять различные стратегии его обхода при поиске решения, что будет равносильно выработке стратегии выбора предложений для резолюции при доказательстве теорем методом резолюции. В Прологе принята стратегия поиска «сначала вглубь», начиная слева, что соответствует порядку обхода дерева, показанному на рис. 4.1 пунктирными стрелками.

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

Заданная цель:— р затем сопоставляется с первым из предложений, имеющим р в качестве заключения. В рассматриваемом случае есть только одно такое предложение р:— q & r. Сопоставление:— р с правилом р:— q & r означает сведение доказательства цели:— р к доказательству цели:— q & r, состоящей из подцелей:— q и:— r (сопоставление:— р с р:— q & r равносильно резолюции предложений р и (р Ú (q & r)), результатом чего является резольвента (q & r)=( q Ú r)).

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

Далее осуществляется поиск подтверждения второй компоненты подцели:— q & r, а именно: подцели:— r. Ее сопоставление с предложением r:— a & b приводит к подцели:— a & b, распадающейся на подцели:— a и:— b, подтверждаемые фактами a:— и b:—, в результате чего подцель:— r получает подтверждение. Поскольку подцель:— q уже была подтверждена, то по правилу р:— q & r подтверждение получает и проверяемая цель:— р.

Таким образом, исходный запрос:— р подтверждается путем обхода последовательности узлов дерева р, q, t, s, r, a, b. Необходимо отметить, что если подтверждение q или r окажется невозможным в силу отсутствия в программе необходимых фактов (s и t, или а, или b), то запрос:— р не получит положительного ответа.

Структура программы на языке Турбо-Пролог. В общем случае программа на Турбо-Прологе состоит из разделов: domains, database, predicates, goal, clauses. Раздел domains содержит определения доменов (классов объектов, используемых в программе). Раздел database включает описание предикатов, фигурирующих в динамических базах данных, используемых в программе. Раздел predicates представляет собой описание предикатов, употребляемых непосредственно в самой программе. Раздел goal формулирует назначение программы (описание искомого решения задачи). Раздел clauses представляет собой перечень фактов и правил, используемых в процессе поиска решения задачи (осуществления цели).

Большинство программ не содержит всех перечисленных разделов. Так, раздел domains необходим, если встроенных в Турбо-Пролог доменов (char, integer, real, string, file, symbol) для построения программы недостаточно. Домены – это, по сути, аналог типов данных, определяемых пользователем в процедурных языках. Раздел database необходим в том случае, если программа предназначена для работы с большими объемами меняющихся со временем данных. Раздел goal также не всегда используется. Если цель (goal) задана, база знаний функционирует как программа, вычисляющая эту цель с учетом поступивших в базу данных и содержащихся в разделе clauses фактов. Если же цель (goal) не задана, Турбо-Пролог при каждом запуске запрашивает ее как внешнюю, задаваемую пользователем цель, т. е. работает как база знаний, отвечающая на запросы пользователя. Необходимыми для работы любой программы являются лишь разделы predicates и clauses, так как в этих разделах сосредоточено описание предикатов, фактов и правил вычисления ответов на запросы пользователя.

Пример программы на языке Турбо-Пролог. Рассмотрим здесь простую программу на языке Турбо-Пролог и реализуемый в этом языке способ ее выполнения. Для более глубокого знакомства с этим языком и освоения программирования можно обратиться к книге А. Н. Адаменко и А. М. Кучукова [1]. Эта книга позволяет пошагово освоить язык Пролог и научиться логическому программированию человеку, ничего не знающему об этом языке.

/* Программа family.pro */

domains /* описание доменов */

person=symbol

predicates /* описание предикатов */

male(person)

female(person)

parents(person,person,person)

sister(person,person)

who_is_sister

goal /* описание цели */

who_is_sister.

clauses /* утверждения программы */

/* факты */

male("Frank").

male("Sam").

female("Ann").

female("Mary").

parents("Sam","Frank","Mary").

parents("Ann","Frank","Mary").

/* правила */

who_is_sister:- sister(SisterName,Name),

write(SisterName," is the sister of ",Name,"."), nl.

sister(SisterName,Name):- female(SisterName),

parents(SisterName,Father,Mother),

parents(Name,Father,Mather),

SisterName<>Name.

/* Конец программы */

В программе в разделе clauses в виде фактов описана семья из четырех человек (Frank, Sam, Ann, Mary). Кроме того, сообщено, что Frank и Sam – мужчины (male), Ann и Mary – женщины (female), а также что Frank и Mary являются родителями для Sam и Ann. Так как имена принято писать с заглавной буквы, а в Турбо-Прологе все слова, начинающиеся с заглавной буквы, воспринимаются как переменные, то имена персон заключены в кавычки (любой текст, заключенный в кавычки, в Турбо-Прологе считается константой). Отметим также, что текст, заключенный в скобки вида /*…*/, Турбо-Пролог воспринимает не как часть программы, а как комментарий и в процессе исполнения программы не обращает на него внимания.

В разделе domains дано описание домена person=symbol, говорящее о том, что объекты типа person – это, по сути, данные типа symbol, представляющие собой либо слова из букв, цифр и подчерков, начинающиеся строчной буквой, либо последовательности любых символов, заключенные в двойные кавычки.

В разделе predicates представлено описание предикатов: трехместного (parents), двухместного (sister), одноместных (male, female) и нольместного (who_is_sister). Назначение этого раздела состоит в том, чтобы указать, какого типа объекты могут быть в качестве аргументов каждого из предикатов. В данной программе во всех случаях (кроме нольместного предиката who_is_sister) в качестве аргументов предикатов выступают объекты типа person. Предикат who_is_sister аргументов не имеет, так как лишь указывает назначение программы (что она вычисляет).

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

В разделе clauses, как можно видеть из самой программы, дается описание фактов и правил, используемых для вычисления заданной или внешних целей. Описания цели, фактов и правил, как и в естественном языке предложения, завершаются точкой. Запятая, фигурирующая в правых частях правил, в Турбо-Прологе выполняет роль конъюнкции &.

Проверка условий, присутствующих в правых частях правил, осуществляется в порядке их записи слева направо. Например, второе правило означает, что предикат sister(SisterName,Name) принимает истинное значение, если выполняется предикат female(SisterName) (персона по имени SisterName является женщиной) и предикат parents(SisterName,Father,Mother) (ее родителями являются персоны Father и Mother) и предикат parents(Name,Father,Mоther) (родителями персоны Name являются те же самые Father и Mother). Условие SisterName<>Name в этом правиле введено, чтобы исключить возможность персоне женского пола быть сестрой самой себе (символ <> означает неравенство). Иначе говоря, этим правилом описывается понятие сестры. В нашей «семье» предикату sister(SisterName,Name) по данному правилу может быть присвоено истинное значение лишь при значениях переменных: SisterName="Ann", Name="Sam", Father="Frank", Mother="Mary". При ином составе "семьи", конечно, возможных вариантов срабатывания этого правила может быть больше.

Срабатывание второго правила в нашей программе создает условия для срабатывания первого, в результате чего на экран дисплея выводится сообщение, содержащее решение задачи (в нашем примере единственно возможное: Ann is the sister of Sam).

Если удалить из программы полностью раздел goal, она превратится в программу, работающую по запросам (внешне заданным целям). Например, на запрос male(Name) будет выдано сообщение, перечисляющее всех лиц мужского пола, приведенных в разделе «факты»; на запрос sister("Ann",Name). будет получен тот же ответ Ann is the sister of Sam.

Попробуйте раширить состав «семьи» и создать правила для поиска в ней брата (brother), дяди (uncle), тети (aunt), бабушки (grandmother), дедушки grandfather), внука (granson), внучки (granddaughter), племянника (nephew), племянницы (niece).

4.3. Стратегии поиска решений для систем продукций [4, 9]

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

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

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

Различают также два типа пробных режимов управления: с возвращением и с поиском на графе.

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

В режиме управления с поиском на графе предусмотрено запоминание результатов применения одновременно нескольких последовательностей правил. Здесь используются различные виды графовых структур и процедур поиска на графе.

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

В ситуации полной неинформированности выбор делается абсолютно произвольно.

В ситуации полной информированности стратегия управления руководствуется знанием, достаточным для того, чтобы каждый раз выбрать «верное» правило.

В целом вычислительная эффективность системы продукций зависит от положения между этими двумя крайнимислучаями данной стратегии управления.

Вычислительные затраты в системе продукций можно разделить на две категории:

а) затраты на применение правил (стоимость пути к цели);

б) затраты на управление (стоимость поиска правил, ведущих к цели).

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

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

Рис. 4.2. Усредненная полная стоимость вычислений

1 – стоимость применения правил; 2 – стоимость стратегии управления;
3 – полная стоимость

Обратные и двусторонние системы продукций. Система продукций для решения игры в 8, при всех рассмотренных режимах управления, работает непосредственно от исходного состояния к целевому (т. е. в прямом направлении) и ее можно назвать прямой системой продукций.

Эта задача (игра в 8) могла бы быть решена и в обратном направлении – продвижением от целевого состояния к исходному и с применением обратных ходов. Каждый ход породил бы подцелевое состояние, из которого текущее целевое состояние можно достичь за один ход вперед. Система продукций для решения игры в 8 таким способом просто изменила бы назначения состояний и целей и использовала бы правила, соответствующие обратным ходам.

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

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

Часто удачной является попытка решить задачу путем двустороннего поиска – одновременно в прямом и обратном направлениях. Для этого в глобальную базу данных включают описания как состояний, так и целей. К части описания состояний применяются П-правила, а к части описания целей применяются О-правила. Управляющая система при этом должна на каждом шаге поиска принимать решение об использовании правила того либо другого типа. При таком поиске терминальное условие для управляющей системы, позволяющее заключить, что задача решена, должно быть определено как условие соответствия между описаниями состояний, достигнутых с помощью П-правил и О-правил.

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

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

Чтобы разложить базу данных на независимые составляющие, необходимо уметь разложить и соответствующее терминальное условие. Если каждая составляющая обрабатывается отдельно, то и глобальное терминальное условие должно быть выражено через терминальные условия каждой составляющей. Наиболее важным является случай, когда глобальное терминальное условие можно выразить как конъюнкцию терминальных условий для каждой составляющей баз данных. Системы продукций, глобальные базы данных и терминальные условия которых допускают такую декомпозицию, называются разложимыми.

Хотя возможна параллельная обработка составляющих баз данных, обычно ищется стратегия управления, позволяющая обрабатывать их в некотором последовательном порядке. Существует два основных способа упорядочивания этих компонент: расположить их в каком-то жестком порядке в момент их порождения или динамически переупорядочивать их в ходе обработки. При обработке составляющей может возникнуть разложимая база данных. В таком случае компоненты этой базы данных также обрабатываются по очереди. Обычно для отбора правил используется стратегия с возвращением в сочетании со стратегией жесткого упорядочивания обработки компонент.

4.4. Методы поиска решений
в сложных пространствах [4, 18]

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

Особенности ПО – это степень сложности объекта, его количественная сложность (размер, количество элементов) и его качественная сложность (сложность его организации и поведения – статический, динамический, развивающийся объект).

Особенности знаний о ПО – это полнота, определенность, точность знаний о ПО (полнота, определенность, точность данных об объекте, а также полнота и адекватность модели объекта).

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

По этим признакам наиболее простая проблемная ситуация возникает в том случае, когда ПО мала, статична и однородна; имеются полные, точные данные и единая адекватная модель; задача состоит в отыскании любого одного решения без каких-либо особенных ограничений. Примером такого рода проблемы может быть игра в «крестики и нолики» или проверка наличия заданного типа товара на складе небольшой торговой фирмы.

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

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

1. Методы поиска в одном пространстве – применяются в случаях, когда ПО статична и невелика, возможно построение единой полной модели и получение полных и точных данных.

2. Методы поиска в иерархии пространств – применяются в случаях, когда ПО велика, но возможно представление знаний о ней в виде иерархии моделей первого типа и получение полных и точных данных.

3. Методы поиска в условиях неопределенности – применяются в случаях, когда ПО недостаточно изучена, имеющиеся данные неполны, ненадежны и недостаточно точны.

4. Методы поиска в динамических пространствах – применяются в случаях, когда ПО представляет собой эволюционирующий, изменяющийся во времени и в пространстве, развивающийся объект.

5. Методы поиска на основе нескольких моделей – применяются в случаях, когда ПО неоднородна, агрегирована из объектов различной природы, представление которых требует использования специфических моделей.