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
|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|
|Performance||Finds solution more quickly||Speed is slower than informed search|
|Algorithms||Depth-first search, breadth-first search and lowest cost first search||Heuristic depth first and breadth-first search, and A* 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.
Key Differences Between Informed and Uninformed Search
- The former informed search technique uses knowledge in order to find the solution. On the other hand, the latter uninformed search technique does not use knowledge. In simpler terms there is no further information is provided about the solution.
- The efficiency of the informed search is better than the uninformed search.
- Uninformed search consumes more time and cost as it has no clue about the solution as compared to informed search.
- Depth-first search, breadth-first search and lowest cost first search are the algorithms come under the category of the uninformed search. As against, informed search covers the algorithms such as heuristic depth-first, heuristic breadth-first search and A* search.
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.