При поиске по критерию стоимости учитывается не количество этапов, имеющихся в пути, а только их суммарная стоимость. Поэтому процедура этого поиска может войти в бесконечный цикл, если окажется, что в ней развернут узел, имеющий действие с нулевой стоимостью, которое снова указывает на то же состояние (например, действие NoOp). Можно гарантировать полноту поиска при условии, что стоимость каждого этапа больше или равна некоторой небольшой положительной константе 8. Это условие является также достаточным для обеспечения оптимальности. Оно означает, что стоимость пути всегда возрастает по мере прохождения по этому пути. Из данного свойства легко определить, что такой алгоритм развертывает узлы в порядке возрастания стоимости пути. Поэтому первый целевой узел, выбранный для развертывания, представляет собой оптимальное решение. (Напомним, что в процедуре Tree-Search проверка цели применятся только к тем узлам, которые выбраны для развертывания.) Рекомендуем читателю попытаться воспользоваться этим алгоритмом для поиска кратчайшего пути до Бухареста.

Поиск по критерию стоимости направляется с учетом стоимостей путей, а не значений глубины в дереве поиска, поэтому его сложность не может быть легко охарактеризована в терминах Ь и d. Вместо этого предположим, что С* — стоимость оптимального решения, и допустим, что стоимость каждого действия составляет, по меньшей мере, 8. Это означает, что временная и пространственная сложность этого алгоритма в наихудшем случае составляет , т.е. может быть намного больше, чем. Это связано с тем, что процедуры поиска по критерию стоимости могут и часто выполняют проверку больших деревьев, состоящих из мелких этапов, прежде чем перейти к исследованию путей, в которые входят крупные, но, возможно, более полезные этапы. Безусловно, если все стоимости этапов равны, то выражение .равняется .