Role of Search Algorithms in AI
- alnavar8
- Nov 27, 2020
- 3 min read
The searching algorithms are used to find one or more element from a dataset. These algorithms are used to retrieve information stored within a data structure. Searching may be sequential or not. If the data in the dataset are random, then we need to use sequential searching else other different techniques can be used to reduce the complexity.
In Artificial Intelligence, search plays a major role as many of the problems the sequence of steps has to be determined by a structured trial and error method. Apart from constraint-satisfaction and two player games, AI solves problems such as path-finding. The classic example of a real world problems in AI literature is the Traveling Salesman Problem.
The different search algorithms covered in this blog post are :
Breadth First Search
Depth First Search
Depth Limited Search
Uniform Cost Search
Iterative Deepening DFS
Bidirectional Search
In each case, the task is to find a sequence of operations that map an initial state to a goal state.
Breadth First Search
Searches breadth-wise in a tree or graph
Searches from root node of tree and expands all successor nodes at the current level before moving to nodes of next level
It follows First In First Out queue structure
Advantages
Provides a solution, if exists
If more than 1 solution exists, then BFS provides optimal solution with least number of steps
Disadvantages
It requires lots of memory since each level is saved
BFS needs lot of time if solution is far from root node
S -> A -> B -> C -> D -> G -> H -> E -> F -> I -> K
Depth First Search
Starts from root node and follows each path to its greatest depth node before moving to the next path
It follows stack data structure
Advantages
Requires very less memory as it only needs to store a stack of the nodes on the path from root to current node
It takes less time to reach goal node compared to BFS
Disadvantages
Many states keep reoccurring and there is no guarantee of finding the solution
DFS goes deep down searching and sometime it may go into an infinite loop
S -> A -> B -> D -> E -> C -> G
Depth Limited Search
Same as DFS but it has a predetermined limit
It solves the drawbacks of the infinite path in DFS
The node at the depth limit will treated as if it has no successor nodes further
Advantages
DFS is memory efficient
Disadvantages
DFS has disadvantage of incompleteness
It may not be optimal if the problem has more than one solution
S -> A -> C -> D -> B -> I -> J
Uniform Cost Search
It is used when a different cost is available for each edge
The primary goal of UCS is to find a path to the goal node which has the lowest cumulative cost
UCS uses priority queue
Maximum priority is given to the node with the lowest cost
It is similar to BFS if the path cost of all edges is the same
Advantages
UCS is optimal because at every state the path with the least cost is chosen
Disadvantages
UCS doesn't focus on the number of steps involved in searching. It focuses only on the path cost and hence it could be stuck in an infinite loop
S -> A -> D -> G
Iterative Deepening Search
It is a combination of BFS and DFS search algorithms
Can find the best depth limit by gradually increasing the limit until a goal is found
Performs DFS to certain depth limit and keeps increasing the depth limit after each iteration until a goal is found
Combines the searching speed of BFS and the memory efficiency of DFS
This is useful when the search space is large and the depth of the goal node is unknown
Advantages
Exhibits BFS's speed and DFS's memory efficiency
Disadvantages
It repeats all the steps from the previous iteration
1st iteration -> A
2nd iteration -> A, B, C
3rd iteration -> A, B, D, E, C, F, G
4th iteration -> A, B, D, H, I, E, C, F, K, G
Bidirectional Search
It runs two simultaneous searches, one from initial state called as forward search and other from goal node called as backward search
Replaces one single search graph with two small sub graphs
Search stops when these two graphs intersect eachother
It can use any method such as BFS, DFS, DLS etc
Advantages
Bidirectional search is fast
It requires less memory
Disadvantages
The implementation is difficult
One should know the goal state in advance
1 is the Root node
9 is the Intersection node
16 is the Goal node
Found this article helpful? Then hit the heart! How else would I know you like my content? Don't forget to check out my Instagram Page. Also, subscribe to THE AI STUDIO for more AI related Content.
Comments