Материал: Алгебра_кортежей
собственности" – как R2[Y1Y2Y3], а таблицу "Трестовский лимит" – как R3[Z1Z2]. Тогда вычисления можно разбить на следующие шаги:
Шаг 1. Найти фирмы, имеющие контрольный пакет акций в других фирмах. Для этого применим селектор [ {>50}] к таблице "Отношение собственности":
P[Y1Y2Y3] = R2[Y1Y2Y3] G [ {>50}].
В проекции P[Y1] содержатся искомые на данном шаге фирмы, в проекции P[Y2] – дочерние фирмы, а проекция P[Y1Y2] выражается как C-система:
{A} |
{B,J} |
||
|
{B} |
{I} |
|
|
|
||
P[Y1Y2] = P[Фирма1 Фирма2] = |
{E} |
{D,F} . |
|
|
{J} |
{K} |
|
|
|
||
|
|
{L} |
|
{M} |
|
||
Отношение P[Y1Y2] можно изобразить в виде графа, в котором дуги – направленные связи между фирмами и контролируемыми ими другими участниками рынка.
Теперь необходимо откорректировать отношение P[Y1Y2Y3], оставив в нем только головные фирмы, работающие с товаром T1. На шагах 2, 3 выполняется эта корректировка.
Шаг 2. Выделить участников рынка, производящих товар T1, для чего применим селектор [* T1 *] к отношению "Фирмы":
E[X1X2X3] = R1[X1X2X3] G [* T1 *].
Шаг 3. Определить головные фирмы из отношения P[Y1Y2Y3], которые производят товар T1. Это можно осуществить разными способами, например, если вычислить соединение P[Y1Y2Y3] E[X1X2X3] = P[Y1Y2Y3] G E[X1X2X3], полагая эквивалентными первые атрибуты этих отношений. Здесь же предлагается другой способ – сравнивать проекции P[Y1] и E[X1]. Можно убедиться в том, что они в примере идентичны, поэтому для C-системы P[Y1Y2Y3] корректировка не нужна.
Шаг 4. Выявить множества фирм на рынке товара T1, которые входят в тресты. На данном этапе вычислений необходимо найти транзитивное замыкание графа, соответствующего С-системе P[Y1Y2]. В результате получим такой АК-объект:
195
|
|
|
|
|
|
{A} {B,I,J,K} |
|
||
|
{B} |
{I} |
|
|
|
|
|
||
P+[Y1Y2] = |
{E} |
{D,F} |
|
, |
|
{J} |
{K} |
|
|
|
|
|
||
|
|
{L} |
|
|
{M} |
|
|
||
где каждая строка соответствует определенному тресту. В левом столбце содержатся фирмы, контролирующие тресты, а в правом – остальные фирмы, которые входят в эти тресты.
Шаг 5. Вычислить доли рынка товара T1, контролируемого соответствующей фирмой (включая долю самой фирмы). В итоге:
для фирмы A – {8, 7, 12, 2, 4}; = 33; для фирмы B – {7, 12}; = 19;
для фирмы E – {0, 13, 12}; = 25; для фирмы J – {2, 4}; = 6;
для фирмы M – {19, 15}; = 34.
Шаг 6. Теперь, используя данные отношения "Трестовский лимит", можно определить, что антитрестовский закон нарушают фирмы A, E и M.
Таким образом, задачу, для решения которой традиционно использовались методы и средства логического программирования, можно решать с применением методов АК.
5.3.Системы искусственного интеллекта
5.3.1.Представление знаний в АК
В интеллектуальных системах наиболее распространены три типа моделей представления знаний: продукции (правила), семантические сети и фреймы.
Правила. Чаще всего используются продукционные правила, то есть импликации типа:
Если A1 и A2 и ... и Ak, то B1 или B2 или ... или Bn, где Ai и Bj – некоторые предикаты.
Предикаты, по сути, являются отношениями. Например, набор предикатов экспертной системы (ЭС)
isa(a1, S1);
196
isa(a2, S1); |
|
isa(a3, S1); |
|
isa(a4, S2); |
(5.4) |
prop(S1, c1, d1); |
|
prop(S1, c2, d2); |
|
prop(S2, c1, d3). |
|
отображает два отношения: бинарное isa и трехместное prop. В структурах АК предикаты можно выразить как C-системы. Тогда модель (5.4) примет вид:
{a1,a2 ,a3} {S isa[XY] =
{a4} {S
|
} |
|
{S1} {c1} |
{d1} |
|
||||
1 |
; prop[YZV] = |
|
|
|
{c2} |
{d2 |
|
(5.5) |
|
|
|
{S1} |
} . |
||||||
2} |
|
{S |
} {c} |
{d } |
|
||||
|
|
|
|
2 |
|
1 |
3 |
|
|
Если правило выражено в виде импликации X Y, то логическое выражение X называется телом правила, а логическое выражение Y – головой (или целью) правила. База данных ЭС хранит факты, содержащие значения некоторых предикатов. Ввод фактов в базу данных инициирует процедуру поиска новых фактов с учетом правил, содержащихся в базе знаний. Она продолжается до тех пор, пока не будет установлено, что больше никаких новых фактов из этой базы знаний извлечь невозможно.
Экспертные системы во многом сходны с СУБД, а процедуры вывода на основе поступивших фактов аналогичны реализациям запросов в БД. Основное отличие состоит в том, что в процедурах вывода ЭС используется больше аналитических средств, чем при реализации запросов СУБД. Это как раз те средства логического анализа, которые отсутствуют в современных СУБД, но разработаны в АК.
Рассмотрим пример, используя совокупность предикатов (5.4) и их представление в АК (5.5). Пусть задано следующее правило вывода:
ЕСЛИ isa[XY] И prop[YZV] ТО property[XZV].
В терминологии АК это типичное для БЗ правило предусматривает формирование нового отношения property с помощью композиции отношений isa и prop. Тогда ввод в систему новых фактов, например, X = a1 и V = d2, эквивалентен запросу Q[XV] = [{a1} {d2}]. Его можно реализовать (в терминологии ЭС – для поиска новых следствий из этих фактов в базе знаний) с помощью нижеприведенного алгоритма, если предварительно выполнить
197
операции с отношениями-предикатами, предусмотренные в теле правила:
(isa[XY] prop[YZV]) [{a1} {d2}],
где в запрос Q[XV] добавлен фиктивный атрибут Z. Популярный пример правила, реализация которого требует композиции отношений, – предложение: «Если X – отец Y и Y – родитель Z, то X – дед Z».
Один из критических узлов любой экспертной системы – это интерпретатор – программно-математическая система преобразования данных в соответствии с правилами. Принципы работы интерпретаторов основаны на символьных преобразованиях математической логики, их программная реализация весьма сложна и, как правило, не показывается даже в самой подробной технической документации. В них обычно используются списковые структуры данных, которые при машинной реализации больших систем характеризуются невысоким быстродействием и поэтому часто не могут использоваться в системах реального времени.
Рассмотрим пример, иллюстрирующий работу интерпретатора в структурах АК. В статье [Индейцев, 1995] описана экспертная система, предназначенная для принятия решений на уровне командира корабля в случае возникновения нештатных ситуаций на корабле или в окружающей обстановке, в частности, в боевых условиях. Исходная информация для принятия решений – обобщенные данные по подсистемам корабля и окружающей среды, т.е. данные типа "утрата непотопляемости возрастает медленно (или быстро)", "возник пожар в энергоотсеках в одном эшелоне", "состояние моря 6 баллов" и т.д.
Опишем пример перевода правил ЭС на язык АК для комплекта правил по анализу электрообеспечения корабля, где используются 4 фактора. Данные по ним и соответствующие обозначения приведены в табл. 5.8.
На предварительном этапе реализации системы был составлен следующий комплект правил для системы электрообеспечения.
Инициализация: W = неизвестно. Цель: W.
Правило 1; приоритет 30:
IF (X = c AND y = b) OR Z = b THEN W = c
Правило 2; приоритет 20:
198
IF X = b OR Z = b
THEN W = b
Наименования факторов и их |
Обозначения |
|
значения |
факторов |
|
СНАБЖЕНИЕ |
W |
|
ЭЛЕКТРОЭНЕРГИЕЙ |
||
|
||
обеспечено полностью |
|
|
утрачено частично |
|
|
утрачено полностью |
|
|
ОСНОВНЫЕ ИСТОЧНИКИ |
X |
|
в строю |
|
|
вышли из строя в одном эшелоне |
|
|
вышли из строя в обоих эшелонах |
|
|
АВАРИЙНЫЕ ИСТОЧНИКИ |
Y |
|
в строю |
|
|
вышли из строя |
|
|
КАНАЛИЗАЦИЯ |
Z |
|
ЭЛЕКТРОЭНЕРГИИ |
||
|
||
не нарушена |
|
|
нарушена частично |
|
|
нарушена полностью |
|
Таблица 5.8.
Обозначения
значений
факторов
a b c
a b c
a b
a b c
Приоритет в данном случае устанавливает порядок применения правил: чем больше приоритет, тем раньше должно быть применено данное правило; переход к следующему правилу происходит в случае безуспешной проверки всех правил с более высокими приоритетами (это идеология нормальных алгоритмов Маркова). При успешной проверке происходит выход из комплекта правил с присвоением значения целевому фактору (в данном случае фактору W). Если в обоих правилах проверка безуспешна, то фактору W присваивается значение a.
Для решения задачи средствами АК введем четыре атрибута:
W = {a, b, c}; X = {a, b, c}; Y = {a, b}; Z = {a, b, c}.
199