A* Search: How Your Map Applications Find Shortest Routes

Показать описание

Chapters:
0:00 Introduction and Graph Representation
1:37 Greedy Approach
4:12 Uniform Cost Search (UCS)
7:13 Greedy vs UCS
8:52 A* Search
11:09 Optimality of A* Search
14:45 Sponsorship

In this video, we explore the algorithms behind how modern mapping applications find routes that optimize time, distance, and cost. We motivate A* search from a first principle approach, building up to showing how it is a harmonious combination of both a careful, rigorous approach and a greedy, opportunistic approach.

Animations created jointly by Nipun Ramakrishnan and Jesús Rascón

This video wouldn't be possible without the open source library manim created by 3blue1brown and maintained by Manim Community.

Music in this video comes from Jesús Rascón

Socials:

Special Thanks to the Following Patreons:
Brian Cloutier
George Sharabidze
kerrytazi
Maggie Nguyen
Adam Dřínek
Andreas
justin
Matt Q
Ram Kanhirotentavida
Rocky
Winston Durand
Asha Ramakrishnan
Eugene Tulushev
Michael Nawenstein
Richard Wells
Zac Landis
Zac LandisZac Landis

Reducible

Рекомендации по теме

Комментарии

babe wake up new reducible video just dropped

benharris

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!

СизоненкоДмитро

Great video! I studied A* a while ago, and this was really helpful to refresh my knowledge

giacomotazzari

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!

Magnasium

i legit thought you dont come back. great to see a video of you again :)

multiarray

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.

zoonvanmichiel

Glad to see that the channel is still in use :)

Mabeeck

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!

forever_stay

I'm so excited reducible is posting again

srivatsajoshi

It's 3am here, let's go straight to A*

niccoboa

My man is back. What a time to be alive.

cariyaputta

He's back!! You're my favourite algorithmics channel, greetings from europe

de_michael

Very good video, actually first time I actually understand how the a* heuristic works, thanks!

Thorum

Ooh bro finally you got some free time i am very happy 😂

crockgaming

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!

leisuretime