The first project to complete as part of the C++ Nanodegree from Udacity is an OpenStreetMap Route Planner. Currently, I am at the point of implementing the A* algorithm in a trial program. For about a week now, I have been mentally skipping over the A* search algorithm and just relying on the information provided. Why? My lawyer brain has so … many … questions since I have not heard of it before, which means I will inevitably end up going down a rabbit hole, which I did not have time to do — until today.
One of my coding tasks today involved was to implement a
Maybe I am unique? Like most programmers I use Google to help solve coding problems, but perhaps unlike most programmers, I have a small collection of foundational printed books (okay, I have some e-books too!) I rely on my books primarily for headier problems. Perhaps books remind me of school, or set my brain into learning mode or something else. For today’s question I ended up searching (pardon the pun!) in three books to find the answers I wanted.
- Book 1: Introduction to Algorithms, Third Edition By Thomas H. Cormen, et al. At Hackbright, this book was one of several that a teachers showed me during data structures and algorithms week in 2016. I remember sitting down with the book for a long time and becoming enamored. I put it on my wishlist and finally purchased a copy earlier this year. Sadly, it did not have A* in the index.
- Book 2: Discrete Mathematics and Its Applications Seventh Edition, 7th Edition By Kenneth Rosen. In my Discrete Math class, this was the textbook. While I took the class in 2017, I kept the book because it has some of the best explanations that I have ever read. The fact that my notes and homework assignments are almost as thick as this 993 page book speaks volumes in its own way. Sadly, it did not have A* in the index either.
- Book 3: Algorithms Unlimited Series by Tim Roughgarden. (I only have part 1 & part 2.) When I was looking for an algorithms class online I came across a class taught by Roughgarden and these books were listed, so I ordered them. While he did not teach my CS class at Stanford, his book and explanation instantly helped me. In the index under graph search, there is an entry for A*!
- The explanation on page 159 helpfully states “The A* search algorithm is a goal-oriented generalization of Dijkstra’s algorithm, which adds to the Dijkstra score of an edge a heuristic estimate of the cost required [to travel from the edge to the goal].”
- As I noted in my last post, I understand the heuristic function (the Manhattan distance in my program) or h value, which gets smaller, the closer a node is to the goal. This way, you know that you are searching in the right direction.
- Also there is the g value or distance cost, which increases with each step in a search. This way, the more steps you take to reach the goal, the more it costs, so the search find the most direct route that is possible.
- Today, among other functions I wrote was a function for the f value — which is the lowest overall cost. For purposes of this program it is f = g + h.
Thankfully, I satisfied both my search for answers and my understanding of search without spending too much time in rabbit hole today!
Photo by Anna Shvets from Pexels
michdcode 