Рис. 3.5. Частично развернутые деревья поиска, предназначенные для определения маршрута от Арада до Бухареста. Развернутые узлы затенены; узлы, которые были сформированы, но еще не развернуты, выделены полужирным контуром; узлы, которые еще не были сформированы, обозначены тонкими штриховыми линиями

Листинг 3.2. Неформальное описание общего алгоритма поиска в дереве

Необходимо учитывать различие между пространством состояний и деревом поиска. В пространстве состояний для задачи поиска маршрута имеется только 20 состояний, по одному для каждого города. Но количество путей в этом пространстве состояний является бесконечным, поэтому дерево поиска имеет бесконечное количество узлов. Например, первыми тремя путями любой бесконечной последовательности путей являются маршруты Арад—Сибиу, Арад—Сибиу—Арад, Арад—Сибиу—Арад—Сибиу. (Безусловно, качественный алгоритм поиска должен исключать возможность формирования таких повторяющихся путей; в разделе 3.5 показано, как этого добиться.)

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

•    State. Состояние в пространстве состояний, которому соответствует данный узел.

•    Parent-Node. Узел в дереве поиска, применявшийся для формирования данного узла (родительский узел).

•    Action. Действие, которое было применено к родительскому узлу для формирования данного узла.

•    Path-Cost. Стоимость пути (от начального состояния до данного узла), показанного с помощью указателей родительских узлов, которую принято обозначать как д(п).

•    Depth. Количество этапов пути от начального состояния, называемое также глубиной.