Difference Between Informed and Uninformed Search

Searching is a process of finding a sequence of steps needed to solve any problem. The prior difference between informed and uninformed search is that the informed search provides the guidance on where and how to find the solution. Conversely, the uninformed search gives no additional information about the problem except its specification.

However, between both informed and uninformed search techniques, the informed search is more efficient and cost-effective.

Content: Informed Search Vs Uninformed Search

1. 1. Comparison Chart
   2. Definition
   3. Key Differences
   4. Conclusion

Comparison Chart

Basis for comparison	Informed Search	Uninformed Search
Basic	Uses knowledge to find the steps to the solution.	No use of knowledge
Efficiency	Highly efficient as consumes less time and cost.	Efficiency is mediatory
Cost	Low	Comparatively high
Performance	Finds solution more quickly	Speed is slower than informed search
Algorithms	Heuristic depth first and breadth-first search, and A* search	Depth-first search, breadth-first search and lowest cost first search

Definition of Informed search

The informed search technique utilizes the problem specific knowledge in order to give a clue to the solution of the problem. This type of search strategy actually prevents the algorithms from stumbling about the goal and the direction to the solution. Informed search can be advantageous in terms of the cost where the optimality is achieved at lower search costs.

To search an optimal path cost in a graph by implementing informed search strategy the most promising nodes n are inserted to the heuristic function h(n). Then the function returns a non-negative real number which is an approximate path cost calculated from node n to the target node.

Here the most important part of the informed technique is the heuristic function which facilitates in imparting the additional knowledge of the problem to the algorithm. As a result, it helps in finding the way to the goal through the various neighbouring nodes. There are various algorithms based on the informed search such as heuristic depth-first search, heuristic breadth-first search, A*search, etcetera. Let’s now understand heuristic depth-first search.

Heuristic Depth First Search

Similar to depth-first search method given below heuristic depth first search chooses a path but traverse all paths from the selected path prior to choosing another path. However, it chooses the best path locally. In cases where the smallest heuristic value is the priority for the frontier, then it is known as best first search.

Another informed search algorithm is A* search which merges the concept of lowest cost first and best first searches. This method considers both path cost and heuristic information in the process of searching and selecting the path to be expanded. An estimated total path cost used for each path residing on the frontier from the start to the target node. Therefore it uses two functions at the same time – cost (p) is the cost of the discovered path and h (p) is the estimated value of the path cost from the starting node to the goal node.

Definition of Uninformed search

The uninformed search is different from informed search in the way that it just provides the problem definition but no further step to finding the solution to the problem. The primary objective of uninformed search is to differentiate between the target and non-target state, and it totally ignores the destination it is heading towards in the path until it discovers the goal and reports successor. This strategy is also known as a blind search.

There are various search algorithms under this category such as depth-first search, uniform cost search, breadth-first search, and so on. Let us now understand the concept behind the uninformed search with the help of depth-first search.

Depth First Search

In depth first search, a Last in first out stack is used to add and remove the nodes. Only one node is added or removed at a time and the first element removed from the frontier of the stack would be the last element added to the stack. By employing stack in the frontier results in the searching of paths proceeded in depth first manner. When a shortest and optimal path being searched using depth-first search, the path created by the adjacent nodes is completed first even if it is not the desired one. Then the alternative path is searched through backtracking.

In other words, the algorithm chooses the first alternative at each node then backtracks to another alternative until it has traversed all paths from first selection. This also raises a problem where the search may cease to stop because of infinite loops (cycles) present in the graph.

Conclusion

The informed search provides the direction regarding the solution while in uninformed search no suggestion is given regarding the solution. This makes uninformed search more lengthy when the algorithm is implemented.