Труды КНЦ вып.18 (ОКЕАНОЛОГИЯ вып. 4/2013(18))

УДК 004.94 А.А. Зуенко ФГБУН Институт информатики и математического моделирования технологических процессов КНЦРАН Кольский филиал ПетрГУ УСКОРЕНИЕ АЛГОРИТМОВ ЛОГИЧЕСКОГО ВЫВОДА НА ОГРАНИЧЕНИЯХ* Аннотация В статье предлагается метод ускорения алгоритмов, применяемых при решении задач удовлетворения ограничений. Многие из упомянутых задач можно свести к поиску выполняющих подстановок некоторого конечного предиката. Метод опирается на ортогонализацию дизъюнктивных нормальных форм конечных предикатов и использует разработанные автором эвристики. Ключевые слова: алгебра кортежей, логико-семантический анализ, программирование в ограничениях, задача удовлетворения ограничений. А.А. Zuenko ACCELERATED ALGORITHMS OF LOGICAL INFERENCE ON CONSTRAINTS Abstract In the paper we propose a method of acceleration algorithms applied to solving constraint satisfaction problems. A lot of these problems could be reduced to finding of satisfying substitutions for a finite predicate. The method is based on the orthogonalization of the disjunctive normal form of finite predicate and uses heuristics developed by the author. Keywords: n-tuple algebra, logical-semantic analysis, constraints programming, constraint satisfaction problem. Введение В современном программировании можно выделить несколько основных парадигм: императивное или алгоритмическое программирование, логическое программирование, функциональное программирование и др. Важное место в этом ряду занимает программирование в ограничениях (constraint programming) [13- Программирование в ограничениях как самостоятельное научное направление сложилось в конце 60-х - начале 70-х годов прошлого века. Примечательно, что первыми приложениями были задачи обработки изображений и параметрического моделирования пространственно-двумерных сцен. С тех пор направление существенно эволюционировало, охватывая новые классы задач, начиная от решения судоку и ребусов и заканчивая решением *Работа выполнена при финансовой поддержке РФФИ (проекты №№ 11-08-00641, 12-07-00550-а, 12-07-00689-а, 13-07-00318-а), ОНИТ РАН (проект 2.3 в рамках текущей Программы фундаментальных научных исследований) и Президиума РАН (проект 4.3 Программы № 16). 110