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

Таблица 17. Реализация ограничения knapsack в популярных библиотеках Constraint Programming Библиотека Choco GeCode JaCoP MiniZinc Имя ограничения knapsack linear Knapsack knapsack connected(FROM, TO, NS, ES) - ограничение задает условие, что в ориентированном графе, состоящем из i ребер (FROM[i], TO[i]), подграф, описанный булевыми массивами NS и ES, является связным. dag ( FROM , TO , NS , ES ) - ограничение задает условие, что в ориентированном графе, состоящем из i ребер (FROM[i], TO[i]), подграф, описанный булевыми массивами NS и ES, является ациклическим. path(FROM, TO, s, t, NS, ES) - ограничение задает условие, что в ориентированном графе, состоящем из i ребер (FROM[i], TO[i]), есть путь из точки s в точку t . Путь описывается булевыми массивами NS и ES , указывающими содержится ли NS[i] узел и ES[i] ребро графа в искомом пути. tree(FROM, TO, r, NS, ES) - ограничение задает условие, что в неориентированном графе, состоящем из i ребер ( FROM [ i ], TO [ i ]), подграф, описанный булевыми массивами NS и ES, является древом с корнем г. regular(V, fa) - ограничение задает условие, что последовательность значений переменных V соответствует условиям перехода, описанным в конечном автомате fa. table(V, T, alg) - ограничение задает условие, что значения переменных V принимают значения одного из кортежей T, если кортежи объявлены истинными, либо не должны их принимать, если кортежи объявлены ложными. Для этого ограничения разработан ряд алгоритмов фильтрации таких как CT+, GAC3rm, GAC2001, GACSTR, GAC2001+, GAC3rm+, FC, STR2+ различной степени применимости и эффективности [13]. Параметр alg позволяет выбрать один из них. Пример 18: Пусть V 6 {0, 1}, V 2 6 {0, 1}, V 3 6 {0, 1}, T = {{0, 0}, {1, 1}}, тогда всеми решениями, удовлетворяющими ограничению table({V 1 , V 2 }, T, alg) для истинных T будут: 1. V 1 = 0, V 2 = 0, V 3 = 0. 2. V 1= 0, V 2= 0, V 3= 1. 3. V 1 = 1, V 2 = 1, V 3 = 0. 4. V 1= 1, V 2= 1, V 3= 1. В случае, если T объявлены ложными, решениями будут являться: 1. V 1 = 0, V 2 = 1, V 3 = 0. 2. V 1 = 0, V 2 = 1, V 3 = 1. 3. V 1 = 1, V 2 = 0, V 3 = 0. 4. V 1 = 1, V 2 = 0, V 3 = 1. Это ограничение имеет реализацию в популярных системах(библиотеках) программирования в ограничениях (таблица 18). 81