Необходимо учитывать различие между узлами и состояниями. Узел — это учетная структура данных, применяемая для представления дерева поиска, а состояние соответствует конфигурации мира. Поэтому узлы лежат на конкретных путях, которые определены с помощью указателей Parent-Node, а состояния— нет. Кроме того, два разных узла могут включать одно и то же состояние мира, если это состояние формируется с помощью двух различных путей поиска. Структура данных узла показана на рис. 3.6.

Рис. 3.6. Узлы представляют собой структуры данных, с помощью которых формируется дерево поиска. Каждый узел имеет родительский узел, содержит данные о состоянии и имеет различные вспомогательные поля. Стрелки направлены от дочернего узла к родительскому

Необходимо также представить коллекцию узлов, которые были сформированы, но еще не развернуты; такая коллекция называется периферией. Каждый элемент периферии представляет собой листовой узел, т.е. узел, не имеющий преемников в дереве. На рис. 3.5 периферия каждого дерева состоит из узлов с полужирными контурами. Простейшим представлением периферии может служить множество узлов. Тогда стратегия поиска должна быть выражена в виде функции, которая выбирает определенным образом из этого множества следующий узел, подлежащий развертыванию. Хотя данный подход концептуально является несложным, он может оказаться дорогостоящим с вычислительной точки зрения, поскольку функцию, предусмотренную в этой стратегии, возможно, придется применить к каждому элементу в указанном множестве для выбора наилучшего из них. Поэтому предполагается, что коллекция узлов реализована в виде очереди. Операции, применимые к любой очереди, состоят в следующем.