Best First Search algorithm

Best First Search is a searching algorithm which works on a set of defined rules. It makes use of the concept of priority queues and heuristic search. The objective of this algorithm is to reach the goal state or final state from an initial state by the shortest route possible.

Table of contents:

1. What are Searching algorithms?
2. What is Best First Search?
3. Comparison of Best First Search Algorithm
4. Example of Best First Search
5. Advantages and Disadvantages of Best First Search Algorithm

We will get started with Best First Search algorithm.

What are Searching algorithms?

In 1997 ‘Deep Blue’ an AI beat the legendary Gary Kasparov in Chess , and in 2016 ‘Alpha Go’ defeated the champion of the game Go. The ability of artificial intelligence to mimc humans and surpass their mental capabilties has exceeded over time.

Searching algorithms form the base of such programs , they are utilized in areas like course and cost optimization, action planning, information mining, mechanical technology, independent driving, computational science, programming and equipment check, hypothesis demonstrating and so on.

As it were, a considerable lot of the AI issues can be considered such that the objective is to reach the final goal from an initial point by means of state change rules. So the search space or options are characterised as a diagram (or a tree) and the point is to arrive at the objective from the underlying state through the shortest path.

The searching algorithms can be classified into two types

• Uninformed methods : in this method no additonal information is provided. Examples of such methods are breadth for search or depth for search algorthims.

• Informed methods : also known as Heuristic method where search is carried out by using additonal information to find out the next step to take.Best first search algorithm falls under this category.

How to perform this algorithm is explained below

What is Best First Search?

Unlike uninformed search where the agent blindly traverses to the next node in best first search a uses an evaluation function to determine which neighbor node would be most appropriate to move to.

It uses the concept of a Priority queue and heuristic search.

Method of Best First Search algorithm

• Create two empty lists
• Start from the inital node and add it to the ordered open list
• Next the below steps are repeated until the final node or endpoint is reached
• If the open list is empty exit the loop and return a False statement which says that the final node cannot be reached
• Select the top node in the open list and move it to the closed list while keeping track of the parent node
• If the node removed is the endpoint node return a True statement meaning a path has been found and moving the node to the closed list
• However if it is not the endpoint node then list down all the neighboring nodes of it and add them to the open list
• According to the evaluation function re order the nodes.

This algorithm will traverse the shortest path first in the queue. The time complexity of the algorithm is O(n*log(n)) .

Comparison of Best First Search Algorithm

A* Algorithm

In best first search algorithm system moves to the next state based on heuristics function , the lowest heuristic value is chosen , however in A* algorithm the next state depends on the heurisitic as well as g componenet which is the path from initial to particular state.

The best first algorithm does not consider the cost of the path to a particular state. All it cares about is that which next state from current state has the lowest heuristics.The A* algorithm but conisders the cost of going to that state along with the heuristic.

A* also allows going back to a previous state however in best first search the decision is final.

Greedy

Greedy builds solution piece by piece always choosing the next node that offers most benefit , the best first search algorithm chooses the next node based on the heuristics function.

The greedy chooses the next best option for short term in the next juncture , the cheaper it is to move to the next node that specific route it will take ,the best first search algorithm chooses the next best option based on the cheapest path it has to take from all the options.

Example of Best First Search

Here we have a graph where our aim is to traverse from the node S to node G

The heuristic value associated with each node has been provided.

We make use of two lists open and close , initally only node S is present in the open list and closed is empty.
Open : [S]
Closed: []

For first iteration we pop node S and move it to the closed list and the neighbor nodes are added to open
Open: [A,B]
Closed: [S]

For second iteration the heuristic value of nodes A and B are compared , since B has lower heuristic it is poped and moved to the closed list.Neighboring nodes of B are pushed to the open list.
Open: [E,F,A]
Closed: [S,B]

For third iteration the heuristic values of E,F and A are compared and since F has lowest heuristic it is added to the closed list.Neighbors of F are added to the open list.
Open: [I,G,E,A]
Closed: [S,B,F]

For the fourth iteration we have our target node in the open list hence we select that and move it to the closed list.
Open: [I,E,A]
Closed: [S,B,F,G]

The path taken is S->B->F->G

Advantages and Disadvantages of Best First Search Algorithm

Advantages

• More efficient compared to algorithms like DFS
• Has advantages of both DFS and BFS as can switch between them both

Disadvantages

• Algorithm may be stuck in a loop

With this article at OpenGenus, you must have the complete idea of Best First Search algorithm.