Insight into programming algorithms

Home » Graph Theory » A-star(A*) in general

A-star(A*) in general


Introduction

A* is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between multiple points, called nodes. Noted for its performance and accuracy, it enjoys widespread use.Source.

It is one of the basic and the most common algorithm which you’ll see widely across the internet. It is widely used for pathfinding and various other problems which have admissible heuristics and can be converted to a graph form. Rather than using example problems for explaining, I’ll discuss A* in general with it’s basic skeletal algorithm more like with blanks than can be filled to solve various problems which will be discussed in a different post.I’ll be supplying with more practical information rather than theory.


 

Pros:

  • It will always find the optimal solution provided that it exist’s and that if a heuristic is supplied it must be admissible.
  • Heuristic is not necessary, it is used to speed up the process.
  • Various heuristics can be integrated to the algorithm without changing the basic code.
  • The cost of each move can be tweaked into the algorithms as easily as the heuristic.
  • It isn’t constrained to a unidirectional search.

Cons:

  • Not the best algorithm for each problem in terms of memory and processing required.
  • Uses a lot of memory since each node created has to be kept accounted for.

Prerequisite knowledge 

There are a few thing you need to know before trying your hand on programming A*.

  • You need to know how to convert your problem into a graph i.e into nodes and edges.

This is most important stuff that you need to get right, so what is a graph? A graph is a representation of a set of objects where some pairs of objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices (also called nodes or points), and the links that connect some pairs of vertices are called edges (also called arcs or lines).Source.

GraphNodesEdges

Figure 1.

As shown in Figure 1 above. From programming point of view a node is where all your information is stored for a particular state of the problem, like current coordinates in pathfinding. The edge is nothing but the pointer to the next node which is stored in the previous node.The distance between each node is called the cost.

There are various types of graphs like cyclic graph, acyclic, directed cyclic,directed acyclic etc etc, explaining them will be off topic.

Let’s take the example of the water jug problem.In this particular example we have one 5 gallon jug and one 3 gallon jug, we have to collect 4 gallons.

bfs12

Figure 2.

As you see in Figure 2 the problem is converted into a tree and as you know a tree is a special case of a Directed acyclic graph(DAG) thus A* can be applied here as well.

The figure is almost self explanatory still I’ll explain how it goes, so the nodes have data as the amount of water in each jug and these are further linked with each step possible from the previous node. As you see, the initial node is the start node where both the jugs are empty from here there are two possible states i.e either fill the 3 gallon jug or the 5 gallon jug, thus the two nodes linked to the start. Now if we see the LHS of the tree at depth 1 there are two possible steps i.e either pour the water from the 3 gallon jug to the 5 gallon jug or fill the 5 gallon jug which is described by the nodes.

This is a simple example of converting your problem space to a tree for implementation of A*.

Note: The water in jug when poured to a container with less capacity  then the extra water will not be counted. Also the jugs can be emptied as a move.

  • You need to have an admissible heuristic for the problem for optimal and faster search(Optional).

What is an admissible heuristic?

An admissible heuristic is which calculates the estimated cost to the goal state and is always lower than or equal to the actual cost of reaching the goal state i.e it never overestimates the cost to reach the goal. A consistent or monotone heuristic can also be used which means that it is admissible and it is equal to the cost to goal plus the estimated distance from each neighbor  in which case the solution will be found the fastest and the least unnecessary nodes would be generated.

Why do we need heuristics?

Heuristics are the main component of the algorithm i.e the brains of the algorithm without it the algorithm is not intelligent, heuristics give boundaries to the algorithm, as in which not to select and which to not since heuristics give the general estimate of the distance to goal node helping the algorithm to choose the optimal node in the next step.

  • You need to know or figure out the cost required to travel from one node to other.

Usually the cost is taken as 1 but it can differ according to where you want to implement it. For example a diagonal move can cost 1.41 if you are implementing it in a 2D map with each tile as a square of 1 x 1 through Pythagoras or for example if a node represents a tile containing water which slows down the movement can be valued 2 etc.

Working

The key feature of the A* algorithm is that it keeps a track of each visited node which helps in ignoring the nodes that are already visited, saving a huge amount of time.It also has a list that holds all the nodes that are left to be explored and from this list it chooses the most optimal node thus saving time not exploring unnecessary or less optimal nodes.

So we use two lists namely ‘open list‘ and ‘closed list‘ the open list contains all the nodes that are being generated and are not existing in the closed list and each node explored after it’s neighboring nodes are discovered is put in the closed list and the neighbors are put in the open list this is how the nodes expand. Each node has a pointer to it’s parent so that at any given point it can retrace the path to the parent. Initially the open list holds the start(Initial) node. The next node chosen from the open list is based on it’s f score, the node with the least f score is picked up and explored.

What is f score?

f score is nothing but the sum of the cost to reach that node and the heuristic value of that node.

For any give node the f score is defined as:

f(x)=h(x)+g(x)

where g(x)  is the cost of that node, h(x) is the calculated heuristic of that node and x is the current node.

What is g score(cost)?

g score is defined as the sum of g score of the parent node and the cost to travel to that node from it’s parent.

g(x)=g(x.parent)+cost(x.parent,x)

What is h score(heuristic)?

Heuristic score is different for each question as explained above heuristic needs to be admissible for each type of problem. I’ll not discuss about various heuristics here as this is just to explain general working of A*.

Now that the explanation is out of the way lets come to the basic algorithm in practice.


 

Algorithm

Start=initial node;
Goal=final node;
open_list.insert(Start);                              //list of type node
closed_list=empty set;                             //list of type node
Start.g=0; Start.h=heuristic(Start); Start.f=Start.g+Start.h;
function A*()                                             //Driver function
{

while(!open_list.empty())             //run until open list is empty
{

process=open_list(node with min(f));
if(process==Goal)
         return (function path(process));              //path to goal found
open_list.remove(process);
closed_list.insert(process);
foreach(node in nextnodes(process))          //run for all the nodes possible from current
{

if(closed_list.count(node)!=0)             //Does not exist in closed list
         skip this loop once;
if(open_list.count(node)==0)               //Does not exist in open list
         open_list.insert(node)
else
{

actual_node=open_list.find(node);       //if exists find node in open_list
if(node.g<actual_node.g)                  //better g score for same node found
{

actual_node.g=node.g;
actual_node.f=node.f;
actual_node.parent=node.parent;//change parent to better(earlier parent)

}

}

}

}
print(“Not possible to reach goal”);

}
function nextnodes(node)
{
             return list of all possible next nodes from node;
}
function path(node)
{
             construct the path from node to start using node.parent;
}


Make sure you read my implementation guide on A* for pathfinding and implementing A* to solve N-Puzzle for making this algorithms crystal clear in your head and make sure you code these in any language possible as it will make it clearer practically on how to use A* for graph search and how to convert problems into graph for using this algorithm.


If you see anything wrong with the post or if you have any queries regarding the algorithm. Post them in the comment section. There can be things wrong with this as I am still a beginner on the path of learning and this is based on what I have learnt so far with examples from external sources as well. So experts, please let me know through the comments section.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: