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}]})$$

TOUniform-cost CONTINUEsearch is complete and is cost-optimal, because the first solution it finds will have a cost that is at least as low as the cost of any other node in the frontier. Uniform-cost search considers all paths systematically in order of increasing cost, never getting caught going down a single infinite path (assuming that all action costs are $> \epsilon > 0$).