Skip to content

Instantly share code, notes, and snippets.

@erika-dike
Created July 3, 2018 11:15
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save erika-dike/457ab4da60f12f565e1913cf0a4f5a44 to your computer and use it in GitHub Desktop.
Save erika-dike/457ab4da60f12f565e1913cf0a4f5a44 to your computer and use it in GitHub Desktop.
def heauristic(a, b):
(x1, y1) = a
(x2, y2) = b
return abs(x1 - x2) + abs(y1 - y2)
def a_star_search(graph, start, goal):
frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0
while not frontier.empty():
current = frontier.get()[1]
if current == goal:
break
for neighbor in graph.neighbors(current):
new_cost = cost_so_far[current] + graph.cost(current, neighbor)
if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
cost_so_far[neighbor] = new_cost
priority = new_cost + heauristic(goal, neighbor)
frontier.put(neighbor, priority)
came_from[neighbor] = current
return came_from, cost_so_far
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment