Time complexity of Uniform-cost search

Question

I am reading the book -- Artificial Intelligence a modern approach. I came across this sentence describing the time complexity of uniform cost search

Uniform-cost search is guided by path costs rather than depths, so its complexity is not easily characterized in terms of b and d. Instead, let C be the cost of the optimal solution,7 and assume that every action costs at least ε. Then the algorithm’s worst-case time and space complexity is O(b^(1+C/ε)), which can be much greater than bd.

As to my understanding, C is the cost of the optimal solution, and every action costs at least ε so that C/ε would be the number of steps take to the destination. But I don't know how this complexity has resulted, thanks.

Answer 1

To get the time complexity of the uniform-cost search, we need the help of path cost instead of the depth d. If C* is the optimal path cost of the solution, and each step costs at least e, then the time complexity is O(b^[1+(C*/ e)]), which can be much greater than that of BFS. When all the step costs are the same, then the optimal-cost search is the same as BFS except that we go one more step deeper.

In the first step, we will store all the successors of the root node. Then, the cost node which is low in comparison to other nodes will get removed, and its successors are added. Since we need the least cost of all the nodes explored, we need to store all the nodes explored until the goal node is found. Hence, the space complexity is also O(b^[1+(C*/e)]).

In terms of time and space complexity, we can see that a uniform-cost search is worse than BFS. Hence, we must apply the uniform-cost search only if the state costs are different, and path costs are not a non-decreasing function of depth. In other cases, we could use BFS.

If you wish to know about Uniformed Search Al algorithms and types of Uniformed Search Algorithms ( Breadth-first search, depth-first search, depth limited search, iterative deepening depth-first search, uniform cost search, bidirectional search ) then visit this Artificial Intelligence Course.