[[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