Scribd
Upload
25 views3 pages

A Star Search Algorithm

The document contains an implementation of the A* search algorithm in Python, which finds the shortest path in a graph from a start node to a goal node using a heuristic. It defines a graph representing locations and their connections, as well as a heuristic for estimating distances to the goal. The algorithm is executed to find the path and total cost from 'Arad' to 'Bucharest'.

Uploaded by

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

A Star Search Algorithm

The document contains an implementation of the A* search algorithm in Python, which finds the shortest path in a graph from a start node to a goal node using a heuristic. It defines a graph representing locations and their connections, as well as a heuristic for estimating distances to the goal. The algorithm is executed to find the path and total cost from 'Arad' to 'Bucharest'.

Uploaded by

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

import heapq

def a_star(graph, start, goal, heuristic):

frontier = [(heuristic[start], 0, start, [start])]

explored = set()

while frontier:

f, g, current, path = heapq.heappop(frontier)

if current == goal:

return path, g

if current in explored:

continue

explored.add(current)

for neighbor, cost in graph[current].items():

if neighbor not in explored:

total_cost = g + cost

estimated_total = total_cost + heuristic[neighbor]

heapq.heappush(frontier, (estimated_total, total_cost, neighbor, path + [neighbor]))

return None, float('inf')

# Define the map

graph = {

'Arad': {'Zerind': 75, 'Timisoara': 118, 'Sibiu': 140},

'Zerind': {'Oradea': 71, 'Arad': 75},

'Oradea': {'Sibiu': 151, 'Zerind': 71},

'Sibiu': {'Arad': 140, 'Oradea': 151, 'Fagaras': 99, 'Rimnicu Vilcea': 80},

'Timisoara': {'Arad': 118, 'Lugoj': 111},

'Lugoj': {'Timisoara': 111, 'Mehadia': 70},


'Mehadia': {'Lugoj': 70, 'Drobeta': 75},

'Drobeta': {'Mehadia': 75, 'Craiova': 120},

'Craiova': {'Drobeta': 120, 'Rimnicu Vilcea': 146, 'Pitesti': 138},

'Rimnicu Vilcea': {'Sibiu': 80, 'Craiova': 146, 'Pitesti': 97},

'Fagaras': {'Sibiu': 99, 'Bucharest': 211},

'Pitesti': {'Rimnicu Vilcea': 97, 'Craiova': 138, 'Bucharest': 101},

'Bucharest': {'Fagaras': 211, 'Pitesti': 101}

# Heuristic (straight-line distances to Bucharest)

heuristic = {

'Arad': 366, 'Zerind': 374, 'Oradea': 380, 'Sibiu': 253,

'Timisoara': 329, 'Lugoj': 244, 'Mehadia': 241, 'Drobeta': 242,

'Craiova': 160, 'Rimnicu Vilcea': 193, 'Fagaras': 178,

'Pitesti': 98, 'Bucharest': 0

# Run the algorithm

path, cost = a_star(graph, 'Arad', 'Bucharest', heuristic)

print("Path:", path)

print("Total Cost:", cost)

You might also like