ฝัง
- เผยแพร่เมื่อ 29 เม.ย. 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
![[TH] VCT Pacific - Regular Season - สัปดาห์ที่ 4 วันที่ 3 // BLD vs DRX | GEN vs RRQ](http://i.ytimg.com/vi/spszLQZOzw4/mqdefault.jpg)
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 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 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.
All paths lead to rome we don’t need an algorithm
I love it when math and science communicators use good animations. Good job!
this video is like a 20 minute long beautiful symphony of ideas
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.
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
Happy to find a great channel like yours!
A+, keep the algo videos coming, so helpful, great explanation ..
wow, this might be one of my favorite explanations of an algorithm ever! Thank you!
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!
Amazing animations! The idea of modifying Dijkstra's algorithm with a 3d visualization is mind-blowing.
Great video! Thanks. So happy that this type of content is shared and celebrated on TH-cam. I subscribed. :)
Thanks!
Potentials has so many potentials... love the explanation @polylog
Love your videos. You are very good at explaining algorithms. Thank you. :)
This is a fantastic explanation! Thank you very much!
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
This is what I was looking for. Thank you so much.
What a beautiful explanation!
you use soooo good animations. appreciate that!
why didnt I find this channel earlier ? Great job with the animation ! Subscribed.
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.
I am happy that the TH-cam algorithm persisted and recommended me this video over and over again. It is really good!
Well made and easy to understand. Great work!
Thanks!
I hit like only for that 3D map explanation. Great work friend !
Loved the video. Very easy to follow along!
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, TH-cam 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 TH-cam'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 TH-cams 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".
Thanks for the video!
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.
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.
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
Nice subject, clear explanation, good animation. I did learn something
Very interesting application to the 15 puzzle!
Really nice video. Great job!
Excellent explanation!
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
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.
Thanks for the vid! You explained it better than my professor for sure
Amazing explanation
Great explanation!
Thanks for mentioning L'viv!
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.
skvěle vysvětlené jako vždy.
Thanks for valuable information
Damn man this was by far the best explanation of an algorithm I have ever seen
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...
New math video! I knew it was worth subscribing to your channel!
beautifully done.
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
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
That is explained so well that I understand it too.
Amazing video!!! Congrats
I had to implement the A* algorithm in a college class. Beautiful explanation! I wish I saw this 3 years ago lol.
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!
Really interesting!
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.
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.
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.
Really amazing explanation, now i get it, thanks
Great to hear!
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.
Skvělé video, posílám pozdrav z Prahy !
:)
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.
Super video kluci!!
This is a trick question, because we know, that all paths lead to Rome.
I've been searching for Rubik's solution. Thanks dude.
That was very interesting, ty
Funnily enough, I learnt about A* before I learnt about Dijkstra's. When they eventually taught us Dijkstra's in university, my thought was basically "Oh, it's just A* without the heuristic" :D
Thanks!
This is nifty!
Awsome video!
>lets write down the pseudocode for our algorithm
Proceeds to write it in python
😂
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.
Animator deserves a cookie. 👍
great video
Who else is here after the OpenAI Q* news?
I am
Excellent
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!
great video!
I hope this work get proper appreciation
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*.
Wonderful video, you got a new sub
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!
Really good video
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.
Where do I go to learn more about this?
This is so fascinating to me :)
I never thought that A* could be used for more than just graphs of euclidean distances, fuckin smart mate.
I love this video, just one suggestion on the color scheme: the color of the dots being almost the same as the color of the sea made it hard to distinguish between them and to read the numbers. I would have chosen to not color the sea at all, just imply it with the outline to europe. Or made the sea a slightly different beige color, so it was easy to see it as different from the continent, but still having a big contrast with the dots and the numbers.
Other than that, I loved this video! I learned a lot
Thanks for the feedback!
@@PolylogCSI have a similar kind of feedback so I’ll put it here. I’m watching the video with subtitles on mobile and the place you’ve chosen to put most of the info like formulas and data gets covered by the subs, so maybe a higher placement of that information would be better for upcoming videos. Thanks for an otherwise great and informative video!
This is such a good video. How does this have so little views . Amazing explanation and graphics. Love it
Yay, some guy with an accent explaining programming concepts! Never seen this before!
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. :)
Came looking for copper, found gold, amazing work.
Very nice
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.
Super video
Great video. What did you use to make the map and animate all of the nodes?
Google Maps is provably reluctant to back-track, so much so that it will choose (timewise) longer routes than the fastest route. This has been true for at least fifteen years.