ИНФОРМИРОВАННЫЙ ПОИСК И ИССЛЕДОВАНИЕ ПРОСТРАНСТВА СОСТОЯНИЙ
В этой главе показано, как можно с помощью информации о пространстве состояний не дать алгоритмам заблудиться в темноте.
В главе 3 показано, что неинформированные стратегии поиска позволяют находить решения задач путем систематической выработки новых состояний и их проверки применительно к цели. К сожалению, в большинстве случаев эти стратегии являются чрезвычайно неэффективными. Как показано в настоящей главе, информированные стратегии поиска (в которых используются знания, относящиеся к конкретной задаче) обеспечивают более эффективный поиск решения. В разделе 4.1 описаны информированные версии алгоритмов главы 3, а в разделе 4.2 показано, как может быть получена необходимая информация, относящаяся к конкретной задаче. В разделах 4.3 и 4.4 представлены алгоритмы, которые выполняют исключительно локальный поиск в пространстве состояний, оценивая и модифицируя одно или несколько текущих состояний вместо систематического исследования путей из начального состояния. Эти алгоритмы применимы для решения задач, в которых стоимость пути не представляет интереса и требуется лишь найти состояние, соответствующее решению. К этому семейству алгоритмов локального поиска относятся методы, созданные под влиянием исследований в области статистической физики (моделируемый отжиг) и эволюционной биологии (генетические алгоритмы). Наконец, в разделе 4.5 рассматривается поиск в оперативном режиме, в котором агент сталкивается с полностью неизвестным пространством состояний.
СТРАТЕГИИ ИНФОРМИРОВАННОГО (ЭВРИСТИЧЕСКОГО) ПОИСКА
В данном разделе показано, как стратегия информированного поиска (в которой кроме определения самой задачи используются знания, относящиеся к данной конкретной проблемной области) позволяет находить решения более эффективно, чем стратегия неинформированного поиска.
Общий рассматриваемый здесь подход называется поиском по первому наилучшему совпадению. Поиск по первому наилучшему совпадению представляет собой разновидность общего алгоритма Tree-Search или Graph-Search, в котором узел для развертывания выбирается на основе функции оценки, f (л). По традиции для развертывания выбирается узел с наименьшей оценкой, поскольку такая оценка измеряет расстояние до цели. Поиск по первому наилучшему совпадению может быть реализован в рамках описанной в данной книге общей инфраструктуры поиска с помощью очереди по приоритету — структуры данных, в которой периферия поиска поддерживается в возрастающем порядке f-значений.
Название "поиск по первому наилучшему совпадению" (best first search) узаконено традицией, но неточно. В конце концов, если бы мы действительно могли развертывать наилучший узел первым, то не было бы и поиска как такового; решение задачи представляло бы собой прямое шествие к цели. Единственное, что мы можем сделать, — это выбрать узел, который представляется наилучшим в соответствии с функцией оценки. Если функция оценки действительно является точной, то выбранный узел в самом деле окажется наилучшим узлом, но фактически функция оценки иногда оказывается малопригодной и способной завести поиск в тупик. Тем не менее авторы будут придерживаться названия "поиск по первому наилучшему совпадению", поскольку более подходящее название "поиск по первому совпадению, которое можно считать наилучшим" было бы довольно громоздким.
Существует целое семейство алгоритмов поиска по первому наилучшему совпадению, Best-First-Search, с различными функциями оценки1. Ключевым компонентом этих алгоритмов является эвристическая функция2, обозначаемая как л (л):
п{п) = оценка стоимости наименее дорогостоящего пути от узла п до целевого узла
Например, в задаче поиска маршрута в Румынии можно было бы оценивать стоимость наименее дорогостоящего пути от Арада до Бухареста с помощью расстояний по прямой до Бухареста, измеряемых в узловых точках маршрута от Арада до Бухареста.
Эвристические функции (или просто эвристики) представляют собой наиболее общую форму, в которой к алгоритму поиска подключаются дополнительные знания о задаче. Эвристики рассматриваются более подробно в разделе 4.2, а на данный момент мы будем определять их как произвольные функции, относящиеся к конкретной проблеме, с одним ограничением: если л — целевой узел, то л (л) =0. В оставшейся части настоящего раздела рассматриваются два способа использования эвристической информации для управления поиском.