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

 
Распространение информации с помощью ограничений Печать

До сих пор в рассматриваемом алгоритме поиска ограничения, распространяющиеся на какую-то переменную, учитывались только в тот момент, когда происходил выбор этой переменной с помощью функции Select-Unassigned-Variable. Но рассматривая некоторые ограничения на предыдущих этапах поиска или даже до начала поиска, можно резко уменьшить пространство поиска.

Предварительная проверка

Один из способов лучшего использования ограничений во время поиска получил название предварительной проверки (forward checking). При каждом присваивании значения переменной Хв процессе предварительной проверки просматривается каждая переменная y c неприсвоеннымзначением, которая соединенасхс помощью некоторого ограничения, и из области определения переменной У удаляется любое значение, которое является несовместимым со значением, выбранным для X. На рисунке показан ход поиска решения задачи раскрашивания карты с помощью предварительной проверки.

На основании данного примера можно сделать два важных вывода. Прежде всего следует отметить, что после присваивания WA=redn Q= green области определения переменных NT и SA сокращаются до единственного значения; таким образом, ветвление, связанное с поиском значений для этих переменных, было полностью устранено путем распространения информации, касающейся переменных WA и Q. Применение эвристики MRV, которая, безусловно, хорошо сочетается с предварительной проверкой, позволяет на следующем этапе автоматически выбрать значение для переменных SA и NT. (Разумеется, то предварительная проверка может рассматриваться как эффективный способ инкрементного вычисления той информации, которая требуется эвристике MRV для выполнения своей работы.)

Второй вывод, заслуживающий внимания, состоит в том, что после присваивания V-blue область определения SA становится пустой. Поэтому предварительная проверка позволила обнаружить, что частичное присваивание {WA=red, =green, V=blue] является несовместимым с ограничениями этой задачи, значит, алгоритм немедленно выполняет возврат.


Поиск решения задачи с раскрашиванием карты на основе предварительной проверки. Вначале выполняется присваивание WA=red, затем предварительная проверка приводит к удалению значений red из областей определения соседних переменных NT и SA. После присваивания Q=green значение green удаляется из областей определения NT, SA и NSW. После присваивания V=blue из областей определения NSW и SA удаляется значение blue, в результате чего переменная SA остается без допустимых значений

Распространение ограничения

Хотя предварительная проверка обнаруживает много несовместимостей, она не позволяет обнаружить их все. Например, рассмотрим третью строку на рисунке, которая показывает, что если переменная WA имеет значение red, a Q— green, то обеим переменным, NT и SA, должно быть присвоено значение blue. Но соответствующие им регионы являются смежными и поэтому не могут иметь одно и то же значение цвета. Предварительная проверка не позволяет обнаружить эту ситуацию как несовместимость, поскольку не предусматривает достаточно далекий просмотр наперед.

Распространение ограничения (constraint propagation) — это общее название методов распространения на другие переменные последствий применения некоторого ограничения к одной переменной; в данном случае необходимо распространить ограничение с WA и Q на NT и SA (как было сделано с помощью предварительной проверки), а затем — на ограничение между NT и 5А, чтобы обнаружить казанную несовместимость. К тому же желательно, чтобы такая операция выполнялась быстро: нет смысла ограничивать таким образом объем поиска, если будет расходоваться больше времени на распространение ограничений, чем на выполнение простого поиска.

Идея проверки совместимости дуг легла в основу быстрого метода распространения ограничений, который является значительно более мощным по сравнению с предварительной проверкой. В данном случае термин дуга обозначает ориентированное ребро в графе ограничений, такое как дуга от SA до NSW. Если рассматриваются текущие области определения SA и NSW, то дуга является совместимой, если для каждого значения х переменной SA существует некоторое значение у переменной NSW, которое совместимо с х. В третьей строке на рисунке текущими областями определения SA и NSW являются {blue} и {red, blue) соответственно. При SA=blue существует совместимое присваивание для NSW, а именно NSW=red, поэтому дуга от SA до NSW совместима. С другой стороны, обратная дуга от NSWjxo SA есовместима, поскольку применительно к присваиванию NSW=blue не существует совместимого присваивания для SA. Эту дугу можно сделать совместимой, удалив значение blue из области определения NSW.

На том же этапе в процессе поиска проверку совместимости дуг можно также применить к дуге от SA до NT Третья строка таблицы, приведенной на рисунке, показывает, что обе переменные имеют область определения {blue}. Результатом становится то, что значение blue должно быть удалено из области определения SA, после чего эта область определения остается пустой. Таким образом, применение проверки совместимости дуг привело к раннему обнаружению той несовместимости, которая не была обнаружена с помощью предварительной проверки, применяемой в чистом виде.

Проверку совместимости дуг можно использовать либо в качестве этапа предварительной обработки перед началом процесса поиска, либо в качестве этапа распространения ограничения (аналогично предварительной проверке) после каждого присваивания во время поиска. (Последний алгоритм иногда называют MAC, сокращенно обозначая метод поддержки совместимости дуг— Maintaining Arc onsistency.) И в том и в другом случае процесс проверки необходимо выполнять повторно, до тех пор, пока не перестанут обнаруживаться какие-либо несовместимости. Это связано с тем, что при удалении (в целях устранения некоторой несовместимости дуг) любого значения из области определения некоторой переменной может появиться новая несовместимость дуг в тех дугах, которые указывают на эту переменную.

В полном алгоритме проверки совместимости дуг, АС-3, используется очередь для отслеживания дуг, которые должны быть проверены на несовместимость листинг. Каждая дуга (XirXj) по очереди "снимается с повестки дня" и проверяется; если из области определения xL необходимо удалить какие-либо значения, о каждая дуга (Хк, xL), указывающая на xL, должна быть повторно вставлена в очередь для проверки. Сложность проверки совместимости дуг можно проанализировать следующим образом: любая бинарная задача CSP имеет самое большее О (л2) дуг; каждая дуга {Xk,XL) может быть "внесена в повестку дня" только d раз, поскольку область определения xL имеет самое большее d значений, доступных для удаления; проверка совместимости любой дуги может быть выполнена за время (d2), поэтому в наихудшем случае затраты времени составляют 0(n2d3). Хотя такой метод является значительно более дорогостоящим по сравнению с предварительной проверкой, все эти дополнительные затраты обычно окупаются.


Алгоритм проверки совместимости дуг АС-3. После применения алгоритма АС-3 либо каждая дуга является совместимой, либо некоторая переменная имеет пустую область определения, указывая на то, что эту задачу CSP невозможно сделать совместимой по дугам (и поэтому данная задача CSP не может быть решена). Обозначение "АС-3" предложено разработчиком данного алгоритма, поскольку это — третья версия, представленная в его статье

function АС-3 (csp) returns определение задачи CSP, возможно,
  с сокращенными областями определения переменных
  inputs: csp, бинарная задача CSP с переменными {Xi, Х2, ..., Хп}
  local variables: queue, очередь, состоящая из дуг, которая
    первоначально включает все дуги
    из определения задачи csp
  while очередь queue не пуста do
    (Xi, Xj) <r- Remove-First (gueue)
    if Remove-Inconsistent-Values (Xi, Xj) then
    for
each Xk in Neighbors [Xi] do
      добавить (Xk, Xi) к очереди gueue
function Remove-Inconsistent-Values(Xi, Xj) returns значение true тогда
  и только тогда, когда произошло удаление некоторого значения
  removed <r- false
  for each х in Domain [Xi] do
    if ни одно из значений у в области определения Domain[Xj] не
    позволяет использовать (х,у) для удовлетворения
    ограничения, установленного между Xi и Xj
    then удалить х из области
    определения Domain [Xi]; removed <— true
    return removed


Поскольку задачи CSP включают задачу 3SAT в качестве частного случая, не следует рассчитывать на то, что удастся найти алгоритм с полиномиальной временной ложностью, позволяющий определить, является ли данная конкретная задача CSP совместимой по дугам. Таким образом, можно сделать вывод, что метод проверки совместимости дуг не позволяет обнаружить все возможные несовместимости. Например, как показано на рисунке, частичное присваивание {WA=red, NSW=red] несовместимо, но алгоритм АС-3 не обнаруживает такую несовместимость. Более строгие формы распространения ограничения можно определить с помощью понятия k-совместимости.

Задача CSP является к-совместимой, если для любого множества к-1 переменных и для любого совместимого присваивания значений этим переменным любой к-й переменной всегда можно присвоить некоторое совместимое значение. Например, 1-совместимость означает, что совместимой является каждая отдельная переменная сама по себе; это понятие называют также совместимостью узла. Далее, 2-совместимость — то же, что и совместимость дуги, а 3-совместимость означает, что любая пара смежных переменных всегда может быть дополнена третьей соседней переменной; это понятие именуется также совместимостью пути.

Любой граф называется ^ строго k-совместимым, если он является к-совместимым, а также (к-1)-совместимым, (к-2)-совместимым, ... и т.д. вплоть до 1-совместимого. Теперь предположим, что имеется некоторая задача CSP с узлами л, которая сделана строго n-совместимой (т.е. строго k-совместимой для к=п). Тогда эту задачу можно решить без dозвратов. Для этого вначале можно выбрать совместимое значение для х±. В таком случае существует гарантия, что удастся выбрать значение для х2, поскольку граф является 2-совместимым, для х3, поскольку он — 3-совместимый, и т.д. Для каждой переменной x± необходимо выполнить поиск только среди d значений в ее области определения, чтобы найти значение, совместимое с xl9...,xi.1. Это означает, что гарантируется нахождение решения за время O(nd). Безусловно, за такую возможность также приходится платить: любой алгоритм обеспечения n-совместимости в наихудшем случае должен 
требовать времени, экспоненциально зависящего от п.

Между методами обеспечения n-совместимости и совместимости дуг существует целый ряд промежуточных методов, выбор которых осуществляется с учетом того, что для выполнения более строгих проверок совместимости потребуется больше времени, но это позволяет получить больший эффект с точки зрения сокращения коэффициента ветвления и обнаружения несовместимых частичных присваиваний. Существует возможность рассчитать такое наименьшее значение к, что выполнение алгоритма проверки k-совместимости будет гарантировать решение данной задачи без возвратов, но применение данного расчета на практике не всегда оправдано. В действительности определение подходящего уровня проверки совместимости в основном относится к области эмпирических методов.

Обработка специальных ограничений

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

Одна из простых форм проверки несовместимости для ограничений Alldiff применяется следующим образом: если в данном ограничении участвуют т переменных все они вместе взятые имеют п возможных разных значений, притом что т>п, то это ограничение не может быть удовлетворено.
Применение данной проверки приводит к созданию следующего простого алгоритма: вначале удалить из ограничения каждую переменную, имеющую одноэлементную область определения, затем удалить значение этой переменной из областей определения оставшихся переменных. Повторять эту операцию до тех пор, пока имеются переменные с одноэлементными областями определения. Если в какой-то момент времени появится пустая область определения или останется больше переменных, чем областей определения, это будет означать, что обнаружена несовместимость.

Этот метод можно применить для обнаружения несовместимости в частичном присваивании {WA=red,NSW=red} на рис. 5.1. Обратите внимание на то, что переменные SA, NT к 0 фактически связаны ограничением Alldiff, поскольку каждая пара соответствующих регионов должна быть обозначена различными цветами. После применения алгоритма АС-3 в сочетании с этим частичным присваиванием область определения каждой переменной сокращается до {green,blue]. Это означает, что меются три переменные и только два цвета, поэтому ограничение Alldiff нарушается. Таким образом, иногда простая процедура проверки совместимости для ограничения более высокого порядка эффективнее по сравнению с процедурой проверки совместимости дуг, применяемой к эквивалентному множеству бинарных ограничений.

Возможно, более важным ограничением высокого порядка является ресурсное ограничение (resource constraint), иногда называемое ограничением "самое большее" (atmost). Например, допустим, что PA1,...,PA4t обозначают количество персонала, назначенного для выполнения каждого из четырех заданий. Ограничение, согласно которому может быть всего назначено не больше 10 членов персонала, записывается как a tmos t A0, РА1, РА2, РАЪ, РА4). Несовместимость можно обнаружить, проверяя сумму минимальных значений текущих областей определения; например, если каждая переменная имеет область определения {3, 4, 5, 6}, то ограничение a tmost не может быть удовлетворено. Кроме того, можно принудительно добиться совместимости, удаляя максимальное значение из любой области определения, если оно не овместимо с минимальными значениями других областей определения.

Таким образом, если каждая переменная в данном примере имеет область определения {2, 3, 4, 5, 6}, то из каждой области определения можно удалить значения 5 и 6. При решении крупных задач проверки ресурсных ограничений с целочисленными значениями (таких как задачи снабжения, в которых предусматривается перемещение тысяч людей в сотнях транспортных средств) обычно не существует возможности представлять область определения каждой переменной в виде большого множества целых чисел и постепенно сокращать это множество с применением методов проверки совместимости. Вместо этого области определения представляются в виде верхнего и нижнего пределов и управляются с помощью метода распространения этих пределов.

Например, предположим, что имеются два рейса, Flight271 и Flight272, в которых самолеты имеют соответственно вместимость 165 и 385 пассажиров. Поэтому начальные области определения для количества пассажиров в каждом рейсе определяются следующим образом: Flight271 G [0,165] и Flight272 G [0,385] Теперь допустим, что имеется дополнительное ограничение, согласно которому в этих двух рейсах необходимо перевести 420 человек: Flight271+Flight272e [420,420] .

Распространяя ограничения пределов, можно сократить области определения до таких величин: Flight271 е [35,165] и Flight272 G [255,385] Задача CSP называется совместимой с пределами (bounds-consistent), если для каждой переменной X, а также одновременно для нижнего и верхнего предельных значений X существует некоторое значение У, которое удовлетворяет заданному ограничению между х и У для каждой переменной Y. Такого рода ^ распространение пределов (bounds propagation) широко используется в практических задачах с ограничениями.

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

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

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

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

А проницательный читатель уже должен был заметить нечто странное: обратный переход происходит, когда каждое значение в некоторой области определения конфликтует с текущим присваиванием, но предварительная проверка обнаруживает этот случай и вообще исключает возможность достижения такого узла! В действительности можно показать, что с^3 каждая ветвь, отсекаемая с помощью обратного перехода, отсекается также с помощью предварительной проверки. Поэтому простой поиск с обратным переходом в сочетании с поиском с предварительной проверкой становится избыточным, а фактически обратный переход избыточен в любом поиске, в котором используется более строгая проверка совместимости, такая как MAC. Несмотря на замечания, сделанные в предыдущем абзаце, идея, лежащая в основе обратного перехода, остается перспективной, если возврат осуществляется с учетом причин неудачи. При обратном переходе неудача обнаруживается после того, как область определения некоторой переменной становится пустой, но во многих случаях какая-то ветвь поиска становится бесперспективной задолго до того, как это происходит. Еще раз рассмотрим частичное присваивание {WA=red;fNSW=red} (которое согласно приведенному выше описанию является несовместимым).

Предположим, что на следующем этапе предпринимается попытка присваивания T=red, а затем осуществляется присваивание значений переменным jvt, Q, V, SA. Известно, что ни одно присваивание не применимо для этих последних четырех переменных, поэтому в конечном итоге не остается доступных значений, которые можно было бы попытаться присвоить переменной NT. Теперь возникает вопрос, куда выполнить возврат? Обратный переход не может применяться, поскольку в области определения переменной NT имеются значения, совместимые со значениями, ранее присвоенными переменным, — переменная NT не имеет полного конфликтного множества из переменных с ранее присвоенными значениями, которое вызвало бы неудачу при попытке присваивания ей значения. Однако известно, что неудачу вызывают четыре переменные, NT, Q, У и SA, вместе взятые, поскольку во множестве переменных с ранее присвоенными значениями должны существовать такие переменные, которые непосредственно конфликтуют с этими четырьмя. Эти рассуждения приводят к созданию более глубокого определения понятия конфликтного множества для такой переменной, как NT конфликтным множеством называется множество переменных с ранее присвоенными значениями, которые, наряду со всеми переменными со значениями, присваиваемыми в дальнейшем, становятся причиной того, что для NT не существует совместимого решения. В таком случае конфликтное множество состоит из переменных WA и NSW, поэтому алгоритм должен выполнить возврат к NSW и пропустить переменную, соответствующую Тасмании. Алгоритм обратного перехода, в котором используются конфликтные множества, определенный таким образом, называется алгоритмом обратного перехода, управляемого конфликтами (conflict-directed backjumping).

Теперь необходимо объяснить, как вычисляются эти новые конфликтные множества. Применяемый для этого метод фактически очень прост. "Окончательная" неудача в какой-то ветви поиска всегда возникает из-за того, что область определения некоторой переменной становится пустой; эта переменная имеет типичное конфликтное множество. В данном примере неудача возникает при присваивании значения переменной SA, а ее конфликтным множеством является (скажем) {WA,NT, Q}. Выполняется обратный переход к переменной Q, и эта переменная поглощает конфликтное множество, полученное от SA (безусловно, после исключения из него самой переменной Q), объединяя его со своим собственным прямым конфликтным множеством, представляющим собой {NT,NSW}', новым конфликтным множеством становится {WA,NT,NSW}. Это означает, что, продолжая поиск от Q, нельзя найти решение при наличии ранее выполненного присваивания переменным [WA,NT, NSW].

Поэтому обратный переход выполняется к переменной NT, присваивание значения которой выполнено последним по времени по сравнению с другими этими переменными. Переменная NT поглощает множество {WA, NT, NSW] - {NT}, бъединяя его со своим собственным прямым конфликтным множеством [WA} что приводит к получению {WA, NSW] (как было указано в предыдущем абзаце). Теперь алгоритм осуществляет обратный переход к NSW, как и предполагалось.

Подведем итог: допустим, что Xj — текущая переменная, a conf (Xj) — ее конфликтное множество. Если все попытки присваивания каждого возможного значения переменной Xj оканчиваются неудачей, то необходимо выполнить возврат к переменной х± с последним по времени присвоенным значением во множестве conf (Xj) и установить: conf(Xi) <- conf(Xi) и conf(Xj) - {Xi} Обратный переход, управляемый конфликтами, позволяет вернуться в правильную точку дерева поиска, но не предотвращает возможности возникновения таких же ошибок в другой ветви того же дерева. Метод определения ограничений с помощью обучения (constraint learning) по сути представляет собой метод модификации задачи CSP путем добавления нового ограничения, выдвинутого на основе логического анализа этих конфликтов.