The hidden beauty of the A* algorithm

00:00 Intro
01:38 Change the lengths!
06:34 What is a good potential?
12:31 Implementation
16:20 Bonus

Some related stuff:

-- One thing I did not mention is that Dijkstra's algorithm is designed to solve the problem of finding the shortest path from the start node to all other nodes of the graph. It does this job very well, in almost linear time, so there is not much to improve there. It is the problem of finding the shortest path between two nodes where A* usually improves upon Dijkstra.

-- Here is a link to another example of A* run from Sarajevo to east Italy. You can see how the algorithm quickly reaches the first city, Tirana, but then it gets stuck because of the Adriatic sea. So it searches along its coastline until it finds Italy. After that it confidently runs through Italy until it finds the destination.

-- If your heuristic is not consistent, but at least admissible, A* will still return the correct answer, though its time complexity may be exponential in the network size.

-- IDA* is a popular algorithm that relates to iterative deepening depth first search the same way as A* relates to Dijkstra/breadth first search.

-- A perhaps simplest application of potential reweighting technique is the Johnson’s algorithm:

-- See also this codeforces blog post that collects some applications of potentials in competitive programming.

-- The underlying reason why potentials are often so useful is that they are dual to the concept of distances in the sense of linear programming duality.

Problems:

-- Prove that heuristics from the video are consistent.

-- Prove that the maximum of two consistent heuristics is still consistent. (Thus, if you have two incomparable heuristics, you should combine them this way. )

-- Prove that for any heuristic that is consistent, equal to zero for the goal state and otherwise nonnegative, A* always explores less states than Dijkstra. That is, apart for the time spent on computing the heuristic, A* is never worse than Dijkstra in the problem of finding the shortest path between two points.

Big thanks to: Richard Hladik, Matěj Konečný, Martin Mareš, Yannic Maus, Jan Petr, Vojtěch Rozhoň, Hanka Rozhoňová, Tom Sláma

Links in the video:

Credits:
music: Also sprach Zarathustra from Strauss from wikimedia commons
images of the cities are from wikimedia commons

[ashwinjain]

this video is like a 20 minute long beautiful symphony of ideas

[laurenlewis]

At first I wasn't very interested, I just figured I should start learning algorithms to improve my code, but by the time in all came together in "Implementation" my tiny little mind was blown. Intuitive, creative, and just downright cool; not only do you make A* easier to grasp, you also made it more interesting than a simple description of the process

[erikziak]

I am happy that the YouTube algorithm persisted and recommended me this video over and over again. It is really good!

[digitig]

That explains something I've noticed about route planning apps. I live near a river, downstream of the most likely crossing for most destinations on the other side of the river. The route my satnav, Google Maps, etc. plots *to* the crossing depends on where I'm going *after* the crossing. I'd worked out that it was looking at routes nearest a straight line between my start and end points. The video has confirmed it, and told me what the algorithm is.

[shaund.]

I did not squint at the rubrics cube to see if I was able to predict whatever you were going to say. Nope...didn't at all...
On a different note, thanks for this clear explanation. Definietly a good starting point to understanding what this A* algorithm is about.

[uzha]

Great explanations!

I think it needs to be noted though that Google maps algorithm isn't formally 100% shortest path. Must be way more optimized for global scale, with precomputation etc, sacrificing formal correctness. On an occasion I've been able to add waypoints and have Google come up with a shorter version of my intended drive.

[Number_Cruncher]

I learnt something new. Thanks! Very well explained. Your pseudo code looks suspiciously similar to python🙂

[buzz_is_here]

As long as the graph has sufficient crossroads, A* will be more effective. But if there's fewer of those, it can be slower.

[nablahnjr.]

i was secretly hoping you'd have made a video about polylogarithms :(

[AA-zoxr]

Okay so I understand that this shows the shortest path, but this assumes that you are moving at a constant speed. What happens if you have one path the has a longer length but allows you to move faster compared to a shorter path in which you move slower?

[ilydevonte]

swear I’ve watched a video very similar to this a while back ?

[gamingfun]

What's the difference in cost to calculate Prague -> Rome compared to Rome -> Prague?

[Jkauppa]

how about if you put all the edge lengths in an array, and sort

[NZStarlight]

Generally breadth-first search algorithms can be improved by starting from both the origin and destination separately and searching outwards from each until the same node is hit by both searches. What would be the effect of that in this instance? Could you do this weighted al heights algorithm separately from both the destination and the origin and start branching out from each until they hit the same middle node?

[csaki]

I had trouble understanding the words you were saying, but as soon as you showed the illustration with the raised nodes it immediately clicked for me.
I've even implemented A* before but had no idea how or why it works.
The application to solve puzzles is intriguing, can this be used to solve more complex games like chess or card games? I might have to write a card game AI in a while and my best idea was just to weight the cards and do some sanity checks before playing a card to see if it would be detrimental to the AI player in that very moment.

[JakubYTb]

This is a trick question, because we know, that all paths lead to Rome.

[jiwujang]

I like how he says pseudocode then proceeds to write Python.

[lohphat]

I think what would have added more interest is selecting two locations separated by a path obstacle, e.g. Athens to Palermo where the straight line Cartesian distance is small but the road path has to detour around the Adriatic Sea.

Then it would be interesting to see how the algorithm adjusts the path weights.

[DFPercush]

I love it when math and science communicators use good animations. Good job!

[rachidyoussefhattab]

All paths lead to rome we don’t need an algorithm