Scribd
Upload
4 views3 pages

A Star Algorithm

The document presents an implementation of the A* algorithm for pathfinding, detailing the process of finding the shortest path from a start node to a stop node in a graph. It defines functions for managing the open and closed sets, calculating distances, and reconstructing the path once the destination is reached. Additionally, it includes a heuristic function and a sample graph structure for testing the algorithm.

Uploaded by

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

A Star Algorithm

The document presents an implementation of the A* algorithm for pathfinding, detailing the process of finding the shortest path from a start node to a stop node in a graph. It defines functions for managing the open and closed sets, calculating distances, and reconstructing the path once the destination is reached. Additionally, it includes a heuristic function and a sample graph structure for testing the algorithm.

Uploaded by

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

A Star Algorithm

def aStarAlgo(start_node, stop_node):

open_set = set(start_node) # {A}, len{open_set}=1


closed_set = set()
g = {} # store the distance from starting node
parents = {}
g[start_node] = 0
parents[start_node] = start_node # parents['A']='A"

while len(open_set) > 0 :


n = None

for v in open_set: # v='B'/'F'


if n == None or g[v] + heuristic(v) < g[n] + heuristic(n):
n = v # n='A'

if n == stop_node or Graph_nodes[n] == None:


pass
else:
for (m, weight) in get_neighbors(n):
# nodes 'm' not in first and last set are added to first
# n is set its parent
if m not in open_set and m not in closed_set:
open_set.add(m) # m=B weight=6 {'F','B','A'} len{open_set}=2
parents[m] = n # parents={'A':A,'B':A} len{parent}=2
g[m] = g[n] + weight # g={'A':0,'B':6, 'F':3} len{g}=2

#for each node m,compare its distance from start i.e g(m) to the
#from start through n node
else:
if g[m] > g[n] + weight:
#update g(m)
g[m] = g[n] + weight
#change parent of m to n
parents[m] = n

#if m in closed set,remove and add to open


if m in closed_set:
closed_set.remove(m)
open_set.add(m)
if n == None:
print('Path does not exist!')
return None

# if the current node is the stop_node


# then we begin reconstructin the path from it to the start_node
if n == stop_node:
path = []

while parents[n] != n:
[Link](n)
n = parents[n]

[Link](start_node)

[Link]()

print('Path found: {}'.format(path))


return path

# remove n from the open_list, and add it to closed_list


# because all of his neighbors were inspected
open_set.remove(n)# {'F','B'} len=2
closed_set.add(n) #{A} len=1

print('Path does not exist!')


return None

#define fuction to return neighbor and its distance


#from the passed node
def get_neighbors(v):
if v in Graph_nodes:
return Graph_nodes[v]
else:
return None
#for simplicity we ll consider heuristic distances given
#and this function returns heuristic distance for all nodes

def heuristic(n):
H_dist = {
'A': 10,
'B': 8,
'C': 5,
'D': 7,
'E': 3,
'F': 6,
'G': 5,
'H': 3,
'I': 1,
'J': 0
}

return H_dist[n]

#Describe your graph here


Graph_nodes = {

'A': [('B', 6), ('F', 3)],


'B': [('C', 3), ('D', 2)],
'C': [('D', 1), ('E', 5)],
'D': [('C', 1), ('E', 8)],
'E': [('I', 5), ('J', 5)],
'F': [('G', 1),('H', 7)] ,
'G': [('I', 3)],
'H': [('I', 2)],
'I': [('E', 5), ('J', 3)],

}
aStarAlgo('A', 'J')

You might also like