Если некоторый алгоритм запоминает каждое состояние, которое он посетил, то может рассматриваться как непосредственно исследующий граф пространства состояний. В частности, можно модифицировать общий алгоритм Tree-Search, чтобы включить в него структуру данных, называемую ^ закрытым списком, в котором хранится каждый развернутый узел. (Периферию, состоящую из неразвернутых узлов, иногда называют открытым списком.) Если текущий узел совпадает с любым узлом из закрытого списка, то не развертывается, а отбрасывается. Этому новому алгоритму присвоено название алгоритма поиска в графе, Graph-Search (листинг 3.6). При решении задач со многими повторяющимися состояниями алгоритм Graph-Search является намного более эффективным по сравнению с Tree-Search. В наихудшем случае предъявляемые им требования к времени и пространству пропорциональны размеру пространства состояний. Эта величина может оказаться намного меньше, чем

Вопрос о том, оптимален ли поиск в графе, остается сложным. Выше было указано, что появление повторяющего состояния соответствует обнаружению алгоритмом двух путей в одно и то же состояние. Алгоритм Graph-Search, приведенный в листинге 3.6, всегда отбрасывает вновь обнаруженный путь и оставляет первоначальный; очевидно, что если этот вновь обнаруженный путь короче, чем первоначальный, то алгоритм Graph-Search может упустить оптимальное решение. К счастью, можно показать (упр. 3.12), что этого не может случиться, если используется либо поиск по критерию стоимости, либо поиск в ширину с постоянными стоимостями этапов; таким образом, эти две оптимальные стратегии поиска в дереве являются также оптимальными стратегиями поиска в графе. При поиске с итеративным углублением, с другой стороны, используется развертывание в глубину, поэтому этот алгоритм вполне может проследовать к некоторому узлу по неоптимальному пути, прежде чем найти оптимальный. Это означает, что при поиске в графе с итеративным углублением необходимо проверять, не является ли вновь обнаруженный путь к узлу лучшим, чем первоначальный, и в случае положительного ответа в нем может потребоваться пересматривать значения глубины и стоимости путей для потомков этого узла.

Листинг 3.6. Общий алгоритм поиска в графе. Множество closed может быть реализовано с помощью хэш-таблицы для обеспечения эффективной проверки повторяющихся состояний. В этом алгоритме предполагается, что первый найденный путь к состоянию s является наименее дорогостоящим (см. текст)

Между прочим, использование закрытого списка closed означает, что поиск в глубину и поиск с итеративным углублением больше не имеют линейных требований к пространству. Поскольку в алгоритме Graph-Search каждый узел хранится в памяти, некоторые методы поиска становятся неосуществимыми из-за недостаточного объема памяти.