BFS (Best First Search) Concept, Algorithm and Implementation

Introduction to Search Algorithms

Most of the AI advancements that have caught our attention in the past have been the ability of the machine to beat humans at playing games. Be it ‘Deep Blue’ defeating the legendary Gary Kasparov in Chess in 1997 or ‘Alpha Go’ defeating Lee Sudol in 2016, the potential of AI to mimic and surpass human mental capabilities has exponentially increased over time.

Search algorithms form the core of such Artificial Intelligence programs. And while we may be inclined to think that this has limited applicability only in areas of gaming and puzzle-solving, such algorithms are in fact used in many more AI areas like route and cost optimizations, action planning, knowledge mining, robotics, autonomous driving, computational biology, software and hardware verification, theorem proving etc. In a way, many of the AI problems can be modelled as a search problem where the task is to reach the goal from the initial state via state transformation rules. So the search space is defined as a graph (or a tree) and the aim is to reach the goal from the initial state via the shortest path, in terms of cost, length, a combination of both etc.

All search methods can be broadly classified into two categories:

1. Uninformed (or Exhaustive or Blind) methods, where the search is carried out without any additional information that is already provided in the problem statement. Some examples include Breadth First Search, Depth First Search etc.
2. Informed (or Heuristic) methods, where search is carried out by using additional information to determine the next step towards finding the solution. Best First Search is an example of such algorithms

Informed search methods are more efficient, low in cost and high in performance as compared to the uninformed search methods.

What is Best First Search?

If we consider searching as a form of traversal in a graph, an uninformed search algorithm would blindly traverse to the next node in a given manner without considering the cost associated with that step. An informed search, like Best first search, on the other hand would use an evaluation function to decide which among the various available nodes is the most promising (or ‘BEST’) before traversing to that node.

The Best first search uses the concept of a Priority queue and heuristic search. To search the graph space, the best first search method uses two lists for tracking the traversal. An ‘Open’ list which keeps track of the current ‘immediate’ nodes available for traversal and ‘CLOSED’ list that keeps track of the nodes already traversed.

Best First Search Algorithm

1. Create 2 empty lists: OPEN and CLOSED
2. Start from the initial node (say N) and put it in the ‘ordered’ OPEN list
3. Repeat the next steps until GOAL node is reached
   1. If OPEN list is empty, then EXIT the loop returning ‘False’
   2. Select the first/top node (say N) in the OPEN list and move it to the CLOSED list. Also capture the information of the parent node
   3. If N is a GOAL node, then move the node to the Closed list and exit the loop returning ‘True’. The solution can be found by backtracking the path
   4. If N is not the GOAL node, expand node N to generate the ‘immediate’ next nodes linked to node N and add all those to the OPEN list
   5. Reorder the nodes in the OPEN list in ascending order according to an evaluation function f(n)

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

Variants of Best First Search

There are various ways to identify the ‘BEST’ node for traversal and accordingly there are various flavors of Best First Search algorithm with different heuristic evaluation functions f(n). We will cover 2 most popular versions of the algorithm in this blog, namely Greedy Best First Search and A* Best First Search

Let’s say we want to drive from city S to city E in the shortest possible road distance, and we want to do it in the fastest way, by exploring the least number of cities in the way, i.e. the least number of steps.

Whenever we arrive at an intermediate city, we get to know the air/flight distance from that city to our goal city E. This distance is an approximation of how close we are to the goal from a given node and is denoted by the heuristic function h(n). This heuristic value is mentioned within each node. However, note that this is not always equal to the actual road distance, as the road may have many curves while moving up a hill, and more..

Also, when we travel from one node to the other, we get to know the actual road distance between the current city and the immediate next city on the way and is mentioned over the paths in the given figure. The sum of the distance from the start city to each of these immediate next city is denoted by the function g(n).

At any point, the decision on which city to go next is governed by our evaluation function. The city which gives the least value for this evaluation function will be explored first.

The only difference between Greedy BFS and A* BFS is in the evaluation function. For Greedy BFS the evaluation function is f(n) = h(n) while for A* the evaluation function is f(n) = g(n) + h(n).

Essentially, since A* is more optimal of the two approaches as it also takes into consideration the total distance travelled so far i.e. g(n).

So let’s have a look at the graph and try to implement both Greedy BFS and A* algorithms step by step using the two list, OPEN and CLOSED.

Even though you would find that both Greedy BFS and A* algorithms find the path equally efficiently, number of steps, you may notice that the A* algorithm is able to come up with is a more optimal path than Greedy BFS. So in summary, both Greedy BFS and A* are Best first searches but Greedy BFS is neither complete, nor optimal whereas A* is both complete and optimal. However, A* uses more memory than Greedy BFS, but it guarantees that the path found is optimal.

Try changing the graph and see how the algorithms perform on them. Leave your comments below for any doubts. Don’t forget to check out popular Artificial Intelligence courses to up skill in the domain.