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

сократить сами по себе алгоритмы фильтрации и распространения не могут, поэтому задействуется алгоритм поиска. Данный алгоритм перебирает возможные присваивания переменным значений из оставшихся доменов. Таким образом получаются решения: X = 0, Y = 1, Z = 2; X = 1, Y = 2, Z = 3. В реальных задачах количество ограничений очень велико, и любое самое незначительное изменение домена на этапе фильтрации в каком-либо ограничении запустит целый каскад вызовов алгоритмов распространения и фильтрации для других ограничений. Поэтому наиболее эффективно было бы максимизировать сокращения доменов именно на этапе фильтрации, чтобы минимизировать количество вызовов алгоритмов. Рассмотрим теперь аналогичную задачу для переменных с теми же начальными доменами, но заданную с помощью одного ограничения: X <Y<Z. В этом случае до этапа поиска домены переменных сократятся до тех же значений X 6 {0, 1}, Y 6 {1, 2} и Z 6 {2, 3}, однако это произойдет уже на этапе фильтрации, без задействования алгоритмов распространения, что существенно эффективнее. На самом деле, чем проще ограничение, тем меньше возможностей у алгоритма фильтрации для анализа и последующего сокращения доменов участвующих в нем переменных. Поэтому набор однотипных ограничений оказалось эффективнее объединять в одно ограничение, для которого разрабатываются эффективные алгоритмы фильтрации. Такие составные ограничения называют глобальными. Количество однотипных простых ограничений, объединенных в глобальное, чаще всего не ограничено, что дает другое определение глобального ограничения, как ограничение, описывающее отношение на неограниченном количестве переменных [2]. Для иллюстрации преимуществ глобальных ограничений рассмотрим одно из самых популярных ограничений alldifferent . Ограничение alldifferent(X\, X 2 , ..., X n ) определяет, что значения переменных X 1 , X 2 , ..., X n должны быть различны между собой и равносильно множеству соответствующих попарных неравенств. Для примера рассмотрим alldifferent(X, Y, Z) для X 6 {1, 2}, Y 6 {1, 2} и Z 6 {1, 2, 3}, что равносильно X Ф Y, XФ Z, Y Ф Z. В случае рассмотрения каждого неравенства отдельно, не получится сократить домены переменных вплоть до этапа поиска, когда какой-то из переменных будет присвоено конкретное значение. С другой стороны, алгоритм фильтрации глобального ограничения позволит сократить домен переменной Z до {3}, существенно снизив тем самым количество рассматриваемых на этапе поиска комбинаций значений переменных (пространство поиска решений). Также следует отметить, что одно ограничение alldifferent для N переменных заменяет N(N-1)/2 простейших неравенств. Аналогичная тенденция прослеживается и для других глобальных ограничений, таким образом глобальные ограничения упрощают описание задач удовлетворения ограничений. Ряд популярных глобальных ограничений и примеры задач с ними приведен ниже. 71