Труды КНЦ вып.124 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 5/2014(24))

А.А. Зуенко1,2, А.А. Апмаматов 1 1Институт информатики и математического моделирования технологических процессов Кольского НЦ РАН 2Кольский филиал Петрозаводского государственного университета УДК 004.832 ПРОГРАММИРОВАНИЕ В ОГРАНИЧЕНИЯХ НА ЯЗЫКЕ PYTHON С ПРИМЕНЕНИЕМ СТРУКТУР И АЛГОРИТМОВ АЛГЕБРЫ КОРТЕЖЕЙ* Аннотация В статье рассмотрены особенности существующих подходов к решению задач удовлетворения ограничений. Для решения подобных задач авторами предлагается применять методы локального поиска на основе анализа структур алгебры кортежей. Приводится сравнение предыдущей версии библиотеки алгоритмов алгебры кортежей, реализованной на языке C++, и текущей версии библиотеки, разработанной на языке Python. Описаны преимущества исполь­ зования интерпретируемых языков для создания среды программирования в ограничениях, представимых в структурах алгебры кортежей. Ключевые слова: программирование в ограничениях, алгебра кортежей, методы локального поиска, интерпретируемый язык программирования. А.А. Zuenko, А.А. Almamatov CONSTRAINT PROGRAMMING BASED ON USING LANGUAGE PYTHON AND PROPOSED STRUCTURES AND ALGORITHMS OF N-TUPLE ALGEBRA Abstract The article describes the features of the existing approaches to solving constraint satisfaction problems. To solve these problems the authors propose to use local search methods based on the analysis of the n-tuple algebra structures. The comparison of the previous version of the library of n-tuple algebra algorithms, implemented in С ++, and the current version of the library, developed in Python, is given. The advantages of using interpreted languages for creating an environment of constraint programming that can be represented in the n-tuple algebra structures is considered. Keywords: constraint programming, n-tuple algebra, local search methods, interpreted programming language. Введение Задача удовлетворения ограничений (CSP) - это тройка ( V, D, С), где ( 1 ) Ѵ= {ѵі, ..., ѵ„} - множество переменных; (2) D = {Di, ..., Dn} - множество доменов; каждый домен Д - конечное множество, содержащее возможные значения, соответствующей переменной; (3) С = {С 1 , ..., С„} - множество ограничений. *Работа выполнена при финансовой поддержке РФФИ (проекты №№12-07-00550-а, 14-07-00205-а, 14-07-00256-а). 158