Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 56
Текст из файла (страница 56)
В третьей строке на рис. 5.4 текущими областями определения ЯА и ЬГЯгу являются (!заве) и (хегг, Ыие) соответственно. При ы=Ыие существует совместимое присваивание для !удгу, а именно эгей!у=хес!, поэтому дуга от Ы до ЛГЯГУ совместима. С другой стороны, обратная дуга от лгд!у до дА несовместима, поскольку применительно к присваиванию ьгд!у=Ыие не суьцествует совместимого присваивания для ~А. Эту дугу можно сделать совместимой, удалив значение Ы ие из области определения ьгЯК На том же этапе в процессе поиска проверку совместимости дуг можно также применить к дуге от дА до зчт Третья строка таблицы, приведенной на рис. 5 4, показывает, что обе переменные имеют область определения (Ь1ие). Результатом становится то, что значение Ы ие должно быть удалено из области определения яА, после чего эта область определения остается пустой.
Таким образом, применение проверки совместимости дуг привело к раннему обнаружению той несовместимости, которая не была обнаружена с помощью предварительной проверки, применяемой в чистом виде. Проверку совместимости дуг можно использовать либо в качестве этапа предварительной обработки перед началом процесса поиска, либо в качестве этапа распространения ограничения (аналогично предварительной проверке) после каждого присваивания во время поиска. (Последний алгоритм иногда называют МАС, сокращенно обозначая метод поддержки совместимости дуг — Ма)пга(п!пя Агс Сопз!згепсу.) И в том и в другом случае процесс проверки необходимо выполнять повторно, до тех пор, пока не перестанут обнаруживаться какие-либо несовместимости. Это связано с тем, что при удалении (в целях устранения некоторой несовместимости дуг) любого значения из области определения некоторой переменной может Глава 5.
Задачи удовлетворения ограничений 22] появиться новая несовместимость дуг в тех дугах, которые указывают на эту переменную. В полном алгоритме проверки совместимости дуг, АС-З, используется очередь для отслеживания дуг, которые должны быть проверены на несовместимость (листинг 5.2). Каждая дуга (х„х, ) по очереди "снимается с повестки дня" и проверяется; если из области определения х.
необходимо удалить какие-либо значения, то каждая дуга (х„, х,), указываюшая на х,, должна быть повторно вставлена в очередь для проверки. Сложность проверки совместимости дуг можно проанализировать следуюшим образом: любая бинарная задача СБР имеет самое большее о(п') дуг; каждая дуга (х„, х,) может быть "внесена в повестку дня" только г] раз, поскольку область определения х, имеет самое большее с] значений, доступных для удаления; проверка совместимости любой дуги может быть выполнена за время () (с]э), поэтому в наихудшем случае затраты времени составляют О(пэс]э) . Хотя такой метод является значительно более дорогостоящим по сравнению с предварительной проверкой, все эти дополнительные затраты обычно окупаются'.
Листинг 5.2. Алгоритм проверки совместимости дуг ъС-3. После применения алгоритма ъС-3 либо квл(дая дуга является совместимой, либо некоторая переменная имеет пустую область апре- деления, указывая на то, что эту задачу СБР невозможно сделать совместимой по дугам (и поэтому данная задача СБР не может быть решена). Обозначение "ъс-з" предложено разрвботчикомданного алгоритма [967), поскольку это — третья версия, представленная в его статье Еппсеаоп ЪС-3(сзр) геепгпв определение задачи СЯР, возможно, с сокращенными областями определения переменных 1прпев: сзр, бинарная задача СЯР с переменными (Хы Хэ, ..., Х„) 1оса1 таг1а)э1ев: диене, очередь, состоящая из дуг, которая первоначально включает все дуги из определения задачи сзр инязе очередь дпеие не пуста со (Х„ Х,) ~ — Рещоче-Рьгзг(диеие) 1г Нещоче-1лсопзззеепе-уа1иез(Х,, Х,) Е)теп дог еасн Х, зп Неьднюсгз1Х,) до добавить (Хь, Х,) к очереди диене гппсс1оп вешоуе-1псолздзсепь-за1иез(хь, х,) геспгпв значение сгые тогда и только тогда, когда произошло удаление некоторого значения гепючеб е- Еа1зе гог васи х зп Рошаьп[Х;] оо 1г ни одно из значений у в области определения Рошаьп[Х,] не позволяет использовать (х,у) для удовлетворения ограничения, установленного между Х; и Х, СЬеп удалить х из области определения Рощаьп[Х,]; гетега Ф- Сгие геепгп гещочем Поскольку задачи СБР включают задачу ЗЛАТ в качестве частного случая, не следует рассчитывать на то, что удастся найти алгоритм с полиномиальной временной ' Алгоритм АС-4, предложенный Мором н Хенаерсоном (10бв), выпалнястся эа время о (и'д'); см.
упр. 5.10. 222 Часть 11. Решение проблем сложностью, позволяющий определить, является ли данная конкретная задача СБР совместимой по дугам. Таким образом, можно сделать вывод, что метод проверки совместимости дуг не позволяет обнаружить все возможные несовместимости. Например, как показано на рис.
5.1, частичное присваивание (йгд=т.ес(, Иж=кес)) несовместимо, но алгоритм АС-3 не обнаруживает такую несовместимость. Более строгие формы распространения ограничения можно определить с помощью понятия ~к )г-совместимосзи. Задача СБР является )г-совместимой, если для любого множества )г-1 переменных и для любого совместимого присваивания значений этим переменным любой к-й переменной всегда можно присвоить некоторое совместимое значение. Например, 1-совместимость означает, что совместимой является каждая отдельная переменная сама по себе; это понятие называют также Ъ.
совместимоспяо узла. Далее, 2-совместимость — то же, что и совместимость дуги, а 3-совместимость означает, по любая пара смежных переменных всегда может быть дополнена третьей соседней переменной; это понятие именуется также Ъ. совместимостью пути. Любой граф называется ',э. строго к-совместимым, если он является й-совместимым, а также ()г-1)-совместимым, ()г-2)-совместимым, ... и т.д, вплоть до 1-совместимого. Теперь предположим, что имеется некоторая задача СБР с узлами п, которая сделана строго и-совместимой (т.е. строго )г-совместимой для )г=п). Тогда эту задачу можно решить без возвратов.
Для этого вначале можно выбрать совместимое значение для хь В таком случае существует гарантия, что удастся выбрать значение для х„поскольку граф является 2-совместимым, для Х,, поскольку он — З-совместимый, и тд. Для каждой переменной х, необходимо выполнить поиск только среди с)значений в ее области определения, чтобы найти значение, совместимое с х„...,хг, Это означает, что гарантируется нахожление решения за время О(пс11 . Безусловно, за такую возможность также приходится платить: любой алгоритм обеспечения и-совместимости в наихудшем случае должен требовать времени, экспоненциально зависящего от и.
Между методами обеспечения и-совместимости и совместимости дуг существует целый ряд промежуточных методов, выбор которых осуществляется с учетом того, что лля выполнения более строгих проверок совместимости потребуется больше времени, но это позволяет получить больший эффект с точки зрения сокращения коэффициента ветвления и обнаружения несовместимых частичных присваиваний. Существует возможность рассчитать такое наименьшее значение )с, что выполнение алгоритма проверки )г-совместимости будет гарантировать решение данной задачи без возвратов (см.
раздел 5.4), но применение данного расчета на практике не всегда оправдано. В действительности определение подходящего уровня проверки совместимости в основном относится к области эмпирических методов. Обработка специальных ограничений В реальных задачах часто встречаются некоторые типы ограничений, которые могут обрабатываться с помощью алгоритмов специального назначения, более эффективных по сравнению с методами общего назначения, которые рассматривались до сих пор. Например, ограничение Л22с(2ГГ указывает, что все участвующие в нем переменные должны иметь разные значения (как в криптоарифметической задаче).
Одна из простых форм проверки несовместимости для ограничений л22с)зГЕ применяется следующим образом: если в данном ограничении участвуют т переменных Глава 5. Задачи удовлетворения ограничений 223 и все они вместе взятые имеют п возможных разных значений, притом что гл и, то это ограничение не может быть удовлетворено. Применение данной проверки приводит к созданию следующего простого алгоритма: вначале удалить из ограничения каждую переменную, имеющую одноэлементную область определения, затем удалить значение этой переменной из областей определения оставшихся переменных. Повторять эту операцию до тех пор, пока имеются переменные с одноэлементнымн областями определения. Если в какой-то момент времени появится пустая область определения или останется больше переменных, чем областей определения, это будет означать, что обнаружена несовместимость.
Этот метод можно применить для обнаружения несовместимости в частичном присваивании ( 1И=хес(, Л(Я)у=тес() на рис. 5.1. Обратите внимание на то, что переменные яА, лгт и О фактически связаны ограничением А22ЖЕЕ, поскольку каждая пара соответствующих регионов должна быть обозначена различными цветами. После применения алгоритма АС-3 в сочетании с этим частичным присваиванием область определения каждой переменной сокращается до (дхееп, Ыие). Это означает, что имеются три переменные и только два цвета, поэтому ограничение А22Жгг нарушается. Таким образом, иногда простая процедура проверки совместимости для ограничения более высокого порядка эффективнее по сравнению с процедурой проверки совместимости дуг, применяемой к эквивалентному множеству бинарных ограничений. Возможно, более важным ограничением высокого порядка является 'ю ресурсное ограничение (геьовгсе сопз(га! пг), иногда называемое ограничением "самое большее" (аелюа е).
Например, допустим, что РА„...,РА, обозначают количество персонала, назначенного для выполнения каждого из четырех заданий. Ограничение, согласно которому может быть всего назначено не больше 1О членов персонала, записывается как а стояс (10, РА„,. А„. А,, РА4). Несовместимость можно обнаружить, проверяя сумму минимальных значений текущих областей определения; например, если каждая переменная имеет область определения (3, 4, 5, б ), то ограничение а гюов г не может быть удовлетворено. Кроме того, можно принудительно добиться совместимости, удаляя максимальное значение из любой области определения, если оно не совместимо с минимальными значениями других областей определения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
