The best first search uses the concept of a priority queue and heuristic search. It is a search algorithm that works on a specific rule. The aim is to reach the goal from the initial state via the shortest path. The best First Search algorithm in artificial intelligence is used for for finding the shortest path from a given starting node to a goal node in a graph. The algorithm works by expanding the nodes of the graph in order of increasing the distance from the starting node until the goal node is reached.
- Introduction to best first search algorithm
- What is Best First Search?
- Best First Search Algorithm
- Variants of Best First Search
- Best First Search Example
- Advantages and Disadvantages
Contributed by: Rana Banerjee
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 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:
- 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.
- Informed (or Heuristic) methods, where the search is carried out by using additional information to determine the next step towards finding the solution. BFS is an example of such algorithms
Informed search methods are more efficient, low in cost and high in performance as compared to 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 BFS, 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.Â
BFS uses the concept of a Priority queue and heuristic search. To search the graph space, the BFS method uses two lists for tracking the traversal. An ‘Open’ list that keeps track of the current ‘immediate’ nodes available for traversal and a ‘CLOSED’ list that keeps track of the nodes already traversed.
Best First Search Algorithm
- Create 2 empty lists: OPEN and CLOSED
- Start from the initial node (say N) and put it in the ‘ordered’ OPEN list
- Repeat the next steps until the GOAL node is reached
- If the OPEN list is empty, then EXIT the loop returning ‘False’
- 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
- 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
- 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
- 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
The two variants of BFS are Greedy Best First Search and A* Best First Search. Greedy BFS makes use of the Heuristic function and search and allows us to take advantage of both algorithms.
There are various ways to identify the ‘BEST’ node for traversal and accordingly there are various flavours of BFS algorithm with different heuristic evaluation functions f(n). We will cover the two 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 along 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 which is mentioned over the paths in the given figure. The sum of the distance from the start city to each of these immediate next cities is denoted by the function g(n).
At any point, the decision on which city to go to 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).
Best First Search Example
Let’s have a look at the graph below and try to implement both Greedy BFS and A* algorithms step by step using the two list, OPEN and CLOSED.
| g(n) | Path Distance |
| h(n) | Estimate to Goal |
| f(n) | Combined Hueristics i.e. g(n) + h(n) |
Even though you would find that both Greedy BFS and A* algorithms find the path equally efficiently, a 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 the 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.
Advantages and Disadvantages of Best First Search
Advantages:
1. Can switch between BFS and DFS, thus gaining the advantages of both.
2. More efficient when compared to DFS.
Disadvantages:
1. Chances of getting stuck in a loop are higher.
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 free Artificial Intelligence courses to upskill in the domain.
While there are ample resources available online to help you understand the subject, there’s nothing quite like a certificate. Check out Great Learning’s PG program in Artificial Intelligence and Machine Learning to upskill in the domain. This course will help you learn from a top-ranking global school to build job-ready AIML skills. This 12-month program offers a hands-on learning experience with top faculty and mentors. On completion, you will receive a Certificate from The University of Texas at Austin, and Great Lakes Executive Learning.
