A* (A Star) Search Algorithm - Computerphile

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

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

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

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

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

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

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.

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

This guy is brilliant.

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.

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

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

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.

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

"sheep 'n' stuff"

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

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!

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.

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

"meh, finished data structure over here" 😂😂