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

УДК 004.832 A.A. Зуенко, A.A. Апмаматов Институт информатики и математического моделирования технологических процессов Кольского НЦ РАН ПРИМЕНЕНИЕ МЕТОДОВ ЛОКАЛЬНОГО ПОИСКА ПРИ РЕШЕНИИ ЗАДАЧ УДОВЛЕТВОРЕНИЯ ОГРАНИЧЕНИЙ* Аннотация В статье приводится определение задачи удовлетворения ограничений. Рассматриваются особенности методов локального поиска, которые могут быть применены при решении задачи удовлетворения ограничений. Проанали­ зированы недостатки существующих алгоритмов систематического поиска, использующих матричное представление конечных предикатов. Сделан вывод о целесообразности исследования свойств рассматриваемых матриц с целью ускорения стандартных алгоритмов локального поиска. Ключевые слова: задача удовлетворения ограничений, программирование в ограничениях, методы локального поиска. A.A. Zuenko, A.A. Almamatov USING OF LOCAL SEARCH METHODS FOR SOLVING CONSTRAINT SATISFACTION PROBLEM Abstract In the article the definition of constraint satisfaction problem is given. The features of the approaches for solving constraint satisfaction problems are described. Disadvantages of existing systematic search algorithms using matrix representation of finite predicates are analyzed. It is drawn a conclusion about necessity of investigation of features of mentioned above matrices. The goal of the investigation is to accelerate typical local search algorithms. Keywords: constraint satisfaction problem, constraint programming, local search methods. Введение Задача удовлетворения ограничений (ЗУО) определяется множеством дискретных переменных Ѵ= {х\, ... , х„}, для каждой из которых задана область определения или домен /.). = { d: 1 ;і. ... , cl/1’0} (j = 1. .... n). и множеством ограничений. Ограничением называется пара ( R , S ), где R - отношение, определенное на диапазоне S. ЗУО может рассматриваться как тройка ( V. 1). ('). где Ѵ= {х, .... х„} - множество переменных, D = {Z)b ..., D n} - множество доме­ нов переменных, С = {Сь ... , Ст} - множество ограничений. Решением ЗУО называется присваивание значений всем переменным, которое удовлетворяет всем ограничениям. Целью решения ЗУО может быть нахождение одного или всех решений. Работа выполнена при финансовой поддержке РФФИ (проекты №№ 14-07-00205-а, 14-07-00256-а). 59