Поиск РЕШЕНИЙ
Сформулировав определенные задачи, необходимо найти их решение. Такая цель достигается посредством поиска в пространстве состояний. В настоящей главе рассматриваются методы поиска, в которых используются явно заданное дерево поиска, создаваемое с помощью начального состояния и функции определения преемника, которые совместно задают пространство состояний. Вообще говоря, вместо дерева поиска может применяться граф поиска, если одно и то же состояние может быть достигнуто с помощью многих путей. Это важное дополнение рассматривается в разделе 3.5.
На рис. 3.5 показаны некоторые расширения дерева поиска, предназначенного для определения маршрута от Арада до Бухареста. Корнем этого дерева поиска является поисковый узел, соответствующий начальному состоянию, In(Arad). Первый этап состоит в проверке того, является ли это состояние целевым. Безусловно, что оно не является таковым, но необходимо предусмотреть соответствующую проверку, чтобы можно было решать задачи, содержащие в себе готовое решение, такие как "начав путешествие с города Арад, прибыть в город Арад". А в данном случае текущее состояние не является целевым, поэтому необходимо рассмотреть некоторые другие состояния. Такой этап осуществляется путем развертывания текущего состояния, т.е применения функции определения преемника к текущему состоянию для формирования в результате этого нового множества состояний. В данном случае будут получены три новых состояния: In (Sibiu), In (Timisoara) и In (Zerind). Теперь необходимо определить, какой из этих трех вариантов следует рассматривать дальше.
В этом и состоит суть поиска — пока что проверить один вариант и отложить другие в сторону, на тот случай, что первый вариант не приведет к решению. Предположим, что вначале выбран город Сибиу. Проведем проверку для определения того, соответствует ли он целевому состоянию (не соответствует), а затем развернем узел Sibiu для получения состояний In(Arad), In(Fagaras), In(Oradea) и In(RimnicuVilcea). После этого можно выбрать любое из этих четырех состояний либо вернуться и выбрать узел Timisoara или Zerind. Необходимо снова и снова выбирать, проверять и развертывать узлы до тех пор, пока не будет найдено решение или не останется больше состояний, которые можно было бы развернуть. Порядок, в котором происходит развертывание состояний, определяется стратегией поиска. Общий алгоритм поиска в дереве неформально представлен D листинге 3.2.
Листинг 3.2. Неформальное описание общего алгоритма поиска в дереве
function Tree-Search{problem, strategy) returns решение solution или индикатор неудачи failure инициализировать дерево поиска с использованием начального
состояния задачи problem loop do
if нет кандидатов на развертывание then return индикатор
неудачи failure выбрать листовой узел для развертывания в соответствии
со стратегией strategy if этот узел содержит целевое состояние
then return соответствующее решение solution else развернуть этот узел и добавить полученные узлы
Необходимо учитывать различие между пространством состояний и деревом поиска. В пространстве состояний для задачи поиска маршрута имеется только 20 состояний, по одному для каждого города. Но количество путей в этом пространстве состояний является бесконечным, поэтому дерево поиска имеет бесконечное количество узлов. Например, первыми тремя путями любой бесконечной последовательности путей являются маршруты Арад—Сибиу, Арад—Сибиу—Арад, Арад—Сибиу—Арад—Сибиу. (Безусловно, качественный алгоритм поиска должен исключать возможность формирования таких повторяющихся путей; в разделе 3.5 показано, как этого добиться.)
Существует множество способов представления узлов, но здесь предполагается, что узел представляет собой структуру данных с пятью компонентами, которые описаны ниже.
• State. Состояние в пространстве состояний, которому соответствует данный узел.
• Parent-Node. Узел в дереве поиска, применявшийся для формирования данного узла (родительский узел).
• Action. Действие, которое было применено к родительскому узлу для формирования данного узла.
• Path-Cost. Стоимость пути (от начального состояния до данного узла), показанного с помощью указателей родительских узлов, которую принято обозначать как д (п).
• Depth. Количество этапов пути от начального состояния, называемое также глубиной.
Необходимо учитывать различие между узлами и состояниями. Узел — это учетная структура данных, применяемая для представления дерева поиска, а состояние соответствует конфигурации мира. Поэтому узлы лежат на конкретных путях, которые определены с помощью указателей Parent-Node, а состояния — нет. Кроме того, два разных узла могут включать одно и то же состояние мира, если это состояние формируется с помощью двух различных путей поиска. Структура данных узла показана на рис. 3.6.
Необходимо также представить коллекцию узлов, которые были сформированы, но еще не развернуты; такая тл •4 :ция называется > периферией. Каждый элемент периферии представляет собой листовой узел, т.е. узел, не имеющий преемников в дереве. На рис. 3.5 периферия каждого дерева состоит из узлов с полужирными контурами. Простейшим представлением периферии может служить множество узлов. Тогда стратегия поиска должна быть выражена в виде функции, которая выбирает определенным образом из этого множества следующий узел, подлежащий развертыванию. Хотя данный подход концептуально является несложным, он может оказаться дорогостоящим с вычислительной точки зрения, поскольку функцию, предусмотренную в этой стратегии, возможно, придется применить к каждому элементу в указанном множестве для выбора наилучшего из них. Поэтому предполагается, что коллекция узлов реализована в виде очереди. Операции, применимые к любой очереди, состоят в следующем.
• Make-Queue (element,...). Создает очередь с заданным элементом (элементами).
• Empty? (gueue). Возвращает истинное значение, только если в очереди больше нет элементов.
• Firs t (gueue). Возвращает первый элемент в очереди.
• Remove-First (gueue). Возвращает элемент First (gueue) и удаляет его из очереди.
• Insert (element, queue). Вставляет элемент в очередь и возвращает результирующую очередь. (Ниже будет показано, что в очередях различных типов вставка элементов осуществляется в различном порядке.)
• Insert-All (elements, queue). Вставляет множество элементов в очередь и возвращает результирующую очередь.
С помощью этих определений мы можем записать более формальную версию общего алгоритма поиска в дереве, показанную в листинге 3.3.
Листинг 3.3. Общий алгоритм поиска в дереве. Следует учитывать, что фактический параметр fringe (периферия) должен представлять собой пустую очередь, а порядок поиска зависит от типа очереди. Функция Solution возвращает последовательность действий, полученную путем прохождения по указателям на родительские узлы в обратном направлении, к корню
function Tree-Search{problem, fringe) returns решение solution или индикатор неудачи failure
fringe <— Insert(Make-Node(Initial-State[problem]) , fringe) loop do
if Empty?(fringe) then return индикатор неудачи failure node <— Remove-First(fringe)
if Goal-Test[problem] применительно к State[node] завершается успешно
then return Solution(node) fringe <— Insert-All(Expand(node, problem), fringe)
function Expand(node, problem) returns множество узлов successors successors <— пустое множество
for each
State[s] <— result Parent-Node[s] <— node Action[s] <— action