В предыдущем разделе приведена формулировка задач CSP в виде задач поиска. Если используется такая формулировка, то появляется возможность решать задачи CSP с помощью любых алгоритмов поиска, приведенных в главах 3 и 4. Предположим, что мы применяем алгоритм поиска в ширину к универсальной формулировке задачи CSP, приведенной в предыдущем разделе. Но мы быстро обнаружим нечто ужасное: коэффициент ветвления на верхнем уровне равен nd, поскольку любое из d значений может быть присвоено любой из п переменных. На следующем уровне коэффициент ветвления равен (п-1) d и т.д., на всех п уровнях. При этом создается дерево с ветвями, даже несмотря на то, что имеется только возможных полных присваиваний!

В применяемой нами формулировке задачи, которая внешне казалась разумной, но оказалась плохо продуманной, не было учтено существенно важное свойство, общее для всех задач CSP, — коммутативность. Задача называется коммутативной, если порядок применения любого конкретного множества действий в процессе ее решения не влияет на результат. Именно это свойство характерно для задач CSP, поскольку, присваивая значения переменным, мы достигаем одного и того же частичного присваивания независимо от порядка присваивания. Поэтому во всех алгоритмах поиска CSP преемники формируются с учетом возможных присваиваний только для единственной переменной в каждом узле дерева поиска. Например, в корневом узле дерева поиска в задаче раскрашивания карты Австралии можно иметь выбор между SA=red, SA= green и SA=blue, но мы никогда не должны выбирать между SA=red и WA=blue. Определив такое условие, можно надеяться сократить количество листьев до

Поиск в глубину, в котором каждый раз выбираются значения для одной переменной и выполняется возврат, если больше не остается допустимых значений, которые можно было бы присвоить переменной, называется поиском с возвратами. Этот алгоритм поиска приведен в листинге 5.1. Обратите внимание на то, что в этом алгоритме по существу используется метод инкрементного формирования преемников по одному преемнику за один раз. Кроме того, для формирования преемника текущее присваивание дополняется, а не копируется. Поскольку это представление задач CSP стандартизировано, то в функции Backtracking-Search не требуется учитывать начальное состояние, функцию определения преемника или проверку цели, характерные для рассматриваемой проблемной области. Часть дерева поиска для задачи раскраски карты Австралии показана на рис. 5.3, где значения присваиваются переменным в порядке wa,nt,q,... .