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 🙌
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?
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?!!!
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.
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?
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.
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 ?
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?
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.
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
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?
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.
![Felix "Unfair" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/Oswujxm2Ag0/mqdefault.jpg)
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!
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?
Calm repetition of important facts/concepts is what makes this so helpful. It's like my Latin teacher always said: Repetitio est mater studiorum.
One of the best explanation of A* algorithm I've ever seen, Thank you Sir and I hope you create more videos about AI
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!
This channel with John Levine is awesome. What a great lecturer! Great channel! Thank you!
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
I am studying an introductory course in Artificial Intelligence here in Gothenburg, this short lecture made the A* very clear to me. Thank you!
Thank you for providing free educational content of such high quality! The world needs more lecturers like yourself
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 most coherent explanation of A* algorithm with an example. Thank you for saving our time and energy.
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!
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.
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.
Truly a godsend! Saved me 5 marks on my A levels 15mins before the exam. Couldn't have explained it better!
the best teacher on the web
Thanks. Glad you liked it.
ruclips.net/channel/UCM-yUTYGmrNvKOCcAl21g3w
she is the best bruh
@@abhishekravichandran6965 she has no video on a star though
@@abhishekravichandran6965 S I M P
@@abhishekravichandran6965 S I M P
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.
I'm not very good in English but your explaination is very easy to listen and understand. Thank you very much!
I love the way you explain the algorithm... easy to understand...
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?!!!
The best exemplification that I found until now, It`s worth watching.
Wow. Perfect lecture on A* search. Highly recommended!
Love from China. Clear explanation and it helps me a lot. Thank you!
Good example. Makes it so easy to understand admissibility issue.
Loved the video. Clear and Understandable. Thanks Professor John. Looking forward for more videos.
I love this man...... you rocked sir... hats off
Thank you! Glad you found it useful.
calm,simple and interestig video..........
i liked it Thanks alot
Thank you very much for these efforts, greetings from Libya
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.
These videos are super helpful in explaining stuff I didn't get from my textbook! Thank you!
Best place to learn A*. U save my day!
A godsend. This is saving me in my CS Discrete Math class, thank you so much!
This is amazing, You deserve more subscribers!!!
If both heuristic and cost of paths are guranteed to be positive, is it necessary to store A* score in visited list ? 2:12
I would like to say thanks to you. Your tutorial about A* is very exciting!
This is well explained thank you sir better explained than my prescribed textbook
Still the best video available on A* search!
Great job sir!!! You explain things very clearly and unambiguously . No need to watch any other vedio after watching this.
Thank you for this great video! Love your clear explanation and your voice!
God level explanation of the concept!!!
This is important content. A related book I read was also significant. "Game Theory and the Pursuit of Algorithmic Fairness" by Jack Frostwell
you're a most talented teacher. Thank you
A* is beautiful
Clear, patient, simple. Thank you.
Thank you sir for the explanation, it helped me a lot to understand the A* algorithm.
This is the Professor we need, but don't deserve.
It's a treat watching this as an introduction to what A* is. :D
Sir, I request you to make another video on the state-of-the-art bidirectional heuristic search BAE*.
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?
You explained way better than my professor! Thank you! Now I finally understand it.
Where do we get the heuristics from?
this is the best video for A* algorithm
These videos are very educational and useful. 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.
Your explanation is amazing. Thank you!
Perfect A* score for the teacher
Clear and concise. But could you share any resource as to why the heuristic should underestimate the cost ?
this man is a hero
Insanely clear explanation. Hope you add more details about completeness, optimality and complexity
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 ?
Absolutely phenomenal explanation. Thank you for this.
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?
This is a perfect video for understanding A* algorithm
@johnLevine Kindly share assessment problem as well with accurate heuristics.
Thank you. I want to know why considering only one path as the goal state. I have a burning assignment.
Best video for Heuristic algorithm!! Thank you !!
11:46 how do we know the solution path to goal node? As in visited nodes we have node B but in the path from source to goal it's not there.
Thanxxxx John. You're the best !!!!!
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...
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?
Truly the best explanation of this algorithm we can find
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.
If only I had a teacher like this in college …
very clear, very smooth, I like the teaching! thanks!
thanks Mr john levine your explanation is excellnt
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.
thank you so much i was really struggling to understand it but you make really clear and simple
the lecture was dilivered in a logical and clear manner, thank you so much
Your videos are the best. Please do Greedy and other topics
very clear speech, awesome explanation. Thanks a lot!
This guys unbelievably skilled with a whiteboard marker
This is wonderful !!! Thanks a ton ... I have a question at 5:53 isn't the A* score to A going to be 17 (5 + 3 +2 + 7) instead of 20?
It would be 5+5+3+7 where 7 is the heuristic value if I am not wrong.
Yes thats what Im wondering too....?
Welldone Machan..
a correction, the C node at the bottom left should have its cost as 9 and not 13
Thank you sir. Made it so much clearer
Short and to the point explanation. Thanks.
One of the best teacher i ever seen
what a clean teaching you are the best
WATCHING FROM PKMKB
Amazing explanation, thank you so much!
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
THANK YOU! Greetings from Poland
How is the goal state considered in a situation with ties?
If using alphabetical order, do goal states count as the alphabet G?
wawo you explained it very simply and quickly.
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?
Brilliant man you should make more videos
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.