Search Algorithms in AI

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 are 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 explained below:

• 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 how to traverse and 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 breadthwise, i.e. it starts from a node called search key and then explores all the neighbouring 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 b^d 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 the 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 b^d 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 b^d 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 with 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.

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.

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 –

1. Searching in Data Structure
2. Deep Learning Algorithms
3. Types of Machine Learning Algorithms
4. Send Mail in Python
5. Guide to Uninformed Search