Обработка специальных ограничений
В реальных задачах часто встречаются некоторые типы ограничений, которые могут обрабатываться с помощью алгоритмов специального назначения, более эффективных по сравнению с методами общего назначения, которые рассматривались до сих пор. Например, ограничение Alldiff указывает, что все участвующие в нем переменные должны иметь разные значения (как в криптоарифметической задаче). Одна из простых форм проверки несовместимости для ограничений Alldiff применяется следующим образом: если в данном ограничении участвуют т переменных и все они вместе взятые имеют п возможных разных значений, притом что т>п, то это ограничение не может быть удовлетворено.
Применение данной проверки приводит к созданию следующего простого алгоритма: вначале удалить из ограничения каждую переменную, имеющую одноэлементную область определения, затем удалить значение этой переменной из областей определения оставшихся переменных. Повторять эту операцию до тех пор, пока имеются переменные с одноэлементными областями определения. Если в какой-то момент времени появится пустая область определения или останется больше переменных, чем областей определения, это будет означать, что обнаружена несовместимость.
Этот метод можно применить для обнаружения несовместимости в частичном присваивании {WA=red,NSW=red} на рис. 5.1. Обратите внимание на то, что переменные ?А, NT и Q фактически связаны ограничением Alldiff, поскольку каждая пара соответствующих регионов должна быть обозначена различными цветами. После применения алгоритма АС-3 в сочетании с этим частичным присваиванием область определения каждой переменной сокращается до {green,blue}. Это означает, что имеются три переменные и только два цвета, поэтому ограничение Alldiff нарушается. Таким образом, иногда простая процедура проверки совместимости для ограничения более высокого порядка эффективнее по сравнению с процедурой проверки совместимости дуг, применяемой к эквивалентному множеству бинарных ограничений.
Возможно, более важным ограничением высокого порядка является ресурсное ограничение (resource constraint), иногда называемое ограничением "самое большее" (atmost). Например, допустим, что PA1,...,PA4t обозначают количество персонала, назначенного для выполнения каждого из четырех заданий. Ограничение, согласно которому может быть всего назначено не больше 10 членов персонала, записывается как a tmos t (10, РА±, РА2, РАЪ, РА4). Несовместимость можно обнаружить, проверяя сумму минимальных значений текущих областей определения; например, если каждая переменная имеет область определения {3 , 4, 5, 6}, то ограничение a tmos t не может быть удовлетворено. Кроме того, можно принудительно добиться совместимости, удаляя максимальное значение из любой области определения, если оно не совместимо с минимальными значениями других областей определения. Таким образом, если каждая переменная в данном примере имеет область определения {2, 3, 4, 5, 6}, то из каждой области определения можно удалить значения 5 и 6.
При решении крупных задач проверки ресурсных ограничений с целочисленными значениями (таких как задачи снабжения, в которых предусматривается перемещение тысяч людей в сотнях транспортных средств) обычно не существует возможности представлять область определения каждой переменной в виде большого множества целых чисел и постепенно сокращать это множество с применением методов проверки совместимости. Вместо этого области определения представляются в виде верхнего и нижнего пределов и управляются с помощью метода распространения этих пределов. Например, предположим, что имеются два рейса, Flight271 и Flight272, в которых самолеты имеют соответственно вместимость 165 и 385 пассажиров. Поэтому начальные области определения для количества пассажиров в каждом рейсе определяются следующим образом:
Flight271 G [0#1б5] и Flight272 G [0#385]
Теперь допустим, что имеется дополнительное ограничение, согласно которому в этих двух рейсах необходимо перевести 420 человек:
Flight271+Flight272e [420#420].
Распространяя ограничения пределов, можно сократить области определения до таких величин:
Flight271 е [35,165] и Flight272 6 [255,385]
Задача CSP называется совместимой с пределами (bounds-consistent), если для каждой переменной х, а также одновременно для нижнего и верхнего предельных значений X существует некоторое значение У, которое удовлетворяет заданному ограничению между X и У для каждой переменной Y. Такого рода распространение пределов (bounds propagation) широко используется в практических задачах с ограничениями.