Best-First Search
Best-First Search is an informed graph traversal algorithm that explores a graph by expanding the most promising node first, as determined by a specific heuristic evaluation function f(n). Unlike uninformed search strategies like Breadth-First or Depth-First Search, Best-First Search uses problem-specific domain knowledge to prioritize nodes, dramatically reducing the state-space search footprint in complex graphs, provided the heuristic function is admissible and monotonic.
HOW-TO IMPLEMENT & CONFIGURE
- Modern runtime environment supporting generic programming and priority queues (e.g., Python 3.10+, Go 1.18+, Rust 1.60+)
- Understanding of graph data structures (adjacency lists, node structs, memory alignment)
- Deterministic heuristic function h(n) estimating the cost from node n to the target goal
Step 1
Define the foundational Node data structures and initialize a min-heap priority queue to maintain the open set ordered by heuristic cost values.
import heapq
class Node:
def __init__(self, state, cost, parent=None):
self.state = state
self.cost = cost
self.parent = parent
def __lt__(self, other):
return self.cost < other.costStep 2
Implement the core Best-First Search loop utilizing a priority queue for the open set and a hash set for closed states to prevent redundant cycles.
def best_first_search(start_state, goal_state, successors_func, heuristic_func):
open_set = []
heapq.heappush(open_set, (heuristic_func(start_state), Node(start_state, 0)))
closed_set = set()
while open_set:
_, current_node = heapq.heappop(open_set)
if current_node.state == goal_state:
path = []
curr = current_node
while curr:
path.append(curr.state)
curr = curr.parent
return path[::-1]
if current_node.state in closed_set:
continue
closed_set.add(current_node.state)
for next_state, step_cost in successors_func(current_node.state):
if next_state not in closed_set:
est_cost = heuristic_func(next_state)
child = Node(next_state, est_cost, current_node)
heapq.heappush(open_set, (est_cost, child))
return NoneStep 3
Verify correctness using structured unit tests on known graph topologies and profile memory consumption under deep expansion trees.
def test_best_first_search():
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('D', 2), ('E', 5)],
'C': [('F', 1)],
'D': [('G', 1)],
'E': [('G', 1)],
'F': [('G', 3)],
'G': []
}
heuristics = {'A': 5, 'B': 3, 'C': 2, 'D': 1, 'E': 2, 'F': 1, 'G': 0}
successors = lambda s: graph[s]
heuristic = lambda s: heuristics[s]
path = best_first_search('A', 'G', successors, heuristic)
assert path == ['A', 'B', 'D', 'G']Step 4
Mitigate infinite loops in cyclic graphs by ensuring proper closed-set enforcement and handle memory exhaustion risks by capping maximum frontier allocations.
MAX_FRONTIER_SIZE = 1000000
def robust_best_first_search(start, goal, succ_fn, heur_fn):
open_set = []
heapq.heappush(open_set, (heur_fn(start), Node(start, 0)))
closed_set = set()
while open_set:
if len(open_set) > MAX_FRONTIER_SIZE:
raise MemoryError("Frontier size exceeded safety threshold, potential infinite expansion.")
_, current = heapq.heappop(open_set)
if current.state == goal:
return reconstruct_path(current)
if current.state in closed_set:
continue
closed_set.add(current.state)
for neighbor, _ in succ_fn(current.state):
if neighbor not in closed_set:
heapq.heappush(open_set, (heur_fn(neighbor), Node(neighbor, 0, current)))
return None