[[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).
- Initialize an empty list of nodes to be explored, called the "open list"
- Initialize a closed list of already-explored nodes
- Set the initial node as the current node and add it to the open list
- 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
- 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