Благодаря такому уменьшению временной сложности двунаправленный поиск становится привлекательным, но как организовать поиск в обратном направлении? Это не так легко, как кажется на первый взгляд. Допустим, что предшественниками узла л, определяемыми с помощью функции Pred(n), являются все те узлы, для которых п служит преемником. Для двунаправленного поиска требуется, чтобы функция определения предшественника Pred(n) была эффективно вычислимой. Простейшим является такой случай, когда все действия в пространстве состояний обратимы таким образом, что , а другие случаи могут потребовать проявить значительную изобретательность.

Рассмотрим вопрос о том, что подразумевается под понятием "цель" при поиске "в обратном направлении от цели". В задачах игры в восемь и поиска маршрута в Румынии имеется только одно целевое состояние, поэтому обратный поиск весьма напоминает прямой поиск. Если же имеется несколько явно перечисленных целевых состояний (например, два показанных на рис. 3.2 целевых состояния, в которых квадраты пола не содержат мусор), то может быть создано новое фиктивное целевое состояние, непосредственными предшественниками которого являются все фактические целевые состояния. Иным образом, формирования некоторых избыточных узлов можно избежать, рассматривая множество целевых состояний как единственное целевое состояние, каждым из предшественников которого также является множество состояний, а именно, множество состояний, имеющее соответствующего преемника в множестве целевых состояний (см. также раздел 3.6).

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