Главная arrow Поиск arrow Повторяющееся состояния
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Предотвращение формирования повторяющихся состояний Печать

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

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

Рассматривая только часть дерева поиска вплоть до некоторой постоянной глубины, можно легко обнаружить ситуации, в которых удаление повторяющихся состояний позволяет достичь экспоненциального уменьшения стоимости поиска. В крайнем случае пространство состояний размером d+1 становится деревом с 2d листьями.

Более реалистичным примером может служить прямоугольная решетка. В решетке каждое состояние имеет четырех преемников, поэтому дерево поиска, включающее повторяющиеся состояния, имеет 4d листьев, но существует приблизительно только 2d2 различных состояний с d этапами достижения любого конкретного состояния. Для d=2 0 это означает, что существует около триллиона узлов, но лишь примерно 800 различных состояний.

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

При поиске в глубину в памяти хранятся только те узлы, которые лежат на пути от корня до текущего узла. Сравнение этих узлов с текущим узлом позволяет алгоритму обнаружить зацикливающиеся пути, которые могут быть немедленно отброшены. Это позволяет обеспечить, чтобы конечные пространства состояний не превращались в бесконечные деревья поиска из-за циклов, но, к сожалению, не дает возможности предотвратить экспоненциальное разрастание нециклических путей в задачах, подобных приведенным на рисунке. Единственный способ предотвращения этого состоит в том, что в памяти нужно хранить больше узлов. В этом заключается фундаментальный компромисс между пространством и временем. Алгоритмы, которые забывают свою историю, обречены на то, чтобы ее повторять.

Пространства состояний, которые формируют экспоненциально более крупные деревья поиска: пространство состояний, в котором имеются два возможных действия, ведущих от А к В, два — от В к С и т.д.; это пространство состояний содержит d + 1 состояний, где d —  максимальная глубина (а); дерево поиска, которое имеет 2d ветвей, соответствующих 2d путям через это пространство (б); пространство состояний в виде прямоугольной решетки (в); состояния, находящиеся в пределах 2 этапов от начального состояния (А), обозначены серым цветом

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

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

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


Общий алгоритм поиска в графе. Множество 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 каждый узел хранится в памяти, некоторые методы поиска становятся неосуществимыми из-за недостаточного объема памяти.