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

TO CONTINUE