[[Heuristic values]]

A* search algorithm:

The A* search algorithm is a popular search algorithm used in pathfinding and graph traversal. It combines the strengths of both Dijkstra's algorithm (which can only find a shortest path in a graph with non-negative edge weights) and the greedy best-first search algorithm (which can only find a shortest path to a target in a graph without negative edge weights).

  1. Initialize an empty list of nodes to be explored, called the "open list"
  2. Initialize a closed list of already-explored nodes
  3. Set the initial node as the current node and add it to the open list
  4. While the open list is not empty: a. Select the node in the open list with the lowest f score (cost function) b. Remove it from the open list and add it to the closed list c. Generate its successors (neighboring nodes) d. For each successor: i. If it is not in either list, compute its f score and add it to open list ii. If it is already in either list, check if using this path is a better route and update accordingly
  5. When all successors of current node have been evaluated, set current node = parent node and repeat steps 4-5 until goal state is reached
# create a set to store explored nodes
explored = set()

# create a set to store unexplored nodes
unexplored = set()

# create a dictionary to store the cost of getting to each node
cost = {}

# create a dictionary to store the best previous node for each node
previous = {}

# create a dictionary to store the estimated cost of getting to the end node from each node
estimated_cost = {}

# set the initial cost of getting to each node to infinity, since we don't know any better at the start
for node in graph:
  cost[node] = float('inf')

# set the initial estimated cost of getting to the end node from each node to the heuristic cost
for node in graph:
  estimated_cost[node] = heuristic(node, end_node)

# set the initial node to the start node and add it to the unexplored set
current_node = start_node
unexplored.add(current_node)

# loop until we either find the end node or there are no more unexplored nodes
while len(unexplored) > 0:
  # find the node in the unexplored set with the lowest estimated cost
  lowest_cost = float('inf')
  lowest_cost_node = None
  for node in unexplored:
    if estimated_cost[node] < lowest_cost:
      lowest_cost = estimated_cost[node]
      lowest_cost_node = node

  # if we've found the end node, we're done
  if lowest_cost_node == end_node:
    break

  # move the current node from the unexplored set to the explored set
  unexplored.remove(lowest_cost_node)
  explored.add(lowest_cost_node)

  # update the cost of getting to each neighbor of the current node
  for neighbor in graph[lowest_cost_node]:
    # skip any neighbors that are already in the explored set
    if neighbor in explored:
      continue

    # calculate the cost of getting to this neighbor
    new_cost = cost[lowest_cost_node] + graph[lowest_cost_node][neighbor]

    # if the new cost is lower than the previous cost, update the cost and set the previous node for this neighbor
    if new_cost < cost[neighbor]:
      cost[neighbor] = new_cost
      previous[neighbor] = lowest_cost_node
      estimated_cost[neighbor] = new_cost + heuristic(neighbor, end_node)

      # if the neighbor is not in the unexplored set, add it
      if neighbor not in unexplored:
        unexplored.add(neighbor)

# create an empty list to store the path
path = []

# set the current node to the end node
current_node = end_node

# loop until we get to the start node
while current_node != start_node:
  # insert the current node at the start of the list
  path.insert(0, current_node)

  # set the current node to the previous node
  current_node = previous[current_node]

# return the path
return path