This tutorial guides you into the fascinating A* (A-Star) using the Python programming language. First, feel free to watch the video guide—we’ll give a detailed textual explanation below.
The slides can be found as a Gif here:
Okay, so let’s dive into the algorithm motivation, explanation, and Python code next!
What is the A* Search algorithm?
A very interesting graph traversal algorithm we will learn about next is the A* algorithm, constructed by the authors Peter Hart, Nils Nilsson, and Bertram Raphael. The A* algorithm belongs to the family of best-first search algorithms and is an extension to the Dijkstra algorithm in the sense that it takes into account both the weights of the graph edges and the heuristic functions of the connected vertices. It is suitable for application in various domains of computer science because of its three key properties: completeness, optimality, and optimal efficiency.
What’s the Purpose of A* Search?
Common applications of the A* algorithm are in domains of optimal pathfinding for various distribution networks. Some of the example usages are power-aware routing of messages in large communication networks, point-to-point path planning tasks, or finding the shortest path in games and web-based maps.
How Does A* Search Work?
The A* algorithm assigns a heuristic function to all the vertices. The heuristic function approximates a cost of reaching the goal vertex from a visited vertex in terms of e.g. (commonly Euclidean) distance or time. The total cost of any vertex is calculated as a sum of weights of the connecting edges between the starting vertex and the visited vertex, and the heuristic function of the visited vertex.
When visited, the cost of each unexplored, adjoining vertex is updated according to the weights associated with the connecting edges. After being visited, each adjoining vertex is added to the priority queue.
In each following iteration, the vertex with the lowest cost is taken out of the priority queue and its processing starts by visiting and conditionally updating all its adjoining (visited), non-explored vertices. The update operation implies two steps: lowering the cost of the visited node and associating with the processed (explored, the terms are used interchangeably) vertex for later reconstruction of the shortest path. Finally, the processed vertex is marked as explored and does not participate in any further cost calculations.
The update condition is determined by comparing each visited vertex’s current cost with its new, potentially lower cost. Its new cost is calculated in the following way: current cost of the explored vertex – its heuristic function + the weight of the adjoining edge (the edge weight between the vertex being explored and the visited vertex) + the heuristic function of the visited vertex.
If the current cost of the visited vertex is still lower than the potential new cost, the vertex cost will not be updated. Otherwise, the visited vertex will be updated to the new cost (its cost will decrease) and form an association with the explored vertex. Vertex cost reduction is also referred to as a relaxation procedure. After visiting and conditionally updating all the adjoining, non-explored vertices, the vertex being processed will be marked as explored and will not participate in any further algorithm calculations. The described process continues until there are no unexplored vertices left in the priority queue.
When the algorithm ends, all vertices are assigned with the lowest possible costs, and the traversal algorithm yields the shortest possible path between the starting and target vertices. For comparison with the previously described Dijkstra’s algorithm, the A* algorithm is superior given that it does not only follow the shortest path available (pure greedy approach) but is also guided by the notion of a right direction, contained in the heuristic function of each vertex.
What Are the Properties of A* Search?
The A* algorithm uses the exact information represented by the edge’s weights and a heuristic function for distance estimation between the goal vertex and other connected vertices in a graph. As the initial costs for all the non-starting vertices are set to infinity, the algorithm successively decreases vertices costs until they reach their minimum.
This behavior leads to a property of being optimal: minimal costs assigned to vertices enable the A* algorithm to always find the shortest path between the starting vertex and any other vertex in the graph. As the shortest paths always start from the starting vertex, the algorithm is attributed as the “single-source” algorithm.
Besides being optimal, the algorithm is also complete, i.e. it will always take a finite time to find a solution.
The third important property is the optimal efficiency, reflected in the fact that vertices positioned further from the target vertex may not be explored at all, as their heuristic function distinguishes and delays the exploration of such vertices among those with equally weighted paths.
The heuristic functions used in the A* algorithm also have two notable properties: admissibility and consistency.
- Admissibility implies that the heuristic function cost estimation is at most as high as the lowest possible cost from the current point in a path towards the target vertex.
- The consistent or monotone heuristic function is constrained by a requirement that its cost estimation is always less than or equal to the estimated distance from any adjoining, successor vertex to the goal, plus the cost of reaching that vertex.
How is A* Search Implemented in Python?
The implementation of the A* algorithm is achieved by the function a_star() and a modification of the underlying class Graph.
The a_star() function takes three parameters:
- The
graphparameter takes an initialized Graph object (see the blog on the breadth-first search algorithm, the section on graphs). - The
start_vertexparameter takes the starting vertex, which we choose freely (remember, a graph is not a tree, there is no absolute root). - The
targetparameter is the entity we want to find in the graph, enclosed in a vertex.
For a better understanding of the algorithm and its implementation, each step is precisely described in the code below.
There have been some further upgrades on the Graph class, so its entire listing follows:
class Graph:
def __init__(self, directed=False):
self._outgoing = {}
# If the graph is undirected, 'self._outgoing'
# is the universal storage.
self._incoming = {} if directed else self._outgoing
# If the graph is directed, the 'self._incoming'
# dictionary differs from the 'self._outgoing'.
def is_directed(self):
return self._incoming is not self._outgoing
# The function returns a generator of incoming
# or outgoing (default) edges of a vertex.
def adjacent_edges(self, vertex, outgoing=True):
# References the corresponding outer dictionary
# (dictionary of dictionaries)
adj_edges = self._outgoing if outgoing else self._incoming
# Access each of the edges for this endpoint vertex.
for edge in adj_edges[vertex].values():
yield edge
def add_vertex(self, entity=None, h=None, cost=None):
# Constructs a new vertex from the entity.
vertex = self.Vertex(entity, h, cost)
# The vertex becomes a key in the outer dictionary,
# but the value is an internal dictionary (as we model
# both dimensions for each edge: origin and destination).
# e.g. {vertex_1a:{vertex_b:edge_a_b}, vertex_b:{vertex_c:edge_b_c}}.
self._outgoing[vertex] = {}
if self.is_directed():
self._incoming[vertex] = {}
def add_edge(self, origin, destination, weight=None):
# Constructs a new edge from the vertices.
edge = self.Edge(origin, destination, weight)
# Adds the edge to the dictionary (dictionaries are
# the same if the graph is undirected). The outer key
# represents the origin, i.e. the component 'a' of
# the edge-defining pair (a, b). The inner key stands
# for the component 'b' of the edge-defining pair (a, b).
self._outgoing[origin][destination] = edge
# Even if the graph is undirected, each edge has to
# be added twice, i.e. once for each of its endpoints.
self._incoming[destination][origin] = edge
def vertices(self):
return self._outgoing.keys()
def edges(self):
# All the edges are collected into a set.
result = set()
for inner_dict in self._outgoing.values():
result.update(inner_dict.values())
return result
class Vertex:
__slots__ = '_entity', '_h', '_cost'
def __init__(self, entity, h=None, cost=None):
self.entity = entity
self.h = h
self.cost = cost
# The real-world entity is represented by the Vertex object.
@property
def entity(self):
return self._entity
@entity.setter
def entity(self, entity):
self._entity = entity
# The real-world entity has a heuristic value of 'h'.
@property
def h(self):
return self._h
@h.setter
def h(self, h):
self._h = h
# The real-world entity has a cost of 'cost'.
@property
def cost(self):
return self._cost
@cost.setter
def cost(self, cost):
self._cost = cost
# We have to implement __hash__ to use the object as a dictionary key.
def __hash__(self):
return hash(id(self))
def __lt__(self, other):
if self.cost is None:
return False
elif other.cost is None:
return True
else:
return self.cost < other.cost
class Edge:
__slots__ = '_origin', '_destination', '_weight'
def __init__(self, origin, destination, weight=None):
self._origin = origin
self._destination = destination
self.weight = weight
def endpoints(self):
return self._origin, self._destination
# Returns the other component of the edge-defining pair (a, b)
# for a given component a or b, respectively.
def opposite(self, vertex):
return self._destination if self._origin is vertex \
else self._origin
# Returns the weight of the edge.
@property
def weight(self):
return self._weight
# Sets the weight of the edge
@weight.setter
def weight(self, weight):
self._weight = weight
def __hash__(self):
return hash((self._origin, self._destination))
The most significant differences to the previous version of the Graph class are highlighted in the code.
With these changes in place, implementation of the core function, a_star() is:
from graph import Graph from queue import