Informed Search: A* Search
Where are we going?
Before I start this week’s newsletter, I want to welcome all the new subscribers, welcome.
In a previous newsletter we talked about uninformed search (BFS, DFS, IDS, and DLS). While its not a pre-requisite, you may want to read that before proceeding with this one…if you haven’t. In uninformed search, we discussed algorithms that were primarily focused on finding a solution (if it exists) with no other knowledge determining their path to the solution.
Funny story, growing up with my brother, the shortest path to any destination was the path that wasn’t paved. If it went through inner streets, through houses, and non-conventional paths, it was considered a “shortcut”. Sometimes this was true, other times, we found out at the end of the journey that we had made a terrible error in judgement.
To demonstrate, suppose we had to move from the start box to the end box, what would be our shortest path? What if we had blockers on the way? How then do we find our shortest path?
My brother and I would sometimes take new paths to same destination in order to measure the distance, time, and effort it takes to arrive in comparison to previous paths. We had no way of measuring and estimating the cost of a path choice until we had made it. A* addresses the issue of estimating the cost of a path choice before taking it.
A* Heuristic Search
A* heuristic search is an algorithm that calculates and estimates the cost of all possible paths, then taking the most cost efficient path. The algorithm determines its next step through the minimum value of `f` where `f = g + h`. Where `g` is the cost to get to that box, and h is the cost from that box to the destination.
g is the cost so far, while h is the cost from the current location to the destination
The cost from a given box to the final destination is calculated using either Euclidean or Manhattan distance. Euclidean distance favors a straight path thus it is often more accurate, however, it is also slower.
Back to our original story, using heuristic search, we could have figured out the cost of taking a path before we actually take it. This would mean we would spend a little more time thinking about the path to take, but we will eventually save more time and effort because we would always make the right choice by picking the shortest path.
Our shortest path would look something like this:
A* is implemented using a priority queue in a BFS search. The priority of the next step is calculated using the heuristic function described above. At each step, we calculate the value of f, and add the grid to our priority queue using the value of f. For those unfamiliar with queues, priority queues, linkedlists, etc, if you want me to cover those, just let me know.
Euclidean distance is calculated as:
` h = sqrt((x_start - x_destination)^2 + (y_start - y_destination)^2) `
Manhattan distance is calculated as:
`h = abs(x_start - x_destination) + abs(y_start - y_destination)`
You can view my repl.it link for A* using Manhattan distance here: https://replit.com/@imoris11/astarmanhattan
In our example, we attempt to move from A to B as shown below
We can move horizontally, vertically, and horizontally.
Manhattan distance will output the following:
The Euclidean distance will output the following:
As we can see, the Euclidean distance does favor a straight line approach. To see the code for euclidean distance, view this repl.it
A* is applied in maps to find the shortest path between two positions. Other applications of A* are products that require moving between two locations while avoiding possible obstacles. A* is often referred to as the search algorithm with “brains” as it has the ability to calculate and estimate the cost of a path before taking it. Dijsktra’s search algorithm is a special form of A* that has a `h` value of 0. We will cover Dijkstra’s algorithm in a later newsletter.
We had previously covered uninformed search, so I thought it’d be nice to cover at least one informed search algorithm. I hope you enjoyed it as much as I enjoyed writing it. If you’re not a paying subscriber, what are you waiting for? Click on subscribe and update to become a paid subscriber. Thank you and see you next week!