Best First Search in AI: How It Works, Types, and Examples

What Is Best First Search in AI?

Best First Search is an informed (heuristic) search technique that traverses a graph or tree by selecting the node that appears closest to the goal at each step. It uses an evaluation function to rank nodes and expands the best-ranked one first.

The algorithm blends the strengths of two uninformed strategies. Like Breadth First Search, it can look across multiple branches, and like Depth First Search, it can dive deep along a promising path. The difference is that Best First Search makes an informed choice using domain-specific knowledge by estimating how close a node is to the goal state, thereby dramatically reducing exploration time.

Build real-world LLM applications, RAG pipelines, and Agentic AI solutions using Microsoft technologies and industry-leading AI frameworks while completing 7+ hands-on projects on that knowledge with the Applied Generative AI Specialization.

Core Concepts of Best First Search

The efficiency of Best First Search hinges on one evaluation formula and two fundamental data-tracking mechanisms.

1. Evaluation Function f(n)

The evaluation function f(n) assigns a score to each node n, determining its priority for expansion. The algorithm always expands the node with the best (lowest) f(n) value next. How f(n) is defined is exactly what separates the different variants of Best First Search.

2. Heuristic Function h(n)

The heuristic function h(n) is an estimate of the remaining cost or distance from node n to the goal. For example, the straight-line distance between two points on a map. A good heuristic guides the search almost directly to the goal, while a weak or misleading one sends it down poor paths, so the quality of h(n) largely determines performance.

3. OPEN List (Priority Queue)

The OPEN list keeps track of all frontier nodes that have been discovered but not yet expanded, sorted in ascending order of their evaluation cost. It is implemented as a priority queue so the most promising node is always ready to be removed and expanded first.

4. CLOSED List

The CLOSED list tracks all nodes that have already been expanded. Keeping it prevents infinite loops and redundant exploration by ensuring the algorithm never re-processes a node it has already visited.

Variants of Best First Search

Depending on how the evaluation function f(n) is defined, Best First Search can be implemented as two primary algorithms.

1. Greedy Best First Search — f(n) = h(n)

Greedy Best First Search focuses exclusively on the immediate future. It uses the evaluation function f(n) = h(n), greedily expanding the node that appears closest to the goal and completely ignoring the backward path cost g(n) incurred to reach that node.

• Pros: Finds a solution quickly when the heuristic is highly accurate; uses less memory than A*.
• Cons: It is not optimal and can easily get stuck in dead ends or loops if a promising path is actually blocked.

2. A* Search Algorithm — f(n) = g(n) + h(n)

A* Search fixes the shortcomings of Greedy Search by evaluating the total path cost. Its evaluation function balances past cost and future cost as f(n) = g(n) + h(n), where g(n) is the exact cost to reach node n from the start and h(n) is the estimated cost from n to the goal.

• Pros: Guaranteed to be optimal and complete, provided the heuristic h(n) is admissible (never overestimates the true cost).
• Cons: High memory consumption because it stores all generated nodes in memory.

The step-by-step AI Engineer roadmap is designed for professionals seeking to understand the full scope of the role. Explore the skills, tools, salary potential, and career roadmap needed to build a successful career as an AI Engineer.

Step-by-Step Best First Search Algorithm

The baseline operational cycle of a Best First Search is structured as follows:

1. Initialize: Place the starting node into the OPEN priority queue with its calculated evaluation score. Leave the CLOSED list empty.
2. Loop: Check whether the OPEN list is empty. If it is, the search has failed.
3. Select Node: Dequeue the node with the lowest f(n) value from OPEN and move it to the CLOSED list.
4. Goal Test: If the selected node is the target goal, terminate the search and reconstruct the path using parent pointers.
5. Expand: Generate all immediate neighboring (child) nodes of the selected node.
6. Evaluate & Insert: For each child node not already in OPEN or CLOSED, calculate its f(n) score and insert it into the OPEN priority queue.
7. Repeat: Return to step 2.

Example Pseudocode

function BestFirstSearch(start, goal):
OPEN = priority_queue()
OPEN.push(start, f(start))
CLOSED = empty set
while OPEN is not empty:
node = OPEN.pop_lowest_f()
if node == goal:
return reconstruct_path(node)
CLOSED.add(node)
for each neighbor of node:
if neighbor not in OPEN and neighbor not in CLOSED:
OPEN.push(neighbor, f(neighbor))
return failure

Best First Search Example

Consider a graph where we want to travel from start node S to goal node G. Each node has a heuristic value h(n) estimating its distance to G: S = 13, A = 12, B = 4, C = 7, D = 3, and G = 0. S connects to A and B, B connects to C and D, and D connects to G. Using a greedy evaluation where f(n) = h(n), the search proceeds like this:

The algorithm expands S, jumps to B because it has the lowest heuristic, then to D, and finally reaches G. The path found is S → B → D → G. Notice how the heuristic let the search skip the less promising node A entirely.

Algorithm Analysis: Greedy Best First Search vs A* Search

Both algorithms are best first searches, but they differ sharply in their guarantees and costs. In the table below, b is the branching factor, m is the maximum depth of the search space, and d is the depth of the optimal goal.

Also Read: Time and Space Complexities

Advantages and Disadvantages of Best First Search

Advantages

• More efficient than uninformed search because the heuristic guides exploration toward the goal
• Flexible, since it can behave like BFS or DFS depending on the graph and heuristic
• Relatively simple to understand and implement
• Well suited to large search spaces where blind search would be too slow

Disadvantages

• The greedy version is neither optimal nor complete
• Performance depends heavily on the accuracy of the heuristic
• Can be memory-intensive because it stores many nodes
• May get trapped following a misleading path without a proper CLOSED list

From zero to AI builder in 8 weeks. Learn to create AI-powered apps, automate workflows, build intelligent agents, and turn your ideas into real-world MVPs using industry-leading AI tools with our AI Accelerator Program.

Applications of Best First Search in AI

Best First Search and its variants power many practical systems, including

• GPS and route navigation
• pathfinding for game AI
• robotics motion planning
• network routing
• puzzle solving such as the 8-puzzle and 15-puzzle
• prioritized crawling in search and NLP tasks

Best First Search Implementation in Python (heapq)

The example below uses Python's heapq module as the priority queue, an adjacency list for the graph, and a dictionary of heuristic values:

import heapq
def best_first_search(graph, heuristic, start, goal):
open_list = [(heuristic[start], start)]
closed = set()
while open_list:
_, node = heapq.heappop(open_list)
if node == goal:
return f"Goal {goal} reached"
closed.add(node)
for neighbor in graph[node]:
if neighbor not in closed:
heapq.heappush(open_list, (heuristic[neighbor], neighbor))
return "Goal not reachable"
graph = {'S': ['A', 'B'], 'A': [], 'B': ['C', 'D'], 'C': [], 'D': ['G'], 'G': []}
heuristic = {'S': 13, 'A': 12, 'B': 4, 'C': 7, 'D': 3, 'G': 0}
print(best_first_search(graph, heuristic, 'S', 'G'))

The priority queue always returns the node with the smallest heuristic value, so the search naturally follows the most promising direction toward the goal.

Key Takeaways

• Best First Search is an informed search algorithm that expands the most promising node first using a heuristic evaluation function f(n)
• Its core components are the evaluation function f(n), the heuristic h(n), the OPEN list (priority queue), and the CLOSED list
• Greedy Best First Search uses f(n) = h(n) and is fast but neither optimal nor complete; A* Search uses f(n) = g(n) + h(n) and is optimal and complete with an admissible heuristic
• It is widely used in GPS navigation, game AI, robotics, and puzzle solving, such as the 8-puzzle

FAQs

1. Is Best First Search the same as Breadth First Search?

No. Both are abbreviated as BFS, which is confusing. Breadth First Search is uninformed and explores levels one by one, while Best First Search is informed and uses a heuristic to choose which node to expand.

2. Is Best First Search optimal?

Greedy Best First Search is not optimal. A* Search, which is a best first algorithm, is optimal when its heuristic is admissible.

3. What is the difference between informed and uninformed search?

Uninformed search (like BFS and DFS) does not know how close a node is to the goal, whereas informed search, such as Best First Search, uses a heuristic to guide exploration.

4. Why is it called greedy?

Because Greedy Best First Search always grabs the node that looks best right now based only on h(n), without considering the cost already spent to get there.

5. What data structure does Best First Search use?

It uses a priority queue (the OPEN list) always to retrieve the most promising node, supported by a CLOSED list to track expanded nodes and prevent loops.