Интеграция методов поиска в ширину и логического вывода для удовлетворения табличных ограничений

Во многих системах искусственного интеллекта (ИИ) применяются методы логического анализа. Они активно развиваются в рамках такого направления ИИ, как программирование в ограничениях, которое основывается на декларативной парадигме представления знаний в форме задачи удовлетворения ограничений [1].

Задача удовлетворения ограничений описывается множеством переменных X1, X2,…, Xn и множеством ограничений С1, С2,…, Cm [2, 3]. Каждая переменная Xi имеет непустую область определения Di. Каждое ограничение Сi на некотором подмножестве переменных задаёт допустимые комбинации значений для этого подмножества. Решением задачи является полное присваивание значений всем переменным {X1 = v1,^, Xn = vn}, которое удовлетворяет всем ограничениям.

В настоящей работе рассматриваются задачи программирования в ограничениях, где переменные дискретны и определены на конечных множествах значений. Статья посвящена вопросам обработки табличных ограничений [4-14]. Простейшим примером табличных ограничений являются реляционные таблицы. В виде реляционных таблиц, содержащих множество выполняющих подстановок, может быть представлен любой конечный предикат. Такое эксплицитное представление для многих отношений нецелесообразно, поскольку приводит к экспоненциальному росту сложности процедур удовлетворения ограничений. Поэтому предпринимаются попытки разработать более компактное табличное представление качественных зависимостей, в частности были предложены такие виды табличных ограничений как compressed -таблицы ( compressed tables ) и smart -таблицы ( smart tables ) [8-14].

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

Некоторые исследования автора, посвящённые обработке табличных ограничений, описаны в [15, 16], подробный анализ приведён в [17].

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

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

• 1    Табличные ограничения для представления знаний

В работе [17] предложено рассматривать следующие виды табличных ограничений: обычная реляционная таблица, compressed таблица, basic smart таблица, smart таблица. Smart таблицы являются обобщением всех названных типов табличных ограничений. Smart таблицы предложено подразделять на структуры С - и D -типа. Smart -таблицы могут в своей схеме содержать не только простые, но и составные атрибуты, значениями которых являются отношения из предопределённого множества. Smart -таблицы С -типа соответствуют дизъюнктивным нормальным формам логических формул с элементарными одно и двуместными предикатами, а smart -таблицы D -типа соответствуют конъюнктивным нормальным формам таких формул.

В настоящей работе при записи содержимого smart -таблиц используются две фиктивные компоненты: полная компонента (обозначается « * ») - это множество, равное домену соответствующего (по месту её расположения в кортеже) атрибута; пустое множество - 0 .

Smart -таблица С -типа записывается в виде матрицы, ограниченной прямыми скобками.

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

составляет 35 долларов, при этом должно быть закуплено больше 15 единиц товара 1 и столько же единиц товара 2, либо цена товара 1 равняется 50 долларам, в противном случае.

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

(X! > 15) л(X1 = X2)л(С = 35) v (X1 < 15)л(С = 50) v (X1 * X2)л(С = 50), где Xi - количество закупаемого товара 1, X1 е [0, 111]; X2 - количество закупаемого товара 2, X2 е [0, 250]; C - цена товара, C е {35, 50}.

Данное ограничение в виде smart -таблицы С -типа запишется так:

> 15

T [ X 1 , X 2 , C , X 1 X 2 ] =

< 15

*

* {35} =

* {50} *

* {50} *

Каждая строка этой smart -таблицы соответствует некоторому дизъюнкту приведённой логической формулы. Данная smart -таблица содержит в описании своей схемы составной атрибут XX 2 , доменом которого является множество бинарных отношений {=, #}.

Как видно из примера 1, c помощью smart -таблиц С -типа удобно представлять дизъюнктивные нормальные формы (ДНФ) конечных предикатов.

С помощью smart -таблиц D -типа моделируются коньюнктивные нормальные формы (КНФ) конечных предикатов. Содержимое smart -таблицы D -типа заключается в перевёрнутые прямые скобки. Smart -таблицы D -типа позволяют легко вычислять дополнение smart -таблиц С -типа относительно заданного универсума: требуется взять дополнение каждой компоненты smart -таблицы. Например, дополнением smart -таблицы T [ X 1 , X 2 , C , XX ₂] является smart -таблица D -типа:

T [ X 1 , X 2 , C , X 1 X 2 ] =

< 15 0 {50}   *

> 15 0 {35} 0

0  0   {35}   =

Smart -таблицу D -типа T можно представить в виде:

[( X , <  15) л ( X ₁ * X ₂ ) л ( С = 50)] v [( X , >  15) л ( С = 35)] v [( X ₁ = X ₂ ) л ( С = 35)],

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

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

	< 15	0
T [ X 1 , X 2 , C , X 1 X 2 ] =	> 15	0
	0	0

{50} *

{35} 0

{35}   =

> 15

*

< 15 *   *

*    * {50}

***

*

*

*

⨝

*	*	*	⨝	- *	*
*	{35}	*		_ *	*

{35} *

*

< 15 *

> 15 *

**

{35} *

{50} =

{35} *

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

Результирующая smart -таблица С -типа «сжато» описывает множество всех выполняющих подстановок КНФ, которая представлена исходной smart -таблицей D -типа. Элементарные подстановки легко получить, рассматривая в отдельности каждую строку smart -таблицы С -типа. Поскольку рассматриваемая smart -таблица является дополнением smart -таблицы T , то она описывает запрещённые комбинации количества товаров и цен. В частности, из первой строки результирующей smart -таблицы С -типа следует, что товар 1 не может быть закуплен по цене 35 долларов, если его количество меньше 15 штук.

Иллюстрацией того, как выполняется соединение smart -таблиц C -типа, может служить соединение второй и третьей таблиц в приведённом выражении (1):

> 15	*    *    * 1	⨝	" * *	{35}	*
*	* {35} * _		* *	*	=

’> 15	*	{35}	* 1
> 15	*	*	=
*	*	{35}	*
*	*	{35}	=

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

Так решается задача нахождения множества всех выполняющих подстановок КНФ конечного предиката. В таком виде решение задачи оказывается слишком трудоёмким.

Одним из методов ускорения вычислений может служить ортогонализация, основанная на известном соотношении Порецкого: A v B = A v AB [3].

В частности, справедливы соотношения:

Соединение этих двух ортогонализованных smart -таблиц C -типа имеет вид:

* *1		г * * {35} * 1		-> 15 * {35}  *
	⨝		=	> 15 * {50} =
{35} * _		* * {50} =
				< 15 * {35} *

-> 15  *    *    * 1 -> 15  *    *    * 1  г *  *  {35}  * I г *  * *    *  {35}   * ~ <  15  *  {35}  * ’ *  *    *     = " *   *

{35}  * 1 {50} =_

> 15 *

< 15 *

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

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

Следует отметить, что:

-> 15	*	{35}	* 1		-> 15	* {35}	* 1
>15	*	*	—
				=	> 15	* {50}	=
*	*	{35}	*		< 15	* {35}	*
*	*	{35}	=.

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

Установлены следующие правила редукции для случая smart -таблиц C -типа, позволяющие удалять отдельные «лишние» значения из доменов атрибутов, компонент smart -таблицы, а также исключать из рассмотрения целые строки и столбцы.

Утверждение 1 (У1). Если все строки smart -таблицы C -типа пусты, то есть содержат хотя бы по одной пустой компоненте каждая, то smart -таблица пуста.

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

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

Утверждение 4 (У4). Если строка smart -таблицы C -типа содержит хотя бы одну пустую компоненту (строка пуста), то строка удаляется.

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

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

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

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

Утверждение 9 (У9). Если усечён домен составного атрибута, то должны быть изменены и домены соответствующих простых атрибутов с учётом вновь выведенного домена составного атрибута.

Аналогичные правила редукции для случая smart -таблиц D -типа приведены в [17].

• 2    Предлагаемый метод

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

На каждом шаге поиска предлагается выбирать пару smart -таблиц С -типа таким образом, чтобы максимально сократить область поиска. При выборе smart -таблиц для соединения используется следующая эвристика, заимствованная из работы [18]:

J ( K [ 5 ], T[ R ]) = | K [ 5 ]| х | T R ]| х | S \ R | х | R \ S |, где K [ S ] - первая из пары выбираемых smart -таблиц, T [ R ] - вторая из пары smart -таблиц, выбираемых на текущем шаге поиска, S - схема (набор атрибутов) smart -таблицы K , R - схема (набор атрибутов) smart -таблицы T . Запись | K [ S ]| обозначает число (элементарных) кортежей данной smart -таблицы С -типа.

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

Значения функции J ( K [ S ], T [ R ]) могут значительно отличаться в зависимости от трактовки понятия «кортеж smart -таблицы C -типа». Можно в качестве кортежей smart -таблицы C -типа рассматривать: а) smart -кортежи (строки smart -таблицы); б) элементарные кортежи, получающиеся при преобразовании smart -таблицы в обычную таблицу.

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

Чтобы оценить, какая из трактовок понятия «кортеж smart -таблицы C -типа» позволяет лучше осуществлять выбор пары соединяемых smart -таблиц на шаге поиска, рассмотрен пример.

Пример 2. Пусть имеется smart -таблица, заданная в S = X ₁ х X ₂ х X ₃ х X 4 = {1, 2, 3, 4, 5}:

1	{2,3}	0	{1,2,3}	0
2	!2)	{1,2,5}	{4}	0
з	0	{1,2,4}	{3,4}	{3,5}
4	{I,2}	{3,4,5}	0	{3}
5	0	0	{1,5}	{4}
6	0	{2,3}	{1,2,3}	{1}
7	{2,4,5}	0	{3,5}	{3,5}
8	{5}	0	{2,3,4}	{1,3,4}
9 _	{1,3}	0	{4,5}	0

Данная smart -таблица D -типа может быть представлена как соединение следующих smart -таблиц С -типа:

K i [ X i X з ] М K 2 [ X i X 2 X з ] М K з [ X 2 X з X 4 ] М K 4 [ X 1 X 2 X 4 ] М K 5 [ X з X 4 ] М K б [ X 2 X з X 4 ] М

K7[Xi Xз X4] М Kз[Xi Xз X4] М K9[Xi Xз], где

K 1 [ X 1 X з ] =

{2,3} {1,4,5}

*

{1,2,з}

K 2 [ X 1 X 2 X 3 ] =

{2} {1,3,4,5} {1,3,4,5}

*

*

K 4 [ X ₍ X 2 X 4 ] =

K 6 [ X 2 X 3 X 4 ] =

{1,2,5} {3,4}

{1,2}

{3,4,5}

{3,4,5}

{2,3}

{1,4,5}

{1,4,5}

*

*

{4}

*

{3, 4,5} {1, 2}

*

K 8 [ X 4 X 3 X 4 ] =

, K з [ X 2 X 3 X 4 ] =

*

*

{3}

{1,2,3} {4,5}

*

{1}

{5}

{1,2,3,4}

{1,2,3,4}

*

{2,3,4} {1,5}

{1,2,4} {3,5} {3,5}

, K 5 [ X 3 X 4 ] =

, K 7 [ X 4 X 3 X 4 ] =

*

*

{1,3,4}

*

*

{3, 4}

{1, 2,5}

*

,

{3,5}

{1,5}     *

{2,3,4} {4} _ ,

{2,4,5} {1,3} {1,3}

, K 9 [ X 4 X 3 ] =

*

*

{3,5} {2,4,5}

{1,3}

*

,

{3,5}

*

{2,4,5} {4,5}

.

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

Элементарный шаг поиска заключается в том, что сначала выполняется соединение двух smart -таблиц С -типа, выбор которых осуществляется согласно приведённой выше эвристике, а затем выполняется процедура распространения ограничений.

Для двух упомянутых интерпретаций понятия «кортеж smart -таблицы C -типа» значения эвристической функции для каждой пары соединяемых на первом шаге поиска smart -таблиц представлены в таблицах 1 и 2.

Таблица 1- Оценка размерности результирующего отношения после выполнения первого шага поиска для варианта с элементарными кортежами

	K 1	K 2	K 3	K 4	K 5	K 6	K 7	K 8	K 9
K 1
K 2	0
K 3	4066	9951
K 4	3838	9393	10807
K 5	247	2418	0	2626
K 6	3838	9393	0	10201	0
K 7	0	9951	11449	10807	0	10807
K 8	0	10137	11663	11009	0	11009	0
K 9	0	0	3424	3232	208	3232	0	0

Таблица 2 - Оценка размерности результирующего отношения после выполнения первого шага поиска для варианта со smart -кортежами

	K 1	K 2	K 3	K 4	K 5	K 6	K 7	K 8	K 9
K 1
K 2	0
K 3	12	9
K 4	12	9	9
K 5	4	12	0	12
K 6	12	9	0	9	0
K 7	0	9	9	9	0	9
K 8	0	9	9	9	0	9	0
K 9	0	0	12	12	4	12	0	0

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

Таблица 3 - Фактическая размерность результирующего отношения после соединения пары smart -таблиц на первом шаге поиска

	K 1	K 2	K 3	K 4	K 5	K 6	K 7	K 8	K 9
K 1
K 2	207
K 3	2056	1644
K 4	1076	1380	1660
K 5	141	916	153	1036
K 6	2404	1444	255	1612	150
K 7	234	1596	1876	1732	165	1660
K 8	249	1696	1964	1764	147	1796	279
K 9	20	180	1384	1312	132	1120	186	204

Из анализа таблицы 1 и 2 следует, что при обеих интерпретациях понятия «кортеж smart - таблицы C » значение «ноль» эвристической функции соответствует одним и тем же парам соединяемых smart -таблиц. Для вычисления таблицы 1 требуется гораздо больше арифметических операций. Основанием для использования в качестве мощности smart -таблицы количества её smart -кортежей, а не элементарных кортежей, состоит в том, что минимальному (максимальному) значению в таблице 2 соответствует минимальное (максимальное) значение в таблице 3.

С применением предложенной эвристики выбраны для соединения smart -таблицы, имеющие одинаковые схемы: K 1 [ X i X ₃] и K ₉[ X i X 3 ]. Результат их соединения представлен так:

K i [ X i X j ] М K 9 [ X i X j ] =

{2,3}      * м   ^{1’^3}      *

{1,4,5} {1,2,3} J   L {2,4,5}  {4,5}

{3}

{2}

{1}

*

{4,5} {1,2,3}

Согласно утверждениям У1-У8 можно «сузить» домен переменной X ₁ до множества {1, 2, 3}, «просуммировав» значения первого столбца smart -таблицы K ₁[ X _l X ₃] М K ₉[ X _l X ₃].

Теперь следует произвести «настройку» остальных smart -таблиц C- типа ( K ₁ - K ₈) на новый домен переменной X ₁. На текущем шаге поиска получаются следующие домены переменных и набор smart -таблиц.

Домены : X 1 - {1, 2, 3}, X 2 - {1, 2, 3, 4, 5}, X 3 - {1, 2, 3, 4, 5}, X 4 - {1, 2, 3, 4, 5}.

Ограничения :

K 1 [ X 1 X 3 ] М K 9 [ X 1 X 3 ] =

:Н: ОДЗЯ [ {2,3}   {4,5} J

K 2 [ X 1 X 2 X 3 ] =	Г {2} _ {1,3}	* {1,2,5} {3,4}	* - * {4}	, K э [ X 2 X 3 X 4 ] =			Г {1,2 {3 _ {3}	}      * {3, 4} {1,2,5}	* * {3,5} _
K 4 [ X 1 X 2	X 4 ] =	Г {1,2} {3}	* {3,4,5}		* 1 *	, K 5 [ X 3 X 4 ] =		" {1,}     * - Z      -s i        4	,
		_ {3}	{1,2}		{3} _			[{2,3} {4}_

	" {2,3}      *      * "
K 6 [ X 2 X 3 X 4 ] =	{1}    {1,2,3}   * _ {1}     {4,5}    {1} _

	" {2}       *        *
K 7 [ X 1 X 3 X 4 ] =	{1,3}    {3,5}      * _ {1,3} {2,4,5} {3,5} _

K 8 [ X 1 X 3 X 4 ] =

{1,2,3}

{1,2,3}

{2,3,4} {1,5}

*

{1,3,4}

В smart -таблицах К 2 - K 7 были откорректированы первые столбцы, в smart -таблице К 8 удалена первая строка. Дальнейшие шаги процесса поиска выполняются по аналогии.

Заключение

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

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

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

Исследование выполнено при финансовой поддержке РФФИ в рамках научных проектов № 20-07-00708-а, 19-07-00359-а.