New Memory bounded A* Algorithm
def astar(start, goal):
opened = [[start, 0]] # List of open nodes
closed = [] # List of closed nodes
visited = set() # Set of visited nodes
while opened:
val, min_cost = opened.pop(0)
if val == goal:
break
visited.add(val)
for neighbor, cost in nodes[val]:
if neighbor not in visited:
new_cost = min_cost + cost
opened.append([neighbor, new_cost])
else:
continue
opened.sort(key=lambda x: x[1]) # Sort open nodes by cost
closed.append(val)
return closed, min_cost
# Define nodes before using the astar function
nodes = {
'A': [('B', 5), ('C', 10)],
'B': [('D', 3), ('E', 8)],
'C': [('F', 6), ('G', 9)],
'D': [('H', 7), ('I', 3)],
'E': [('J', 4)],
'F': [('K', 2)],
'G': [('L', 5)],
'H': [('M', 6)],
'I': [('N', 2)], # Adding node 'N' with its neighbor and cost
'J': [('O', 1)],
'N': [], # Adding node 'N' without any neighbors initially
}
# Start-'A', Goal = 'J'
print(astar('A', 'J'))
Comments
Post a Comment