Uniform Cost Search Algorithm
As discussed in the previous post Breadth First Search Algorithm, BFS is optimal when all step costs are equal. In this post I am going to discuss another uninformed search algorithm, which is, Uniform Cost Search Algorithm. This algorithm is simple extension of the breadth first search, by which it works for any cost function.
Instead of expanding the shallowest node, uniform cost search expands the node \(n\) with the lowest path cost \(g(n)\). This is done by storing the frontier as a priority queue ordered by \(g\).
Uniform Cost Search Algorithm
Uniform cost search algorithm is shown below.
function UNIFORMCOSTSEARCH(problem) return a solution or failure node < a node with {STATE = problem.INITIALSTATE and PATHCOST=0} frontier < a priority queue ordered by PATHCOST with node as the only element explored < an empty set loop: if EMPTY(frontier): return failure node < POP(frontier) //choose the lowest cost node in frontier if problem.GOALTEST(node.STATE): return SOLUTION(node) add node.STATE to explored for each action in problem.ACTIONS(node.STATE): child < CHILDNODE(problem, node, action) if child.STATE is not in explored or frontier: frontier < INSERT(child, frontier) else if child.STATE is not in frontier with higher PATHCOST: replace that frontier node with child
In addition to ordering of the queue by the path cost, there are two other significant differences from breadth first search:
 Goal test is applied to a node when it is selected for expansion, rather than when it is first generated. The reason to do this is, the first goal node that is generated may be on a suboptimal path.
 A test is added in case a better path is found to a node in currently on the frontier.
Both of these modification is explained through the following example, where the problem is to get from Sibiu to Bucharest.
The successor of Sibiu are Rimnicu Vilcea and Fagaras, with cost \(80\) and \(99\) respectively. The least cost node Rimnicu Vilcea, is expanded next, adding Pitesti with cost \(80\)\(+\)\(97\)\(=\)\(177\). The least cost node is now Fagaras, so it is expanded, adding Bucharest with cost \(99\)\(+\)\(211\)\(=\)\(310\). Now a goal node has been generated, but uniform cost search keep going, choosing Pitesti for expansion and adding a second path to Bucharest with cost \(80\)\(+\)\(97\)\(+\)\(101\)\(=\)\(278\). Now the algorithm checks to see if this new path is better than the old one. Since it is better, so the old one is discarded. Bucharest, is now with gcost \(278\), is selected for expansion and the solution is returned.
Performance of Uniform Cost Search Algorithm

Completeness
Since, 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 there is a path with an infinite sequence of zerocost actions – for example, a sequence of NoOp actions. So Completeness is guaranteed provided the cost of every step exceeds some small positive constant \(\epsilon\).

Optimality
Since, whenever uniform cost search selects a node \(n\) for expansion, the optimal path to that node has been found, then because step costs are nonnegative, paths never get shorter as nodes are added. these two facts together imply that, uniform cost search expands nodes in order of their optimal path cost. Hence, first goal node selected for expansion must be the optimal solution.

Time Complexity
Uniform cost search is guided by path costs rather than depths, so its complexity is not easily characterized in terms of \(b\) and \(d\). Let \(C^{*}\) be the cost of the optimal solution, and cost of every action is at least \(\epsilon\), then time complexity is \(\mathcal O(b^{1+\lfloor \frac{C^{*}}{\epsilon}\rfloor})\).

Space Complexity
Space complexity of the uniform cost search is same to time complexity i.e., \(\mathcal O(b^{1+\lfloor \frac{C^{*}}{\epsilon}\rfloor})\).
This article is contributed by Ram Kripal. If you like eLgo Academy and would like to contribute, you can mail your article to admin@elgoacademy.org. See your article appearing on the eLgo Academy page and help others. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.