A* Search Algorithm
The all star search algorithm
To begin, what exactly are algorithms?
An algorithm is a method of expressing a process in a measurable amount of time and space.
In naive terms it is a set of rules that should be followed in calculations, It is designed to perform a particular/specific task. This can be as simple as implementing arithmetic operations (addition, subtraction, multiplication, division, etc.) or as complex as playing a compressed video file.
We see applications of algorithms everywhere from a basic calculator to cloud computing, Artificial intelligence, and many more. These algorithms play a huge role in computer science.
Now let us know what is path searching and Traversal?
1.Path Searching
Pathfinding, also known as pathing, is the process of mapping the shortest route between two points using a computer programme. It is a more realistic approach to maze solving.
2. Traversal
Graph traversal in computer science refers to the operation of accessing each node in a graph data structure exactly once. Iterating over the data structure is another term for traversing. Simply put, traversal is the process of walking through (all or some) components of a data structure.
Let us have a look at A* search algorithm
The A*(pronounced as A-star)Search algorithm is a well-known and commonly used technique in path-finding and graph traversals. Because of its completeness, optimality, and maximum efficiency, it is commonly used in many fields of computer science. It has “brains,” which distinguishes it from other traversal strategies. What this means is that it is a smart algorithm, which distinguishes it from most conventional algorithms.
Here is a pictorial example of A* Search!
Consider a two-dimensional grid with various barriers, where we begin at a source cell (shown in red below) and work our way to a target cell (coloured green below)
Consider a square grid of numerous barriers, as well as a start and finish cell. We want to get to the target cell as soon as possible from the starting cell. A * search algoritm corresponding to the sum of the remaining two parameters, ‘g’ and ‘h,’ is applied to pick a node at any point. It selects and processes the node/cell with the lowest ‘f’ at any stage.
Below, we describe ‘g’ and ‘h’ as clearly as possible.
g = the expense of following the path formed from the starting point to a given square on the grid.
h = the approximate cost of travelling from a given grid square to the final destination.
This is generally referred to as the heuristic, and is nothing more than a kind of educated assumption. We won’t know the exact distance until we find the road, because something can get in the way.
Comparing A* Search Algorithm and Dijkstra Algorithm
A* is still superior to Dijkstra because it conducts educated rather than uninformed search: it extends more promising vertices than Dijkstra because A* takes into account additional knowledge about the shortest path to the goal (the distance function).
The only difference between A* and Dijkstra is that A* seeks to find a better way by using a heuristic algorithm that priorities nodes that are meant to be better than others, while Dijkstra simply explores all possible paths.
Let us discuss time complexity of A* Search
A* time complexity depends on heuristic, In worst case the complexity is O(bd) where b is branching factor and d is the depth or shortest path.
Working of A* Search Algorithm
The A* Algorithm operates as follows:
It keeps track of a tree of paths that begin at the root node.
It enlarges such pathways by extending one edge at a time.
It runs until the termination requirement is met.
A* Algorithm extends the path that minimises the equation-valued function-
f(n) = g(n) + h (n)
In this case,
’n’ is the path’s last node.
The cost of the path from start node to node ’n’ is given by g(n).
h(n) is a heuristic function that calculates the expense of the shortest path from node ’n’ to the destination node.
Following are the steps below:
In this we need two lists, open list (which contains nodes evaluated heuristic function) and other closed list (which are visited).
Step1: We implement by creating open list which contains one node.
Step2: We return failed or exit when list is empty.
Step3: Find the smallest value of f(n) and n then move that from open list to closed list.
Step4: Now we expand the node n
Step5: If the next node of n is the required node then return success or else go to the next step.
Step6: We have to apply the evaluation function if the node is not in either list add it to open.
step7: we return to Step2.
Let look at the Limitations of A* Search
Despite being the best pathfinding algorithm possible, A* Search Algorithm does not always provide the shortest path since it heavily relies on heuristics / approximations to determine — h
Advantages of A* search algorithm
It is comprehensive and ideal. It is equivalent to all other methods. It is used to solve highly challenging problems. It is optimally efficient, such that no other optimal algorithm guarantees less nodes than A*.
Lets look at some Important points regarding the Algorithm
It is worth remembering that-
One of the better path finding algorithms is the A* Algorithm.
However, it does not always yield the shortest path.
This is attributed to the fact that it is highly dependent on heuristics.
Pseudo code of the A* Search
Here is a pseudo code explained in details with comments :
To summarise, we have seen what an algorithm is, what A* Search is and its applications, and then we saw the comparison between A* Search Algorithm and Dijkstra Algorithm, and then a pictorial example of how A* works, next we looked into the complexity of the algorithm, working of the algorithm along with the steps of implementation, further we discussed limitations, advantages and some important points of the A* search Algorithm and lastly we learned the pseudocode of A*.
The applications of A* search is diverse in different fields. So, what are you going to do with this Algorithm?
