Введение

Скрытая трансформация переформулирует задачу об удовлетворении ограничений таким образом, что все ограничения содержат не более двух переменных. Новая задача выполнима тогда и только тогда, когда выполнима исходная задача, и решения можно легко преобразовать из одной задачи в другую. Существует ряд алгоритмов для решения задач об удовлетворении ограничений, которые работают только с ограничениями, содержащими не более двух переменных. Если задача содержит ограничения с большим числом переменных (большей арите), преобразование к задаче, состоящей из бинарных ограничений, позволяет применить эти алгоритмы решения. Ограничения с одним, двумя или более переменными называются унарными, бинарными или ограничениями более высокого порядка. Число переменных в ограничении называется его аритетом. Скрытая трансформация преобразует произвольную задачу об удовлетворении ограничений в бинарную. Эта трансформация аналогична построению двойственной задачи. В задачу добавляются новые переменные, по одной для каждого ограничения исходной задачи. Область определения каждой такой переменной – это множество допустимых кортежей, удовлетворяющих соответствующему ограничению. Ограничения новой задачи обеспечивают согласованность значений исходных переменных со значениями новых переменных. Например, если новые переменные, соответствующие старому ограничению, могут принимать значения и , добавляются два новых ограничения: первое требует, чтобы принимало значение , если принимает значение , и наоборот. Второе условие накладывает аналогичное требование на переменную . Граф, представляющий результат этой трансформации, является двудольным, поскольку все ограничения связывают новую и старую переменные. Более того, ограничения являются функциональными: для любого заданного значения новой переменной только одно значение старой переменной может удовлетворять ограничению.