2024-07-27

[public] 14.5K views, 2.28K likes, dislikes audio only

Reducible

To try everything Brilliant has to offer for free for a full 30 days, visit https://brilliant.org/Reducible/

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.

The Manim Community Developers. (2024). Manim – Mathematical Animation Framework (Version v0.18.1) [Computer software]. https://www.manim.community/

Here is link to the repository that contains the code used to generate the animations in this video: https://github.com/nipunramk/Reducible

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

Socials:

https://www.patreon.com/reducible

https://x.com/reducible20?lang=en

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