Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 50
Текст из файла (страница 50)
Доран и Мичи [404] осуществили обширные экспериментальные исследования в области применения эвристического поиска к решению ряда задач, в частности задач игры в восемь и игры в пятнадцать. Хотя Доран и Мичи провели теоретический анализ длины пути и "проникновения" (репе!гапсе) (отношения длины пути к общему количеству узлов, исследованных к данному моменту) в процессе эвристического поиска, они, по-видимому, игнорировали ту информацию, которую может предоставить текущая длина пути. Алгоритм А*, предусматривающий использование в эвристическом поиске текущего значения длины пути, был разработан Хартом, Нильссоном и Рафаэлем [623], с некоторыми дальнейшими поправками [624]. Декстер и Перл [37 Ц продемонстрировали оптимальную эффективность алгоритма А*, В указанной выше оригинальной статье, посвященной алгоритму А*, было впервые представлено условие преемственности (сопя]а!епсу сопгй!!оп), которому должны удовлетворять эвристические функции.
В качестве более простой замены этого условия Полом [1223] было предложено условие монотонности, но Перл [1188] показал, что эти два условия эквивалентны. Аналоги открытых и закрытых списков использовались 200 Часть 11. Решение проблем во многих алгоритмах, явившихся предшественниками алгоритма А*; к ним относятся алгоритмы поиска в ширину, поиска в глубину и поиска по критерию стоимости [97], [399]. Важность применения алдитивных стоимостей путей для упрошения алгоритмов оптимизации особо ярко была показана в работа Беллмана [97]. Пол [1220], [!223] впервые провел исследования связи между ошибками в эвристических функциях и временной сложностью алгоритма А*. Доказательство того, что работа алгоритма А" завершается за линейное время, если ошибка в эвристической функции ограничена некоторой константой, можно найти в работах Пола [1223] и Гашнига [522].
Перл ]! 188] развил этот результат, что позволило учитывать логарифмический рост ошибки. Применение "эффективного коэффициента ветвления" в качестве критерия эффективности эвристического поиска было предложено Нильссоном [1141]. Существует много вариантов алгоритма А*. Пол [1222] предложил использовать в алгоритме А' динамическое взвешивание (г)упав[с юе!8лг!п8), в котором в качестве функции оценки применяется взвешенная сумма текущей длины пути и эвристической функции Е (п)=и~,д(п)+ы„й(п), а не просто сумма г(п) =д(п)+)з(п). Веса ь, и ь„корректируются динамически по мере развития поиска.
Можно доказать, что алгоритм Пола является е-допустимым (т.е. гарантирует нахождение решений с отклонением от оптимального решения на коэффициент 1+а), где е — параметр, предусмотренный в алгоритме. Таким же свойством обладает алгоритм А,"[1! 88], который способен выбрать из периферии любой узел, при условии, что его Бстоимость находится впределах коэффициента 1+в от стоимости периферийного узла с наименьшей Г-стоимостью.
Выбор соответствующего коэффициента может быть сделан таким образом, чтобы существовала возможность минимизировать стоимость поиска. Алгоритм А' и другие алгоритмы поиска в пространстве состояний тесно связаны с методами ветвей и гранин, которые широко используются в исследованиях операций [901]. Соотношения между алгоритмами поиска в пространстве состояний и методами ветвей и границ были глубоко исследованы в [867], [869], [1115]. Мартелли и Монтанари [990] показали связь между динамическим программированием (см. главу 17) и некоторыми типами поиска в пространстве состояний.
Кумар и Канал [868] предприняли попытку "великой унификации" методов эвристического поиска, динамического программирования, а также методов ветвей и границ под обшим названием СОР (Согпрогй!е Пес!гйоп Ргосезз — комплексный процесс принятия решений). Поскольку компьютеры в конце 1950-х — начале !960-х годов имели не больше нескольких тысяч слов оперативной памяти, темой ранних исследовательских работ часто служил эвристический поиск с ограничением памяти. Одна из самых первых программ поиска, Огарй Тгахегзег [404], фиксирует свои результаты в виде некоторого оператора после выполнения поиска по первому наилучшему совпадению вплоть до заданного предела объема памяти. Алгоритм ! РА* [835], [836] стал одним из первых широко применяемых оптимальных алгоритмов эвристического поиска с ограничением памяти, после чего было разработано большое количество его вариантов. Анализ эффективности алгоритма 1ГЗА* и сложностей, возникающих при его применении с эвристическими функциями, которые встречаются в реальных задачах, приведен в работе Патрика и др.
[1182]. Алгоритм КВРБ [840], [841] фактически является лишь немного более сложным по сравнению с алгоритмом, приведенным в листинге 4.1. Послелний вари- Глава 4. Информированный поиск и исследование пространства состояний 201 ант ближе к независимо разработанному алгоритму, получившему название алгоритма Ж итеративного развертывания, или сокращенно 1Е (1!егаг)хе Ехрапбйоп) )1324]. В алгоритме ВВРБ используется не только верхняя, но и нижняя граница; эти два алгоритма при использовании допустимых эвристических функций ведут себя одинаково, но КВГБ развертывает узлы в порядке первого наилучшего совпадения даже при наличии недопустимой эвристической функции.
Идея отслеживания наилучшего альтернативного пути появилась еще раньше в изящной реализации алгоритма А* на языке Рго)ой, предложенной Братко [174], и в алгоритме РТА* [1332]. В последней работе обсуждаются также метауровневые пространства состояний и метауровневое обучение. Алгоритм МА* впервые опубликован в [229]. Появление алгоритм БМА", или Бппрййед МА*, стало результатом попытки реализовать МА* в качестве алгоритма сравнения для метода 1Е [1324]. Кайндл и Корсанд [763] применили алгоритм БМА* для создания алгоритма двунаправленного поиска, который функционирует значительно быстрее по сравнению с предшествующими алгоритмами. В [845) описан подход по принципу "разделяй и властвуй", а в [1645] представлен алгоритм А' поиска в графе с ограничением памяти.
Обзор методов поиска с ограничением памяти приведен в [842]. Идея о том, что допустимые эвристические функции могут быть получены с помощью ослабления условий задачи, впервые опубликована в оригинальной статье [645], авторы которой использовали звристику на основе минимального связующего дерева для решения задачи ТБР (см. упр. 4.8).
Автоматизация процесса ослабления условий задачи была успешно осуществлена Придитисом [1237] на основе его более ранней совместной работы с Мостоу [1092]. Использование баз данных шаблонов для составления допустимых эвристических функций предложено в ]313] и [523); базы данных с непересекающимися шаблонами описаны в [844). Вероятностная интерпретация эвристических функций глубоко исследована в [616] и [1188]. Безусловно, наиболее исчерпывающим источником сведений об эвристических функциях и алгоритмах эвристического поиска является книга Перла Неипзгки [1188].
В этой книге приведено особенно хорошее описание широкого разнообразия версий и вариантов алгоритма А*, включая строгие доказательства их формальных свойств. В работе Канала и Кумара представлена антология важных статей по эвристическому поиску [767]. Результаты новейших исследований в области алгоритмов поиска регулярно публикуются вжурналеАгг8)па!!лге!й~елге. Методы локального поиска имеют долгую историю в математике и компьютерных науках. Безусловно, как очень эффективный метод локального поиска в непрерывных пространствах, в которых доступна информация о градиенте, может рассматриваться метод Ньютона — Рафсона [1132], [1266]. В [182] можно найти классический справочник по алгоритмам оптимизации, для которых не требуется такая информация.
Алгоритм лучевого поиска, представленный в данной книге как алгоритм локального поиска, впервые появился в виде одного из вариантов методов динамического программирования с ограничением по ширине, предназначенного для распознавания речи, в системе Натру [952]. Еше один алгоритм подобного типа был глубоко проанализирован Перлом [1188) (глава 5). В последние годы снова пробудился интерес к теме локального поиска под влиянием исключительно качественных результатов, полученных при решении таких круп- 202 Часть П. Решение проблем ных задач удовлетворения ограничений, как задача с и-ферзями [1058] и задача формирования логических рассуждений [1382], а также под влиянием успешного включения в алгоритмы методов рандомизации, методов множественного одновременного поиска и других усовершенствований.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
