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

2. Обзор глобальных ограничений наиболее популярных библиотек программирования в ограничениях diffn(X, Y, DX, DY) - ограничение задает условие, что прямоугольники, заданные координатами угла (X[i],Y[i]) и длинами сторон DX[i] и DY[i] не перекрываются [3]. Пример 1: Пусть X1 6 {1, 2, 3}, X 2 6 {1, 2, 3}, X 3 6 {1, 2}, X 4 6 {1, 2, 3}, DX = {2, 3, 1, 4}, Y 1 6 {1, 2, 3}, Y 2 6 {2, 3}, Y 3 6 {1, ..., 4}, Y 4 6 {1, 2, 3}, DY = {3, 2, 4, 1}, тогда всеми решениями, удовлетворяющими ограничению diffn({X\, X 2 , X3, X 4 },{Y 1 , Y 2 , Y 3 , Y 4 }, DX, DY) будут (рис. 1): 1. X 1 = 1, X 2 = 3, X 3 = 1, X 4 = 3, Y 1 = 1, Y 2 = 2, Y 3 = 4, Y 4 = 1. 2. X 1 = 1, X 2 = 3, X 3 = 2, X 4 = 3, Y 1 = 1, Y 2 = 2, Y 3 = 4, Y 4 = 1. 3. X 1 = 1,X 2 = 3 ,X 3 = 1,X 4 = 3, Y 1 = 1, Y 2 = 3, Y 3 = 4, Y 4 = 1. 4. X 1 = 1, X 2 = 3, X 3 = 1, X 4 = 3, Y 1 = 1, Y 2 = 3, Y 3 = 4, Y 4 = 2. 5. X 1 = 1,X 2 = 3 ,X 3 = 2 ,X 4 = 3, Y 1 = 1, Y 2 = 3, Y 3 = 4, Y 4 = 1. 6 . X 1 = 1, X 2 = 3, X 3 = 2, X 4 = 3, Y 1 = 1, Y 2 = 3, Y 3 = 4, Y 4 = 2. Рис. 2. Визуализация решений задачи Это ограничение имеет реализацию в популярных системах(библиотеках) программирования в ограничениях (таблица 1 ). Таблица 1. Реализация ограничения diffn в популярных библиотеках Constraint Programming Библиотека Choco GeCode JaCoP MiniZinc Имя ограничения diffN nooverlap diffldiff 2 diffn among(n, V, T) - ровно n переменных из множества переменных V должны принимать значения из множества значений T [3]. 72