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$$\epsilon$$, a lower bound on the cost of each action, with $$\epsilon$$ > 0. Then the algorithm’s worst-case time and space complexity is

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.

$$x$$