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