A* Search

[@7sparksai]

7 years later, this is still best video available

[@miladnoori2098]

i agree

[@pranavdeshmukh311]

I agree

[@nocredits8066]

i gree

[@johnlevine2909]

Thank you!

[@a.m.4154]

He's the only one that got it right imo.

[@NikosXouselas10]

Absolute legend. This dude has literally been more helpfull than I could ever imagine! Insane work!

[@jm.101]

Calm repetition of important facts/concepts is what makes this so helpful. It's like my Latin teacher always said: Repetitio est mater studiorum.

[@tashijawed5472]

Great Explanation, as always. Just want to add one thing. at 9:43 When we reached node G2 with a cost of 13, we will stop the algorithm and won't go further with "E" node. Why? because it uses Priority Queue, the algorithm will stop once it finds a Goal node with a cost "less than or equal" to costs of other nodes. And it makes sense!! because once you reached G2 with a cost of 13, even if you have another node with the same cost, there's no point in checking it because it will only add to the cost.

[@peterlawrence3505]

But if the heuristic was not admissible this would not be the case right?

[@mostafakarimi1733]

One of the best explanation of A* algorithm I've ever seen, Thank you Sir and I hope you create more videos about AI

[@terrycamerlengo5492]

This channel with John Levine is awesome. What a great lecturer! Great channel! Thank you!

[@whiningmachine]

Thank you for this explanation. You have no idea how many pages and videos I had to go through before somebody explained that the heuristic indicates the estimated cost to a goal node. I had no idea why we only added the destination node's heuristic to the total (and not the other nodes' heuristics along the path), and now I know. Thanks!

[@nitinneo7]

The most coherent explanation of A* algorithm with an example. Thank you for saving our time and energy.

[@Geek-jx3gw]

throwback 2 years ago, you helped me to pass my exam and understand this algorithm really well

[@balochx]

How's life?

[@Geek-jx3gw]

@@balochx Amazing

[@balochx]

@@Geek-jx3gw stay amazing!

[@Geek-jx3gw]

@@balochx i didnt know what to answer but, life is not organized or as i wanted but it is better now 2 years before I was a stressed person, stressed about a lot of things including my future, grades, etc now, i am older and i changed into a better version of me i guess, less stressed, i love my struggles, i love to help people as much as i can, I’m trying my best to be good enough for me and my family so yeah life is amazing now🙌🏻

[@balochx]

@@Geek-jx3gw thank you so much for sharing. and yes, ups and downs are a part of life. no one is completely satisfied with his/her life, we just have to embrace it and strive for the good. helping people for no agenda brings out huge happiness. and it was nice knowing about your story. I love hearing common people rather than famous people who are faking everything. Stay blessed 🙌

[@tollwutpinguin]

Thank you for providing free educational content of such high quality! The world needs more lecturers like yourself

[@dennissaluaar9103]

I am studying an introductory course in Artificial Intelligence here in Gothenburg, this short lecture made the A* very clear to me. Thank you!

[@Leyan_leyuna]

calm,simple and interestig video.......... i liked it Thanks alot

[@KuliahInformatika]

I love the way you explain the algorithm... easy to understand...

[@dushanrathnayake5007]

Just brilliant! Thank you so much! At 5:53 the A* score for A is 17 (5 + 3 +2 + 7) instead of 20 I think.

[@johnlevine2909]

Thank you, and well spotted!

[@coxixx]

the best teacher on the web

[@johnlevine2909]

Thanks. Glad you liked it.

[@abhishekravichandran6965]

kzbin.info/door/M-yUTYGmrNvKOCcAl21g3w she is the best bruh

[@runneypo]

@@abhishekravichandran6965 she has no video on a star though

[@vakiljay8686]

@@abhishekravichandran6965 S I M P

[@heer1359]

@@abhishekravichandran6965 S I M P

[@NinaHProductions1]

You are the best teacher and provide the cleanest of explanations - at 5:53 the A* score for A is 17 (5 + 3 +2 + 7) instead of 20 I think?

[@que_93]

It should be 17, not 20.

[@ngusumakofu1]

Indeed it should be 17

[@JackyShaw]

I agree too.

[@know_how5661]

yup... its 17

[@sussananukem7101]

Nope... He's correct. He readded the path cost from A to B since we are revisiting A. That is: 5+3+(3)+2+7 =20

[@mohammadvasegh1754]

in our country, today is teacher's day good sir. thank you for all of your clarification and examples that you've solved and happy teacher's day to you

[@johnlevine2909]

Thank you Mohamad! I'm really glad you find the videos useful.

[@HafizAsimNawaz]

I love this man...... you rocked sir... hats off

[@johnlevine2909]

Thank you! Glad you found it useful.

[@koibathekingofgames8522]

The best exemplification that I found until now, It`s worth watching.

[@nihilrocks]

Truly a godsend! Saved me 5 marks on my A levels 15mins before the exam. Couldn't have explained it better!

[@breadsteeth2562]

Love from China. Clear explanation and it helps me a lot. Thank you!

[@niled.r.1639]

What to consider when defining the heuristic values? ...or how to calculate these values? - (Normally?) the "costs" represent distances or times, what other examples have you seen?

[@prakashbhattarai947]

If both heuristic and cost of paths are guranteed to be positive, is it necessary to store A* score in visited list ? 2:12

[@AsomyTraiget]

Thank you very much for these efforts, greetings from Libya

[@Dr.SamirKumarSadhukhan-jw1wk]

Sir, I request you to make another video on the state-of-the-art bidirectional heuristic search BAE*.

[@zaid_marridi]

Thank you for this simple and great explanation... You're simply the best at this. Clean, clear, easy and very informative What else could someone ask for?!!!

[@555to_infinity]

Wow. Perfect lecture on A* search. Highly recommended!

[@MohammadAwad-s8y]

Hello Prof John, I want to thank you for the great and clear explanation! I just have one question, shouldn't the total A* score at @5:58 be (5+3+2)+7 = 17 instead of 20?

[@therealajmelmuadz]

I was thinking the exact same thing! Glad I'm not the only one who was wondering if this is an error. Still not sure why he said 20 instead of 17.

[@husseinsylla4850]

Hello Sir, Best tutorial I have covered on A* algorithms. Clear and complete, include all explanations for f(n)=g(n)+h(n) and over-estimations of theoritical heuristics. Brilliant. Thank you so much.

[@bars5762]

I'm not very good in English but your explaination is very easy to listen and understand. Thank you very much!

[@iampujan]

Loved the video. Clear and Understandable. Thanks Professor John. Looking forward for more videos.

[@willardmakinishi6980]

Thank you so much Mr. Levin. Trust me these things did not make any sense in the first encounter with my Lecturer with due respect to him. I have just watched the first minute and i Have decided to download the tutorial. Hopefully I will find your explanations on all the search Algorithms. God bless you and I hope to understand these things before June for my exams

[@SiEmG]

Hello Mr. John Levine and the rest of the people IN THE COMMENTS :). Mr. Levin thank you very much for your help. You give totally clear instructions!! :) My only question is this: is G node visited also? I think in A* goal state is also added in the visited list, right?

[@mahwashshahid2499]

@johnLevine Kindly share assessment problem as well with accurate heuristics.

[@OsamaAlmas]

This is amazing, You deserve more subscribers!!!

[@vivekpadman5248]

Where do we get the heuristics from?

[@TheSophiaLight]

Clear, patient, simple. Thank you.

[@siddarvind6410]

A godsend. This is saving me in my CS Discrete Math class, thank you so much!

[@sagartalagatti1594]

God level explanation of the concept!!!

[@TheWheen]

For the most left line which is ignored, as B3 -> A7 from 5:45 in the video, the cost is not 20 as said, should it be 5+3+2+7=17? How the heuristic is known ?

[@뚝딱-q8j]

How is the goal state considered in a situation with ties? If using alphabetical order, do goal states count as the alphabet G?

[@AnsumanMohanty]

Clear and concise. But could you share any resource as to why the heuristic should underestimate the cost ?

[@mvvkiran]

So, two points I believe worth mentioning for the General Public's information sake: 1. The Search considered here is a GRAPH Search - NOT a Tree search. John Levine generally considers all Graph Search for all Search Algorithms - at least in the Uninformed & this A* Algs, so far 2. The REASON why the Heuristic MIGHT BE LESS THAN the Actual Cost of Reaching of a Goal is Because the Basic Heuristic considered for an A* Search is a Straight Line Distance - SLD. And we a know a PATH is NOT ALWAYS a Straight Line. How much ever Better a Heuristic you introduce, you'll never get the Actual Cost of Reaching a Goal State to be less than it. The Best Heuristic will Predict the EXACT cost of reaching a Goal State (only with ZERO Path Costs of course as A* Cost = Path Cost + Heuristic Cost) Hope this helps.

[@Astronomy.532lifenspace]

Thank you. I want to know why considering only one path as the goal state. I have a burning assignment.

[@saiprasad8311]

Good example. Makes it so easy to understand admissibility issue.

[@rishavlalshrestha9755]

Amazing video. Learned very much. Thank you. But on what basis heuristic are measured as it alters the way tree flows ?

[@johnlevine2909]

The heuristic function h(Si) is a quick-to-compute estimate of the cost to get from state Si to a goal state. The function you use is dependent on the problem being solved - for example, in robot navigation, you might use the Euclidean distance between the point that the robot is at and the goal state. The heuristic function has to have certain properties in order to work well - for A*, the most important is that it must be admissible - that is it must never over-estimate the cost. Hope this helps!

[@rishavlalshrestha9755]

Thank You John.😀

[@Alex_Yong]

A question is why the visited nodes don't need to be visited again, I think it may skip the node of the optimal path...

[@nilsmartel2295]

you're a most talented teacher. Thank you

[@simongrome9073]

These videos are super helpful in explaining stuff I didn't get from my textbook! Thank you!

[@nethmagunathilaka]

Best place to learn A*. U save my day!

[@lianghaoquan]

Thank you for this great video! Love your clear explanation and your voice!

[@shreengul6488]

Great job sir!!! You explain things very clearly and unambiguously . No need to watch any other vedio after watching this.

[@cuchuoisalay9263]

I would like to say thanks to you. Your tutorial about A* is very exciting!

[@YUMYUMINMYTUMTUM]

Still the best video available on A* search!

[@sibusisondimande5209]

Thanxxxx John. You're the best !!!!!

[@zhenyufan8988]

It's a great illustration!! But can u give us a example of how to decide the estimate value from certain node to a goal node?

[@coderlife2706]

This is the Professor we need, but don't deserve.

[@LarryP248]

This is important content. A related book I read was also significant. "Game Theory and the Pursuit of Algorithmic Fairness" by Jack Frostwell

[@Peter-bg1ku]

Your explanation is amazing. Thank you!

[@pantepember]

5:51 Did you ignore A because it was already visited or it would cost more (20) than in its first appearance (12)? 10:25 Shouldn't have we finished the search at G2 (13) instead of going on with E (13)? 11:15 You ended the search by choosing G2 (13) this time while we still had F (21). Was that because F cost more than G2 did? Thank you for the video.

[@anirvangoswami]

1. Because it was already visited. 2. We are following the alphabetical order as a tie-breaker. 3. Yes, we give priority to the lowest-cost node in the fringe.

[@flienky]

Does the condition that the heuristic value of a node should be bigger than the distance to the goal, apply to the starting node as well? Or it only applies for the intermediate nodes?

[@SaifUlIslam-di5xv]

It's a treat watching this as an introduction to what A* is. :D

[@ecekucukpehlivan9779]

These videos are very educational and useful. Thank you so much!

[@drc-ek2zu]

AT 10:00, don't you mean 15? where or why did it go to 21? In the end, we can see that the path was right, but I give pause to arithmetic in error in any of these examinations. And if we have these errors, should we just overlook them? I believe a correction is in order if not just to settle the masses who found the error.

[@robs939]

John the Goat! Thanks man!

[@melihekinci7758]

Very good explanation.. thank you

[@adeelali8417]

Where do you get the initial node heuristics from or do you estimate them?

[@tanle7317]

You said that if we encountered a visited node, we can ignore it if it has the higher A* score than the previous. What about when it has lower A* score? Are we supposed to draw that node again on the tree with the lower score?

[@zijunliu7765]

You explained way better than my professor! Thank you! Now I finally understand it.

[@harpreetset]

really insightful. I am learning AI and have been reading about agent searches for a while. This one is quite helpful. Can you also cover big O notations for time and space for these algorithms? it will help in analyzing in what environments it makes sense to apply them.

[@johnlevine2909]

Thanks. I'm planning to do a video comparing the algorithms, including the time and space requirements, in due course.

[@AshutoshSingh-do4ts]

Thank you sir for the explanation, it helped me a lot to understand the A* algorithm.

[@franchello1105]

If 2 active nodes are tied, can you break the tie with the actual cost? Instead of alphabetical order?

[@nandudara3845]

This is a perfect video for understanding A* algorithm

[@NARAYAN-vf9kx]

amazing job sir!!!

[@LucasofAppalachia]

Absolutely phenomenal explanation. Thank you for this.

[@vqvinh0405]

this is the best video for A* algorithm

[@Mousta_alpha94]

thanks Mr john levine your explanation is excellnt

[@muinmohammadmozammel281]

Short and to the point explanation. Thanks.

[@alibrahim4686]

You are fantastic. Please make more videos.

[@justafreak15able]

wawo you explained it very simply and quickly.

[@Alyson7924]

A* is beautiful

[@LowellBoggs]

This is an excellent presentation, thank you very much. I am tempted to code it up. A question: if the graph nodes are on an xy grid, should the heuristic actually be the real word Pythagorian distance, or the distance along allowed paths?

[@EddieMasseyIII]

Typically euclidean distance, manhattan distance, or great circle distance.

[@LowellBoggs]

@@EddieMasseyIII thanks

[@LowellBoggs]

Another question if you don't mind. Since the video said that the heuristic doesn't have to be perfect, but must be an underestimate: suppose you don't know the actual heuristic , but can search the graph for some fixed maximum distance from the start node in all valid directions, and if you don't find an endpoint , you can return the fixed maximum in liew thereof. Would this work? And would the performance decay to being somewhat worse than Dykstra?

[@nishantagrawal6244]

What, if we encounter a visited node again with less A* score??

[@ramiyousif8024]

Best video for Heuristic algorithm!! Thank you !!

[@alfianabdulhalin1873]

Thanks John. This video is a lifesaver. BTW, I've a question. Say I want to drive to the nearest city, and he wants to choose between 3 cities on a map (i.e. 3 goals states/nodes). So does this mean I have to calculate the A* score of each goal state, and then choose the smallest one? Thanks!

[@piotrptak5507]

Truly the best explanation of this algorithm we can find

[@rashidafoodcornervlog654]

Brilliant man you should make more videos

[@maxharris6926]

Great Video, thank you for explaining A*. For clarification if you find a node that has been visited, but the current path's A* score is less than the cost in the visited set, would you continue on the path and update the A* score in the visited set?

[@ComputerGuru-tk2hg]

This is well explained thank you sir better explained than my prescribed textbook

[@ShinnyxAKAvincent]

very clear speech, awesome explanation. Thanks a lot!

[@cieslak4004]

THANK YOU! Greetings from Poland

[@faox7565]

what a clean teaching you are the best

[@jamesthuo8763]

Your videos are the best. Please do Greedy and other topics

[@Imhotep1278]

very nice explanation and example, indeed

[@muhammadhabib3442]

Great Tutorial, Please also Make another tutorial on the Optimality proof of A∗

[@johnlevine2909]

Many thanks, and thanks for the suggestion - I think that's a great idea.

[@MuhammadUsman-ry6tp]

One of the best teacher i ever seen

[@cemozen7074]

Did you have to look at E(13) before G(13) ? Since heuristic always underestimates the actual cost, I guess there was no need to expand the E(13) node. However, it was great explanation of A*. Thank you.

[@ArunkrishnaMurugan]

19.09 minute, In G2 (13) already goal has been found. then why we need to do F(21)?

[@johnlevine2909]

The algorithm says that the goal state is recognised only when the node is selected for possible expansion, and this guarantees that we get the least costly path to the goal state. So we have to add G2 (13) to the agenda first - for example, if the cost of A-G1 was 7 rather than 9, then S-A-G1 (12) would need to be selected next, before looking at S-D-C-G2 (13).

[@kuanghuang2773]

very clear, very smooth, I like the teaching! thanks!

[@abdolvakilfazli2488]

Insanely clear explanation. Hope you add more details about completeness, optimality and complexity