# What is Best First Search

The Best-First Search is a strategy used to find the most efficient path from one point to another in a network or graph. Imagine you're trying to navigate through a maze to reach a specific destination.

The Best-First Search algorithm works by exploring the available paths and always choosing the one that seems most promising based on a specific criterion. This criterion is typically a heuristic, which is a fancy word for a rule of thumb or an estimation of how good a path is.

For example, let's say you're in a maze, and you can only see a few steps ahead. You might use the distance to the destination as your heuristic. The Best-First Search would prioritize the paths that seem closer to the goal based on that heuristic. It would keep exploring those paths until it either finds the destination or realizes that it's stuck and needs to backtrack.

The algorithm keeps a list of the available paths and selects the one that appears to be the most promising according to the chosen heuristic. It continues this process of selecting the best path, exploring it, and updating the list until it reaches the destination.

In summary, Best-First Search is like a smart explorer who tries to make the best decisions by considering a heuristic, like distance to the goal, to find the most efficient path through a maze or network. It's an effective strategy for navigation and optimization problems.

## Who invented it?

The Best-First Search algorithm is a general search strategy that has been developed and refined by multiple researchers in the field of computer science and artificial intelligence. It is not attributed to a single inventor.

The concept of best-first search can be traced back to the early days of artificial intelligence research. Some notable contributors to the development of search algorithms include John McCarthy, Marvin Minsky, and Herbert A. Simon, among others. These researchers laid the foundation for various search algorithms, including best-first search, in the 1950s and 1960s.

Over time, the Best-First Search algorithm has been studied and adapted by numerous researchers and practitioners in the field of computer science. It has found applications in various domains, such as pathfinding, game playing, robotics, and more. The algorithm continues to be a fundamental tool in the field of artificial intelligence and remains an active area of research.

## Pseudocode

```
function BestFirstSearch(startNode, goalNode)
create an empty priority queue Q
create an empty set visited
enqueue startNode into Q with a priority based on a heuristic value
visited.add(startNode)
while Q is not empty
currentNode = Q.dequeue()
if currentNode is the goalNode
return path to currentNode
for each neighborNode of currentNode
if neighborNode is not in visited
enqueue neighborNode into Q with a priority based on a heuristic value
visited.add(neighborNode)
return no path found
```

In this pseudocode, startNode represents the initial node or starting point, and goalNode represents the destination or goal node. The algorithm uses a priority queue Q to store the nodes to be explored. The priority of each node in the queue is determined by a heuristic value, which estimates the desirability of that node based on the problem domain.

The algorithm starts by enqueueing the startNode into the priority queue with an initial priority based on the heuristic value. It also keeps track of the visited nodes in the visited set.

The main loop continues until the priority queue is empty. In each iteration, the algorithm dequeues the node with the highest priority from Q. If this node is the goalNode, it means the path to the goal has been found, and the algorithm returns that path.

If the current node is not the goal, the algorithm examines its neighboring nodes. For each unvisited neighbor, it calculates the heuristic value and enqueues it into the priority queue Q. The visited set is updated to include the newly visited node.

If the loop completes without finding a path to the goal, it means no path exists.

The algorithm starts by enqueueing the startNode into the priority queue with an initial priority based on the heuristic value. It also keeps track of the visited nodes in the visited set.

The main loop continues until the priority queue is empty. In each iteration, the algorithm dequeues the node with the highest priority from Q. If this node is the goalNode, it means the path to the goal has been found, and the algorithm returns that path.

If the current node is not the goal, the algorithm examines its neighboring nodes. For each unvisited neighbor, it calculates the heuristic value and enqueues it into the priority queue Q. The visited set is updated to include the newly visited node.

If the loop completes without finding a path to the goal, it means no path exists.

## Sample Code

```
// C++ code snippet
#include "iostream"
#include "queue"
#include "vector"
#include "unordered_set"
// Structure to represent a node in the graph
struct Node {
int id;
std::vector < std::pair < Node*, int > > neighbors; // List of neighbor nodes and their edge weights
};
// Comparator for priority queue based on heuristic values
struct CompareNodes {
bool operator()(const Node* lhs, const Node* rhs) const {
// Assuming the heuristic value is stored in the "heuristic" member of the Node struct
return lhs->heuristic > rhs->heuristic;
}
};
// Best-First Search function
std::vector < Node* > bestFirstSearch(Node* startNode, Node* goalNode) {
std::priority_queue< Node*, std::vector
```, CompareNodes> pq; // Priority queue
std::unordered_set < Node* > visited; // Set of visited nodes
// Initialize the start node
startNode->heuristic = calculateHeuristic(startNode, goalNode);
pq.push(startNode);
visited.insert(startNode);
while (!pq.empty()) {
Node* currentNode = pq.top();
pq.pop();
if (currentNode == goalNode) {
// Goal node reached, construct and return the path
return constructPath(currentNode);
}
// Explore neighbors
for (auto neighbor : currentNode->neighbors) {
Node* neighborNode = neighbor.first;
if (visited.find(neighborNode) == visited.end()) {
neighborNode->heuristic = calculateHeuristic(neighborNode, goalNode);
pq.push(neighborNode);
visited.insert(neighborNode);
}
}
}
// No path found
return std::vector < Node* >();
}
// Function to calculate the heuristic value (dummy implementation, replace with appropriate logic)
int calculateHeuristic(Node* currentNode, Node* goalNode) {
// Replace with your heuristic calculation logic here
// The heuristic value should estimate the cost or distance from the current node to the goal node
return 0;
}
// Function to construct the path from start to goal
std::vector < Node*> constructPath(Node* goalNode) {
std::vector < Node*> path;
Node* currentNode = goalNode;
while (currentNode != nullptr) {
path.push_back(currentNode);
currentNode = currentNode->parent;
}
std::reverse(path.begin(), path.end());
return path;
}
int main() {
// Create the graph (dummy graph for demonstration)
Node* nodeA = new Node{1};
Node* nodeB = new Node{2};
Node* nodeC = new Node{3};
Node* nodeD = new Node{4};
Node* nodeE = new Node{5};
nodeA->neighbors = {{nodeB, 2}, {nodeC, 3}};
nodeB->neighbors = {{nodeD, 4}};
nodeC->neighbors = {{nodeD, 2}, {nodeE, 5}};
nodeD->neighbors = {{nodeE, 1}};
// Perform Best-First Search
std::vector < Node*> path = bestFirstSearch(nodeA, nodeE);
// Print the path
if (!path.empty()) {
std::cout << "Path found: ";
for (Node* node : path) {
std::cout << node->id << " ";
}
std::cout << std::endl;
}
}
}

```
# Python code snippet
import heapq
# Node class to represent a node in the graph
class Node:
def __init__(self, id):
self.id = id
self.neighbors = [] # List of neighbor nodes and their edge weights
# Best-First Search function
def best_first_search(start_node, goal_node):
priority_queue = [] # Priority queue
heapq.heappush(priority_queue, (0, start_node)) # Initial priority is 0 (dummy value)
visited = set()
while priority_queue:
_, current_node = heapq.heappop(priority_queue)
if current_node == goal_node:
# Goal node reached, construct and return the path
return construct_path(current_node)
if current_node not in visited:
visited.add(current_node)
# Explore neighbors
for neighbor, _ in current_node.neighbors:
if neighbor not in visited:
priority = calculate_heuristic(neighbor, goal_node)
heapq.heappush(priority_queue, (priority, neighbor))
neighbor.parent = current_node
# No path found
return []
# Function to calculate the heuristic value (dummy implementation, replace with appropriate logic)
def calculate_heuristic(current_node, goal_node):
# Replace with your heuristic calculation logic here
# The heuristic value should estimate the cost or distance from the current node to the goal node
return 0
# Function to construct the path from start to goal
def construct_path(goal_node):
path = []
current_node = goal_node
while current_node is not None:
path.append(current_node)
current_node = current_node.parent
path.reverse()
return path
# Create the graph (dummy graph for demonstration)
nodeA = Node(1)
nodeB = Node(2)
nodeC = Node(3)
nodeD = Node(4)
nodeE = Node(5)
nodeA.neighbors = [(nodeB, 2), (nodeC, 3)]
nodeB.neighbors = [(nodeD, 4)]
nodeC.neighbors = [(nodeD, 2), (nodeE, 5)]
nodeD.neighbors = [(nodeE, 1)]
# Perform Best-First Search
path = best_first_search(nodeA, nodeE)
# Print the path
if path:
print("Path found:", end=" ")
for node in path:
print(node.id, end=" ")
print()
else:
print("No path found.")
```

```
import java.util.*;
// Node class to represent a node in the graph
class Node {
int id;
List
``` neighbors; // List of neighbor nodes and their edge weights
Node(int id) {
this.id = id;
this.neighbors = new ArrayList<>();
}
}
// Edge class to represent an edge between nodes
class Edge {
Node neighbor;
int weight;
Edge(Node neighbor, int weight) {
this.neighbor = neighbor;
this.weight = weight;
}
}
// Best-First Search class
class BestFirstSearch {
// Comparator for priority queue based on heuristic values
static class NodeComparator implements Comparator {
@Override
public int compare(Node node1, Node node2) {
// Assuming the heuristic value is stored in the "heuristic" member of the Node class
return Integer.compare(node1.heuristic, node2.heuristic);
}
}
// Best-First Search function
static List bestFirstSearch(Node startNode, Node goalNode) {
PriorityQueue priorityQueue = new PriorityQueue<>(new NodeComparator()); // Priority queue
priorityQueue.offer(startNode);
Set visited = new HashSet<>();
while (!priorityQueue.isEmpty()) {
Node currentNode = priorityQueue.poll();
if (currentNode == goalNode) {
// Goal node reached, construct and return the path
return constructPath(currentNode);
}
if (!visited.contains(currentNode)) {
visited.add(currentNode);
// Explore neighbors
for (Edge neighbor : currentNode.neighbors) {
if (!visited.contains(neighbor.neighbor)) {
neighbor.neighbor.heuristic = calculateHeuristic(neighbor.neighbor, goalNode);
priorityQueue.offer(neighbor.neighbor);
neighbor.neighbor.parent = currentNode;
}
}
}
}
// No path found
return new ArrayList<>();
}
// Function to calculate the heuristic value (dummy implementation, replace with appropriate logic)
static int calculateHeuristic(Node currentNode, Node goalNode) {
// Replace with your heuristic calculation logic here
// The heuristic value should estimate the cost or distance from the current node to the goal node
return 0;
}
// Function to construct the path from start to goal
static List constructPath(Node goalNode) {
List path = new ArrayList<>();
Node currentNode = goalNode;
while (currentNode != null) {
path.add(currentNode);
currentNode = currentNode.parent;
}
Collections.reverse(path);
return path;
}
public static void main(String[] args) {
// Create the graph (dummy graph for demonstration)
Node nodeA = new Node(1);
Node nodeB = new Node(2);
Node nodeC = new Node(3);
Node nodeD = new Node(4);
Node nodeE = new Node(5);
nodeA.neighbors.add(new Edge(nodeB, 2));
nodeA.neighbors.add(new Edge(nodeC, 3));
nodeB.neighbors.add(new Edge(nodeD, 4));
nodeC.neighbors.add(new Edge(nodeD, 2));
nodeC.neighbors.add(new Edge(nodeE, 5));
nodeD.neighbors.add(new Edge(nodeE, 1));
// Perform Best-First Search
List path = bestFirstSearch(nodeA, nodeE);
// Print the path
if (!path.isEmpty()) {
System.out.print("Path found: ");
}
}

## Time and Space Complexity

**Time Complexity:**

The time complexity of Best-First Search is often expressed in terms of the number of nodes explored. Let's denote the total number of nodes in the graph as "N" and the number of edges as "E."

In the worst case, where the goal node is located deep within the graph, the algorithm might need to explore a large portion of the graph before finding the goal. In such cases, the time complexity can be exponential, specifically O(b^d), where "b" is the branching factor (average number of successors for each node) and "d" is the depth of the goal node. This happens when the heuristic function does not provide a strong enough estimate to guide the search efficiently.

However, with a good heuristic function that consistently provides accurate estimates, the Best-First Search algorithm can often achieve a much better time complexity. In practice, it tends to perform quite well on many real-world problems, often outperforming uninformed search algorithms like Breadth-First Search or Depth-First Search.

**Space Complexity:**

The space complexity of Best-First Search is influenced by the size of the graph and the data structures used to implement the algorithm.

The algorithm uses a priority queue to store and retrieve nodes based on their heuristic values. The space complexity of the priority queue is typically O(N), where N is the number of nodes in the graph.

Additionally, the algorithm maintains a set of visited nodes to avoid revisiting them. The space required for this set is also O(N) in the worst case, as it needs to store information about each visited node.

Overall, the space complexity of the Best-First Search algorithm is generally O(N), where N is the number of nodes in the graph. However, if there are additional data structures or bookkeeping required, the space complexity may increase accordingly.

## Advantages

1. Efficiency: Best-First Search can be highly efficient when a good heuristic function is used. The algorithm focuses on exploring the most promising paths first, based on the heuristic values, which can lead to finding the goal node faster compared to uninformed search algorithms.

2. Optimality (under certain conditions): If the heuristic function used in Best-First Search satisfies certain conditions, such as being admissible (never overestimating the cost to reach the goal) and consistent (satisfying the triangle inequality), then the algorithm is guaranteed to find an optimal solution. This means it will find the shortest path or the best solution according to the problem's objective.

3. Memory efficiency: Best-First Search only needs to store a priority queue of nodes, which makes it memory-efficient compared to some other search algorithms. It doesn't require maintaining a tree or graph structure explicitly.

## Disadvantages

1. Completeness: Best-First Search is not guaranteed to find a solution if one exists, especially in cases where the heuristic function is not well-informed or leads to poor decisions. The algorithm may get trapped in a suboptimal path or fail to explore certain areas of the graph, potentially missing the optimal solution.

2. Heuristic dependency: The effectiveness of Best-First Search heavily relies on the quality of the heuristic function used. If the heuristic function is inaccurate or provides poor estimates, the algorithm may not find an optimal solution or could be misled into exploring less promising paths.

3. Lack of exploration: Best-First Search tends to prioritize the most promising path based on the heuristic, potentially neglecting other paths that might lead to better solutions. It can be limited in its ability to explore alternative options or consider the global picture of the search space.

4. Sensitivity to input order: The order in which nodes are expanded can impact the behavior of Best-First Search. If the initial ordering of nodes in the priority queue is unfavorable, the algorithm may not perform optimally or may exhibit different characteristics.

5. Time complexity in worst cases: In worst-case scenarios where the heuristic function fails to guide the search efficiently, Best-First Search can suffer from exponential time complexity, similar to uninformed search algorithms like Breadth-First Search or Depth-First Search. It may become inefficient and impractical for large or complex search spaces.