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