The hidden beauty of the A* algorithm
835,774
Published 2023-01-20
01:38 Change the lengths!
06:34 What is a good potential?
12:31 Implementation
16:20 Bonus
Tom Sláma's video: • Theseus and the Minotaur | Exploring ...
Our Patreon: www.patreon.com/Polylog
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.
github.com/polylog-cs/Astar/blob/main/Explore.mp4
-- 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:
en.wikipedia.org/wiki/Johnson%27s_algorithm
-- See also this codeforces blog post that collects some applications of potentials in competitive programming.
codeforces.com/blog/entry/95823
-- 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:
maps.google.com
geojson.io/
public.opendatasoft.com/explore/dataset/europe-roa…
stackoverflow.com/questions/29470253/astar-explana…
Credits:
To make this video, we used manim, a Python library: docs.manim.community/en/stable/
The color palette we use is solarized: ethanschoonover.com/solarized/
music: Thannoid by Blue Dot Sessions: app.sessions.blue/browse/track/126782
music: Also sprach Zarathustra from Strauss from wikimedia commons
image of the scroll: www.pxfuel.com/en/desktop-wallpaper-aadkb
images of the cities are from wikimedia commons
All Comments (21)
-
This explanation gets an A*
-
I like how he says pseudocode then proceeds to write Python.
-
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.
-
This is a trick question, because we know, that all paths lead to Rome.
-
I love it when math and science communicators use good animations. Good job!
-
Excellent video! Wonderful explanation involving many intuitions with cool examples to boot. Had a lot of fun listening and learning!
-
I love the intuitive understanding you present here, brilliant stuff 👍
-
A+, keep the algo videos coming, so helpful, great explanation ..
-
While the first part of the video was clarifying and reinforced what I already knew + gave better intuition, the last part with the 15 puzzle was really illuminating! It kinda illustrates a thought I've had lately that "everything can be a graph problem if you squint hard enough"!
-
Well explained. I have been using A* pathfinding in my game for over a year now. It's insanely fast in video games compared to Djikstra for example, because the areas to be calculated are often very very large. I roughly knew how A* works, but this video certainly clarified well!
-
this video is like a 20 minute long beautiful symphony of ideas
-
A great video and an amazing channel!! I can't wait to see what you have in store for us next.
-
Happy to find a great channel like yours!
-
Amazing animations! The idea of modifying Dijkstra's algorithm with a 3d visualization is mind-blowing.
-
wow, this might be one of my favorite explanations of an algorithm ever! Thank you!
-
All paths lead to rome we don’t need an algorithm
-
Love your videos. You are very good at explaining algorithms. Thank you. :)
-
This is a fantastic explanation! Thank you very much!
-
Great video! Thanks. So happy that this type of content is shared and celebrated on YouTube. I subscribed. :)
-
I hit like only for that 3D map explanation. Great work friend !
