В предыдущем разделе приведена формулировка задач CSP в виде задач поиска.Если используется такая формулировка, то появляется возможность решать задачи CSP с помощью любых алгоритмов поиска. Предположим, что мы применяем алгоритм поиска в ширину к универсальной формулировке задачи CSP, приведенной в предыдущем разделе. Но мы быстро обнаружим нечто ужасное: коэффициент ветвления на верхнем уровне равен nd, поскольку любое из d значений может быть присвоено любой из n переменных. На следующем уровне коэффициент ветвления равен (n-1) d и т.д., на всех nп уровнях. При этом создается дерево n!dn ветвями, даже несмотря на то, что имеется только dn возможных олных присваиваний! В применяемой нами формулировке задачи, которая внешне казалась разумной, но оказалась плохо продуманной, не было учтено существенно важное войство, общее для всех задач CSP, — коммутативность. Задача называется коммутативной, если порядок применения любого конкретного множества действий в процессе ее решения не влияет на результат. Именно это свойство характерно для задач CSP, поскольку, присваивая значения переменным, мы достигаем одного и того же частичного присваивания независимо от порядка присваивания. Поэтому во всех алгоритмах поиска CSP преемники формируются с четом возможных присваиваний только для единственной переменной в каждом узле дерева поиска. Например, в корневом узле дерева поиска в задаче раскрашивания карты Австралии можно иметь выбор между SA=red, SA= green и SA=blue, но мы никогда не должны выбирать между SA=red и WA=blue. Определив такое условие, можно надеяться сократить количество листьев до dn. Поиск в глубину, в котором каждый раз выбираются значения для одной переменной и выполняется возврат, если больше не остается допустимых значений, которые можно было бы присвоить переменной, называется ^ поиском с возвратами. Этот алгоритм поиска приведен в листинге. Обратите внимание на то, что в этом алгоритме по существу используется метод инкрементного формирования преемников по одному преемнику за один раз. Кроме того, для формирования преемника текущее присваивание дополняется, а не копируется. Поскольку это представление задач CSP стандартизировано, то в функции Backtracking-Search не требуется учитывать начальное состояние, функцию определения преемника или проверку цели, характерные для рассматриваемой проблемной области. Часть дерева поиска для задачи раскраски карты Австралии показана, где значения присваиваются переменным в порядке WA, NT, Q,... .
Простой алгоритм поиска с возвратами для решения задач удовлетворения ограничений CSP. Этот алгоритм составлен по принципу рекурсивного поиска в глубину. Функции Select-Unassigned-Variable и Order-Domain-Values могут использоваться для реализации эвристических функций общего назначения function Backtracking-Search(csp) returns решение result или индикатор отказа failure return Recursive-Backtracking({}, csp) function Recursive-Backtracking{assignment, csp) returns решение result или индикатор отказа failure if присваивание assignment является полным then return assignment var <— Select-Unassigned-Variable(Variables[csp], assignment, csp) for each value in Order-Domain-Values(var, assignment, csp) do if значение value является совместимым с присваиванием assignment согласно ограничениям Constraints[csp] then добавить {var = value} к присваиванию assignment result <— Recursive-Backtracking{assignment, csp) if result Ф failure then return result удалить {var = value} из присваивания assignment return failure
Часть дерева поиска, сформированного путем простого поиска с возвратами при решении задачи раскрашивания карты
Согласно определениям, алгоритм простого поиска с возвратами представляет собой неинформированный алгоритм, поэтому не следует рассчитывать на то, что он окажется очень эффективным при решении крупных задач. Результаты его применения к некоторым примерам задач показаны в первом столбце таблице и подтверждают эти предположения. Ранее было показано, что такой недостаток неинформированных алгоритмов поиска, как низкая производительность, можно устранить, предусмотрев использование в них эвристических функций, соответствующих данной проблемной области, которые основаны на наших знаниях о данной задаче. Как оказалось, задачи CSP можно решать эффективно без таких знаний о конкретной проблемной области. - Какой переменной должно быть присвоено значение в следующую очередь и в каком порядке необходимо пытаться присваивать эти значения?
- Как влияют текущие присваивания значений переменным на другие переменные с неприсвоенными значениями?
- Если какой-то путь оказался неудачным (т.е. достигнуто состояние, в котором ни одна переменная не имеет допустимых значений), позволяет ли поиск избежать повторения этой неудачи при прохождении последующих путей?
В приведенных ниже подразделах по очереди даны ответы на каждый из этих вопросов. Результаты применения различных алгоритмов CSP для решения разных задач. Слева направо показаны алгоритмы простого поиска с возвратами, поиска с возвратами на основе эвристической функции MRV, локального поиска с предварительной проверкой, локального поиска с редварительной проверкой на основе MRV и локального поиска с минимальными конфликтами. В каждой ячейке показано среднее количество проверок совместимости (за пять прогонов), которые отребовались для решения данной задачи; обратите внимание на то, что все эти числа, кроме двух, находящихся вверху справа, выражены в тысячах (К). Числа в круглых скобках показывают, что за назначенное количество проверок не было найдено ни одного ответа. Первой задачей является поиск раскраски в 4 цвета для 50 штатов США. Остальные задачи взяты из [56]. Во второй задаче подсчитывается общее количество проверок, необходимых для решения всех задач с n ферзями для л от 2 до 50. Третьей задачей является "головоломка с зеброй", которая описана в упр. 5.13. Последние две задачи представляют собой искусственные задачи, формируемые случайным образом (алгоритм с минимальными конфликтами к ним не применялся). Эти результаты показывают, что предварительная проверка на основе эвристической функции MRV является лучшим способом решения всех этих задач по сравнению с другими алгоритмами поиска с возвратами, но этот метод не всегда превосходит локальный поиск с минимальными конфликтами Задача | Поиск с возвратами
| Поиск с возвратами на основе MRV | Локальный поиск с предварительной проверкой
| Локальный поиск с предварительной проверкой на основе MRV
| Локальный поиск с минимальными конфликтами
| Определение раскраски в 4 цвета для 50 штатов США
| (> 1000K)
| (> 1000K)
| 2K
| 60
| 64
| Задача с n ферзями
| (> 40 000K)
| 13 500K
| (>40 000K)
| 817K
| 4K
| Головоломка с зеброй
| 3859K
| 1K
| 35K
| 0,5K
| 2K
| Сформированная случайным образом задача 1
| 415K
| 3K
| 26K
| 2K
| -
| Сформированная случайным образом задача 2
| 942K
| 27K
| 77K
| 15K
| -
|
|