The hidden beauty of the A* algorithm
Vložit
- čas přidán 16. 05. 2024
- 00:00 Intro
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 Minota...
Our Patreon: / 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/b...
-- 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...
-- 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/explo...
stackoverflow.com/questions/2...
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/trac...
music: Also sprach Zarathustra from Strauss from wikimedia commons
image of the scroll: www.pxfuel.com/en/desktop-wal...
images of the cities are from wikimedia commons
This explanation gets an A*
Underrated comment
I see what you did there 😆
@@slavicprogrammer6100 Not anymore.
@@mustafa-damm there's a blanket
Polylog is A* 😊
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.
Agree it would be interesting to see what happens there! I wanted to mainly rely on an example where everything works exactly as we want, thus Prague and Rome. But giving your example e.g. at the very end would be definitely very nice!
EDIT: Made a clip with a similar example and linked in the video description. (github.com/...)
@@PolylogCS I'm struggling to find it in the description. O.o Perhaps I'm being stupid. Could you post a link here?
@@PolylogCS Oh beloved convexity, my dear. Thank you for always make your way into simplifing optimization problems.
@@PolylogCS Beautiful! Further, what a surprise to actually discover a fellow matfyzák doing these videos. :)
I have that problem here. eBay tells me that Cardiff UK is only 25 miles away. But there is a long estuary in between. It's actually 90 miles by road.
I like how he says pseudocode then proceeds to write Python.
Python is pseudocode
lmaooo
@@theguynextdoor--_--9591fcking diabolical
python reads like pseudocode so its often used as a substitute. it also has an added bonus of standard definitions for terms so its easier to understand
@@tofu_3369 ok
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 great video and an amazing channel!!
I can't wait to see what you have in store for us next.
Okay, writing down my understanding: A* is a way to speed up a Djikstra search through a graph by providing an opportunity to input information from what the graph represents. For example, if each node in the graph represents a point in 2D space, you can use those points to set a “potential” for each node, which warps the graph into a new one which Djikstra will solve more quickly. So it will still produce the same output as Djikstra - but it changes the order in which Djikstra searches so that it makes its way to the solution sooner. Because Djikstra searches shorter path lengths first, if you warp the graph such that the better paths are shorter, it’ll search them first. It’s just a matter of warping the graph into something that still works for Djikstra, using a method which is actually faster. Do I have this right?
Yes! But be careful, purely geometrical intuition is hard here, since the graph is directed, with different length in one direction and the opposite one.
@@PolylogCS Excellent, thank you!
This was a great video, and you should be very proud of it.
*Dijkstra, but yes! en.wikipedia.org/wiki/IJ_(digraph)
This is actually a common pattern in Computer Science. Usually when we find something that works we try to optimize it giving information to the structure of the input data. That's what happened going from Fully connected Neural networks to Convolutional Neural networks for example.
A* is basically guiding your search with an heuristic function you designed intuitively, or gained by other means (AI Analysis of problem), its all really about the quality of the heuristic and how well the search problem space is fit for it
A+, keep the algo videos coming, so helpful, great explanation ..
this video is like a 20 minute long beautiful symphony of ideas
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!
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"!
An important thing he forgot to mention about the puzzle: It doesn't find **a** solution, it finds **the best** solution. That's the point of A*: returning the same optimal solution as Dijkstra, but faster. I love A*.
@@m.sierra5258 thanks for feedback! I mentioned it at the very beginning of that chapter, but it is very easy to miss...
A pathfinding algo used for rubiks cube.... WTF
wow, this might be one of my favorite explanations of an algorithm ever! Thank you!
Happy to find a great channel like yours!
This is a fantastic explanation! Thank you very much!
Love your videos. You are very good at explaining algorithms. Thank you. :)
Potentials has so many potentials... love the explanation @polylog
This is what I was looking for. Thank you so much.
Great video! Thanks. So happy that this type of content is shared and celebrated on CZcams. I subscribed. :)
Thanks!
One major way that maps can give you answers so quickly is that they actually cache the results.
One person searches for Prague to Rome and that result is saved for later searches, making the second search exceedingly faster.
Saved results have a max timeout where they will always be forgotten after a certain time as they will invariably become obsolete at some point.
And each node along saved paths have a list of saved routes going through it, should anything change with a node then all saved results are immediately invalidated or re-evaluated.
Frequent searches for routes (say London City to Heathrow) are given a higher priority than infrequent searches such as Yakutsk to Lisbon.
The high value routes are ALWAYS re-evaluated on node changes rather than just forgotten. To ensure that when the next search happens, the result is as always pretty much immediate.
There's most likely also an imbalance in node lengths. Despite road ABC being shorter than DEF, DEF is always FASTER than ABC in the long term.
Another place where results are cached are on the internet as a whole. Your ISP (Internet Service Provider) keeps the last result of a certain web request stored locally so subsequent requests can be satisfied much faster than having to contact the endpoint in say California when the client is in Berlin. A local copy in Berlin can be served in milliseconds where having to fetch all resources from California could take several seconds.
Heck, even your browser has a local cache of pages. Especially the heavy stuff like images, audio and video. (Which is funny by the way, you are not allowed to download copyrighted material but at the same time your browser does exactly this when it caches copyright protected images etc)
On an even grander scale, CZcams caches A LOT. When a new video is released in Tokyo and saved to a data center in Japan. That is the only actual copy of the video until it is slowly trickled across all CZcams's datacenters.
But when a person from Norway watches that video for the first time, that video is immediately stored in a data center in Norway and so anyone else watching the video from Norway will have no issues with buffering it unlike the first one.
Eventually, all of CZcamss data centers will have a (basic) copy of a newly released (and popular) video such that new viewers can at least see the video in real time without having to buffer it (though they might be seeing it in 480p at first)
And videos that aren't as popular will simply fade away from non-major data centers over time as fewer to no one is watching them.
In short, everything on the internet is generally going fast because results are cached. That is why data centers need petabytes of storage. Not because there's petabytes of video being uploaded to each of them but the fact that ANYTHING that is uploaded ANYWHERE is cached locally in data centers even if that local data center only really serves a thousand clients.
"Frequent searches for routes"
In that case there must be some sort of "location rounding" included to find earlier searches. Practical everyone have different start or finish address. Most likely starting from or going to their home address and that will be different for each search.
@@Foersom_ Yes, locally going from north part of city A to south part of city B creates a path to any one point where a cached path exists that take you from city A to city B the fastest.
The algo is still the same, just that once you hit a cached path going to your destination city (read, not locale) it will piggyback on that cached path.
At the same time it does a reverse search from the locale in city B which would take you to city A until it finds the cached path A->B and then says "hop off this path at this node in City B".
What a beautiful explanation!
Amazing animations! The idea of modifying Dijkstra's algorithm with a 3d visualization is mind-blowing.
Loved the video. Very easy to follow along!
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
you use soooo good animations. appreciate that!
Good explanation!
Thank you!
Great video! The use of Also Spoke Zarathustra by Strauss for the reveal of the "physical" interpretation of node potentials really tickled my funny bone.
I also really loved how you avoid introducing the vocabulary of heuristic until it basically falls out of massaging the initial algorithm - I've often seen A* introduced and explained directly reasoning with straight-line distances, and I never really grasped how that is more of a special case for applying A* than the general case [operating on the graph by redistributing potentials].
Thanks!
The German "also" differs in meaning from the English "also", so it's either "Thus spoke Zarathustra" or "Also sprach Zarathustra". If you mix the languages, you distort the meaning.
I am happy that the CZcams algorithm persisted and recommended me this video over and over again. It is really good!
I hit like only for that 3D map explanation. Great work friend !
I always thought of A* in a similar way, however I thought of potential as more of an abstract selection/queuing process than something physical. This is why manhattan distance and binary heaps are so effective at speeding up the process. There is a fractal nature to the algorithm because the set of explored paths can be expressed as a node, where the paths escaping it are dynamically recomputed based on the discovered cost of the path to the discovered nodes adjacent to undiscovered nodes. This of course isn't how the algorithm works but it is isometric with the method. There is inherent comparative nature to the algorithm, where the actual distance does not matter, but instead the relative measure between possible paths.
Thanks for the video!
Well made and easy to understand. Great work!
Thanks!
Really nice video. Great job!
skvěle vysvětlené jako vždy.
Nice subject, clear explanation, good animation. I did learn something
Excellent explanation!
why didnt I find this channel earlier ? Great job with the animation ! Subscribed.
Very interesting application to the 15 puzzle!
Thanks for valuable information
Amazing explanation
Great explanation!
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.
This is a trick question, because we know, that all paths lead to Rome.
Thanks for mentioning L'viv!
Wow this is probably the best explanation of A* I've seen. I finally understand why A* always gives the true shortest path, rather than an estimate.
beautifully done.
Thanks for the vid! You explained it better than my professor for sure
Damn man this was by far the best explanation of an algorithm I have ever seen
New math video! I knew it was worth subscribing to your channel!
Amazing video!!! Congrats
Super video kluci!!
Subscribed lightning fast, I need more algorithms intuitively taught not the mindless pseudo code without intuition or reason why something is done. Keep coming the great series on algorithms, I would also love to see systems topics covered, compilers, HPC and microprocessors. Do consider
That is explained so well that I understand it too.
I am a physics undergrad and as soon as you started talking about potentials and showed the road map in a 3D view with Prague being at a high point and Rome at a lower one, it immediately started screaming in to my ears "Gradient". The way I visualize the problem is that we are trying to find the direction at which we must move from each node in order to have the most steep descent because the steepest descent means that the next node is going to be closer to Rome than the rest. This is exactly what the gradient in vector calculus shows you. For anyone who isn't familiar a gradient is a vector that shows you the direction of steepest ascent so by simply taking the negative of that you find the direction of steepest descent. So all you have to do to solve the problem is at each node to take the negative gradient for each path and then simply choose the one at which the grad was smallest. Then you repeat for the next node until you reach Rome at which point the grad will be zero because you're at the lowest point.
It's not that easy. This greedy approach misses shorter paths hidden behind a temporarily longer path.
@@poopcatapult2623 I see. You're right I didn't think of such a scenario, I basically assumed straight lines, no backtracking etc. Thanks for the help
There is a connection with physics that I did not want to get into in the video: The way you operate with potentials mathematically is a discrete analogue to how you operate with physical potentials/fields.
@@sirkinguin4890what you described sound like best first search
Using A* to solve search problems is always fun. I've had a bunch of random problems about finding the shortest way to solve something where I pretty quickly decide that the graph search is just the best way. No wonder why these graph search algorithms are the main thing I remember from AI course...
Skvělé video, posílám pozdrav z Prahy !
:)
Really interesting!
I had to implement the A* algorithm in a college class. Beautiful explanation! I wish I saw this 3 years ago lol.
Using the third dimension to visualise the direct distance of each node to Rome is GENIUS. I don't know if that was your idea but regardless the animation is great and the explanation is clear, this is a great video.
Great video, I think I finally understand A*after all these years!
For the 15-puzzle, I thought we had to divide the heuristic by 2, but we're not swapping numbers so that doesn't make sense lol
Actually, when we first wrote the code for the 15 puzzle, we also divided by two as we did not think it out properly and then were surprised that the heuristic sucked :D
Awsome video!
This is nifty!
I've been searching for Rubik's solution. Thanks dude.
That was very interesting, ty
Really amazing explanation, now i get it, thanks
Great to hear!
All paths lead to rome we don’t need an algorithm
okay that actually is beautiful
This is a really nice video. this reminds me of a similar idea with kirchhoff's law. A cicuit is like a directed acylic graphy of potential differences.
Wow, I am absolutely blown away by the quality of your videos! The content, the script, and the overall production value is truly amazing. I am a CS student myself, and I have been considering starting my own channel. Your work has truly inspired me and I can't wait to try my hand at creating something similar. Would it be possible for you to share the tools and techniques you use to make your videos? It would be an honor to learn from someone as skilled as yourself. I would be eternally grateful if you could make a video about it, your guidance would be invaluable!
I think you are using manim but I am not sure. I am thinking of using it for my projects as well!
Hi, thanks! We use manim, a python library, then kdenlive. In any case, i recommend you try making your own videos! A good place to submit them to is 3blue1brown competition, this helped us a lot!
Thanks!
Wonderful video, you got a new sub
Very nice explanation and animation.
I came to understanding A* in a different, maybe the classic way, but this one with node elevation is definitely a very interesting view on the same thing. I started with Dijkstra (which is in turn a BFS with priorities added to the edges) and instead of using distance as the priority, use something that is commonly called a "cost". This cost can (under the rules you described well in the video) consist of more factors added up - like the road distance and straight-line distance. One can then add other factors as fuel consumption, elevation and toll prices as other factors by summing them up.
I think some real-world route-finding algorithms are based on a bi-directional version of A*, where the boundary gets expanded from both starting and ending points and the route is formed when the boundaries meet (perhaps oversimplified).
It should be also possible to find more alternative routes this way when the algorithm doesn't terminate immediately after the first route is found but tries, say, three times where some cost is already added to existing routes.
Awesome video! Have an exam in a week on autonomous robots and this is part of the curric. This video really helped set my studied knowledge in stone and give an alternative visualisation!
great video!
great video
Animator deserves a cookie. 👍
I hope this work get proper appreciation
Lol @ the space odyssey music. Also the idea you highlighted at the beginning is nice. The weights on the edges makes the problem a discrete analog of finding length minimizing geodesics in Finsler geometry, as opposed to in Riemannian geometry.
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.
Excellent
I feel like a huge mapping database like Google Maps could use some other strategies to improve the A* heuristic as well, like using previous queries to see what routes are generally faster than others.
Yes! Precomputation is actually the main trick, I would say.
Doesn't it use contraction hierarchies instead? Precomputed in bulk every few minutes to account for live traffic.
@@cooperised I would assume so yes, they have plenty of real time traffic data from the location and status information sent by android devices. They know for example not only where the device is but also whether the step tracker thinks you are walking/running/cycling etc. Also whether you previously spent time idle at a known transit stop etc so they can get a pretty good idea which devices are in private automobiles and average their speeds to estimate current congestion levels (simply compare this number to the speed limit). But then for calculating travel time the latter step is not necessary, that is only useful to highlight those segments on the map, for average travel time you need only the segment length and average speed, divide the former by the latter and there you have it.
They must have super massive location specific caching systems. I imagine they get (Prague, Rome) a bit more often in Prague and Rome than they do in other parts of the world ;)
@@RHCPhooligan Yeah, caching would be great for this. Sending the requests from NY, for someone planning a vacation, to their eurocache may be faster than calculating it in us-east. Your (Prague, Rome) comment made me wonder if routes are always symmetrical.
I am a very confused aerospace engineering student who stumbled upon map algorithm youtube by clicking a video that I thought referred to the aerodynamic variable A*, which we use to find the throat area for perfectly sonic flow through a wind tunnel. A few videos later and I feel very educated about something completely different. :)
Skvělá práce. Moc povedené.
Zrovna letos jsem pro Advent of Code hledal IDA* (iterative deepening A star).
Díky :) Tom Sláma má pěknou aplikaci a star v advent of code
@@PolylogCS viděl jsem video. Konkrétně jde taky o ty roboty. Má někde odkaz na repo? Možná bych se inspiroval.
Really good video
Very good video you got my sub, one precision about Maps and other maps software
, 1 to 1 shortest path A* is great however when you have an extensible graph then a matrix distance is needed which is using dijkstra, when you talk about maps the distance matrix is using a dijkstra algorithm and once the shortest road is define a 1 to 1 is defined, maps turn by turn api will use A*.
Yay, some guy with an accent explaining programming concepts! Never seen this before!
4:34 I knew what was coming for the explanation, but the Space Odyssey just made me burst into laughter, caught me completely by surprise! A+ editing!
Super video
Who else is here after the OpenAI Q* news?
I am
I coded an A* algorithm from scratch after reading how it worked, and not looking up any code snippets. As a junior coder, it was very fulfilling and enlightening. I highly recommend anyone dabbling in this stuff, such as unity, to give it a try.
This is such a good video. How does this have so little views . Amazing explanation and graphics. Love it
Came looking for copper, found gold, amazing work.
can you explain the new minpath algorithm for graphs with negative edges that quantamagazine made an article about recently?
It is quite complicated, actually. I suggest you look at a talk from the authors. :) I think i would need like an hour to explain it...
Okay. As an amateur programmer, I'm trying to get my head around how we actually Dijkstra navigate the graph without actually storing the whole graph in memory - for something like the Tile Puzzle, with 10 trillion nodes, we would clearly have to do this, since storing the map is not viable. As such we translate a Puzzle State into a Node along with its Potential (using the 'optimistic distance' as out potential as suggested in the video).
We then interpret every legal move as an 'edge' to-from the State Node we're at and a 'nearby' State Node. When Dijkstra removes the Start node and adds in all its 'neighbors', that is the first time those neighboring nodes exist; we have to generate these new State Nodes and, at the same time, determine if it is a Node that already exists - the only way I can think to do this is by comparing it to every previously generated State Node. With a good Potential function, we should not add too many more nodes than we need to, so the 'neighborhood' of nodes to check should remain relatively small. More to the point, the only nodes being stored in memory at once time are those that are at any point part of the Neighborhood (or Boundary in the code). Is there a good way to estimate the Memory Impact of the algorithm as a function of size of the input space (in a similar way that we estimate Runtime in that big-Oh way?).
At the end of the process, we have only acknowledged the existence of a tiny fraction of the total graph, and used the structure of the puzzle itself as a way to directly 'compute' the base edge lengths and the Potentials on an as-needed basis, which is pretty genius. It also cleanly explains why having an edge with a negative length would break the algorithm entirely, because the choice of how to expand the neighborhood depends on the fact that you are always getting 'further away' from the starting point in a global sense; that the length of your 'best current path' is always increasing, which is violated if a path-length can be negative.
I would love to see some example where the appropriately well-chosen Potential could be used to fix the negative path length problem.
One of the best i ever seen explaining A* algorithm. I'm quite fascinated by the visuals. Can you let me know what kind of tools use for visualisation.
I have a very strong love/hate relationship with A*. On the one hand, it's a really cool algorithm. On the other, I'm deathly allergic to heuristics.
Being a theoretician, i had a similar sentiment until I started to view the algorithm as an application of potential reweighting, which is a beatiful trick with many theoretical applications.
@@PolylogCS It really is. It's just that coming up with heuristics makes me cry.
Very nice, well done.
What a stellar explanation with references to Interstellar music :D
Most people know that as Space Odyssey music hehe... But it predates movies
Great Video! I enjoyed it a lot. Giving those 3b1b vibes
Very nice