Scribd
Upload
6 views3 pages

Best First Search Algorithm Explained

Best First Search utilizes a Priority Queue to explore nodes based on a heuristic function that estimates the cost to the goal. The algorithm initializes with the starting node, selects the node with the lowest heuristic value, expands its neighbors, and repeats until the goal is reached. An example implementation demonstrates the process of finding the path from node A to G using heuristic values.

Uploaded by

fapiser937
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views3 pages

Best First Search Algorithm Explained

Best First Search utilizes a Priority Queue to explore nodes based on a heuristic function that estimates the cost to the goal. The algorithm initializes with the starting node, selects the node with the lowest heuristic value, expands its neighbors, and repeats until the goal is reached. An example implementation demonstrates the process of finding the path from node A to G using heuristic values.

Uploaded by

fapiser937
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Best First Search Works

Unlike Breadth-First Search (which expands level by level) or Depth-First Search (which goes deep
into one branch), Best First Search uses a Priority Queue to store nodes. It ranks nodes based on a
Heuristic Function $h(n)$, which estimates the cost from the current node to the goal.

1. Initialize: Put the starting node into a Priority Queue.

2. Selection: Pick the node with the lowest heuristic value (the "best" node).

3. Expansion: If the node is the goal, stop. Otherwise, expand its neighbors.

4. Repeat: Add neighbors to the Priority Queue and repeat until the goal is found.

CODE
from queue import PriorityQueue

def best_first_search(graph, start, goal, heuristics):

visited = set()

pq = PriorityQueue()

# PriorityQueue stores (priority, node)

[Link]((heuristics[start], start))

path = []

print(f"Starting search from {start} to {goal}...\n")

while not [Link]():

# Get the node with the lowest heuristic value

cost, current_node = [Link]()

[Link](current_node)

print(f"Visiting: {current_node} (Heuristic: {cost})")

# Check if goal is reached

if current_node == goal:

print("\nGoal Reached!")

print(f"Path taken: {' -> '.join(path)}")

return

[Link](current_node)

# Explore neighbors

for neighbor in graph[current_node]:

if neighbor not in visited:


[Link]((heuristics[neighbor], neighbor))

# --- Data Setup ---

# Adjacency list representing the graph

graph = {

'A': ['B', 'C'],

'B': ['D', 'E'],

'C': ['F', 'G'],

'D': [], 'E': [], 'F': [], 'G': []

# Heuristic values (estimated distance to goal 'G')

heuristics = {

'A': 10,

'B': 8,

'C': 5,

'D': 7,

'E': 6,

'F': 3,

'G': 0

best_first_search(graph, 'A', 'G', heuristics)

Output

When you run this program, it prioritizes nodes with the smallest heuristic values:

 Step 1: Starts at A. It sees neighbors B (h=8) and C (h=5).

 Step 2: It chooses C because 5 is smaller than 8.

 Step 3: From C, it sees neighbors F (h=3) and G (h=0).

 Step 4: It chooses G because 0 is the lowest possible value.

Starting search from A to G...

Visiting: A (Heuristic: 10)

Visiting: C (Heuristic: 5)

Visiting: G (Heuristic: 0)
Goal Reached!

Path taken: A -> C -> G

You might also like