Scribd
Upload
143 views

Best First Search in Python

This Python code implements best-first search to find the optimal path between nodes in a graph. It defines a graph with nodes and connections, heuristic values for each node, and performs a best-first search using the heuristic values as priorities to find the path from a start to goal node with the lowest estimated total cost. The search returns a dictionary indicating the path came from for each node, which is then used to print out the optimal path from start to goal.

Uploaded by

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

Best First Search in Python

This Python code implements best-first search to find the optimal path between nodes in a graph. It defines a graph with nodes and connections, heuristic values for each node, and performs a best-first search using the heuristic values as priorities to find the path from a start to goal node with the lowest estimated total cost. The search returns a dictionary indicating the path came from for each node, which is then used to print out the optimal path from start to goal.

Uploaded by

Darshan Jain
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 6

Implementation of Best First

Search in Python
graph = {
    'A': [('B'), ('C')],
    'B': [('D'), ('E')],
    'C': [('F')],
    'D': [('G'), ('I')],
    'E': [('H')],
    'F': [],
    'G': [],
    'H': [],
    'I': []
}
heuristic = {
    'A': 10,
    'B': 8,
    'C': 7,
    'D': 6,
    'E': 4,
    'F': 5,
    'G': 3,
    'H': 2,
    'I': 0
}
start_node = 'A'
goal_node = 'I'
came_from = best_first_search(graph, start_node,
  goal_node, heuristic)
def best_first_search(graph, start, goal, heuristic):
    frontier = [(heuristic[start], start)] # priority queue of (priority, node)
    came_from = {}
    came_from[start] = None
    while frontier:
        _, current = heapq.heappop(frontier) # node with lowest heuristic value
        
        if current == goal:
            break
        
        for neighbor in graph[current]:
            if neighbor not in came_from:
                priority = heuristic[neighbor]
                heapq.heappush(frontier, (priority, neighbor))
                came_from[neighbor] = current
                
    return came_from
print("Path from", start_node, "to", goal_node, ":")
node = goal_node
path = [node]
while node != start_node:
    node = came_from[node]
    path.append(node)
path.reverse()
print(path)

You might also like