Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Example
3.
Algorithm Used
3.1.
Implementation in C++
3.1.1.
Output:
3.2.
Implementation in Java
3.2.1.
Output:
4.
Complexities Analysis
5.
Frequently Asked Questions
5.1.
Best First Search uses which data structure?
5.2.
What is the advantage of the best first search?
5.3.
Is Informed Search Complete?
5.4.
Why is A * better than Best First Search?
5.5.
What is Graph?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Best First Search or Informed Search

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

This article will discuss a famous Data Structure (Graph) Problem, i.e., Best First Search or Informed Search.

Best First Search or Informed Search is a traversal technique of a tree traversal that uses an evaluation function to decide the most promising adjacent to be visited next and then explored.

It is different from BFS and DFS Algorithm because, in both, we can consider any of the adjacent as the next node without considering any cost function.

Let's see an example to better understand Best First Search or Informed Search.

Example

Best First Search or Informed Search Image

Suppose we start from source "A" to goal "J" in this example.

Considering the given cost and the Best First Search.

The PriorityQueue initially contains A.

 

We remove A from the PriorityQueue and process the unvisited neighbours of A to PriorityQueue.

Now, the PriorityQueue contains {B,D,C}. Here D is put before C as D has the lesser cost.

 

We remove B and process the unvisited neighbours of B to PriorityQueue.

Now, the PriorityQueue contains {D,C,F,E}.

 

We remove D and process the unvisited neighbours of C to PriorityQueue.

Now, the PriorityQueue contains {C,I,F,E}.

 

We remove C from the PriorityQueue and process the unvisited neighbours of B to PriorityQueue.

Now, the PriorityQueue contains {I,F,E,G,H}.

 

Now, We remove I from the PriorityQueue.

Since our goal is "J" and J is the neighbour of I.

Therefore, we return.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Algorithm Used

The algorithm used is similar to that of the BFS Search. The only difference is to use PriorityQueue instead of Queue to store the costs of nodes with the lowest evaluation function value. 

The first is to create an empty PriorityQueue, Suppose, PriorityQueue pq;

Then Insert "element" in pq, pq.insert(element) and until the PriorityQueue is empty, we do u = PriorityQueue.DeleteMin and 

Run an if-else statement where 

         If u is the goal, then we exit.

         else

            For each neighbour v of u

               If v = "Unvisited"

                    Then Mark v = "Visited"                    

                    And do pq.insert(v)

               and Mark u "Examined".

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
vector<vector<pi>> graph;
// Function to add edges to a graph
void addedge(int x, int y, int cost)
{
    graph[x].push_back(make_pair(cost, y));
    graph[y].push_back(make_pair(cost, x));
}

//Driver Code
int main()
{
    //Number of Nodes
    int v = 14;
    graph.resize(v);
 
    addedge(0, 1, 2);
    addedge(0, 2, 5);
    addedge(0, 3, 4);
    addedge(1, 4, 8);
    addedge(1, 5, 7);
    addedge(2, 6, 9);
    addedge(2, 7, 10);
    addedge(3, 8, 6);
    addedge(8, 9, 3);
    addedge(8, 10, 4);
    addedge(9, 11, 1);
    addedge(9, 12, 5);
    addedge(9, 13, 2);
 
    int source = 0;
    int target = 7;
    int n=v;
    
    vector<bool> visited(n, false);
    // Priority Queue is sorted by the first value of the pair.
    priority_queue<pi, vector<pi>, greater<pi> > pq;
    pq.push(make_pair(0, source));
    int s = source;
    visited[s] = true;
    while (!pq.empty()) {
        int x = pq.top().second;
        // Displaying the path having the lowest cost.
        cout << x << " ";
        pq.pop();
        if (x == target)
            break;
 
        for (int i = 0; i < graph[x].size(); i++) {
            if (!visited[graph[x][i].second]) {
                visited[graph[x][i].second] = true;
                pq.push(make_pair(graph[x][i].first,graph[x][i].second));
            }
        }
    }
    return 0;
}

 

Output:

0 1 3 2 8 9 11 13 10 12 5 4 6 7 

Implementation in Java

import java.util.ArrayList;
import java.util.PriorityQueue;
 
class CodingNinjas
{
  static ArrayList<ArrayList<edge> > adj = new ArrayList<>();
  // Function for adding the edges to a graph
  static class edge implements Comparable<edge>
  {
    int v, cost;
    edge(int v, int cost)
    {
      this.v = v;
      this.cost = cost;
    }
    @Override public int compareTo(edge o)
    {
      if (o.cost < cost) {
        return 1;
      }
      else
        return -1;
    }
  }
 
  public CodingNinjas(int v)
  {
    for (int i = 0; i < v; i++) {
      adj.add(new ArrayList<>());
    }
  }
 
  //Function to apply Best- First Search
  static void best_first_search(int source, int target, int v){
    PriorityQueue<edge> pq = new PriorityQueue<>();
    boolean visited[] = new boolean[v];
    visited = true;
    pq.add(new edge(source, -1));
    while (!pq.isEmpty()) {
      int x = pq.poll().v;
      //Displaying the path having the lowest cost.
      System.out.print(x + " ");
      if (target == x) {
        break;
      }
      for (edge adjacentNodeEdge : adj.get(x)) {
        if (!visited[adjacentNodeEdge.v]) {
          visited[adjacentNodeEdge.v] = true;
          pq.add(adjacentNodeEdge);
        }
      }
    }
  }
  void addedge(int u, int v, int cost)
  {
    adj.get(u).add(new edge(v, cost));
    adj.get(v).add(new edge(u, cost));
  }
 
// Driver Code
  public static void main(String args[])
  {
    int v = 14;
    CodingNinjas graph = new CodingNinjas(v);
    graph.addedge(0, 1, 2);
    graph.addedge(0, 2, 5);
    graph.addedge(0, 3, 4);
    graph.addedge(1, 4, 8);
    graph.addedge(1, 5, 7);
    graph.addedge(2, 6, 9);
    graph.addedge(2, 7, 10);
    graph.addedge(3, 8, 6);
    graph.addedge(8, 9, 3);
    graph.addedge(8, 10, 4);
    graph.addedge(9, 11, 1);
    graph.addedge(9, 12, 5);
    graph.addedge(9, 13, 2);
 
    int source = 0;
    int target = 9;
    best_first_search(source, target, v);
  }
}

 

Output:

0 1 3 2 8 9

Complexities Analysis

Time Complexity- The worst-case time complexity is O(b^d+1), where b is the branching factor and d is the depth of a tree. In the worst case, we may have to visit all nodes before we reach the goal. 

Space  Complexity- The worst-case space complexity is O(b^d), where b is the branching factor and d is the depth of a tree.

Let's see some FAQs related to the Best First Search or Informed Search.

Frequently Asked Questions

Best First Search uses which data structure?

Priority Queue is used for the best first search as Priority Queue maintains the fringe in ascending order of f values. 

What is the advantage of the best first search?

Best-first search allows us to take advantage of both algorithms. With the help of the best-first search, we can choose the most promising node at each step.

Is Informed Search Complete?

It may or may not be complete as Informed Search is also known as Heuristic Search. 

Why is A * better than Best First Search?

A* achieves better performance by using heuristics to guide its search and combines the advantages of Best-first Search and Uniform Cost Search.

What is Graph?

A graph is a non-linear data structure having a finite number of nodes or vertices and the edges that connect them.

Conclusion

This article discusses the problem of Best First Search or Informed Search with their examples and implementation. We had also seen some FAQs related to them.

After reading about the above problem, Best First Search or Informed Search, are you not feeling excited to read/explore more articles on Data Structures and Algorithms? Don't worry; Coding Ninjas has you covered. See GraphBinary TreeBFS vs DFSCheck for Balanced Parentheses in an Expression, and Stack to learn.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! 

Happy Learning!

Conclusion Image

Previous article
Breadth-First Search
Next article
BFS in Disconnected Graph
Live masterclass