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

Двунаправленный поиск

В основе двунаправленного поиска лежит такая идея, что можно одновременно проводить два поиска (в прямом направлении, от начального состояния, и в обратном направлении, от цели), останавливаясь после того, как два процесса поиска встретятся на середине (рис. 3.10). Дело в том, что значение bd/2+bd/2 гораздо меньше, чем bd, или, как показано на этом рисунке, площадь двух небольших кругов меньше площади одного большого круга с центром в начале поиска, который охватывает цель поиска.
Двунаправленный поиск реализуется с помощью метода, в котором предусматривается проверка в одном или в обоих процессах поиска каждого узла перед его развертыванием для определения того, не находится ли он на периферии другого дерева поиска; в случае положительного результата проверки решение найдено. Например, если задача имеет решение на глубине d=6 и в каждом направлении осуществляется поиск в ширину с последовательным развертыванием по одному узлу, то в самом худшем случае эти два процесса поиска встретятся, если в каждом из них будут развернуты все узлы на глубине 3, кроме одного. Это означает, что при Ь=10 будет сформировано общее количество узлов, равное 22 200, а не 11 111 100, как при стандартном поиске в ширину. Проверка принадлежности узла к другому дереву поиска может быть выполнена за постоянное время с помощью хэш-таблицы, поэтому временная сложность двунаправленного поиска определяется как 0(bd/2). В памяти необходимо хранить по крайней мере одно из деревьев поиска, для того, чтобы можно было выполнить проверку принадлежности к другому дереву, поэтому пространственная сложность также определяется как о (bd/2). Такие требования к пространству являются одним из наиболее существенных недостатков двунаправленного поиска. Этот алгоритм является полным и оптимальным (при единообразных стоимостях этапов), если оба процесса поиска осуществляются в ширину; другие сочетания методов могут характеризоваться отсутствием полноты, оптимальности или того и другого.
Благодаря такому уменьшению временной сложности двунаправленный поиск становится привлекательным, но как организовать поиск в обратном направлении? Это не так легко, как кажется на первый взгляд. Допустим, что предшественниками узла л, определяемыми с помощью функции Pred(n), являются все те узлы, для которых п служит преемником. Для двунаправленного поиска требуется, чтобы функция определения предшественника Pred(n) была эффективно вычислимой. Простейшим является такой случай, когда все действия в пространстве состояний обратимы таким образом, что Pred(n) =5ucc_1 (п), а другие случаи могут потребовать проявить значительную изобретательность.
Рассмотрим вопрос о том, что подразумевается под понятием "цель" при поиске "в обратном направлении от цели". В задачах игры в восемь и поиска маршрута в Румынии имеется только одно целевое состояние, поэтому обратный поиск весьма напоминает прямой поиск. Если же имеется несколько явно перечисленных целевых состояний (например, два показанных на рис. 3.2 целевых состояния, в которых квадраты пола не содержат мусор), то может быть создано новое фиктивное целевое состояние, непосредственными предшественниками которого являются все фактические целевые состояния. Иным образом, формирования некоторых избыточных узлов можно избежать, рассматривая множество целевых состояний как единственное целевое состояние, каждым из предшественников которого также является множество состояний, а именно, множество состояний, имеющее соответствующего преемника в множестве целевых состояний (см. также раздел 3.6).
Наиболее сложным случаем для двунаправленного поиска является такая задача, в которой для проверки цели дано только неявное описание некоторого (возможно, большого) множества целевых состояний, например всех состояний, соответствующих проверке цели "мат" в шахматах. При обратном поиске потребовалось бы создать компактные описания "всех состояний, которые позволяют поставить мат с помощью хода ль/', и т.д.; и эти описания нужно было бы сверять с состояниями, формируемыми при прямом поиске. Общего способа эффективного решения такой проблемы не существует.