Компактное представление ограничений на основе новой интерпретации понятия "кортеж многоместного отношения"

В современных информационных системах, особенно тех, что связаны с применением методов искусственного интеллекта, для описания связей между объектами часто используют понятие «отношение», а для обозначения элемента отношения – понятие «кортеж». К таким системам, например, относятся системы: моделирования рассуждений [1, 2]; онтологического инжиниринга [3]; управления базами данных (СУБД) [4]; программирования в ограничениях ( Constraint Programming - CP ) [5, 6] и т.п. Однако оказывается, что в известных автору работах присутствуют различные взгляды на такие понятия, как «многоместное отношение» и «кортеж многоместного отношения». Игнорирование этих различий может привести к неверному пониманию выдвигаемых научных идей.

В статье рассматриваются различные трактовки понятия «кортеж многоместного отношения», используемые в математике и информационных технологиях. Особое внимание уделено эволюции понятия «кортеж» в рамках технологии CP . Базовым в рамках данной технологии является понятие ограничения, которое по смыслу очень близко понятию многоместного отношения. Основной раздел посвящён развитию технологии CP в части повышения эффективности обработки качественных ограничений, таких как: продукционные правила, логические выражения, бинарные и многоместные отношения и т.п. В настоящий момент процедуры удовлетворения качественных зависимостей, поддерживаемые существующими библиотеками CP , недостаточно эффективны. Перспективным подходом к представлению и обработке качественных ограничений следует признать подход, основанный на применении их специализированного табличного представления. В рамках CP был выделен отдельный класс глобальных ограничений - табличные ограничения. Простейшим примером табличных ограничений являются реляционные таблицы. В виде реляционных таблиц, содержащих множество выполняющих подстановок, может быть представлен любой конечный предикат. Однако, такое эксплицитное представление для многих отношений нецелесообразно, поскольку приводит к экспоненциальному росту сложности процедур удовлетворения ограничений. Поэтому предпринимаются попытки разработать более компактное табличное представление качественных зависимостей [7-10].

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

1    Разбор понятия «кортеж многоместного отношения» 1.1    Понятия «кортеж» и «многоместное отношение»

«Кортеж», как и понятие «множество», относится к первичным понятиям (т.е. не определяемым строго) [11].

Под кортежем традиционно понимается упорядоченный набор конечного числа объектов любой природы. Число объектов называется длиной кортежа, а сами объекты - компонентами кортежа. Кортеж длиной 2 называется парой, длиной 3 - тройкой, длиной n - n- кой.

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

Вместо слова «кортеж» в математической литературе употребляются также в качестве синонимов термины «вектор», «набор».

Традиционно в математике под многоместным отношением понимают некоторое подмножество декартова (прямого) произведения множеств.

Определение 1.1. (Декартово произведение конечного семейства множеств).

Пусть имеется n множеств Xi, „., Xn, тогда их декартово произведение определяется как X1х ... хXn ={(x 1, x2, ., xn) | xi e Xi}, где запись (x1, x2, ., xn) обозначает упорядоченную n- ку, в которой первая компонента принадлежит X1, вторая - X2 и т.д. [11].

Определение 1.2. (Многоместное отношение). Отношением между множествами X i , „., X n называется любое подмножество их декартова произведения R с X ₁х, „,,х X n . Если требуется явно указать число n , то говорят об n -арных или n -местных отношениях. При n = l, 2, 3 имеем унарное, бинарное, тернарное отношения соответственно. Унарное отношение на множестве X представляет собой подмножество множества X [ll].

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

Пример. Пусть заданы множества X = { a , b , c } и Y = {l, 2}. Необходимо удостовериться, что: X х Y ф Y х X. При этом X х Y и Y х X являются универсальными отношениями.

Тогда: Xх Y = {( a , l), ( a , 2), ( b , I), ( b , 2), ( c , I), ( c , 2)} и Y х X = {(l, a ), (2, a ), (I, b ), (2, b ), (l, c ), (2, c )}. Из сопоставления между собой кортежей этих отношений видно, что это два совершенно разных отношения.

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

• 1.2    Формализация понятия «кортеж» в реляционной алгебре

В реляционной алгебре схемой отношения R называется конечное множество имен атрибутов { А 1 , A 2 , ..., A n }[4]. Каждому имени атрибута A i ставится в соответствие множество D i ,, называемое доменом атрибута A i , l <  i <  п . Домены являются произвольными непустыми конечными или счётными множествами.

Пусть D = D i u D 2 и ... u D n . Отношение r со схемой R - это конечное множество отображений { t ₁, t ₂,..., t p } из R в D , причём каждое отображение t е r должно удовлетворять следующему ограничению: t ( A i ) е D i , l < i < п. Эти отображения называются кортежами. В данной формализации понятие отношения вводится через понятие отображения, чтобы избежать любого упорядочения имен атрибутов в схеме отношения. В рассматриваемой формализации расширяется традиционное понимание кортежа как последовательности значений, заданной в определённом порядке. Под кортежем понимается множество значений, взятых по одному для каждого имени атрибута из схемы отношения.

Пусть имеется n ( n > 0) не обязательно различных доменов D _l, D 2 ,..., D n . Пусть имеется n атрибутов (переменных) A _l, A ₂,..., A n .

Поскольку кортеж в реляционной алгебре рассматривается как отображение, то он может задаваться как множество пар ( A , v ), где A - некоторый атрибут, а v - значение, взятое из домена атрибута A .

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

• ■    не существует дубликатов строк (кортежей);

• ■    порядок строк (кортежей) является несущественным;

• ■    порядок столбцов (атрибутов) является несущественным;

• ■    все элементы таблицы являются атомарными значениями.

• 1.3    Эволюция понятия «кортеж» в рамках технологии CP

Для того, чтобы прикладная задача могла быть решена с применением технологии программирования в ограничениях, она должна быть представлена в форме задачи удовлетворения ограничений ( Constraint Satisfaction Problem - CSP ).

З адача удовлетворения ограничений состоит из трёх компонент: < X , D , C> [12]. X - множество переменных { X ₁, X ₂, „., X_n }, D - множество доменов { D 1 , D ₂, „., D_n }, где D i является доменом переменной X i ; С - множество ограничений { С 1 , С ₂, ..., C m }, которые предписывают допустимые комбинации значений переменных. Каждый домен D i описывает множество допустимых значений { v i , „., v_k } для переменной X i . Каждое ограничение есть пара < scope , rel >, где scope – множество переменных, которые участвуют в ограничении, а rel – отношение, регламентирующее допустимые комбинации значений, которые переменные из scope могут принимать.

Задача описывается как присваивание значений некоторым ( частичное присваивание ) или всем переменным ( полное присваивание ): { X i = v i , X j = V j ,...}. Решением задачи CSP является полное присваивание, которое удовлетворяет всем ограничениям.

Для различных типов ограничений разрабатываются свои способы вывода на данных ограничениях, при этом процедура вывода называется распространением ограничений . Любая система программирования в ограничениях обладает библиотекой стандартных функций-распространителей для обработки наиболее популярных типов ограничений. Как правило, подобные ограничения содержат нефиксированное количество переменных и носят название глобальных ограничений, например ограничение Alldiff ( X 1 , ..., X k ) [13].

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

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

Например, предикат ( X i <  X ₂) л ( X ₃ # t ), где домены переменных X i и X ₂ равны множеству {1, 2, 3}, а доменом переменной X ₃ является множество { t , k , r }, может быть описан следующим образом:

X 1	X 2	X 3
" 1	2	k
1	2	r
1	3	k
1	3	r
2	3	k
2	3	r

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

В последние годы в рамках технологии CP появляется много подходов, посвящённых более компактному представлению табличных ограничений [7-10, 15, 16]. Один из них состоит в изменении классического понятия кортеж и введении в рассмотрение нового понятия - compressed-кортеж (compressed tuple) [7-9]. В отличие от обычных кортежей, compressed -кортежи содержат в своих компонентах не отдельные значения переменных, а подмножества значений соответствующего домена. Целиком compressed-кортеж соответствует декартову произведению компонент-множеств. Таблица, содержащая compressed-кортежи, называется compressed-таблицей (compressed table).

Ранее рассмотренному предикату ( X ₁<  X 2 ) л ( X 3 # t ) соответствует следующая compressed -таблица:

X 1	X.	X з
{1}	{2,3}	{ k , r }
{2}	{3}	{ k , r }

Дальнейшая эволюция понятия «кортеж» заключалась в том, что в [10] было предложено обобщить понятия compressed -кортежей и коротких поддержек ( short supports ) [15] до понятия smart -кортежи ( smart tuple ). В описании компонент таблицы было разрешено вместо явного перечисления подмножества элементов соответствующего домена использовать обозначения некоторых одноместных и двуместных предикатов, моделирующих простые арифметические выражения. Таблицы, состоящие из smart -кортежей, называются smart -таблицами ( smart table ). Ниже приводится smart -кортеж, который соответствует упомянутому ранее предикату:

X 1    X ₂     X ₃

[ < X ₂    *      ^ t ]

.

Обозначение фиктивной компоненты “*” используется здесь для указания того факта, что на месте переменной X 2 может находиться любое значение из домена данной переменной. Стоит заметить, что до введения понятия « smart -таблица» подобные структуры рассматривались автором в работе [16].

2    Представление исходной задачи удовлетворения ограниченийс использованием smart-таблиц D-типа и организация логического вывода

Из приведённых примеров compressed -таблиц и smart -таблиц видно, что эти структуры хорошо подходят для моделирования дизъюнктивных нормальных форм логических формул.

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

Пример 1 . Имеется следующее продукционное правило: «Если человеку больше 65 лет и у него имеется основной диагноз, отнесённый к списку М ={сахарный диабет, заболевания органов дыхания, сердечно-сосудистые заболевания}, то риск заражения COVID-19 оценивается как высокий».

Для формализации данного правила в виде ограничения введены три переменные: X -целочисленная переменная, обозначающая возраст человека и имеющая домен [0, 150]; Y -переменная, обозначающая основной диагноз человека и принимающая возможные значения из списка возможных медицинских диагнозов; Z - переменная, обозначающая риск заражения и принимающая значения из множества { a - высокий, b - низкий, c - средний}.

На языке логических формул данное ограничение может быть представлено следующим образом: ( X> 65) л ( Y е M) ^ ( Z = a ).

Раскрытие в данном выражении импликации приводит к записи: ( X <  65) v ( Y е M v ( Z = a ).

С помощью smart -таблиц это ограничение может быть представлено так:

XYZ

"< 65   *      *

• *    е м *

• *     * Z = a

.

Данное табличное представление при трёх значащих компонентах содержит шесть фиктивных компонент “*”. В данном иллюстративном примере видно, что использование табличных ограничений известных типов является нерациональным с точки зрения компактного представления данных.

Для эффективной обработки качественных ограничений предлагается использовать новый тип представления ограничений, а именно, smart-таблицы D - типа.

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

Автору не известны работы, где в контексте решения задач удовлетворения ограничений рассматривались бы структуры, подобные предлагаемым smart -таблицам D -типа.

Представленное выше правило может быть смоделировано следующей smart -таблицей D -типа:

XYZ

] < 65 е M = a [ .

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

Пример 2 . Пусть имеется три вещественных переменных X , Y, Z, домены переменных равны интервалу целых чисел “[1,4]”, также задан следующий набор правил (семантика правил несущественна):

• 1.    ( X е {2,3}) л ( Y > X ) ^ ( Z = 4);

• 2.    ( X е {2,3}) л ( Y < X ) ^ ( Z = 2);

• 3.    ( X е {2,3}) л ( Y ^ X ) ^ ( Z = 3).

Путём избавления от импликации в формулах получены следующие дизъюнкты:

• 1.    ( X е {2,3}) v ( Y < X ) v ( Z = 4);

• 2.    ( X е {2,3}) v ( Y > X) v ( Z = 2);

• 3.    ( X е {2,3}) v ( Y = X ) v ( Z = 3).

Пусть в дополнение к уже заданным ограничениям для переменных X и Y заданы следующие унарные ограничения: X =3, Y=3.

Этот набор ограничений может быть представлен в виде следующей smart -таблицы D -типа.

X	Y	Z	YX
^ {2,3}	0	= 4	<	■
^ {2,3}	0	= 2	^
^ {2,3}	0	= 3	=
= 3	0	0	0
0	= 3	0	0

.

Символ « 0» обозначает компоненту, не содержащую ни одного значения. Каждая строка данной таблицы соответствует некоторому дизъюнкту.

Отличительной особенностью предлагаемых smart -таблиц D -типа по сравнению с обычными таблицами и compressed -таблицами является наличие составных атрибутов в заголовке матрицы (схеме отношения). Значениями компонент составных атрибутов могут быть отношения из предопределённого множества. В приведённой в качестве примера таблице имеется составной атрибут YX , в качестве компонент могут выступать все возможные отношения сравнения на паре атрибутов Y и X , а именно: {>, <, =, #, <, >}.

При организации рассуждений на данных структурах ключевым понятием является понятие кванта информации. Квант - это совокупность значений переменной, рассматриваемая как единое целое: все значения одного кванта элиминируются из домена или компоненты одновременно. Множество квантов для некоторого домена представляет собой разбиение соответствующего домена или компоненты. Процедуру квантования можно показать на примере 2. Домен переменной YX разбивается на три кванта . Первым квантом является отношение “ Y”, вторым квантом - отношение “Y=X\ третьим - отношение “Y>X”. С помощью данной совокупности квантов может быть представлено любое из отношений {>, <, =, ≠, ≤, >} для переменных (Y, X). Для простых атрибутов X, Y, Z с дискретными областями определения в качестве квантов можно взять элементы домена, то есть значения {1, 2, 3, 4}.

Результат квантования всей представленной выше матрицы можно записать с использованием секционированных булевых векторов:

X	Y	Z	YX
1,2,3,4.	1,2,3,4.	1,2,3,4.	< , = , >
10 0 1.	0 0 0 0.	0001.	10 0 ■
10 0 1.	0 0 0 0.	0 10 0.	0 11
10 0 1.	0 0 0 0.	0 0 10.	0 1 0
0 0 10.	0 0 0 0.	0 0 0 0.	0 0 0
0 0 0 0.	0 0 10.	0 0 0 0.	0 0 0

Во второй строке заголовка таблицы перечислены обозначения квантов. Данная матрица показывает как производится разложение каждой компоненты на кванты. Например, четвёртая компонента второй строки 011 соответствует отношению “>”. Данный булев вектор показывает, что: “ Y > X” = “ Y>X” u “ Y = X”.

Любой метод решения задачи CSP содержит в себе две компоненты: компоненту, реализующую поиск, и компоненту, реализующую распространение ограничений (логический вывод на ограничениях). Как правило, в качестве компоненты, реализующей поиск, выступает один из методов поиска в глубину с возвратами. Вывод на ограничениях сводится к усечению областей определения переменных и характеризуется полиномиальной временной сложностью. Компонента, реализующая вывод, разрабатывается отдельно под каждый тип ограничений. В случае smart-таблиц D-типа, помимо редуцирования доменов переменных, в результате вывода на ограничениях удаляются некоторые строки, столбцы, компоненты, значения компонент таблиц. Вывод на ограничениях, представленных в виде smart-таблиц D-типа, предлагается осуществлять с использованием следующих утверждений.

Утверждение 1 ( У1 ). Если хотя бы одна строка smart -таблицы D -типа пуста (содержит все пустые компоненты), то таблица пуста (соответствующая система ограничений несовместна, задача CSP не имеет решения).

Утверждение 2 ( У2 ). Если все компоненты некоторого атрибута пусты, то данный атрибут можно удалить из smart -таблицы D -типа (удаляются все компоненты, стоящие в соответствующем столбце, а пара “переменная-домен переменной” сохраняется в вектор частичного решения).

Утверждение 3 ( У3 ). Если в smart -таблице D -типа есть строка ( smart -кортеж), содержащая лишь одну непустую компоненту, то все кванты, не входящие в эту компоненту, удаляются из соответствующего домена.

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

Утверждение 5 ( У5 ). Если компонента атрибута smart -таблицы D -типа содержит квант, не принадлежащий соответствующему домену, то этот квант удаляется из компоненты.

Утверждение 6 ( У6 ). Если в smart -таблице D -типа усечён один или несколько доменов простых атрибутов, которые формируют некоторый составной атрибут, домен составного атрибута должен быть конкретизирован с учётом новых доменов простых атрибутов: из домена составного атрибута исключаются кванты, которые обращаются в пустое множество при новых доменах соответствующих простых атрибутов.

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

Поскольку две последних строки таблицы в нашем примере содержат по одной непустой компоненте каждая, то в процессе распространения ограничений, согласно У3 , новые домены переменных X и Y становятся равными множеству {3} . Строки с номерами 4 и 5 удаляются из рассматриваемой таблицы после применения У4 . Далее осуществляется “настройка” компонент первого столбца на новый домен переменной X. Согласно У5 , из компонент первого столбца удаляются все значения, поскольку они не содержатся в новом домене. Таким образом, все компоненты первого столбца становятся пустыми, и столбец можно исключить из рассмотрения, пользуясь У2 . По тем же причинам из рассмотрения исключается столбец Y . Дальнейшие вычисления связаны с особенностями обработки сложного атрибута YX : поскольку конкретизировались домены переменных X и Y , то согласно У6 должна быть выполнена следующая проверка для сложного атрибута YX : требуется выяснить, какое из отношений-квантов {<, =, >} перестало выполняться после того, как были уточнены домены простых атрибутов. Ненарушенным оказывается только отношение-квант “ Y=X\ Тогда домен сложного атрибута YX “сужается” до отношения “ Y=X ” и, пользуясь У5 , можно исключить лишние значения (кванты) из компонент соответствующего столбца:

Z YX

• 1,2,3,4 =

"= 4 0"

= ² = .

= 3 =

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

Далее, по У4 исключаются из рассмотрения строки 2 и 3. Теперь первая строка содержит только одну непустую компоненту (в атрибуте Z). Тогда, согласно У3 , новый домен атрибута Z будет равен одноэлементому множеству {4} (переменная Z равна 4). Затем, согласно У4 , вычеркивается из матрицы первая строка. Строк в матрице более не остаётся: они все были вычеркнуты без образования пустых строк (строк, состоящих лишь из пустых компонент). Это является признаком успешного окончания процесса редукции с получением решения поставленной задачи CSP. Окончательные значения атрибутов: X= 3, Y =3, Z=4. В процессе вывода конкретизировались значения всех простых атрибутов.

3 Моделирование знаний с помощью smart-таблиц нового типа

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

Пример 3 . Ограничение Permutation ( x ₁, x ₂, ..., x_n ), задающее множество перестановок из n элементов, где элементы принадлежат множеству { a 1 , a ₂, ..., a n }, может быть представлено следующим образом:

X1      X2     ...

=a1       = a1       ...

= a 2       = a 2       ...

...                ...               ......

= a       = a       ...

n               n ...

Представление того же самого отношения в виде таблиц С-типа слишком громоздко и сводится к явному перечислению всех возможных перестановок.

Ограничение Permutation(x 1, x2, ..., xn) можно рассматривать как частный случай глобального ограничения Alldiff(x 1, x2, ..., xn), когда домены всех переменных равны одному и тому же множеству, и количество переменных совпадает с суммарным количеством возможных значений для этих переменных. Следует заметить, что и в общем случае ограничение Alldiff(x 1, x2, ..., xn) также может быть успешно смоделировано с помощью предложенных smart-таблиц D -типа.

Пример 4 . Глобальное ограничение NotAllEqual ( x ₁,..., x m ): 3 1 <  i , j <  m : x i # x j .

Данное ограничение может быть представлено с помощью smart -таблицы C -типа:

X 2 X 1   X 3 X 1 "^       *	...   X n X * 1 ...
•       ,	* ...
...             ... *        *	...       ... ...      ^

Сходным образом данное ограничение представлено в работе [10]. Однако подобную формализацию ограничения NotAllEqual ( x ₁, ... , x m ) нельзя признать удовлетворительной, поскольку в данном случае табличное представление содержит много фиктивных компонент.

Данное ограничение можно представить в виде smart -таблицы D -типа, состоящее из единственной строки:

X ₂ X 1   X 3 X 1     ...   X n X ,

] ^        ^          ...       ^ [ .

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

Пример 5. Задача кластерного анализа, где есть возможность учитывать знания о предметной области в форме пользовательских ограничений Constrained Clustering [17].

Пусть стоит задача разбить объекты { G 1 , G ₂, .„, G_n } на k <  n кластеров. В этом случае домены всех переменных равны множеству {1, .„, к }. Пусть критерием кластеризации служит нахождение разбиения с минимальным диаметром, где диаметр разбиения - это максимальный диаметр для всех кластеров разбиения. Диаметр кластера - это максимальное расстояние между любыми двумя точками, принадлежащими данному кластеру.

При поиске разбиения с минимальным диаметром для каждого i и j формулируется ограничение: ( G i = G j ) ^ ( D > d ij ) [6]. Это выражение равносильно ( G i # G j ) v ( D > d ij ), где d ij -константа, показывающая расстояние между точками i и j , D - переменная, обозначающая диаметр разбиения и принимающая значения из множества [ d_min , d_max ], причём d_min и d_max - минимальное и максимальные расстояния между парой объектов, принадлежащих множеству { G i , G 2 , ., G n } .

Данное ограничение может быть выражено в виде следующей smart -таблицы D -типа:

GiGj D

]*    ^ d ij [ .

Аналогичным образом может быть формализовано ограничение, которое задаётся в случае, если критерием кластеризации служит максимизация межкластерного расстояния ( split -критерий): ( 5 > d ij ) ^ ( G i = G j ) [17].

Здесь переменная S обозначает минимальное расстояние между точками двух различных кластеров, входящих в одно разбиение.

Пример 6 . Задачи Constraint-Based Scheduling, рассмотренные в [18]. Переменные, используемые для описания задач:

X ( A i , t ) - булевы переменные, служащие для указания исполняется (значение 1) или нет (значение 0) задача (работа, задание) A i в текущий момент времени t ;

start ( A i ) и end ( A i ) - обозначают моменты начала и окончания работы A i , изначальные домены переменных start ( A i ) и end ( A i ) равны соответственно [ r i , lst i ] и [ eet i , d i ], где lst i and eet i - наиболее позднее время начала и наиболее раннее время завершения задания A i ; [ r i , d i ] - временное окно, в которое должна быть выполнена работа A i .

В различных постановках задач Constraint-Based Scheduling используются различные виды качественных ограничений, которые могут быть представлены в форме smart -таблиц D -типа.

Например, ограничение Time-Table Constraint , представляющее собой условия на временное окно, в которое должно быть выполнено задание A i , записано так:

[ X ( A i , t ) = 0] л [ t <  eet i ] ^ [ start ( A i ) >  t ].

[ X ( A i , t ) = 0] л [ lst i <  t ] ^ [ end ( A i ) <  t ].

Оно сводится к совокупности логических импликаций и может быть легко представлено с помощью smart -таблиц D -типа.

Ограничение Disjunctive Constraint , которое предписывает, что два задания A i и A j не могут перекрываться по времени: [ end ( A i ) <  start ( A j )] v [ end ( A j ) <  start ( A i )], также представляет собой логическое выражение, легко моделируемое с помощью smart -таблиц D -типа.

Заключение

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

В статье предложен новый тип табличных ограничений, а именно smart -таблицы D -типа, а также приводятся правила эквивалентных преобразований данных таблиц, которые лежат в основе процедур редукции ограничений. За счёт новой интерпретации понятия «кортеж многоместного отношения» применение smart -таблиц D -типа позволяет в некоторых случаях существенно снизить потребление памяти компьютера по сравнению с известными типами табличных ограничений. В частности, smart -таблицы D -типа хорошо подходят для моделирования продукционных правил, некоторых типов логических выражений, а также некоторых типов глобальных ограничений.

Настоящее исследование выполнено при поддержке Российского фонда фундаментальных исследований (РФФИ), номера проектов 18-07-00615-а, 20-07-00708-а.