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?
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?
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 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?!!!
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.
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.
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
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.
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.
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 ?
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?
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!
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!
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?
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?
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?
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.
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.
If at some point you get a node having better A* score and the node was already visited (but has inferior A* score than the most recent one), do you replace the old visited node with the current new one?
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?
Great explanation, it really helped me. Just one thing, in case of a tie, why don't take the node with the lowest heuristic value instead of solving it alphabetically?
Thank you for your clean explanation, Sir, very helpful. I have a question about your explanation on why we didn't put node A after S->A->B. You explained that we didn't put A after B because the total cost will be 20. Isn't it 17? Since S->A->B->A = 5+3+2 = 10, and with heuristic score 7, we have 10+7=17? Please correct me if I'm wrong. Thank you.
You are correct. [S][A][B][A] = (cost to A) + (predicted future cost) = (5+3+2) + (7) = (10) + (7) = 17, NOT 20. But yes, even an A* score of 17 is not preferable since that SECOND score for node [A] is higher than the FIRST A* score of 12 for [A]. Thus, we ignore node [A]'s higher (thus more costly, and thus unpreferable) cost of 17. To understand why we ignore such nodes of the same letter (e.g., [A]), recall that at 5:06, he says that in order for the A* algorithm to find the most optimal path, part of the algorithm's rule to make that happen is that "if later on in the search we find a path to A that has an A* score of less than 12 then we will look at that. However if we find later on in the algorithm a path to A with an A* score of more than 12 then we can completely ignore it and prune that part of the search."
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.
One of the best explanation of A* algorithm I've ever seen, Thank you Sir and I hope you create more videos about AI
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!
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
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
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!
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 🙌
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!
If both heuristic and cost of paths are guranteed to be positive, is it necessary to store A* score in visited list ? 2:12
calm,simple and interestig video..........
i liked it Thanks alot
I love the way you explain the algorithm... easy to understand...
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.
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 best teacher on the web
Thanks. Glad you liked it.
ua-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
The best exemplification that I found until now, It`s worth watching.
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!
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.
How is the goal state considered in a situation with ties?
If using alphabetical order, do goal states count as the alphabet G?
Love from China. Clear explanation and it helps me a lot. Thank you!
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?!!!
I love this man...... you rocked sir... hats off
Thank you! Glad you found it useful.
Thank you very much for these efforts, greetings from Libya
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.
Wow. Perfect lecture on A* search. Highly recommended!
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...
@johnLevine Kindly share assessment problem as well with accurate heuristics.
I'm not very good in English but your explaination is very easy to listen and understand. Thank you very much!
This is amazing, You deserve more subscribers!!!
Thank you. I want to know why considering only one path as the goal state. I have a burning assignment.
Loved the video. Clear and Understandable. Thanks Professor John. Looking forward for more videos.
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?
Sir, I request you to make another video on the state-of-the-art bidirectional heuristic search BAE*.
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 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
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.
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.
God level explanation of the concept!!!
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 ?
Where do we get the heuristics from?
Good example. Makes it so easy to understand admissibility issue.
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?
Still the best video available on A* search!
These videos are super helpful in explaining stuff I didn't get from my textbook! Thank you!
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.😀
A godsend. This is saving me in my CS Discrete Math class, thank you so much!
you're a most talented teacher. Thank you
Clear, patient, simple. Thank you.
Thank you for this great video! Love your clear explanation and your voice!
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!
I would like to say thanks to you. Your tutorial about A* is very exciting!
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?
Clear and concise. But could you share any resource as to why the heuristic should underestimate the cost ?
Great job sir!!! You explain things very clearly and unambiguously . No need to watch any other vedio after watching this.
It's a treat watching this as an introduction to what A* is. :D
Where do you get the initial node heuristics from or do you estimate them?
Best place to learn A*. U save my day!
Your explanation is amazing. Thank you!
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?
Typically euclidean distance, manhattan distance, or great circle distance.
@@EddieMasseyIII thanks
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?
This is important content. A related book I read was also significant. "Game Theory and the Pursuit of Algorithmic Fairness" by Jack Frostwell
Hello Sir,
It was very helpful.
Want to confirm if the path cost will be f(n) for the goal node?
Thank you
Your videos are the best. Please do Greedy and other topics
This is well explained thank you sir better explained than my prescribed textbook
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.
These videos are very educational and useful. Thank you so much!
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.
Best video for Heuristic algorithm!! Thank you !!
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.
Thank you sir for the explanation, it helped me a lot to understand the A* algorithm.
this is the best video for A* algorithm
Absolutely phenomenal explanation. Thank you for this.
If at some point you get a node having better A* score and the node was already visited (but has inferior A* score than the most recent one), do you replace the old visited node with the current new one?
Thanxxxx John. You're the best !!!!!
John the Goat! Thanks man!
how can ther multiple goal states, are you computing optimal distance to each one. If so, that wasnt mentioned. strange
This is the Professor we need, but don't deserve.
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 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?
A* is beautiful
At 5:59 you said that A* would be 20 for node A. Why? I am getting 17 (10 + 7). Sorry for. my English, this is not my first language. Thank you.
If 2 active nodes are tied, can you break the tie with the actual cost? Instead of alphabetical order?
thank you so much i was really struggling to understand it but you make really clear and simple
You are fantastic. Please make more videos.
Great explanation, it really helped me. Just one thing, in case of a tie, why don't take the node with the lowest heuristic value instead of solving it alphabetically?
Why would you do that in the first place ?
Thank you for your clean explanation, Sir, very helpful.
I have a question about your explanation on why we didn't put node A after S->A->B. You explained that we didn't put A after B because the total cost will be 20. Isn't it 17? Since S->A->B->A = 5+3+2 = 10, and with heuristic score 7, we have 10+7=17?
Please correct me if I'm wrong. Thank you.
I also find it 17..
A trivial mistake :3
all in all it doesn,t change the answer because 17 is still higher than 12
You are correct.
[S][A][B][A] = (cost to A) + (predicted future cost) = (5+3+2) + (7) = (10) + (7) = 17, NOT 20.
But yes, even an A* score of 17 is not preferable since that SECOND score for node [A] is higher than the FIRST A* score of 12 for [A]. Thus, we ignore node [A]'s higher (thus more costly, and thus unpreferable) cost of 17. To understand why we ignore such nodes of the same letter (e.g., [A]), recall that at 5:06, he says that in order for the A* algorithm to find the most optimal path, part of the algorithm's rule to make that happen is that "if later on in the search we find a path to A that has an A* score of less than 12 then we will look at that. However if we find later on in the algorithm a path to A with an A* score of more than 12 then we can completely ignore it and prune that part of the search."
what a clean teaching you are the best
You explained way better than my professor! Thank you! Now I finally understand it.
Short and to the point explanation. Thanks.
very clear, very smooth, I like the teaching! thanks!
thank u soo much u r a the savior
but i wonder why u dont calculate the cost of (G) with the cost of the path
very clear speech, awesome explanation. Thanks a lot!
If only I had a teacher like this in college …
this man is a hero
thanks Mr john levine your explanation is excellnt
Amazing explanation, thank you so much!