BFS is optimal when all step costs are equal, because it always expands the shallowest un expanded node. By a simple extension, we can find an algorithm that is optimal with any step cost function. Instead of expanding the shallowest node, uniform cost search expands the node n with the lowest path cost. Note that, if all step costs are equal, this is identical to BFS.

Uniform cost search does not care about the number of steps a path has, but only about their total cost. Therefore, it will get stuck in an infinite loop if it ever expands a node that has a zero – cost action leading back to the same state (example: a no op action.) We can guarantee completeness provided the cost of every step is greater than or equal to some small positive constant ? this condition is also sufficient to ensure optimality.

It means that the cost of path always increases as we go along the path. From this property, it is easy to see that the algo expands nudes in order of increasing path cost. Therefore, the first goal node selected for expansion is the optimal solution. We recommend trying the algo out to find the shortest path to Bucharest. Uniform cost search is guided by path costs rather than depths , so its complexity cannot easily be characterized in terms of b and d.

Instead, let $C^*$ be the cost of the optimal solution and assume that every action costs at least 6. Then the algorithms worst case time and space complexity is $O ( b^{[c*/6]})$, which can be much greater than $6^d$ this is because uniform cost search can and often does, explore large trees of small steps before exploring paths involving large and perhaps useful steps. When all step costs are equal, of course, $b^{[c*/6]}$ is just $b^d$