A* Search: How Your Map Applications Find Shortest Routes

[@benharris8382]

babe wake up new reducible video just dropped

[@Masterhitman935]

He is alive!!!

[@user-pq5jy3yo8v]

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"

[@applesaregoodeatings]

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!

[@joaoguerreiro9403]

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.

[@shauryatomer1058]

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_]

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!

[@justaharmlesspotato885]

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

[@broccoloodle]

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!

[@abyssaljam441]

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_2013]

0:24 *specifically

[@pgrvloik]

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)?

[@ciCCapROSTi]

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_cultist]

they're different names for essentially the same algorithm

[@itsAbhinav5383]

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_cultist]

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.

[@cybermats2004]

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*.

[@humusstealr9982]

Ai

[@neon2633]

[@besiansherifaj9350]

GREEDY THUMBNAIL Yellow Line

[@unepintade]

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?

[@the_cheese_cultist]

that's just Floyd Warshall with a log factor

[@markuszeller_official]

Awesome explained and beautiful visuals!