Uniform-cost search

When actions have different costs, an obvious choice is to use best-first search where the evaluation function is the cost of the path from the root to the current node.

Complexity

The complexity of uniform-cost search is characterized in terms of the cost of the optimal solution $C*$, and $\epsilon$, a lower bound on the cost of each action, with $\epsilon$ > 0. Then the algorithm’s worst-case time and space complexity is $$O(b^{1+[\frac{C^*}{\epsilon}]})$$

which can be much greater than This is because uniform-cost search can explore large trees of actions with low costs before exploring paths involving a high-cost and perhaps useful action. When all action costs are equal, is just and uniform-cost search is similar to breadth-first search.