Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 44
Текст из файла (страница 44)
Но при решении многих задач путь к цели не представляет интереса. Например, в задаче с восемью ферзями (см. с. 1) важна лишь окончательная конфигурация ферзей, а не порядок, в котором они были поставлены на доску. К этому классу задач относятся многие важные приложения, такие как проектирование интегральных схем, разработка плана цеха, составление производственного расписания, автоматическое программирование, оптимизация сети связи, составление маршрута транспортного средства и управление портфелем акций. Если путь к цели не представляет интереса, то могут рассматриваться алгоритмы другого класса, в которых вообще не требуются какие-либо данные о путях. Алгоритмы Ъ.
локального поиска действуют с учетом единственного 'в. текущего состояния (а не многочисленных путей) и обычно предусматривают только переход в состояние, соседнее по отношению к текущему состоянию. Как правшю, информация о путях, пройденных в процессе такого поиска, не сохраняется. Хотя алгоритмы локального поиска не предусматривают систематическое исследование пространства состояний (не являются систематическими), они обладают двумя важными преимуществами: во-первых, в них используется очень небольшой объем памяти, причем обычно постоянный, и, во-вторых, они часто позволяют находить приемлемые решения в больших или бесконечных (непрерывных) пространствах состояний, для которых систематические алгоритмы не применимы.
Глава 4. Информированный поиск и исследование пространства состояний 175 Кроме поиска целей, алгоритмы локального поиска являются полезным средством решения чистых сть задач оптимизации, назначение которых состоит в поиске состояния, наилучшего с точки зрения ек целевой функции. Многие задачи оптимизации не вписываются в "стандартную" модель поиска, представленную в главе 3.
Например, природа предусмотрела такую целевую функцию (пригодность для репродукции), что дарвиновская эволюция может рассматриваться как попытка ее оптимизации, но в этой задаче оптимизации нет компонентов "проверка цели" и "стоимость пути". Авторы пришли к выводу, что для понимания сути локального поиска очень полезно рассмотреть сь ландшафт пространства состояний (подобный показанному на рис. 4.7). Этот ландшафт характеризуется и "местонахождением" (которое определяется состоянием), н "возвышением'* (определяемым значением эвристической функции стоимости или целевой функции).
Если возвышение соответствует стоимости, то задача состоит в поиске самой глубокой долины — 'Ъ. глобального минимума, а если возвышение соответствует целевой функции, то задача заключается в поиске высочайшего пика — 'сь глобального максимума. (Минимум и максимум можно поменять местами, взяв их с обратными знаками.) Алгоритмы локального поиска исследуют такой ландшафт. Алгоритм полного локального поиска всегда находит цель, если она сушествует, а оптимальный алгоритм всегда находит глобальный минимум/максимум.
Беленая функмяя ум кальямй максимум Пространство состояний Токушсс состояние Рис. 4. 7. Ландшафт одномерного пространства состояний, в котором возвышение соответствует целевой функции. Задача состоит в поиске глобального максимума. Как обозначено стрелкой, в процессе поиска по принципу "подьема к вершине" осуществляются попытки модификации текущего состнояния в целях его улучшения. Различные топографические особенности ландшафта определены в тексте Поиск с восхождением к вершине Алгоритм поиска 'сь с восхождением к вершине показан в листинге 4.2. Он представляет собой обычный цикл, в котором постоянно происходит перемещение в направлении возрастания некоторого значения, т.е.
подъем. Работа этого алгоритма заканчивается после достижения "пика", в котором ни одно из соседних состояний не имеет бол:е высокого значения. В данном алгоритме не предусмотрено сопрово- Часть [!. Решение проблем 176 жление дерева поиска, поэтому в структуре данных текущего узла необходимо регистрировать только состояние и соответствующее ему значение целевой функции. В алгоритме с восхождением к вершине не осуществляется прогнозирование за пределами состояний, которые являются непосредственно соседними по отношению к текущему состоянию. Это напоминает попытку альпиниста, страдающего от амнезии, найти вершину горы Эверест в густом тумане.
Листинг 4.2. Аягорнтм поиска с восхождением к вершине (вереня с наиболее крутым подъемом), который представляет собой самый фундаментальный метод локального поиска. На калшем этапе текушнй узел заменяется наилучшим соседним узлом; в данной версия таковым является узел е максимальным значением Уа1ие, не еелн используется эвристическая ененка стоимости Ь, тс может быть предусмотрен поиск соседнего узла с минимальным знвченнем Ь Еипсгьоп н111-С11паэьпд[ргоЬ1ем) гееигпв состояние, которое представляет собой локальный максимум ьприев: ргоЬ1ем, задача 1оса1 тагьаЪ1ев: сиггепе, узел педдЬЬог, узел сиггепс ь- маке-нобе[тпьсьа1-ясасе[ргоь1ем)) 1оор со пехдЬЬог ь- преемник узла сиггепе с наивысеим значением ья уа1ие[пейдЬЬог) < уа1ие[сиггепс) сиен гееигп ясаке[поклепе) сиггепе ь- пейдЬЬог Для иллюстрации поиска с восхождением к вершине воспользуемся задачей с восемью ферзями, которая представлена на с.
[18. В алгоритмах локального поиска обычно применяется формулировка полного состояния, в которой в каждом состоянии на доске имеется восемь ферзей, по одному ферзю в каждом столбце. Функция определения преемника возвращает все возможные состояния, формируемые путем перемещения отдельного ферзя в другую клетку одного и того же столбца (поэтому каждое состояние имеет йх7=56 преемников). Эвристическая функция стоимости Ь определяет количество пар ферзей, которые атакуют друг друга либо прямо, либо косвенно (атака называется косвенной, если на одной горизонтали, вертикали или диагонали стоят больше двух ферзей).
Глобальный минимум этой функции становится равным нулю, и это происходит только в идеальных решениях. На рис. 4.8, а показано состояние со значением Ь=17. На этом рисунке также показаны значения всех преемников данного состояния, притом что наилучшие преемники имеют значение Ь=12. Алгоритмы с восхождением к вершине обычно предусматривают случайный выбор в множестве наилучших преемников, если количество преемников больше одного. Поиск с восхождением к вершине иногда называют ',ъ.
жадным локальным поиском, поскольку в процессе его выполнения происходит захват самого хорошего соседнего состояния без предварительных рассуждений о том, куда следует отправиться дальше. Жадность считается одним из семи смертных грехов, но, как оказалось, жадные алгоритмы часто показывают весьма высокую производительность. Во время поиска с восхождением к вершине зачастую происходит очень быстрое продвижение в направлении к решению, поскольку обычно бывает чрезвычайно легко Часть Н. Решение проблем 178 Рис.
4.й Иллкктрания того, понему хребты вызывают сложности при восхождении к вершине. На хребет, возвышаютийся слева направо, налигается решетка состоянии (пснзужирные дуги), создавая последовительность локальных максимумов, кпторые не являются непосредственно связинными друг с другом. В каждом локальном максимуме все доступные действия направлены вниз В каждом из этих случаев рассматриваемый алгоритм достигает такой точки, из которой не может осуществляться дальнейшее успешное продвижение.
Начиная со случайно сформированного состояния с восемью ферзями, алгоритм поиска с восхождением к вершине по самому крутому подъему заходит в тупик в 8б% случаях, решая только 14% экземпляров этой задачи. Но он работает очень быстро, выполняя в среднем только 4 этапа в случае успешного завершения и 3 этапа, когда заходит в тупик.
Это не очень плохой результат для пространства состояний с 8'=17 миллионами состояний. Алгоритм, приведенный в листинге 4.2, останавливается, достигнув плато, на котором наилучший преемник имеет такое же значение, как и в текушем состоянии. Имеет ли смысл продолжать движение, разрешив ск движение в сторону в надежде на то, что это плато в действительности представляет собой уступ, как показано на рис. 4.77 Ответ на этот вопрос обычно является положительным, но необходимо соблюдать осторожность. Если будет всегда разрешено движение в сторону, притом что движение вверх невозможно, могут возникать бесконечные циклы после того, как алгоритм достигнет плоского локального максимума, не являющегося уступом.
Одно из широко применяемых решений состоит в том, что устанавливается предел количества допустимых последовательных движений в сторону. Например, можно разрешить, допустим, 100 последовательных движений в сторону в задаче с восемью ферзями. В результате этого относительное количество экземпляров задачи, решаемых с помощью восхождения к вершине, возрастает с 14 до 94% Но за этот успех приходится платить: алгоритм в среднем выполняет приблизительно 21 этап при каждом успешном решении экземпляра задачи и 64 этапа при каждой неудаче. Разработано много вариантов поиска с восхождением к вершине. При Ж стохастическом поиске с восхождением к вершине осушествляется выбор слу- Глава 4.
Информированный поисг; и исследование пространства состояний 179 чайным образом одного из движений вверх; вероятность такого выбора может зависеть от крутизны движения вверх. Обычно этот алгоритм сходится более медленно по сравнению с вариантом, предусматриваюгцим наиболее крутой подъем, но в некоторых ландшафтах состояний он находит лучшие решения. При Ж поиске с восхождением к вершине с выбором первого варианта реализуется стохастический поиск с восхождением к вергдине путем формирования преемников случайным образом до тех пор, пока не будет сформирован преемник, лучший по сравнению с текугцим состоянием.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
