ПРИМЕНЕНИЕ ПОИСКА С ВОЗВРАТАМИ ДЛЯ РЕШЕНИЯ ЗАДАЧ CSP


В предыдущем разделе приведена формулировка задач CSP в виде задач поиска. Если используется такая формулировка, то появляется возможность решать задачи CSP с помощью любых алгоритмов поиска, приведенных в главах 3 и 4. Предположим, что мы применяем алгоритм поиска в ширину к универсальной формулировке задачи CSP, приведенной в предыдущем разделе. Но мы быстро обнаружим нечто ужасное: коэффициент ветвления на верхнем уровне равен nd, поскольку любое из d значений может быть присвоено любой из п переменных. На следующем уровне коэффициент ветвления равен (л-1) d и т.д., на всех п уровнях. При этом создается дерево с л! - cf ветвями, даже несмотря на то, что имеется только cf1 возможных полных присваиваний!
В применяемой нами формулировке задачи, которая внешне казалась разумной, но оказалась плохо продуманной, не было учтено существенно важное свойство, общее для всех задач CSP, — коммутативность. Задача называется коммутативной, если порядок применения любого конкретного множества действий в процессе ее решения не влияет на результат. Именно это свойство характерно для задач CSP, поскольку, присваивая значения переменным, мы достигаем одного и того же частичного присваивания независимо от порядка присваивания. Поэтому во всех алгоритмах поиска CSP преемники формируются с учетом возможных присваиваний только для единственной переменной в каждом узле дерева поиска. Например, в корневом узле дерева поиска в задаче раскрашивания карты Австралии можно иметь выбор между SA=red, SA= green и SA=blue, но мы никогда не должны выбирать между SA=red и WA=blue. Определив такое условие, можно надеяться сократить количество листьев до cf1.
Поиск в глубину, в котором каждый раз выбираются значения для одной переменной и выполняется возврат, если больше не остается допустимых значений, которые можно было бы присвоить переменной, называется поиском с возвратами. Этот алгоритм поиска приведен в листинге 5.1. Обратите внимание на то, что в этом алгоритме по существу используется метод инкрементного формирования преемников по одному преемнику за один раз, который описан на с. 131. Кроме того, для формирования преемника текущее присваивание дополняется, а не копируется. Поскольку это представление задач CSP стандартизировано, то в функции Backtracking-Search не требуется учитывать начальное состояние, функцию определения преемника или проверку цели, характерные для рассматриваемой проблемной области. Часть дерева поиска для задачи раскраски карты Австралии показана на рис. 5.3, где значения присваиваются переменным в порядке WA,NT,Q,... .
Листинг 5.1. Простой алгоритм поиска с возвратами для решения задач удовлетворения ограничений csp. Этот алгоритм составлен по принципу рекурсивного поиска в глубину, описанного в главе 3. Функции 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
Согласно определениям, приведенным в главе 3, алгоритм простого поиска с возвратами представляет собой неинформированный алгоритм, поэтому не следует рассчитывать на то, что он окажется очень эффективным при решении крупных задач. Результаты его применения к некоторым примерам задач показаны в первом столбце табл. 5.1 и подтверждают эти предположения.
В главе 4 было показано, что такой недостаток неинформированных алгоритмов поиска, как низкая производительность, можно устранить, предусмотрев использование в них эвристических функций, соответствующих данной проблемной области, которые основаны на наших знаниях о данной задаче. Как оказалось, задачи CSP можно решать эффективно без таких знаний о конкретной проблемной области. Вместо этого в данной главе будут разработаны методы общего назначения, позволяющие найти ответ на перечисленные ниже вопросы.
• Какой переменной должно быть присвоено значение в следующую очередь и в каком порядке необходимо пытаться присваивать эти значения?
• Как влияют текущие присваивания значений переменным на другие переменные с неприсвоенными значениями?
• Если какой-то путь оказался неудачным (т.е. достигнуто состояние, в котором ни одна переменная не имеет допустимых значений), позволяет ли поиск избежать повторения этой неудачи при прохождении последующих путей?
В приведенных ниже подразделах по очереди даны ответы на каждый из этих вопросов.
Таблица 5.1. Результаты применения различных алгоритмов CSP для решения разных задач. Слева направо показаны алгоритмы простого поиска с возвратами, поиска с возвратами на основе эвристической функции MRV, локального поиска с предварительной проверкой, локального поиска с предварительной проверкой на основе MRV и локального поиска с минимальными конфликтами. В каждой ячейке показано среднее количество проверок совместимости (за пять прогонов), которые потребовались для решения данной задачи; обратите внимание на то, что все эти числа, кроме двух, находящихся вверху справа, выражены в тысячах (К). Числа в круглых скобках показывают, что за назначенное количество проверок не было найдено ни одного ответа. Первой задачей является поиск раскраски в 4 цвета для 50 штатов США. Остальные задачи взяты из [56, табл. 1]. Во второй задаче по дочитывается общее количество проверок, необходимых для решения всех задач с п ферзями для л от 2 до 50. Третьей задачей является "головоломка с зеброй", которая описана в упр. 5.13. Последние две задачи представляют собой искусственные задачи, формируемые случайным образом (алгоритм с минимальными конфликтами к ним не применялся). Эти результаты показывают, что предварительная проверка на основе эвристической функции MRV является лучшим способом решения всех этих задач по сравнению с другими алгоритмами поиска с возвратами, но этот метод не всегда превосходит локальный поиск с минимальными конфликтами







Материалы

Яндекс.Метрика