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

Основным преимуществом обратного поиска является то, что он позволяет рассматривать только релевантные действия. Действие релевантно конъюнктивной цели, если оно достигает одного из конъюнктов данной цели. Например, целью описанной выше задачи по воздушной перевозке грузов с 10 аэропортами была доставка 20 единиц груза в аэропорт В или, точнее:

Теперь рассмотрим конъюнкт At(ClfB). Двигаясь в обратном направлении, можно найти действия, имеющие этот результат. Таковым является только одно действие: Unload (Clf ρ, В), где самолет ρ не задан.

Обратите внимание на то, что имеется также много нерелевантных действий, способных привести к целевому состоянию. Например, можно организовать перелет пустого самолета из аэропорта JFK в аэропорт SFO; это действие позволяет достичь целевого состояния из состояния-предшественника, в котором самолет находился в JFK и все целевые конъюнкты были удовлетворены. Обратный поиск, в котором допускаются нерелевантные действия, по-прежнему будет полным, но гораздо менее эффективным. Если решение существует, то должно быть найдено с помощью обратного поиска, допускающего только релевантные действия. Наличие такого ограничения, в котором допускаются только релевантные действия, означает, что процедура обратного поиска часто имеет гораздо более низкий коэффициент ветвления по сравнению с прямым поиском. Например, в рассматриваемой задаче грузовых воздушных перевозок имеется около 1000 действий, ведущих в прямом направлении из начального состояния, но только 20 действий, позволяющих перейти в обратном направлении от цели.