In this post I will talk about the Uniform Cost Search algorithm for finding the shortest path in a weighted graph. Given below are the diagrams of example search problem and the search tree. If you don’t know what search problems are and how search trees are created visit this post.
Uniform Cost Search
Uniform Cost Search is the best algorithm for a search problem, which does not involve the use of heuristics. It can solve any general graph for optimal cost. Uniform Cost Search as it sounds searches in branches which are more or less the same in cost.
Uniform Cost Search again demands the use of a priority queue. Recall that Depth First Search used a priority queue with the depth upto a particular node being the priority and the path from the root to the node being the element stored. The priority queue used here is similar with the priority being the cumulative cost upto the node. Unlike Depth First Search where the maximum depth had the maximum priority, Uniform Cost Search gives the minimum cumulative cost the maximum priority. The algorithm using this priority queue is the following:
Insert the root into the queue
While the queue is not empty
Dequeue the maximum priority element from the queue
(If priorities are same, alphabetically smaller path is chosen)
If the path is ending in the goal state, print the path and exit
Else
Insert all the children of the dequeued element, with the cumulative costs as priority
While the queue is not empty
Dequeue the maximum priority element from the queue
(If priorities are same, alphabetically smaller path is chosen)
If the path is ending in the goal state, print the path and exit
Else
Insert all the children of the dequeued element, with the cumulative costs as priority
Now let us apply the algorithm on the above search tree and see what it gives us. We will go through each iteration and look at the final output. Each element of the priority queue is written as [path,cumulative cost].
Initialization: { [ S , 0 ] }
Iteration1: { [ S->A , 1 ] , [ S->G , 12 ] }
Iteration2: { [ S->A->C , 2 ] , [ S->A->B , 4 ] , [ S->G , 12] }
Iteration3: { [ S->A->C->D , 3 ] , [ S->A->B , 4 ] , [ S->A->C->G , 4 ] , [ S->G , 12 ] }
Iteration4: { [ S->A->B , 4 ] , [ S->A->C->G , 4 ] , [ S->A->C->D->G , 6 ] , [ S->G , 12 ] }
Iteration5: { [ S->A->C->G , 4 ] , [ S->A->C->D->G , 6 ] , [ S->A->B->D , 7 ] , [ S->G , 12 ] }
Iteration6 gives the final output as S->A->C->G.
Iteration1: { [ S->A , 1 ] , [ S->G , 12 ] }
Iteration2: { [ S->A->C , 2 ] , [ S->A->B , 4 ] , [ S->G , 12] }
Iteration3: { [ S->A->C->D , 3 ] , [ S->A->B , 4 ] , [ S->A->C->G , 4 ] , [ S->G , 12 ] }
Iteration4: { [ S->A->B , 4 ] , [ S->A->C->G , 4 ] , [ S->A->C->D->G , 6 ] , [ S->G , 12 ] }
Iteration5: { [ S->A->C->G , 4 ] , [ S->A->C->D->G , 6 ] , [ S->A->B->D , 7 ] , [ S->G , 12 ] }
Iteration6 gives the final output as S->A->C->G.
Things worth mentioning:
->The creation of the tree is not a part of the algorithm. It is just for visualization.
->The algorithm returns the first path encountered. It does not search for all paths.
->The algorithm returns a path which is optimal in terms of cost.
->The algorithm returns the first path encountered. It does not search for all paths.
->The algorithm returns a path which is optimal in terms of cost.
At any given point in the execution, the algorithm never expands a node which has a cost greater than the cost of the shortest path in the graph. The elements in the priority queue have almost the same costs at a given time, and thus the name Uniform Cost Search. It may seem as if the elements don’t have almost the same costs, from the above example. But when applied on a much larger graph it is certainly so.
Uniform Cost Search can also be used as Breadth First Search if all the edges are given a cost of 1. I mentioned earlier that Uniform Cost Search is the best algorithm which does not use heuristics. We shall see what heuristics are and how they are applied in search algorithms in the coming posts.
