Главная arrow Поиск arrow Задачи CSP
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Применение поиска с возвратами для решения задач CSP Печать

В предыдущем разделе приведена формулировка задач 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
-