A* (A Star) Search Algorithm - Computerphile

Improving on Dijkstra, A* takes into account the direction of your goal. Dr Mike Pound explains.

Correction: At 8min 38secs 'D' should, of course, be 14 not 12. This does not change the result.

This video was filmed and edited by Sean Riley.

[obwwcfs]

8:41 "You know what? I'm just going to leave the lids off"
8:50 *Puts lid back on*

[jedigecko]

Books on the shelf...

_Security Engineering, 2nd Edition._ Ross Anderson;
_Secrets and Lies._ Bruce Schneier;
_The Elements of Statistical Learning._ Trevor Hastie, Robert Tibshirani, Jerome Friedman;
_C++ The Complete Reference, 4th Edition._ Herb Schildt;
_Cryptography and Network Security: Principles and Practice, 2nd Edition._ William Stallings;
_Computers and Intractability; a guide to the theory of NP-Completeness._ David S. Johnson, Michael Garey;
_Computer Security, 3rd Edition._ Dieter Gollmann;
_Hacking: The Art of Exploitation._ Jon Erickson;
_Database Systems: A Practical Approach to Design, Implementation, and Management, 5th Edition._ Carolyn E. Begg, Thomas M. Connolly;
_The Manga Guide to Databases._ Mana Takahashi, Shoko Azuma; /* Yes! Really! */
_A Brief Guide to Cloud Computing._ Christopher Barnatt;
_Pro WPF in C# 2010._ Matthew MacDonald; /* Ooh! Companion ebook available! */

/*
* Whew! For any simple task, take your initial runtime estimate and double it.
*/

[undead]

I have actually wanted Computerphile to talk about A* for a long time. It's so fascinating how it works.

[KarnKaul]

Extremely well done run-through!

Dr. Pound is right: A* is incredibly fast; so much so that we use it generously in path-finding (in gameplay engineering). That's a subroutine that multiple NPC instances are executing, 60 times a second, along with all the other stuff (that's a LOT more intensive).

[scabbynack]

Dr. Pound is great in his videos. He has a great on camera presentation and disposition. Thanks for these examples and explanations!

[fablungo]

I think something important to note which was very only briefly suggested is that if your distance-to-goal heuristic always underestimates you will always find the shortest path, but if not then the path you get may not be the shortest (which for some problems may be suitable).

If you underestimate too much then the benefits of A* diminish and you'll explore more and more of the graph. Additionally, Dijkstra is a generalisation of A* where the distance-to-goal is always underestimated as 0.

[bolerie]

Prefering to call a list a "data structure" is the sign of a true programmer

[garethdean]

This is not to be confused with the Sagittarius A* search algorithm, used often in astronomical science. *That* method simply involves shoving everything together in one big pile so whatever you need is nearby.

[brunoalves-pgeo]

I had an advanced algorithm exam 2 weeks ago and this algorithm was part of the test, I passed but never understood the algorithm. Until now.

Nice video

[johnsmithee]

There's a slight mistake - the distance from S-B-D is 2+4 = 6 and the D is 8 inches away from E, so the total for D is 6+8 = 14, not 12

[philipjohansson]

Rest in peace, Dr. Nils Nilsson, coinventor of A*, 1933-2019

[aaronsalenga]

Never in my life did I think that I'd be cracking up at a video about an A* Search Algorithm implementation. An entertaining video for sure 😂

I have a project due in less than 24 hours where we need to code A* from scratch, so thanks for reducing my stress and while teaching me this algorithm. I feel a lot better now.

[Jacoomo]

"Let's move the books to be in the frame"

[omkar_sawant]

I really appreciate Dr Mike taking the time out to not only host these videos but also make all the materials necessary for them. Being a professor must be definitely a busy job and all this must definitely take quite some effort. Appreciated!

[Clashkh]

I'd just like to note that you, Dr. Pound, are the most likeable Computer Science professor I've ever come across.
This is coming from a student of one of Germany's top MINT universities.

[vinitvsankhe]

One neat trick is to "prefer" one metric over another and use power notation to calculate overall heuristic. E.g. a node with distance 7 but weight 2, we added them as 7+2 = 9. But instead of that if we prefer shorter distance over smaller weight then weight should be the base raised to the power of distance.

So this way we can choose easily between two nodes that would otherwise yield the same heuristic if we add them but with the new rule if one node is with weight of 2 and distance of 7 (2^7=128) and another has distance of 2 and weight of 7 (7^2 = 49) ... we chose the later as 49 < 128 because we preferred the one closer to the end node.

Google maps often use this trick.

[tabidots]

The use of physical cards really helped make this explanation of the algorithm really clear. I was really struggling to follow purely written explanations, pseudocode, and actual code, because while I can code, I don't have a formal CS background.

[friewire]

Exactly like having a smart friend in class explaining it to you! Amazing

[smal]

My uni professor made this SO blurry - exact opposite of your explanation. Thanks a ton for restoring my interest in my major, kind sire.

[KarlFFF]

8:10 I like to live dangerously, I always shuffle my lists before storing!