Сформулировав определенные задачи, необходимо найти их решение. Такая цель достигается посредством поиска в пространстве состояний. В настоящей главе рассматриваются методы поиска, в которых используются явно заданное дерево поиска, создаваемое с помощью начального состояния и функции определения преемника, которые совместно задают пространство состояний. Вообще говоря, вместо дерева поиска может применяться граф поиска, если одно и то же состояние может быть достигнуто с помощью многих путей. Это важное дополнение рассматривается в разделе 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.