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.
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!
@@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🙌🏻
@@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 🙌
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
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.
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
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.
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?!!!
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?
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?
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.
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.
this guy is good. he's on my team. other videos on A* are full of fluff distractions giddiness and terrible form when it comes to conveying a simple idea. Good work John Levine
I am serious like wow loved the lecture was soooooo interesting please keep this up you will be helping alot of ppl since most teachers dont know what they are talking about
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?
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!
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.
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!
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.
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 ?
7 years later, this is still best video available
i agree
I agree
i gree
Thank you!
He's the only one that got it right imo.
Absolute legend. This dude has literally been more helpfull than I could ever imagine! Insane work!
Calm repetition of important facts/concepts is what makes this so helpful. It's like my Latin teacher always said: Repetitio est mater studiorum.
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.
But if the heuristic was not admissible this would not be the case right?
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!
One of the best explanation of A* algorithm I've ever seen, Thank you Sir and I hope you create more videos about AI
This channel with John Levine is awesome. What a great lecturer! Great channel! Thank you!
Thank you for providing free educational content of such high quality! The world needs more lecturers like yourself
The most coherent explanation of A* algorithm with an example. Thank you for saving our time and energy.
I am studying an introductory course in Artificial Intelligence here in Gothenburg, this short lecture made the A* very clear to me. Thank you!
Truly a godsend! Saved me 5 marks on my A levels 15mins before the exam. Couldn't have explained it better!
throwback 2 years ago, you helped me to pass my exam and understand this algorithm really well
How's life?
@@balochx Amazing
@@Geek-jx3gw stay amazing!
@@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🙌🏻
@@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 🙌
The best exemplification that I found until now, It`s worth watching.
the best teacher on the web
Thanks. Glad you liked it.
th-cam.com/channels/M-yUTYGmrNvKOCcAl21g3w.html
she is the best bruh
@@abhishekravichandran6965 she has no video on a star though
@@abhishekravichandran6965 S I M P
@@abhishekravichandran6965 S I M P
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
Thank you Mohamad! I'm really glad you find the videos useful.
I'm not very good in English but your explaination is very easy to listen and understand. Thank you very much!
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.
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
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?
It should be 17, not 20.
Indeed it should be 17
I agree too.
yup... its 17
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
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.
I love the way you explain the algorithm... easy to understand...
Love from China. Clear explanation and it helps me a lot. Thank you!
calm,simple and interestig video..........
i liked it Thanks alot
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?!!!
Wow. Perfect lecture on A* search. Highly recommended!
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.
Thank you, and well spotted!
Good example. Makes it so easy to understand admissibility issue.
This is amazing, You deserve more subscribers!!!
Thank you very much for these efforts, greetings from Libya
God level explanation of the concept!!!
I love this man...... you rocked sir... hats off
Thank you! Glad you found it useful.
A godsend. This is saving me in my CS Discrete Math class, thank you so much!
Loved the video. Clear and Understandable. Thanks Professor John. Looking forward for more videos.
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?
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.
Thank you sir for the explanation, it helped me a lot to understand the A* algorithm.
this man is a hero
This is the Professor we need, but don't deserve.
you're a most talented teacher. Thank you
This is well explained thank you sir better explained than my prescribed textbook
Clear, patient, simple. Thank you.
Great job sir!!! You explain things very clearly and unambiguously . No need to watch any other vedio after watching this.
Where do we get the heuristics from?
These videos are super helpful in explaining stuff I didn't get from my textbook! Thank you!
It's a treat watching this as an introduction to what A* is. :D
You explained way better than my professor! Thank you! Now I finally understand it.
I would like to say thanks to you. Your tutorial about A* is very exciting!
Thank you for this great video! Love your clear explanation and your voice!
Best place to learn A*. U save my day!
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?
These videos are very educational and useful. Thank you so much!
Sir, I request you to make another video on the state-of-the-art bidirectional heuristic search BAE*.
Thanxxxx John. You're the best !!!!!
If both heuristic and cost of paths are guranteed to be positive, is it necessary to store A* score in visited list ? 2:12
Your videos are the best. Please do Greedy and other topics
this is the best video for A* algorithm
Best video for Heuristic algorithm!! Thank you !!
John the Goat! Thanks man!
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.
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.
this guy is good. he's on my team. other videos on A* are full of fluff distractions giddiness and terrible form when it comes to conveying a simple idea. Good work John Levine
Thanks! You're too kind.
A* is beautiful
Still the best video available on A* search!
Your explanation is amazing. Thank you!
Insanely clear explanation. Hope you add more details about completeness, optimality and complexity
I am serious like wow loved the lecture was soooooo interesting please keep this up you will be helping alot of ppl since most teachers dont know what they are talking about
thanks Mr john levine your explanation is excellnt
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?
thank you so much i was really struggling to understand it but you make really clear and simple
This is important content. A related book I read was also significant. "Game Theory and the Pursuit of Algorithmic Fairness" by Jack Frostwell
Absolutely phenomenal explanation. Thank you for this.
Clear and concise. But could you share any resource as to why the heuristic should underestimate the cost ?
very clear, very smooth, I like the teaching! thanks!
Amazing video. Learned very much. Thank you. But on what basis heuristic are measured as it alters the way tree flows ?
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!
Thank You John.😀
Thank you. I want to know why considering only one path as the goal state. I have a burning assignment.
Short and to the point explanation. Thanks.
Thank you sir. Made it so much clearer
the lecture was dilivered in a logical and clear manner, thank you so much
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.
Thanks. I'm planning to do a video comparing the algorithms, including the time and space requirements, in due course.
@johnLevine Kindly share assessment problem as well with accurate heuristics.
This is a perfect video for understanding A* algorithm
very clear speech, awesome explanation. Thanks a lot!
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...
How is the goal state considered in a situation with ties?
If using alphabetical order, do goal states count as the alphabet G?
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?
Great Tutorial, Please also Make another tutorial on the Optimality proof of A∗
Many thanks, and thanks for the suggestion - I think that's a great idea.
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!
wawo you explained it very simply and quickly.
Thank you sir for this clear explanation of A* search.
THANK YOU! Greetings from Poland
This guys unbelievably skilled with a whiteboard marker
Very good explanation.. thank you
You are fantastic. Please make more videos.
what a clean teaching you are the best
Brilliant man you should make more videos
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.
Truly the best explanation of this algorithm we can find
Amazing explanation. thanks sir
One of the best teacher i ever seen
Very Clearly!If you have courses in Coursera or Udemy, I must buy it!
Amazing explanation, thank you so much!
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 ?