Труды КНЦ (Технические науки вып.3/2025(16))

После постановки объекта W необходимо определить допустимую область для объектов Y, Z. Область для Y: Координаты области: Xd = 44MOD 10 = 4 ; Yd= 44 D IV 10 = 4 ; X i f = 4 - 1 - 0 = 3 ;X g t = 4 + 2 + 0 = 6; Ytop = 4 - 2 - 0 = 2; Ybottom= 4 + 2 + 0 = 6. Клетки области p s =y х widthg + x, где x е [3, 6], y е [2, 6], показаны на рисунке ниже (рис. 11). Область для Z: Координаты области: X d = 44 MOD 10 = 4; Yd = 44 DIV 10 = 4; XUft= 4 - 2 - 1= 1; X nght = 4 + 2 + 1 = 7; Ytop = 4 - 1 - 1 = 2; Ybottom= 4 + 2 + 1 = 7. Клетки области p s =y х widthg + x, где x е [1, 7], y е [2, 7], показаны на рисунке выше (рис. 12). Полученные области становятся доменом переменных и могут содержать значения, которые не удовлетворяют ограничению GDConstaint, но они будут удалены при распространении ограничения GDConstaint. Труды Кольского научного центра РАН. Серия: Технические науки. 2025. Т. 16, № 3. С. 117-130. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2025. Vol. 16, No. 3. P. 117-130. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 Рис. 11. Область допустимых значений Рис. 12. Область допустимых значений для переменной Y для переменной Z Программная реализация Процедура решения рассматриваемой в работе задачи удовлетворения ограничений была реализована с применением библиотеки программирования в ограничениях Choco на языке программирования Java. Реализация включала формализацию переменных, их доменов и системы ограничений средствами используемой библиотеки. Поиск решений задачи выполнялся стандартными для решателя стратегиями поиска с возвратом, а распространение ограничений осуществлялось с применением оригинальных процедур вывода, разработанных в ходе исследований. При ветвлении в качестве переменной выбиралась переменная с наименьшим размером домена, а значения переменной выбирались по порядку. Для каждого ограничения был реализован свой класс-распространитель. Ниже показана общая схема работы программы (рис. 13). Программа имеет пользовательский интерфейс, внутри которого пользователь создает пространство (рис. 14), объекты (рис. 15) и задает для них ограничения (рис. 16). После на основе полученных данных формируется задача в рамках модели Choco. Первым этапом поиска решений является первичное распространение, которое удовлетворяет унарные ограничения, сокращает домены переменных, сужая пространство поиска, и в некоторых случаях позволяет сразу определить, что решений нет. Если первоначальное распространение не выявило противоречий в задаче, то запускается ветвление. Среди переменных, у которых не определено значение, выбирается та переменная, у которой размер домена минимален. Значения переменной выбираются по порядку. После ветвления запускается распространение для сокращения доменов неопределенных переменных. В результате распространения проверяется текущее состояние системы. У каждого ограничения есть параметр ESat , который принимает одно из трех значений: ESat.TRUE — если ограничение удовлетворено; ESat.FALSE — если ограничение не может быть удовлетворено на данной ветви поиска; ESat.UNDEFINED — если ограничение пока не удовлетворено. © Таран П. В., Зуенко А. А., 2025 125