Искусственный интеллект. Современный подход

ПРЕДОТВРАЩЕНИЕ ФОРМИРОВАНИЯ ПОВТОРЯЮЩИХСЯ СОСТОЯНИЙ

Вплоть до этого момента мы рассматривали все аспекты поиска, но игнорировали одно из наиболее важных усложнений в процессе поиска — вероятность появления непроизводительных затрат времени при развертывании состояний, которые уже встречались и были развернуты перед этим. При решении некоторых задач такая ситуация никогда не возникает; в них пространство состояний представляет собой дерево и поэтому имеется только один путь к каждому состоянию. В частности, эффективной является формулировка задачи с восемью ферзями (в которой каждый новый ферзь помещается на самый левый пустой вертикальный ряд), и ее эффективность в значительной степени обусловлена именно этим — каждое состояние может быть достигнуто только по одному пути. А если бы задача с восемью ферзями была сформулирована таким образом, что любого ферзя разрешалось бы ставить на любую вертикаль, то каждого состояния с п ферзями можно было бы достичь с помощью п l различных путей.
В некоторых задачах повторяющиеся состояния являются неизбежными. К ним относятся все задачи, в которых действия являются обратимыми, такие как задачи поиска маршрута и игры со скользящими фишками. Деревья поиска для этих проблем бесконечны, но если мы отсечем некоторые из повторяющихся состояний, то сможем уменьшить дерево поиска до конечного размера, формируя только ту часть дерева, которая охватывает весь граф пространства состояний. Рассматривая только часть дерева поиска вплоть до некоторой постоянной глубины, можно легко обнаружить ситуации, в которых удаление повторяющихся состояний позволяет достичь экспоненциального уменьшения стоимости поиска. В крайнем случае пространство состояний размером d+1 (рис. 3.11, а) становится деревом с 2d листьями (рис. 3.11, б). Более реалистичным примером может служить прямоугольная решетка, как показано на рис. 3.11, в. В решетке каждое состояние имеет четырех преемников, поэтому дерево поиска, включающее повторяющиеся состояния, имеет 4d листьев, но существует приблизительно только 2d2 различных состояний с d этапами достижения любого конкретного состояния. Для d=20 это означает, что существует около триллиона узлов, но лишь примерно 800 различных состояний.
Таким образом, неспособность алгоритма обнаруживать повторяющиеся состояния может послужить причиной того, что разрешимая задача станет неразрешимой. Такое обнаружение обычно сводится к тому, что узел, подлежащий развертыванию, сравнивается с теми узлами, которые уже были развернуты; если обнаружено совпадение, то алгоритм распознал наличие двух путей в одно и то же состояние и может отбросить один из них.
При поиске в глубину в памяти хранятся только те узлы, которые лежат на пути от корня до текущего узла. Сравнение этих узлов с текущим узлом позволяет алгоритму обнаружить зацикливающиеся пути, которые могут быть немедленно отброшены. Это позволяет обеспечить, чтобы конечные пространства состояний не превращались в бесконечные деревья поиска из-за циклов, но, к сожалению, не дает возможности предотвратить экспоненциальное разрастание нециклических путей в задачах, подобных приведенным на рис. 3.11. Единственный способ предотвращения этого состоит в том, что в памяти нужно хранить больше узлов. В этом заключается фундаментальный компромисс между пространством и временем. Алгоритмы, которые забывают свою историю, обречены на то, чтобы ее повторять.
Если некоторый алгоритм запоминает каждое состояние, которое он посетил, то может рассматриваться как непосредственно исследующий граф пространства состояний. В частности, можно модифицировать общий алгоритм Tree-Search, чтобы включить в него структуру данных, называемую закрытым списком, в котором хранится каждый развернутый узел. (Периферию, состоящую из неразвернутых узлов, иногда называют открытым списком.) Если текущий узел совпадает с любым узлом из закрытого списка, то не развертывается, а отбрасывается. Этому новому алгоритму присвоено название алгоритма поиска в графе, Graph-Search (листинг 3.6). При решении задач со многими повторяющимися состояниями алгоритм Graph-Search является намного более эффективным по сравнению с Tree-Search. В наихудшем случае предъявляемые им требования к времени и пространству пропорциональны размеру пространства состояний. Эта величина может оказаться намного меньше, чем О (bd).
Вопрос о том, оптимален ли поиск в графе, остается сложным. Выше было указано, что появление повторяющего состояния соответствует обнаружению алгоритмом двух путей в одно и то же состояние. Алгоритм Graph-Search, приведенный в листинге 3.6, всегда отбрасывает вновь обнаруженный путь и оставляет первоначальный; очевидно, что если этот вновь обнаруженный путь короче, чем первоначальный, то алгоритм Graph-Search может упустить оптимальное решение. К счастью, можно показать (упр. 3.12), что этого не может случиться, если используется либо поиск по критерию стоимости, либо поиск в ширину с постоянными стоимостями этапов; таким образом, эти две оптимальные стратегии поиска в дереве являются также оптимальными стратегиями поиска в графе. При поиске с итеративным углублением, с другой стороны, используется развертывание в глубину, поэтому этот алгоритм вполне может проследовать к некоторому узлу по неоптимальному пути, прежде чем найти оптимальный. Это означает, что при поиске в графе с итеративным углублением необходимо проверять, не является ли вновь обнаруженный путь к узлу лучшим, чем первоначальный, и в случае положительного ответа в нем может потребоваться пересматривать значения глубины и стоимости путей для потомков этого узла.
Листинг 3.6. Общий алгоритм поиска в графе. Множество closed может быть реализовано с помощью хэш-таблицы для обеспечения эффективной проверки повторяющихся состояний. В этом алгоритме предполагается, что первый найденный путь к состоянию s является наименее дорогостоящим (см. текст)
function Graph-Search{problem, fringe) returns решение или индикатор неудачи failure
closed 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) if State[node] не находится в множестве closed then добавить State[node] к множеству closed fringe <— Insert-All(Expand(node, problem), fringe)
Между прочим, использование закрытого списка closed означает, что поиск в глубину и поиск с итеративным углублением больше не имеют линейных требований к пространству. Поскольку в алгоритме Graph-Search каждый узел хранится в памяти, некоторые методы поиска становятся неосуществимыми из-за недостаточного объема памяти.