Между методами обеспечения n-совместимости и совместимости дуг существует целый ряд промежуточных методов, выбор которых осуществляется с учетом того, что для выполнения более строгих проверок совместимости потребуется больше времени, но это позволяет получить больший эффект с точки зрения сокращения коэффициента ветвления и обнаружения несовместимых частичных присваиваний. Существует возможность рассчитать такое наименьшее значение к, что выполнение алгоритма проверки k-совместимости будет гарантировать решение данной задачи без возвратов (см. раздел 5.4), но применение данного расчета на практике не всегда оправдано. В действительности определение подходящего уровня проверки совместимости в основном относится к области эмпирических методов.

Обработка специальных ограничений

В реальных задачах часто встречаются некоторые типы ограничений, которые могут обрабатываться с помощью алгоритмов специального назначения, более эффективных по сравнению с методами общего назначения, которые рассматривались до сих пор. Например, ограничение Alldiff указывает, что все участвующие в нем переменные должны иметь разные значения (как в криптоарифметической задаче). Одна из простых форм проверки несовместимости для ограничений Alldiff применяется следующим образом: если в данном ограничении участвуют т переменных и все они вместе взятые имеют п возможных разных значений, притом что т>п, то это ограничение не может быть удовлетворено.

Применение данной проверки приводит к созданию следующего простого алгоритма: вначале удалить из ограничения каждую переменную, имеющую одноэлементную область определения, затем удалить значение этой переменной из областей определения оставшихся переменных. Повторять эту операцию до тех пор, пока имеются переменные с одноэлементными областями определения. Если в какой-то момент времени появится пустая область определения или останется больше переменных, чем областей определения, это будет означать, что обнаружена несовместимость.

Этот метод можно применить для обнаружения несовместимости в частичном присваивании {WA=red,NSW=red} на рис. 5.1. Обратите внимание на то, что переменные SA, NT и Q фактически связаны ограничением Alldiff, поскольку каждая пара соответствующих регионов должна быть обозначена различными цветами. После применения алгоритма АС-3 в сочетании с этим частичным присваиванием область определения каждой переменной сокращается до {green,blue}. Это означает, что имеются три переменные и только два цвета, поэтому ограничение Alldiff нарушается. Таким образом, иногда простая процедура проверки совместимости для ограничения более высокого порядка эффективнее по сравнению с процедурой проверки совместимости дуг, применяемой к эквивалентному множеству бинарных ограничений.