EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login

Uniform Cost Search

Home » Data Science » Data Science Tutorials » Artificial Intelligence Tutorial » Uniform Cost Search

Uniform Cost Search

Introduction to Uniform Cost Search

Uniform Cost Search is an algorithm used to move around a directed weighted search space to go from a start node to one of the ending nodes with a minimum cumulative cost. This search is an uninformed search algorithm since it operates in a brute-force manner, i.e. it does not take the state of the node or search space into consideration. It is used to find the path with the lowest cumulative cost in a weighted graph where nodes are expanded according to their cost of traversal from the root node. This is implemented using a priority queue where lower the cost higher is its priority.

Algorithm of Uniform Cost Search

Below is the algorithm to implement Uniform Cost Search in Artificial Intelligence:-
centre;”>Algorithm for USC

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

  • Insert RootNode into the queue.
  • Repeat till queue is not empty:
  • Remove the next element with the highest priority from the queue.
  • If the node is a destination node, then print the cost and the path and exit

else insert all the children of removed elements into the queue with their cumulative cost as their priorities.

Here rootNode is the starting node for the path, and a priority queue is being maintained to maintain the path with the least cost to be chosen for the next traversal. In case 2 paths have the same cost of traversal, nodes are considered alphabetically.

Example of Uniform Cost Search

Consider the below example, where we need to reach any one of the destination node{G1, G2, G3} starting from node S. Node{A, B, C, D, E and F} are the intermediate nodes. Our motive is to find the path from S to any of the destination state with the least cumulative cost. Each directed edge represents the direction of movement allowed through that path, and its labelling represents the cost is one travels through that path. Thus Overall cost of the path is a sum of all the paths.

For e.g. – a path from S to G1- {S->A -> G1} whose cost is SA +AG1 = 5 + 9 = 14

Popular Course in this category
Artificial Intelligence Training (3 Courses, 2 Project)3 Online Courses | 2 Hands-on Project | 32+ Hours | Verifiable Certificate of Completion | Lifetime Access
4.5 (5,112 ratings)
Course Price

View Course

Related Courses
All in One Data Science Bundle (360+ Courses, 50+ projects)Machine Learning Training (17 Courses, 27+ Projects)

Uniform Cost Search

Here we will maintain a priority queue the same as BFS with the cost of the path as its priority, lower the cost higher is the priority.

We are going to use a tree to show all the paths possible and also maintain a visited list to keep track of all the visited nodes as we need not visit any node twice.

Explanation Flow Visited List
Step 1-

We will start with start node and check if we have reached any of the destination nodes, i.e. No thus continue.

 

Uniform Cost Search2
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.

Algorithm 4 S, A
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 node D S,A,D
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. visited node S,A,D,B
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.

node S,A,D,B,C
Step 7:- From E we can reach only G3. E will move to the visited list. visited list S,A,D,B,C,E
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.

 

path S,A,D,B,C,E

In this way we can find the path with the minimum cumulative cost from a start node to ending node – S->D->C->G2 with cost total cost as 13(marked with green colour).

Advantages and Disadvantages of Uniform Cost Search

Below are the advantages and disadvantages:

Advantages

  • 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.

Disadvantage

  • 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.

Conclusion

Uniform Cost Search is a type of uninformed search algorithm and an optimal solution to find the path from root node to destination node with the lowest cumulative cost in a weighted search space where each node has a different cost of traversal. It is similar to Heuristic Search, but no Heuristic information is being stored, which means h=0.

Recommended Article

This is a guide to Uniform Cost Search. Here we discuss the introduction to Uniform Cost Search, algorithm, examples, advantages and disadvantages. You can also go through our other related articles to learn more –

  1. Uninformed Search
  2. Informed Search
  3. Search Algorithms in AI
  4. What is a Genetic Algorithm?

All in One Data Science Bundle (360+ Courses, 50+ projects)

360+ Online Courses

50+ projects

1500+ Hours

Verifiable Certificates

Lifetime Access

Learn More

0 Shares
Share
Tweet
Share
Primary Sidebar
Artificial Intelligence Tutorial
  • Basics
    • Introduction to Artificial Intelligence
    • What is Artificial Intelligence
    • Careers in Artificial Intelligence
    • Future of Artificial Intelligence
    • Uses of Artificial Intelligence
    • Artificial Intelligence Ethics
    • Types of Artificial Intelligence
    • Artificial Intelligence Tools & Applications
    • Artificial Intelligence Applications
    • Advantages of Artificial Intelligence
    • Artificial Intelligence Tools
    • Benefits of Artificial Intelligence
    • Artificial Intelligence Companies
    • Artificial Intelligence Techniques
    • Artificial Intelligence Software
    • How Artificial Intelligence Works
    • Importance of Artificial Intelligence
    • Subsets of Artificial Intelligence
    • Artificial Intelligence Problems
    • Artificial Intelligence Technology
    • Application of Neural Network
    • Applications of NLP
    • Global Positioning Systems
    • Production System in AI
    • Agents in Artificial Intelligence
    • Intelligent Agent in AI
    • Artificial Intelligence Algorithm
    • Search Algorithms in AI
    • Informed Search
    • Bidirectional Search
    • Adversarial Search
    • Uninformed Search
    • Uniform Cost Search
    • Hill Climbing in Artificial Intelligence
    • Propositional Logic in AI
    • Minimax Algorithm
    • Applications of Fuzzy Logic
    • Fuzzy Logic System
    • Implementation of Neural Networks
    • Turing Test in AI
    • Recurrent Neural Networks (RNN)
    • Spiking Neural Network
    • Feedforward Neural Networks
    • Probabilistic Neural Network
    • Overfitting Neural Network
    • Means-Ends Analysis
    • DNN Neural Network
    • Principal Component Analysis
    • Artificial Intelligence Interview
  • Pattern Recognition
    • Pattern Recognition
    • Pattern Recognition Algorithms
    • Forensic Tools
    • PRTools
    • Pattern Recognition Applications

Related Courses

Artificial Intelligence Training Courses

All One Data Science Training Courses

Machine Learning Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

© 2020 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you