Artificial Intelligence – Uniform Cost Search(UCS)

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.

searchProblem

searchTree

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

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.

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.

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.

Advertisements

9 comments

  1. Behzad · · Reply

    1- What “the algorithm never expands a node which has a cost greater than the cost of the shortest path in the graph” does mean? In Iteration1 the algorithm expanded the node G which is grater than A and so on.

    2- Why on the Iteration4 the node B isn’t expanded, but it’s expanded on the Iteration5 ?

  2. 1 – The path S -> G is never expanded, it is a result of the expansion of S.
    2 – The queue at Iteration3 has the path S -> A -> C -> D as the highest priority path with cost 3, which is expanded into S -> A -> C -> D -> G with cost 6, as you can see in the queue at Iteration4. At this stage, S -> A -> B is the highest priority path with cost 4, which is expanded into S -> A -> B -> D with cost 7, as seen in the queue at Iteration5.

    I hope that makes things clearer.

    1. Innocent · · Reply

      Siddharth I want to friendship with you plz….

  3. chandan · · Reply

    where does the cost come from?

  4. Oh, excellent question. As you can see, we need the cost of every edge to search for an optimal path. Now, these costs are assumed to be given as input, and may vary from application to application. Consider a hypothetical situation, where your car has to give you directions to get from one place to another, and each road is taken as an edge of the graph. The cost associated with that edge may be dependent on the length of the road, the current traffic scenario or probably the condition of the road (a pothole filled road will have a higher cost!).

    I hope that gives you an idea of how these algorithms are used in the real world.

  5. M.Usman Mazhar · · Reply

    why uniform-cost search is guaranteed to find the shortest path to a
    goal state (if there is a goal state).

    1. As you can see from the above example, the algorithm in each iteration picks out the least costly among ALL the paths that it hasn’t already visited. So I can argue that when the algorithm picks up a path going to the goal state, it will shortest (in terms of cost) compared to all the other paths going to the goal state.

  6. Reblogged this on inet113114263 and commented:
    UCS search Algo

  7. This piece of writing will help the internet people for building up new blog or even a weblog from start to end.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: