Introduction to Search Algorithms in AI
Artificial Intelligence is basically the replication of human intelligence through computer systems or machines. It is done through the process of acquisition of knowledge or information and the addition of rules that is used by information i.e. learning, and then using these rules to derive conclusions (i.e. reasoning) and then self- correction.
Properties of Search Algorithms
- Completeness: A search algorithm is complete when it returns a solution for any input if at least one solution exists for that particular input.
- Optimality: If the solution deduced by the algorithm is the best solution i.e. it has the lowest path cost then that solution is considered as the optimal solution.
- Time and Space Complexity: Time complexity is the time taken by an algorithm to complete its task and space complexity is the maximum storage space needed during the search operation.
Types of Search Algorithms
There are two types of search algorithms.
- Uninformed
- Informed
1. Uninformed Search Algorithms
Uninformed search algorithms do not have any domain knowledge. It works in a brute force manner and hence also called brute force algorithms. It has no knowledge about how far the goal node is, it only knows the way to traverse and to distinguish between a leaf node and goal node. It examines every node without any prior knowledge hence also called blind search algorithms.
Uninformed search algorithms are of mainly three types:
- Breadth-first search (BFS)
- Depth-first search (DFS)
- Uniform cost search
Breadth-First Search(BFS)
- In breadth first search, the tree or the graph is traversed breadth wise i.e. it starts from a node called search key and then explores all the neighboring nodes of the search key at that depth-first and then moves to the next level nodes. It is implemented using the queue data structure that works on the concept of first in first out (FIFO). It is a complete algorithm as it returns a solution if a solution exists.
- The time complexity for breadth first search is bd where b (branching factor) is the average number of child nodes for any given node and d is depth.
- The disadvantage of this algorithm is that it requires a lot of memory space because it has to store each level of nodes for the next one. It may also check duplicate nodes.
- Example: If search starts from root node A to reach goal node G then it will traverse A-B-C-D-G. It traverses level wise i.e. explores the shallowest node first.
Depth First Search(DFS)
- In depth first search, the tree or the graph is traversed depth-wise i.e. it starts from a node called search key and then explores all the nodes along the branch then backtracks. It is implemented using a stack data structure that works on the concept of last in first out (LIFO).
- The time complexity for breadth first search is bd where b (branching factor) is the average number of child nodes for any given node and d is depth.
- It stores nodes linearly hence less space requirement.
- The major disadvantage is that this algorithm may go in an infinite loop.
- Example: If the search starts from root node A to reach goal node G then it will traverse A-B-D-G. It traverses depth wise i.e. explores the deepest node first.
Uniform Cost Search
- Uniform cost search is different from both DFS and BFS. In this algorithm, the cost comes into the picture. There may be different paths to reach the goal so the path with the least cost (cumulative sum of costs) is optimal. It traverses the path in the increasing order of cost. It is similar to the breadth-first search if the cost is the same for each transition.
- The time complexity for breadth first search is bd where b (branching factor) is the average number of child nodes for any given node and d is depth.
- Example: If the search starts from node A of the graph to reach goal node G then it will traverse A-C-G1. The cost will be 3.
2. Informed Search Algorithms
Informed search algorithms have domain knowledge. It contains the problem description as well as extra information like how far is the goal node. It is also called the Heuristic search algorithm. It might not give the optimal solution always but it will definitely give a good solution in a reasonable time. It can solve complex problems more easily than uninformed.
It is mainly of two types:
- Greedy Best First Search
- A* Search
Greedy Best First Search
In this algorithm, we expand the closest node to the goal node. The closeness factor is roughly calculated by heuristic function h(x). The node is expanded or explored when f (n) = h (n). This algorithm is implemented through the priority queue. It is not an optimal algorithm. It can get stuck in loops.
- Example: If we need to find the path from root node A to any goal state having minimum cost using greedy search then the solution would be A-B-E-H. It will start from B because it has less cost than C, then E because it has less cost than D and then G2.
A* Search
A* search is a combination of greedy search and uniform cost search. In this algorithm, the total cost (heuristic) which is denoted by f(x) is a sum of the cost in uniform cost search denoted by g(x) and cost of greedy search denoted by h(x).
f (x) = g (x) + h (x)
In this g(x) is the backward cost which is the cumulative cost from the root node to the current node and h(x) is the forward cost which is approximate of the distance of goal node and the current node.
4.5 (2,421 ratings)
View Course
Conclusion
In this article, various artificial intelligence search algorithms are explained in detail with examples. AI is growing at a rapid rate and acquiring the market and search algorithms are an important part of artificial intelligence.
Recommended Articles
This is a guide to Search Algorithms in AI. Here we discuss the introduction, properties, and types of search algorithms in AI. You may also have a look at the following articles to learn more –
