A* (A Star) Search Algorithm - Computerphile

[@jedigecko06]

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

[@williamwambua7710]

Thanks i needed this

[@jorandebraekeleer7557]

@@williamwambua7710 Sarcasm?

[@Mmustafa-v4j]

Oh Great

[@evanl5299]

FYI - Herb Schildt was the multi-keyboard in the rock band Starcastle.

[@novikovPrinciple]

The... I'm sorry, _The Manga Guide to_ *what* ?

[@undead890]

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

[@chrisdrew1768]

I love how simple an improvememt A* is over Djikstra

[@mrben9058]

In addition, once you got A*, you can recreate Dijkstra by setting all heuristics to the same value.

[@chrisdrew1768]

Benjamin Collet bruh

[@StreamlineDeet]

(Almost) any cup that would be filled up by A* would also be filled up by Djikstra's. Remember, A* is still factoring in the distance travelled to get to a given node, so any path that is extremely long will be ignored, unless it brings it substantially closer to the destination. Meanwhile, Djikstra's would check out every node in the cup the moment those paths are shorter than the path it is taking around the cup.

[@Zazz30]

It depends on the graph and the strength of the heuristic. A* may cross a mountain where Dijkstra might go around it. Which reaches the end first depends on the mountain. If Dijkstra is faster, then you can weaken A*s heuristic (use smaller distance values) so it mostly goes around the mountain, but may take shortcuts that Dijkstra doesn't. Refining the heuristic's strength for the types of graphs you present it with is a key part of using A*. Is it mostly used for exploring flat or difficult terrain?

[@scabbynack]

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

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

[@jardeshna]

Damn that's reallly efficient

[@user-ob8ww5cf7s]

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

[@ojussinghal2501]

8:41 FOR MARKERS 8:50 FOR PEN

[@gacsizclickon]

muscle memory

[@bolerie]

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

[@sumitmomin5753]

Why ??

[@hopko7579]

@@sumitmomin5753 If I had to guess, abstraction?

[@sumitmomin5753]

@@hopko7579 wat abstraction has 2 do wid it ?

[@TurboWindex]

@@sumitmomin5753 IMO, it is because he's writing pseudocode so instead of using one particular data structure type (Vector, List, Map, etc ) and confuse anyone with "technical" programming terms, he's just saying "data structure" !

[@lucaspeters-murphy2770]

@@TurboWindex I mean, technically the only example where Dijkstra/A* is possible is a weighted graph.

[@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.

[@ShaojunZhao]

I think it is the other way around: A* is a generalization of Dijkstra's algorithm, as Dijkstra's algorithm assumes the heuristic function to be zero.

[@PHHE1]

Actually we saw an example for that in the video. We finished so fast in the end because the final distance was actually shorter than we expected only a step before. The heuristic being a overestimating one wouldn't have guaranteed to find the optimal path if there would have been a shorter ones in the right branch but it let us finish very fast

[@redy55]

A* has its uses. You can program edge weights of ones you want your algorithm to avoid to be positive infinity or something if you want to be sure. Also, the euclidian distance based heuristic you pretty much only use when you have a 2 dimensional map aside from nodes on it. So there cant be a realistic situation, when the path where heuristic is bigger is actually shorter. If you are measuring weight on a different parameter (like, how many shops does the town have, and thats your criteria, not difficulies on the road itself) then you should use another heuristic function or another algorithm altogether :)

[@brunoalves-pg9eo]

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

[@tengkuizdihar]

bruno alves I too like to live dangerously.

[@davidson2727what]

Yeah this guy saved me on dijkstra. Pre exam thankfully.

[@aurelia8028]

Should you have passed then?

[@georgeborsa5346]

@@aurelia8028 Yes, he should have passed. Most of the time those exams just test your memory. At that time he was only able to reproduce his college's explanation of the algorithm, after this video he's able to explain it with his own words (and maybe even implement it).

[@aaronsalenga3221]

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.

[@justinernest2363]

Was it part of a snake game? Like you know the snake searches for the apple etc?

[@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!

[@johnsmithee6660]

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

[@w47-p1e]

Its fixed

[@ProBarokis]

@@null3081 how bro

[@itsCh4rl1e]

the description fella@@ProBarokis

[@garethdean6382]

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.

[@mrBlagstock]

Dr Mike Pound is fab - so watchable. A KZbin star is born. Knows his stuff and a great explainer.

[@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.

[@Sindoku]

You not having a formal CS background has nothing to do with struggling with algos like this. That is simply b/c you aren't used to solving those types of problems, and 99% of universities do no prepare students adequately in DSA either, so most of them are struggling too.

[@smal7812]

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

[@Jacoomo]

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

[@Clashkh22]

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.

[@Nadox15]

Ich auf einer der besten Universitäten (bezogen auf Naturwissenschaftliche Studiengänge) als Informatik-Student im Master, wäre mal gespannt zu hören über welche Universität du spricht? :) Das wäre mir neu, dass "MINT" Universitäten die besten in Informatik seien. Aber hey go ahead :)

[@Clashkh22]

@@Nadox15Fernuni Hagen natürlich, was denn sonst, du neunmalkluger Sitzpisser

[@Nadox15]

​@@Clashkh22 hahahaha und du sagst, "one of the Germany's Top MINT Universities" wtf alter, von der habe ich noch nie gehört. Gute Unis sind, Tu-München, Humboldt-Universität zu Berlin oder auch Tu-Berlin. wat für Fernuni alter

[@Clashkh22]

@@Nadox15 siehst auch den Wald vor lauter Bäumen nich, wa?

[@glennchoi897]

Excellent explanation. I noticed D, and played it twice to make sure it is a mistake. And, then I read the description. Thank you for putting the video up.

[@KarlFFF]

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

[@rafaelplugge3214]

or even worse divide by 0! :O

[@NZAnimeManga]

dividing by "0!"? - no problem ;)

[@bfs7668]

Dennis Fluttershy soooo divide by one Doable

[@parktamaroon226]

hahah... did you write “sorting” out of sequence?

[@moellerdk93]

0! = 1 - google it

[@philipjohansson3949]

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

[@Mr123ichkomme]

I am watching this channel for decades by now. But this is the first time, that i was looking for a video on a topic and this vid was suggested. I'm getting there..

[@friewire]

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

[@IkonAndDiva690]

I've been watching your videos over the last few days, in order to solve a Pacman algorithm of Ghosts taking the shortest route, and found your explanations and content to be very educational and easy to follow. Many thanks and keep up the great work! Fingers crossed that I can now implement my version of A* on an adjacent list of nodes I've created for the maze...

[@RyanLucroy]

Man, I could listen to this guy for ages. His way to present his topics is just amazing :)

[@lerneninverschiedenenforme7513]

1st: '~ just adds a heuristic to dijktra' was the best statement!! Further, no usage of stupid unnecessary words like 'open list' and 'closed list'. Everythig nice and simple. Also, the animations help overcome handwriting. And the handwriting is there to keep the explaination realistic. 6 from 5 stars

[@Raggaliamous]

As someone with very little maths background, this video/ tutorial was just what I needed to get my heard around building a pathfinding algorithm.

[@kostyapesterew1068]

why 'D' was 4+8=12? traveled distance is clearly 2+4=6 so... 6+8=14?

[@EscapeMCP]

yup

[@Rachio666]

kostya pesterew that's correct. it should have been 14

[@ThaerRazeq]

To be honest, I was confused too @8:20, it should have been 14.

[@NiraExecuto]

I wouldn't call that annoying, because from what I've seen, the people not as talented can get seriously confused if the teacher makes a mistake, so in pointing it out, you're probably doing at least some of them a favor.

[@comrade1912]

exactly.. and I was not able to concentrate after that point... :P

[@russelllewis9215]

Let me nitpick just a little... You're correct that A* terminates when the destination node gets to the front of the queue *if* the heuristic is guaranteed to be a lower bound on the actual path length. But in this video, the physical distance doesn't actually correlate with the path lengths, and so you cannot actually exclude the possibility that the shortest path to E might go through C, or some other not-yet-examined node. But nonetheless, I loved the video, and it was a great explanation of the algorithm. Thanks!

[@hattrickster33]

One question I had was, how do we know we can stop when E is removed from the priority queue? The answer is that every element removed from the priority queue is guaranteed to have the most efficient way to get back to the element before it in the path back to the start node S. So basically, once E is removed from the priority queue, we know there is a path from S to E, and all elements removed so far are part of the shortest path, or the path that minimizes the total heuristic cost.

[@xPROxSNIPExMW2xPOWER]

This guy should just do all the videos tbh

[@silaslancashire2879]

"sheep 'n' stuff"

[@EgoShredder]

Sheep and Sheeple and Steeples! :-D

[@ChadNierenhausen]

Dr. Mike is one of the best presenters on this channel! Thanks for another fun one.

[@smartess]

I worked with A* Algo years ago, learning it wasn't that simple, but this man make it so easy to understand, Thump up (y)

[@diorcula]

He actually makes a mistake, writes down for: s->b->d: 8+4 = 12. although the actual value was 6+8 = 14 for D...

[@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.

[@glennzone12]

1:55 On the bookshelf; "The Manga Guide to Databases"

[@egg1645]

Student here, thank you! This is a really clean explanation and you clearly really love A star :)

[@iandavidson9761]

That lean forward with the "imperial woo!" gave me a good chuckle. watching from the states.

[@TheALPHA1550]

British chap.

[@amrsaber5457]

"meh, finished data structure over here" 😂😂

[@monilcharola6873]

Why did not I refer this elegent video of your's when I was back in college. I have feared this A* algo till this day, because of the heuristic function, and literally nobody has been able to explain it in this simple manner. Thanks for the video, much appreciated!

[@hesgrant]

Mike Pound is my favorite. What a brilliant communicator.

[@andreatoth9329]

I'm so thankful for your video! I learned about A* in uni and watched multiple videos about it, but I didn't understand it fully until now. Your explanation is very clear, you helped me so much.

[@seelyw.4818]

I like your unorthodox style of teaching. It's like a friend explains it to you. Thank you!

[@christaylor5613]

Great video, you've given me some great insights. The clever, subtle (and sometimes not so subtle) humor makes it all the better!

[@hafizhamzahafeez7576]

Am I the only one who thinks there is a great resemblance between the looks of Toni Kroos and Dr. Mike Pound. Wonderful personality and amount of confidence.

[@Sindoku]

His calculation for "D" in A* was off. D was S + B + D (0 + 2 + 4) or 6, and it had a heuristic of 8, so that is 14. He wrote down 12 in black. Not a major deal breaker here obviously, but just pointing it out b/c that's what us programmers do :). Thanks so much for the video!

[@Sindoku]

Nvm, they fixed it in the video description. Nice!

[@peanut7945]

This new office episode looks great

[@seanfy9399]

Never thought I could actually understand A*, BUT this video do make everything clear enough, you are brilliant, thank you!!!

[@Infaviored]

Many thanks for the good video. However, I think you missed to highlight one thing: The heuristic *always underestimates* the distance. I saw people questioning why it can't be that the path through the right side is shorter when we did not calculate the cost. The actual shortest path is always longer than the heuristic distance. Here this lies in the nature of the problem, the euclidean distance (straight path) is always shorter than the lengths when driving zig-zag.

[@joelproko]

I have two questions in regard to this: A) How do these algorithms handle two adjacent nodes being connected more than once? B) Assume a road was an amazing shortcut but was open and closed for public use at unpredictable times. [Say a very rich person had a lot of land on which they built said road with their own money. They either want quiet to sleep but don't mind traffic using the road at other times or they need the traffic noise to fall asleep and dont mind traffic while they're away but want quiet while awake and there. To either end, they are able to remotely close off and open the road (while allowing traffic still on it to leave at all times, of course).] How would a navigation algorithm handle that? Would it pretend the road is always closed, or would it pretend there were tiny one-way slivers at both ends of the road where the barriers would be if it was closed (so it wouldn't direct you to turn around if you were savvy enough to spontaneously go onto that road when seeing it open)?

[@generalzugs6017]

Please, ask dr. Mike to explain more stuff. He's very good at it.

[@SianaGearz]

I recall a car equipped with a satnav from the mid 90s, and it used a CD to store navigation data across all of Europe, with a slow and silent-spinning optical drive, probably 2x speed at best, maybe 1x. I imagine in my mind that it was equipped with a dinky little 68k processor, capable of addressing a total of 16MB, likely equipped with barely any memory at all, and it didn't take long at all to load the data or compute the path. Indeed it would do so in a couple of very audible optical drive head moves, just a handful. I imagine it would have to load just the local map around the start, a local map around the destination, and then just have all the routes between selected points precomputed on CD, at least one point per map sector, so it would need one lookup into a hash table on CD indexed by map start and end sectors to find the disk address of the route, and then it could fetch that route, and then augment and optimise the route with real start and destination points in mind, instead of precomputed ones, but it would only need to search local data at each end into account for that. This is how i imagine it being done. How wrong am i? How would such a system work in practice, what algorithms are involved at runtime?

[@thomasscanlan8624]

this is the best explanation of this algorithm that I have found on youtube thus far! Excellent!

[@SuperNolane]

Important thing that was missed is that used heuristic must be less than cost of least path to node. Otherwise you can get wrong answer.

[@rumfordc]

he mentions that right before he starts using the tape measure

[@SuperNolane]

He sad "for A* to work really well you have to have a consistent metric and you have to not overestimate of how far you've got to go". But it will not work at all if you have overestimating metric.

[@rumfordc]

won't it just return a less-than-optimal path?

[@SuperNolane]

It will. But why to pick such intricate method to get wrong answer when you can just return random path?

[@hendrikw4104]

"not overestimating lengths" is called admissible. Every consistent heuristic is also admissible. Consistent means that h(n)

[@HebaruSan]

Search from both ends at the same time and stop when the two searches meet. Instead of one search to depth N, now you have two searches to depth N/2. In a graph with many nodes and many connections, the number of nodes at each depth increases with the depth, so each search tree is less than half the size of the original, and the total number of nodes searched is reduced.

[@dragoncurveenthusiast]

finished pack... finished stack... finished list?... finished data structure! :-D gotta love this guy! 9:10

[@getvasued]

Amazing! No other video on A* will ever be needed :)

[@totlyepic]

It's interesting that you went with a relatively sparse graph for this. Most people introduce A* in the context of grid-like graphs.

[@B0XMATTER]

I suppose you don't really have a 256*256*256 grid to describe the basics of A* since what was described here technically works.

[@andreyrumming6842]

"You could come up with lots of interesting heuristics, not just euclidean distance" I know that he didn't strictly say this, but I totally wanna write a non-euclidean A* algorithm now!

[@dw61w]

For Dijkstra, you get the shortest path from start to every other node, regardless which end node you choose. But for A*, in order to use the heuristic, you need to specify an end node for the algorithm.

[@C4rb0neum]

I'm very close to having tears in my eyes from laughing when 'super sneaky' was introduced as 'not an official term you will find in the literature.' Brilliant side note.

[@EllipticGeometry]

Efficient routing engines do precompute the map. There are all kinds of techniques like transit nodes, contraction hierarchies, landmarks and arc flags. They formalize the concept that sufficiently long routes all end up on the same few major roads for most of their length. That it makes no sense to explore alleys when you want to get to another city, except very close to the origin and destination. While variable speeds trouble A* (admissible heuristic must assume motorway speeds, largely defeating its purpose on slower roads), they only make these algorithms more focused. They’re not exactly hardcoded either. They analyze the map and figure out what’s possible. All the alleys will still be used if they do happen to be faster. Not to claim that no one has ever hardcoded such a thing, but there’s certainly no need for it. In all, queries become very fast and lightweight, and possible at all on devices with limited processing power and memory. The size of the map can even shrink a little in some cases. Often, finding the route is faster than listing its edges. There are also ridiculously fast variants that can find a continental route in a few random access delays, at the cost of needing tons of RAM.

[@DontTalkShite]

This guy is brilliant.

[@docwhogr]

Adam Smith. stop trolling

[@DontTalkShite]

I wasn't

[@CxC2007]

Adam Smith is not brilliant. he did no invented this. he just study computer science, and he knows thing you don't.

[@meinbherpieg4723]

You don't have to invent something to be brilliant. Just being able to understand, accurately recall, and be able to explain this material in a way that enables other people - especially people who don't have a formal background in this material - to understand it is brilliant in and of itself.

[@DontTalkShite]

I just meant I really enjoy when he's hosting. He's brilliant at explaining things.

[@DustinRodriguez1_0]

I'm surprised that he didn't mention that A* is used in practically all games for non-player characters to navigate. That's the biggest direct use of A* I know of and it's pretty much universal.

[@icedragon769]

That's the most trivial use of A*. A* is the standard searching algorithm for all AI applications, not just video game NPCs. This is kinda like commenting on an electrical engineering video on the peizoelectric effect, "Oh why didn't you talk about the board game Operation, it has a peizo speaker in it!"

[@benjiusofficial]

Dennis Fluttershy that comment was just like in Minecraft

[@fytubevw]

Behavioral pseudocode (for NPCs) - normal person, without any particular phobias - uses A* to travel A-B - does walkTrace() - so saves the amount of people encountered during a trip - is not particularly acute in saving walkTrace() information, since he doesn't mind people - agoraphobic - simply avoids "hotspots" where he estimates it is likely to be crowded - is o.k. with encounters, as long as they do not occur WITH "crowded" situation - doesn't engage in conversations when the encounter is clustered with being crowded - basically should be able to function both day and night, if needed - anxious person - avoids close encounters with people - and crowding - might lead to emergent behavior: prefers night time (works in night shift since it's less crowded then) - if very anxious, or happens to have a difficult preferred path, might leave the person unable to leave home

[@sparshpriyadarshi]

Was struggling with a bug in my implementation, the timing could not have been better. you made me see it ! Thanks !

[@VidimusWolf]

Why does he always sound and look like he is constantly on the verge of breaking out into an unstoppable laughter? Haha, Amazing explanations as always!

[@sabriath]

I prefer double a* pathfinding....basically you have a start-to-finish on the queue (S:10:E for example) and a finish-to-start on the queue (E:10:S). You work the queue in the same manner, by expanding the smallest value, but you're finished when the one you are expanding connects with the second one in the queue. This helps immensely in situations of tree-like patterns, where the path from one to the other keeps splitting into multiple directions, while the reverse direction is pretty straightforward (think binary tree).

[@eccentriccode3158]

You guys are saving cs students. Got an exam on A* and others soon so thanks (:

[@usptact]

Finally somebody explains what A* actually does! It was bit rushed but I managed to follow (usually I get lost).

[@בןחלפון]

great video!!! I came across a situation where checking the distances of all nodes to the target before starting the algorithm was a pretty hard task. So I recommend to measure the distance of the node to the target only when it need to be inserted in to the queue thank you!

[@yukewang3164]

very vivid presentation of the graph algorithm helps me a lot to understand the process

[@roelvoort]

WHY o' WHY inches.

[@tychothorpe4515]

Probably because it would be smaller numbers

[@gannebamm2]

so. The centimeter A* video should be placed on the numberphile channel than?

[@modernkennnern]

or because the numbers themselves are larger on the measure itself.

[@wierdalien1]

Florian Hoedt centimetre. whats a centimeter? what do you measure with a centi?

[@gannebamm2]

A hundretst of a meter for example?

[@benjaminramsey4695]

This video primarily, plus a couple other sites I looked up after, helped me implement pathfinding in my game! Thanks!

[@karangupta3394]

great and fascinating explanation of a star.

[@deathhog]

As for the SatNav, it might just be a simple system of prioritization. Consider that the highest speed roads are highways. And they're usually as short a distance between cities as they can be. They're expensive. So, the computer will likely just give a very very low weight to those roads, and prune all the other side roads until you get to the closest hub city, and *then* activates the proper algorithm. This has the added benefit of encouraging motorists to use the best maintained roads to boot.

[@prashanth95r]

At 4:32, s, a and b are forming a triangle and not obeying the triangle inequality theorem, sb+ab < as

[@kebman]

This explanation is great in that it explains what the machine does. Meanwhile I also like the intuition given in polylog's video.

[@MegaTheDarkdemon]

This was one of the most enlightening and interesting ways to explain searching algorithm. Thank you. Subbed and liked!

[@SimonBuggeSiggaard]

You can clearly tell that Mike practiced this explanation beforehand :P

[@kwanarchive]

They do edit the videos you know.

[@philips9042]

Simon Bugge Siggaard Just shows how much dedication he puts into this. Not saying the others were bad, but Dr Mike Pound is my favorite

[@General12th]

I'm sure every interviewee practices first. Also, I think Dr. Pound is a professor, so he's given this lecture before.

[@TheDuckofDoom.]

I borrowed a freind's older tomtom sat-nav some years ago(2010-13 ish) and told it to find the best paths between Dallas and Tacoma, several minutes later it responds that "the path has dirt roads, would you like to avoid dirt roads?" I select yes and it goes back to calculate for several more minutes and says "destination is on a dirt road no path found" and reset with no results. A broken algorithm for sure I don't know why they would even release it to the public, it wouldn't take the preference before calculating so it had to calc twice, interpreted "avoid" as an absolute command of no dirt at all, then discards all the calculations. My home is 100meters onto a dirt road so some dirt is unavoidable, I just wanted it to minimize unpaved routes so it wouldn't route me down a 50 mile mountain service road. Which it attempted to do on several occations. Like the plant nursury that, like my home, was just off the end of the pavement, the tomtom routed me from the other side over 5 miles of winding dirt road, because it was shorter physically and had no speed data so was assumed the fastest route.(and in this case I was only traveling/calculating about 40 miles)

[@rameshkumargovindaraju4504]

brilliant. thank you for this lecture. So much better than what I had heard thus far.

[@xpaganda]

"super sneak is not a technical term you see in the literature" LOL Never change, britbongs!

[@xeladas]

If I where to guess how satnavs get around the issue of combination explosion problem (or how I'd try to do it if suddenly asked to do it (not at all likely)) would be to store not just the "proper" road system but also a map of only motorways. The algorithm A*s (with euclidean distance to destination as the heuristic) until the destination or a motorway bubbles to the top, if you find your destination it's done, if it finds a motorway it saves that node, then runs A* on the destination, if it also hits a motorway it saves that node as well, then it goes to the motorway map and does the same thing with the two motorway nodes. Honestly it is probably much more complex, with more layers (one map has everything, the next ignores country roads, the next ignores B-roads, etc.), some system to go to a previous map level if maps don't connect, and may sample multiple nodes when going up just in case.

[@Mdatafication]

His videos are absolutely awesome.

[@thejoebegs]

These are the best. Thank you.

[@leonbishop7404]

2+2 is 4, minus 1 that's three quick mafs

[@rpgquestboard]

Points for both Security Engineering and Bruce Schneiner on the shelf. I knew I liked Mike.

[@draco18s]

Speaking of interesting heuristics, it might be worth doing a pass through Jump Point Search, which is great for grid-based pathfinding that lets A-star expand even fewer nodes than it would normally. It would take a different example graph, though.

[@Anvilshock]

THIS JUST IN: POUND BACK, INCHES AHEAD, SHORTEST PATH TO BREXIT PACED

[@tomburns5231]

Fantastic videos, as always, Computerphile. And thanks Mike, nicely summed up together with other videos.

[@Xappreviews]

Wow what a coincidence, I'll have an exam about artificial intelligence tomorrow, and it also will contain A* :) One interesting thing you did not mention is that A* is "optimally efficient", that is, in general there cannot be a better search algorithm than A*

[@spiderstheythem]

I'd let Dr. Mike Pound me

[@spiderstheythem]

😉😘👌

[@DJChiefX197]

*the wedding band on his left hand glistens*

[@AP-eh6gr]

i knew this one was coming......

[@_tyrannus]

Basic satnav is already impressive, but traffic-aware satnav (like Google's since they bought Waze) is even more so. Traffic can change quite a lot in the duration of one's commute, which means the shortest path changes in real time. Combining real-time data from users and daily averages become necessary. And all this needs to be trimmed down to be as little power-hungry as possible, since many millions use it at the same time over the world.

[@umountable]

you should point out, that the heuristic must be consistent (don't violate trianguar inequality, meaning, detours can't shorten a path) and admissable (underestimate the cost) in order for A* to find the optimal solution. In general, the direct distance would be a admissable and consistent heuristic, but the distances between nodes are not in inches, therefore it does not work properly. In this case the heuristic was not admissable, so one could have ended up with a suboptimal path.

[@BlackJar72]

I found A* very useful in testing and fixing the passabiliy of procedurally generated rooms. A* proper hardly required any code, most of the code was setting up the graph and using the results.

[@selsuru]

I use this algorithm myself for pathfinding in games, it's efficient and doesn't cost a lot of memory.

[@gonzooxx]

If the distance between G and E is set to 15. This could happen, if this route was crossing a mountain, whit lots of bending roads up and down a mountain. It could be close in term of the euclidean distance, but the route could be much longer, both in time, fuel consumption and km/miles. So again if the distance between nodes G and E is set to 15, then this algorithm is not finding the shortest path. Because it will still find this route S -> B -> H -> G -> E even though there is a shorter route, which is S -> C -> L -> J -> K -> E. This happens because G is on the top of the 'ordered list of combined length', just before it finds the solution going to E, which is heavily penalized on the last stretch between G and E. So to mitigate this problem the algorithm should continue, to search after a shorter route, after finding the first solution. All nodes witch is being evaluated, after finding the first 'shortest path', should not be inserted again or deleted into/from the 'combined length sorted list', if the combined length calculated, is longer than the first found 'shortest path'. Then continue until the 'combined length sorted list' is empty. 'shortest path' could be lowered many times.

[@hcblue]

I love Dr Pound.

[@egor.okhterov]

I am here after Q* from OpenAI 😂

[@AdrianMunteanu92]

I would like a video about the D* algorithm, please.