SUBJECT MATERIAL, EBOOKS, IMPORTANT QUESTION , ASSIGNMENT QUESTION, OLD QUESTION PAPER

Monday, 25 July 2022

Uniform cost search in Artificial Intelligence

What is Uniform cost search Algorithm? Uniform-cost search is a searching algorithm used for traversing a weighted tree or graph.  This alg... thumbnail 1 summary

What is Uniform cost search Algorithm?

  • Uniform-cost search is a searching algorithm used for traversing a weighted tree or graph. 
  • This algorithm comes into play when a different cost is available for each edge. 
  • The primary goal of the uniform-cost search is to find a path to the goal node which has the lowest cumulative cost. 
  • Uniform-cost search expands nodes according to their path costs form the root node. 
  • It can be used to solve any graph/tree where the optimal cost is in demand. 
  • A uniform-cost search algorithm is implemented by the priority queue. 
  • It gives maximum priority to the lowest cumulative cost. 
  • Uniform cost search is equivalent to BFS algorithm if the path cost of all edges is the same.

The architecture of Uniform cost search algorithm


Algorithm of Uniform cost search :d

  • 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

Uniform cost search – Example

 

Implementation:

  • Step 1-We will start with start node and check if we have reached any of the destination nodes, i.e. No thus continue.
  • Step 2– We reach all the nodes that can be reached from S I .eA, B, D. And Since node S has been visited thus added to the visited List. Now we select the cheapest path first for further expansion, i.e. A     Algorithm 3     S
  • Step 3 – Node B and G1 can be reached from A and since node A is visited thus move to the visited list. Since G1 is reached but for the optimal solution, we need to consider every possible case; thus, we will expand the next cheapest path, i.e. S->D.
  • Step 4– Now node D has been visited thus it goes to visited list and now since we have three paths with the same cost, we will choose alphabetically thus will expand node B
  • Step 5-: From B, we can only reach node C. Now the path with minimum weight is S->D->C, i.e. 8. Thus expand C. And B has now visited node.    
  • Step 6:- From C we can reach G2 and F node with 5 and 7 weights respectively. Since S is present in the visited list thus, we are not considering the C->S path.
  • Now C will enter the visited list. Now the next node with the minimum total path is S->D->E, i.e. 8. Thus we will expand E.
  • Step 7:- From E we can reach only G3. E will move to the visited list.
  • Step 8 – In the last, we have 6 active paths. S->B – B is in the visited list; thus will be marked as a dead end.

            b.Same for S->A->B->C – C has already been visited thus is considered a dead end.

Out of the remaining
S->A->G1
S->D->C->G2
S->D->C->F
S->D->E->G3
Minimum is S->D->C->G2
And also, G2 is one of the destination nodes. Thus, we found our path.

Advantages of Uniform cost search:

  • It helps to find the path with the lowest cumulative cost inside a weighted graph having a different cost associated with each of its edge from the root node to the destination node.
  • It is considered to be an optimal solution since, at each state, the least path is considered to be followed.

Disadvantages of Uniform cost search:

  • The open list is required to be kept sorted as priorities in priority queue needs to be maintained.
  • The storage required is exponentially large.
  • The algorithm may be stuck in an infinite loop as it considers every possible path going from the root node to the destination node.

Performance Measurement

  • Completeness: Uniform-cost search is complete, such as if there is a solution, UCS will find it.
  • Time Complexity: Let C* is Cost of the optimal solution, and ε is each step to get closer to the goal node. Then the number of steps is = C*/ε+1. Here we have taken +1, as we start from state 0 and end to C*/ε. Hence, the worst-case time complexity of Uniform-cost search isO(b1 + [C*/ε])/.
  • Space Complexity: The same logic is for space complexity so, the worst-case space complexity of Uniform-cost search is O(b1 + [C*/ε]).
  • Optimal: Uniform-cost search is always optimal as it only selects a path with the lowest path cost.