Well done! Future generations of students will be grateful to you. When I was learning this algorithm there were no such well done, visually explained lessons!
@zoonvanmichiel9045Ай бұрын
Today's mapping applications go even further, using an idea called contraction hierarchies. An analogy for this: Suppose you need to find a route from New York to Los Angeles. As a human you do not look at individual streets first, but look at which states you are likely to pass through. Then for those states you look at which counties you are likely to pass through. And finally how you can cross those counties with roads. The implementation for this contains three parts: figuring out good boundaries, computing the distances for crossing these regions, and combining these into the a route. The first two can be precomputed, so only the final step needs to be calculated on the fly which can be done within milliseconds.
@giacomotazzari2060Ай бұрын
Great video! I studied A* a while ago, and this was really helpful to refresh my knowledge
@Magnasium038Ай бұрын
Nice! I had learnt how A* works earlier, but found the choice of adding the two costs random as I didn't understand the rationale. This presentation of A* as an intermediate between greedy and uniform cost search makes the rationale clear now!
@niccoboaАй бұрын
It's 3am here, let's go straight to A*
@sirk3vАй бұрын
same time zone haha
@multiarray2320Ай бұрын
i legit thought you dont come back. great to see a video of you again :)
@MabeeckАй бұрын
Glad to see that the channel is still in use :)
@crockgaming5958Ай бұрын
Ooh bro finally you got some free time i am very happy 😂
@farklegriffen2624Ай бұрын
0:25 "Pacifically"
@applesaregoodeatings15 күн бұрын
as opposed to atlanticaly of course
@srivatsajoshi4028Ай бұрын
I'm so excited reducible is posting again
@leisuretime7417Ай бұрын
I cannot believe this timing holy shit we are literally studying problem solving by searching in our AI class and this video comes up in my feed just as I completed my assignment problems for this class. This is a great video mate, cheers!
@joaoguerreiro940320 күн бұрын
This channel is pure gold. Please never stop ❤️
@forever_stay6793Ай бұрын
Wow what perfect timing! I'm doing a research project this summer that involves routing algorithms. I've only learned about Dijkstra's algorithm in class, so I was confused when I first started reading papers that mentioned A*. Thank you for the great explanation!
@de_michael1222Ай бұрын
He's back!! You're my favourite algorithmics channel, greetings from europe
@xaceffulgentАй бұрын
Thank you so much! And Welcome back!
@purerandomness4208Ай бұрын
The best A* Algorithm explanation I have ever seen.
@shauryatomer105814 күн бұрын
Damn dude, until now A* just seemed like magic to me. This video changes that magic to logical understanding. Thanks for dropping this gem best video on A* I have seen so far
@NicolasChanCSYАй бұрын
Here's how I memorized the need of admissible heuristic: if you cannot justify the alternative route even when you are being optimistic about it, then why go down that route?
@badpriestess_13 күн бұрын
oh my god i have always wondered about this. im so ready for this video
@cariyaputtaАй бұрын
My man is back. What a time to be alive.
@Thorum0Ай бұрын
Very good video, actually first time I actually understand how the a* heuristic works, thanks!
@ba8eАй бұрын
This was awesome! Beautiful presentation.
@0000kkАй бұрын
Needed this last semester
@kripposoftАй бұрын
Please keep making videos! They're very well presented and interesting!
@justaharmlesspotato88526 күн бұрын
YEY you are back!!! So happy! Please never leave us again
@pra.Ай бұрын
That was simpler than I thought, also you have some of the best visualizations of algorithms out there
@azxu3419Ай бұрын
Reducible keep making great videos!! I miss you so much
@Masterhitman935Ай бұрын
Thank you for providing a very illuminating approach to measuring and optimization of cost of travel between nodes.
@mujtabaalam5907Ай бұрын
Google has never publicly declared which algorithm it uses for maps, but the current public state of thr art is the hub labelling algorithm by Abraham et al
@DiegoGarcia-nm6kiАй бұрын
All i see iis flames! 🔥
@KevinHoreckaАй бұрын
It seems like if you could compute some statistical properties of your graph you could use those to make some better choices about your heuristic. Make the heuristic have a few more parameters and you could probably even build a model trainable on random or a graph dataset and optimize the heuristic for your specific problem. I'm sure someone already does this. Would be interested if it has a name.
@Killerkraft975Ай бұрын
Its funny, I immediately thought, combine them both, right after the drawback of uniform cost search. I didn't realise how efficient the algorithm really was until i figured it out.
@prototypeinheritance515Ай бұрын
I am so happy. I thought you couldn't continue this channel because of economic reasons
@broccoloodle16 күн бұрын
to addon, with admissible heuristic, not only A* search is able to find the optimal path, A* search is also the optimal algorithm, i.e. there is no other algorithm able to expand fewer nodes than A*
@MicrochaosmacАй бұрын
This was awesome! Beautiful presentation. Learned a lot ^^
@joelflanagan7132Ай бұрын
Can't wait to recommend this to my students next year.
@LinesAreVeryCoolАй бұрын
9:57 Isn't 5 rising to the top because it has 0.8 lower cost? The h(5) and h(6) are the same, so I wouldn't that is what actually causes it to rise to the top. Since 6 is also at 2.8 but doesn't rise to the top due to the difference in cost to get there
@mysyntax1311Ай бұрын
welcome back legend!!
@Xxnightwalk1Ай бұрын
Thank you so much, your videos are always very clear and informative
@8y8xАй бұрын
HE CAME BACK!!!!
@General12thАй бұрын
I can't wait!
@roborogue_Ай бұрын
NEW REDUCIBLE VIDEO LETS FUCKING GO (fav channel out of 1k)
@soumalyaАй бұрын
While seeing this video the code of djikstra, bellman ford, floyd warshall went through my head..
@MrLuigiBean1Ай бұрын
Fantastic work as always!!
@knkootbaoat6759Ай бұрын
welcome back!
@thomasmeslin8399Ай бұрын
A* is great indeed ! When I learned it, the uniform cost search is so bad compared to it.
@davidhicks8290Ай бұрын
It ends right when I was getting excited! Explain a good heuristic, please!!! Glad to see you back!
@VaaaaadimАй бұрын
The explanation I had gotten before was that you can get a heuristic by solving a relaxed version of a problem. For the example of driving a car between places in a city, the Euclidean distance works as a heuristic, it is a relaxed version of the problem in that it removes the constraint of having to travel along the roads. For the example of finding the exit in a square maze, the Manhattan distance works as a heuristic, it removes the constraint of the walls whilst still having you move along the grid. If you have a puzzle where you can only move one thing at a time, and the solved state has everything in a specific position, a simple heuristic would be the number of things that are out of place, a better heuristic would be the sum of the distances of every object's current location to goal location.
@davidhicks8290Ай бұрын
Thank you for the comment! What about a mapping problem, but every node only has the distance between its connecting nodes. This would get rid of the Euclidean distance because there's no coordinates associated with the nodes. Do you know of a heuristic for that problem?
@VaaaaadimАй бұрын
@@davidhicks8290 If all you are given is a graph, and you are tasked with doing a single search for a shortest path from one node to another node and do it as fast as possible once you're given the graph, I don't think there is any heuristic you can come up with that'll help. If you are given a graph, and you're told that you can do some precomputation in preparation to answer a query in the future, or you have to handle a batch of queries, then you can algorithmically analyze the graph somewhat and come up with some heuristic that could be useful overall. A (possibly dumb but maybe it could be useful) idea is that you can try embedding the graph into a 2D, 3D, actually any nD space, and apply forces on nodes to try to separate them as much as possible whilst always making sure their Euclidean distance is less than their actual distance between neighboring nodes. Based on this embedding, you use the Euclidean distance as the heuristic. Another idea I have is that you can try partitioning the graph into subgraphs. The partitioning could be done in any way, as long as every node in the original graph is part of some graph in the partition. From thereon, you can notice how the subgraphs connect to each other, look at the minimum distance from any subgraph to a different subgraph, and you'll declare that is the actual distance. So your subgraphs will end up connecting to each other with weights as a new kinda meta-graph. The heuristic now becomes the distance in this meta-graph, where you can't distinguish a node from the subgraph it belongs to. Partitioning your starting graph in different ways would lead to effectively better or worse heuristics, if you partition the graph into a small subgraphs the heuristic is likely to be more accurate but also more costly to compute, conversely bigger subgraphs would make for a less accurate but easier to compute heuristic. How cleverly you partition would also be a factor, probably putting nodes with high centrality in different subgraphs would likely help, making subgraphs where the nodes in them are not connected in the original graph probably wouldn't help. Anyways, all that being said, I don't know what is actually used in practice for A* on graphs where the only thing you know is distance between connecting nodes. Generally for A* you come up with the heuristic by learning/analyzing the problem domain, you generally want to find the shortest path from one node to another in a graph because you're trying to solve a problem, e.g. solve a puzzle, find the cheapest configuration for something, minimize latency, etc... If you know nothing about the graph you're given, I think the only way you can come up with a heuristic is by exploring the graph and then doing extra work. If you get a heuristic by analyzing the problem domain, you don't have to do such precomputation.
@VaaaaadimАй бұрын
@@davidhicks8290 For some reason I don't see the reply I made to your comment here. I'm gonna be less thorough b/c I don't want to retype everything I did the first time. I don't know exactly you mean by "mapping problem". I'm assuming you just mean "shortest path". I don't know what heuristics if any are commonly applied to graphs where all you know is the distance between connecting nodes. If all you know about the graph you're given is the distances between adjacent nodes, I don't think there is a heuristic you can apply to get a free speedup, but maybe I'm wrong. I think that you need to have some additional knowledge. In general the heuristic function you use will depend on the problem domain. Usually we try to find the shortest path in a graph to solve some problem, like solving a puzzle, or minimizing the cost of something, or minimizing latency, or whatever. So by thinking about the problem that the graph comes from, we can try to think of a heuristic. However! If we are allowed to precompute a heuristic function in preparation for handling a future shortest path query, or a batch of them, or many for a long time all using the same graph... I think it is possible to algorithmically deduce a useful heuristic. But in the time it takes to run any of these following approaches to find a heuristic, you will definitely have been able to finish one shortest path query. The simplest option is to just compute the distances between all nodes to all other nodes. The table that you get as a result will be a 100% accurate heuristic, but expensive to precompute, and uses O(N^2) memory. One idea I have is that you can embed a graph in 2D, 3D or any higher dimensional space, and try to move the nodes as far apart as you can while respecting the distance constraint. Perhaps you can separate out the nodes with gradient descent or by doing something like a physics simulation where repulsive forces are applied to the nodes. Anyways, the Euclidean metric would be your heuristic in this case. This method may very well take too long practically to compute though. Last idea I have is that you can split up your starting graph into smaller subgraphs. Treat these subgraphs as a single node each, look at how they connect to each other, and assign distances based on that. You get another graph that is smaller than what you started with, and you can form a heuristic by doing yet another search algorithm on this kinda meta graph. What makes this a relaxed version of the original problem, is that instead of finding a path from one node to another, you just need a path connecting "zones" (and movement inside a zone becomes free). I can imagine a few ways you can tweak this approach to have a more accurate heuristic, as well as trade-off accuracy and time/memory.
@VaaaaadimАй бұрын
@@davidhicks8290 In short, I don't think there is a useful heuristic that works for any arbitrary graph, where the only information you have about the graph is the weights between the nodes. But maybe I'm wrong. Heuristics for A* search are I think typically tailored to a problem domain. For shortest path to minimize latency for a specific problem you might use one heuristic, for solving puzzles in a minimum amount of steps you might use another, etc. If you're given a graph with no extra information, you can algorithmically come up with your own heuristic function, but in the time it takes to compute such a function, you probably could have already finished finding the shortest path from your start to your goal with UCS. But if you have to do many shortest path searches on the same graph, it could make sense. I have a few ideas for how you could compute a heuristic function.
@kaishang6406Ай бұрын
the channel is still alive!
@atha5469Ай бұрын
Excellent video !
@ngtrxpwgdrkАй бұрын
Great explanation!
@abyssaljam4418 күн бұрын
I wish UCS was in Google maps, as then you could look up where can i get to in an hour, if you only have a few hours free in the afternoon..
@30IYouTubeАй бұрын
Researching this takes a very, VERY long time, because it takes O(n^(enourmous but definitely constant number)) to solve and O(n^^(even biger constant number)) to research where n^^m is a power tower of n's height m.
@bennikllr5509Ай бұрын
Nice video. Please do more again
@cardosovАй бұрын
Thanks
@_spartan11796Ай бұрын
Sweet a new video!
@suseJattackIsBackАй бұрын
the legend has returned
@iso_201310 күн бұрын
0:24 *specifically
@pgrvloik9 күн бұрын
How is the Euclidean distance between nodes calculated? Does it require the GPS coordinates of each node?
@rusty-nekoАй бұрын
WOW u are really alive
@adoqАй бұрын
wow he's back
@sebastianzander87Ай бұрын
What does it have to do with AI (mentioned in the thumbnail)?
@ciCCapROSTi13 күн бұрын
When you say work backwards, but the problem is perfectly symmetric it doesn't make much sense
@isbat31416Ай бұрын
Welcome back ❤
@gigantopithecus8254Ай бұрын
nroi just implemented this
@traveler9212Ай бұрын
Welcome back.
@lucascogrossi2974Ай бұрын
hes back
@PhilogyАй бұрын
Isn’t “Uniform Cost Search” Dijkstra’s Algorithm?
@the_cheese_cultist21 күн бұрын
they're different names for essentially the same algorithm
@itsAbhinav538328 күн бұрын
I was thinking of using the result of greedy search as heuristic for A* would it be usable?
@zrIywcN8XJdHaY13K3txАй бұрын
i was here!
@timseguine2Ай бұрын
Isn't what you described as Uniform Cost Search usually called Dijkstra's algorithm?
@the_cheese_cultist21 күн бұрын
they're different names for the same algorithm.
@CHEH_tfАй бұрын
n00b ads, my bro forced me to watch this on stock youtube
@user-nw9fl1pe4pАй бұрын
finally updated😂
@noanyobiseniss7462Ай бұрын
I thought the shortest route problem has been solved by fungus.
@nekoDanАй бұрын
The beginning of this video has an organic approach for a good solution: kzbin.info/www/bejne/jl7MhISHnLSXZ6Msi=MwelIyWoMvpU7AR9
@leovalde7zАй бұрын
its beeen sooo long!
@forever_stay6793Ай бұрын
If anyone knows of any good videos explaining how multi-objective A* algorithms work please share :')
@BleachWizzАй бұрын
12:30- wait but you want to use manhatan distance and find optimal on the euclidean distance? manhatan distance DOES find optimal solution. In the manhatan distance.
@cybermats200411 күн бұрын
On image it looks easy and then you look at how to code
@patfreАй бұрын
Bro committed a crime you talked about A* without mentioning Dijktra’s algorithm which is what it’s based on
@DaffyDaffyDaffy33322Ай бұрын
Isn't UCS the same algorithm?
@psolienАй бұрын
you've beeen missed!
@suaeb175Ай бұрын
❤
@TehPwnererАй бұрын
A* search formulates the path(graph) problem into a gradient descent. The path of least resistance you could say, is lightning search!
@VaaaaadimАй бұрын
I disagree with this somewhat. Although A* uses the heuristic to "tilt" the search towards the goal, it may simultaneously search many paths. In contrast, gradient descent in ML, at least a basic implementation of it, essentially acts like a greedy search algorithm rather than A*.
@humusstealr99825 күн бұрын
Ai
@neon2633Ай бұрын
@besiansherifaj9350Ай бұрын
GREEDY THUMBNAIL Yellow Line
@unepintade21 күн бұрын
How is a perfectly defined procedure AI ? 😭
@user-nj1qc7uc9cАй бұрын
Did you actually put "AI" in the thumbnail? Ive never unsubscribed so quickly in my life AI can refer to things other than ML, but here it is 100% buzzword clickbait Dijkstra is rolling in his grave
@VaaaaadimАй бұрын
For what it's worth, BFS, Dijkstra's, A*, finding heuristics for A* were all covered as part of an AI course I took in uni. A* is widely applicable and extends beyond just finding a path from one place to another on a map or grid or whatever. The backbone of chess playing AI is minimax, an algorithm which just switches between computing min and max on a search tree, making it not so different in complexity to A*, yet I assume you have no problem with calling it AI. Also, a much older form of AI was "Expert Systems", which generally speaking used a knowledge base(which holds facts and rules) and an inference engine (which applies rules to conclude new facts), and to resolve a query inference engines perform a search! Prolog for example does a depth-first, backtracking search. I would imagine that any versatile symbolic AI would be utilizing some search algorithms as a core component.
@timseguine2Ай бұрын
This is the dumbest comment ever. This belongs to the domain of what is known as Classical AI and always has been canonically. If you knew anything about the history of computing whatsoever you would know that. Get off your high horse and quit the pretend outrage. Read any textbook from the 80s or 90s on AI (probably today too but no clue since I am old AF and have no reason to check newer learning material) and there is going to be a ton of stuff about graph search algorithms.
@user-gh4lv2ub2jАй бұрын
All of these are bad. Write an adjacency matrix instead and take it to the highest power you can before the matrix converges: simple.
@VaaaaadimАй бұрын
That solution would be memory-intensive, and requires you to explore the whole graph first (I think). Also the search space for a problem can be infinite. And if we have V vertices, E edges in the graph, and assume matrix multiplication is an O(n^2.4) algorithm, the time complexity of your approach would be O(log(V) * V^2.4) (assuming you're using a binary search sorta approach). In contrast Uniform Cost Search is O(E + V*log(V)).
@eugenedsky3264Ай бұрын
Meh... Write a simple brute force search with all special conditions on input data (like the Euclidean distance rule mentioned in the video) and then apply the whole program optimization (symbolic regression?) by AI. No need to even learn about those fancy... adjacency matrices?