В алгоритме Backtracking-Search, приведенном в листинге 5.1, применялось очень простое правило, касающееся того, что делать, если какая-то ветвь поиска оканчивается неудачей: вернуться к предыдущей переменной и попытаться использовать для нее другое значение. Такой метод называется хронологическим поиском с возвратами, поскольку повторно посещается пункт, в котором было принято последнее по времени решение. В данном подразделе будет показано, что существуют намного лучшие способы поиска с возвратами.

Рассмотрим, что произойдет в случае применения простого поиска с возвратами в задаче, показанной на рис. 5.1, с постоянным упорядочением переменных Q, NSW, V, Т, SA, WA, NT. Предположим, что сформировано частичное присваивание {Q= red,NSW= green, V-Ыие, T-red). А после попытки присвоить значение следующей переменной, SA, будет обнаружено, что любое значение нарушает какое-то ограничение. Алгоритм возвращается к узлу т и пытается назначить новый цвет для Тасмании! Очевидно, что это— бессмысленное действие, поскольку смена цвета Тасмании не позволяет решить проблему с Южной Австралией.

Более интеллектуальный подход к поиску с возвратами состоит в том, чтобы вернуться к одному из множеств переменных, которые стали причиной неудачи. Это множество называется конфликтным множеством; в данном случае конфликтным множеством для SA является {Q,NSW, V). Вообще говоря, конфликтное множество для переменной х представляет собой множество переменных с ранее присвоенными значениями, которые связаны с X ограничениями. Метод обратного перехода выполняет обратный переход к переменной с последним по времени присвоенным значением из конфликтного множества; в данном случае в обратном переходе следует перескочить через узел Тасмании и попытаться применить новое значение для V. Такая операция может быть легко реализована путем модификации алгоритма Backtracking-Search таким образом, чтобы он накапливал данные о конфликтном множестве, одновременно проверяя одно из значений, допустимых для присваивания. Если не будет найдено ни одного допустимого значения, алгоритм должен возвратиться к последнему по времени элементу конфликтного множества и наряду с этим установить индикатор неудачи.

Внимательный читатель уже должен был заметить, что предварительная проверка позволяет определить конфликтное множество без дополнительной работы, поскольку каждый раз, когда процедура предварительной проверки, основанная на присваивании значения переменной X, удаляет некоторое значение из области определения у, она должна добавить X к конфликтному множеству Y. Кроме того, каждый раз, когда это последнее значение удаляется из области определения у, переменные из конфликтного множества Y добавляются к конфликтному множеству X. В этом случае после перехода к Y можно сразу же установить, куда должен быть выполнен обратный переход в случае необходимости.