Uninformed Search Algorithms
In this page we will learn about Uninformed Search Algorithms | What is Uninformed Search Algorithms? | Breadth-first Search | Advantages of Breadth-first Search | Disadvantages of Breadth-first Search | Depth-first Search | Advantage of Depth-first Search | Disadvantage of Depth-first Search | Depth-Limited Search Algorithm | Uniform-cost Search Algorithm | Iterative deepeningdepth-first Search | Bidirectional Search Algorithm
What is Uninformed Search Algorithms?
Uninformed search is a class of general-purpose search algorithms which operates in brute force-way. Uninformed search algorithms do not have additional information about state or search space other than how to traverse the tree, so it is also called blind search.
The various types of uninformed search algorithms are as follows:
- Breadth-first Search
- Depth-first Search
- Depth-limited Search
- Iterative deepening depth-first search
- Uniform cost search
- Bidirectional Search
1. Breadth-first Search:
The most frequent search approach for traversing a tree or graph is breadth-first search. Breadth-first search is the name given to an algorithm that searches a tree or graph in a breadth-first manner.
Before going on to nodes of the next level, the BFS algorithm starts searching from the tree's root node and extends all successor nodes at the current level.
A general-graph search algorithm like the breadth-first search algorithm is an example.
A FIFO queue data structure was used to implement a breadth-first search.
Advantages of Breadth-first Search:
If a solution is available, BFS will provide it.
If there are multiple answers to a problem, BFS will present the simplest solution with the fewest steps.
Disadvantages of Breadth-first Search:
It necessitates a large amount of memory since each level of the tree must be saved into memory before moving on to the next.
If the solution is located far from the root node, BFS will take a long time.
Example:
We've showed how to traverse the tree using the BFS method from the root node S to the destination node K in the diagram below. Because the BFS search algorithm traverses in layers, it will follow the dotted arrow's path, and the travelled path will be:
S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
Time Complexity: The number of nodes traversed in BFS till the shallowest Node can be used to determine the algorithm's time complexity. Where d represents the depth of the shallowest solution and b represents a node at each state.
Space Complexity: Space complexity of BFS algorithm is given by the Memory size of frontier which is O(bd).
Completeness: BFS is complete, which means it will discover a solution if the shallowest target node is at a finite depth.
Optimality: BFS is optimal if the path cost is a non-decreasing function of the node's depth.
2. Depth-first Search
- A recursive approach for traversing a tree or graph data structure is depth-first search.
- The depth-first search is named after the fact that it begins at the root node and follows each path to its greatest depth node before going on to the next path.
- DFS is implemented using a stack data structure.
- The DFS algorithm works in a similar way as the BFS method.
Note: Backtracking is a recursive algorithm strategy for identifying all possible answers.
Advantage of Depth-first Search:
- Because DFS only needs to store a stack of nodes on the path from the root node to the current node, it uses extremely little memory.
- It takes less time to reach the goal node than the BFS method (if it traverses in the correct order).
Disadvantage of Depth-first Search:
- There's a chance that many states will recur, and there's no certainty that a solution will be found.
- The DFS algorithm performs deep searching and may occasionally enter an infinite cycle.
Example:
The flow of depth-first search is depicted in the search tree below, and it will proceed in the following order:
Right node ----> root node ----> left node
It will begin its search from root node S and traverse A, B, D, and E; after traversing E, it will backtrack the tree because E has no successors and the goal node has yet to be discovered. It will retreat to node C and then to node G, where it will end because it has reached the goal node.
Completeness: Within a finite state space, the DFS search algorithm is complete since it expands every node within a constrained search tree.
Time Complexity: DFS's time complexity will be equal to the number of nodes traversed by the algorithm. It is provided by:
T(n)= 1+ n2+ n3 +.........+ nm = O(nm)
Where m is the greatest depth of any node, which can be significantly greater than d. (Shallowest solution depth)
Space Complexity: Because the DFS algorithm only has to record one path from the root node, its space complexity is equal to the size of the fringe set, which is O. (bm).
Optimal: DFS search algorithm is not optimum since it may result in a huge number of steps or a high cost to reach the goal node.
3. Depth-Limited Search Algorithm:
A depth-limited search algorithm works similarly to a depth-first search but with a limit. The problem of the endless path in the Depth-first search can be overcome by depth-limited search. The node at the depth limit will be treated as if it has no additional successor nodes in this procedure.
Two conditions of failure can be used to end a depth-limited search:
The standard failure value implies that the task is unsolvable.
Cutoff failure value: It indicates that there is no solution to the problem within a certain depth range.
Advantages of Depth-Limited Search:
Memory is saved by using a depth-limited search.
Disadvantages of Depth-Limited Search:
- Incompleteness is another drawback of depth-limited search.
- If there are multiple solutions to an issue, it may not be the best option.
Example:
Completeness: If the solution is above the depth-limit, the DLS search procedure is complete.
Time Complexity: The DLS algorithm has a time complexity of O(bl).
Space Complexity: The DLS algorithm has a space complexity of O(bl).
Optimal: Depth-limited search can be thought of as a subset of DFS, and it is inefficient even when l>d.
4. Uniform-cost Search Algorithm:
A searching algorithm for traversing a weighted tree or graph is uniform-cost search. When a separate cost is provided for each edge, this algorithm is used. The uniform-cost search's main purpose is to discover the shortest path to the goal node with the lowest cumulative cost. Uniform-cost search grows nodes from the root node based on their path costs. It can be used to solve any graph or tree in which the best cost is required. The priority queue employs a uniform-cost search algorithm. It gives the lowest total cost the highest priority. If the path cost of all edges is the same, uniform cost search is comparable to BFS algorithm.
Advantages of Uniform-cost Search:
- Because the path with the lowest cost is chosen at each state, uniform cost search is the best option.
Disadvantages of Uniform-cost Search:
- It is unconcerned with the number of steps involved in the search and is just concerned with the expense of the path. As a result, this algorithm may become stuck in an endless cycle.
Completeness: The uniform-cost search is complete, so if a solution exists, UCS will discover it.
Time Complexity: Let C* be the cost of the best solution, and be the cost of each step toward the goal node. The number of steps is then equal to C*/ε+1. We've chosen +1 because we're starting from state 0 and ending at C*/ε.
As a result, the Uniform-cost search's worst-case time complexity is O(b1 + [C*/ε])/.
Space Complexity: The same argument applies to space complexity, therefore Uniform-cost search's worst-case space complexity is O(b1 + [C*/ε]).
Optimal: Uniform-cost search is always the best option because it only chooses the cheapest path.
5. Iterative deepeningdepth-first Search:
DFS and BFS algorithms are combined in the iterative deepening algorithm. This search algorithm determines the best depth limit by gradually increasing it until a goal is discovered.
This algorithm searches in depth first up to a certain "depth limit," then increases the depth limit after each iteration until the goal node is found.
This search algorithm combines the speed of breadth-first search with the memory efficiency of depth-first search.
When the search space is large and the depth of the goal node is unknown, the iterative search algorithm is useful for uninformed search.
Advantages of Iterative deepeningdepth-first:
In terms of fast search and memory efficiency, it combines the advantages of the BFS and DFS search algorithms.
Disadvantages of Iterative deepeningdepth-first:
The main disadvantage of IDDFS is that it duplicates all of the previous phase's work.
The iterative deepening depth-first search is demonstrated in the following tree structure. The IDDFS algorithm iterates until it can't find the goal node any longer. The algorithm's iteration is described as follows:
1'st Iteration-----> A
2'nd Iteration----> A, B, C
3'rd Iteration------>A, B, D, E, C, F, G
4'th Iteration------>A, B, D, H, I, E, C, F, K, G
In the fourth iteration, the algorithm will find the goal node.
Completeness: If the branching factor is finite, this algorithm is complete.
Time Complexity: If the branching factor is b and the depth is d, the worst-case time complexity is O(bd).
Space Complexity: IDDFS will have an O space complexity (bd).
Optimal: If path cost is a non-decreasing function of node depth, the IDDFS algorithm is optimal.
6. Bidirectional Search Algorithm:
To find the goal node, the bidirectional search algorithm performs two simultaneous searches, one from the initial state (forward-search) and the other from the goal node (backward-search). Bidirectional search splits a single search graph into two small subgraphs, one starting from an initial vertex and the other from the goal vertex. When these two graphs intersect, the search comes to an end.
BFS, DFS, DLS, and other search techniques can be used in bidirectional search.
Advantages of Bidirectional Search:
- Bidirectional search is quick.
- Bidirectional search necessitates less memory
Disadvantages of Bidirectional Search:
- The bidirectional search tree is difficult to implement.
- In bidirectional search, the goal state should be known ahead of time.
Example:
The bidirectional search algorithm is used in the search tree below. One graph/tree is divided into two sub-graphs using this algorithm. In the forward direction, it begins at node 1 and in the backward direction, it begins at goal node 16.
The algorithm comes to a halt at node 9, where two searches collide.
Completeness: If we utilize BFS in both searches, we have a full bidirectional search.
Time Complexity: The bidirectional search using BFS has a time complexity of O(bd).
Space Complexity: The bidirectional search has a space complexity of O(bd).
Optimal: Bidirectional search is Optimal.