Рассматривая некоторую задачу в виде задачи CSP, можно достичь нескольких важных преимуществ. Представление состояний в задаче CSP соответствует некоторому стандартному шаблону (т.е. выражается в виде множества переменных с присвоенными значениями), поэтому функцию определения преемника и проверку цели можно записать в универсальной форме, применимой ко всем задачам CSP. Более того, могут быть разработаны эффективные, универсальные эвристические функции, для создания которых не требуются дополнительные знания о конкретной проблемной области. Наконец, для упрощения процесса решения может использоваться сама структура графа ограничений, что позволяет в некоторых случаях добиться экспоненциального уменьшения сложности. Это представление задачи CSP является первым и простейшим из ряда схем представления, которые будут разрабатываться на протяжении данной книги.

Рис. 5. 1. Пример определения задачи CSP: основные штаты и территории на карте Австралии (а); раскраска этой карты может рассматриваться как задача удовлетворения ограничений; задание состоит в том, чтобы назначить цвет каждому региону так, что ни одна пара соседних регионов не будет иметь одинаковый цвет; рассматриваемая задача раскраски карты, представленная в виде графа ограничений (б)

Можно довольно легко показать, что любой задаче CSP может быть дана ин-крементная формулировка, как и любой стандартной задаче поиска, следующим образом.

•    Начальное состояние. Пустое присваивание {}, в котором ни одной переменной не присвоено значение.

•    Функция определения преемника. Значение может быть присвоено любой переменной с неприсвоенным значением, при условии, что переменная не будет конфликтовать с другими переменными, значения которым были присвоены ранее.

•    Проверка цели. Текущее присваивание является полным.

•    Стоимость пути. Постоянная стоимость (например, 1) для каждого этапа.