5. Uniform Cost Search:

• • uniform-cost search is a searching algorithm used for traversing a weight tree or graph to find a path to the goal node having minimum cost.
• • It is similar to the Breadth First Search (BFS) algorithm if the path cost of all the edges is same, otherwise it gives the maximum priority to the lowest commutative cost.
• • uniform cost search algorithm starts from the root node and expands nodes according their path costs from the root node.
• • It can be used to solve any graph/tree problem where optimal cost is in demand.
• • A Uniform Cost Search algorithm is implemented by the priority queue.

Advantages

Uniform Cost search algorithm is optimal because at every state the path with the least cost is chosen.

Disadvantages

It does not care about the number of steps involve in searching and only concerned about the path cost due to which this algorithm may be stuck in an infinite loop.

Time complexity

Let C* is cost of the optimal solution, and ∈ is each step to get 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*/∈. The worst-case time complexity of uniform-Cost Search is

Space complexity

The same logic is for space complexity.

Completeness

Uniform-cost Search is complete, such as if there is a solution, UCS will find it.

Optimal

Uniform Cost search is always optimal as it only selects a path with the lowest path cost.

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc