Труды КНЦ вып.29 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 3/2015(29))

Рассматриваемые матрицеподобные структуры можно рассматривать как недоопределенные расширения обычных отношений, поскольку их кортежи содержат в качестве значений множества, а не отдельные элементы. Ниже в кратком изложении приводятся методы решения CSP на основе матричного представления ограничений. Распространение ограничений и систематический поиск решений задачи CSP Согласно [1] задача удовлетворения ограничений определена множест­ вом переменных Х\, х2, ..., х„ и множеством ограничений С\, С2, ..., Ст. Каждая переменная хг имеет непустую область определения /), (область возможных значений, домен). Каждое ограничение Сг включает некоторое подмножество переменных и задает допустимые комбинации значений для этого под­ множества. Состояние задачи описывается как присваивание значений некото­ рым ( частичное присваивание) или всем переменным ( полное присваивание ): {Xj=Vj, Xj=Vj, ...}. Присваивание, не нарушающее никаких ограничений, назы­ вается допустимым присваиванием. Решением задачи CSP является полное присваивание, которое удовлетворяет всем ограничениям. Теперь кратко затронем один из методов вывода на ограничениях, моделируемых матрицами конечных предикатов [4]. В отличие от ранее разработанных в АК методов [9], в данном методе решение строится путем пошагового усечения доменов. Само решение представляется в виде сово­ купности доменов или установлении того факта, что все вершины дерева поиска являются тупиковыми. В отличие от имевшихся в АК методов “слепого” поиска, в предлагаемом методе широко применяются эвристики. При решении задач CSP дерево поиска можно представить, как дерево частичных присваиваний - это дерево, где каждая вершина соответствует некоторому частичному присваиванию. Корень дерева отвечает пустому присваиванию. В вершине ѵ выбирается лишь одна переменная, которой еще не было присвоено значение на предыдущих уровнях дерева поиска. Для выбора “наилучшего” преемника вершины дерева поиска необхо­ димо указать переменную, которой на текущем шаге следует присвоить значе­ ние, а также само присваиваемое значение, которое быстрее всего приводит к цели. Пусть ограничения задачи моделируются в виде некоторой D -системы. В предлагаемом методе выбор “наилучшего” преемника производится на основе следующих эвристик: 31. Выбирается атрибут D -системы с доменом, содержащим наименьшее количество значений, что позволяет проверять меньшее количество преемников. 32. В случае неоднозначности выбора, производимого согласно Э1, выбирается атрибут, количество непустых компонент которого максимально. 33. Для формирования нового одноэлементного домена выбирается наиболее часто встречающееся в соответствующем столбце D -системы значение атрибута. Само присваивание заключается в “настройке” D -системы на новый одноэлементный домен выбранного на текущем шаге атрибута с последующим 78