Листинг 5.1. Простой алгоритм поиска с возвратами для решения задач удовлетворения ограничений csp. Этот алгоритм составлен по принципу рекурсивного поиска в глубину, описанного в главе 3. Функции Select-Unassigned-Variable и Order-Domain-Values могут использоваться для реализации эвристических функций общего назначения, которые рассматриваются в тексте данной главы

Рис. 5.3. Часть дерева поиска, сформированного путем простого поиска с возвратами при решении задачи раскрашивания карты, приведенной на рис. 5.1

Согласно определениям, приведенным в главе 3, алгоритм простого поиска с возвратами представляет собой неинформированный алгоритм, поэтому не следует рассчитывать на то, что он окажется очень эффективным при решении крупных задач. Результаты его применения к некоторым примерам задач показаны в первом столбце табл. 5.1 и подтверждают эти предположения.

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

•    Какой переменной должно быть присвоено значение в следующую очередь и в каком порядке необходимо пытаться присваивать эти значения?

•    Как влияют текущие присваивания значений переменным на другие переменные с неприсвоенными значениями?

•    Если какой-то путь оказался неудачным (т.е. достигнуто состояние, в котором ни одна переменная не имеет допустимых значений), позволяет ли поиск избежать повторения этой неудачи при прохождении последующих путей?

В приведенных ниже подразделах по очереди даны ответы на каждый из этих вопросов.