Q: What’s a good heurisitic function? A: A good heurisitc function does not overestimate the distance to the goal. This is known as admissibility. Running A* with an admissible heuristic function will always return the shortest path to the goal state. Q: How I get the values for a heuristic function? A: A heuristic value represents the estimated distance from the current node to the cheese. Imagine you’re in a room and you can smell food in the other room. You can just guess how far you are from the food in meters or some other unit of measurement. As long as your estimate is equal to or below the actual distance to the food, the A* search algorithm will work. In more complicated settings, like Pacman, you can estimate the distance between objects using something like the Manhattan distance.
i know it has been many years since your upload, but still, i would like to add that a heuristic can be applied but A* will not always find the min path. This can happen IF the graph does NOT contain Euclidian distances. In that case, the heuristic must comply to an even more strict constraint named consistency. Stated as : abs( H(x,G) - H(y,G))
this explained heuristics very well. Thank you. I was so confused on heuristics but after watching this video, it made me feel like I was stuck on nothing😭
Who was the original creator of this video to whom credit is due, from the accent I know that it is not you who explains the video. I am interested in the content of this creator, could you please give the link or the name of the author?
That's so wrong, A* is more than that, heuristic is just an estimation of the total distance from that point and not the actual distance in so many cases. Also it doesn't account for the obstacles in the way and ignores that it involves backtrack from end point to determine the best/ideal way
Right. I think in a 2 minute video, you have to pick and choose what’s the most important thing to learn. The goal of this video was to try to give intuition behind why we use heuristics and what they actually represent, and it never claimed to cover heuristics extensively. Plus, I think your question was actually clarified in OP‘s comment above.
Kam Because adding eight seconds to the video to explain how the numbers are generated would have been too much. Yeah, okay. You also missed the part of my question asking about the distance. Thanks for your passive-aggressive response, though.
It depends, but one way to determine heuristic value is to calculate the distance between the point where you are standing and the end goal and add it to the total travelled node. Another way to calculate heuristic value is using Manhattan distance.
bro dropped one of the greatest algorithm explanation videos and then left
xd, what about weights, seems kinda funny missing most important part of algo
This deserves much more views , best explanation i have ever seen , maybe even the only one that explained the meaning of Heuristic data
agreed!!!
agreeeeed
Hands down the best explanation about A* algorithm on TH-cam so far.
This was the best explanation I've seen on TH-cam! So intuitive!
I agree. Best yet
True
I am amazed at how simply such a seemingly complex topic was explained. Best explanation on A* so far!
I really love that you explained the heuristic as the smell of cheese. I was struggling at understanding that concept
Q: What’s a good heurisitic function?
A: A good heurisitc function does not overestimate the distance to the goal. This is known as admissibility. Running A* with an admissible heuristic function will always return the shortest path to the goal state.
Q: How I get the values for a heuristic function?
A: A heuristic value represents the estimated distance from the current node to the cheese. Imagine you’re in a room and you can smell food in the other room. You can just guess how far you are from the food in meters or some other unit of measurement. As long as your estimate is equal to or below the actual distance to the food, the A* search algorithm will work. In more complicated settings, like Pacman, you can estimate the distance between objects using something like the Manhattan distance.
i know it has been many years since your upload, but still, i would like to add that a heuristic can be applied but A* will not always find the min path. This can happen IF the graph does NOT contain Euclidian distances. In that case, the heuristic must comply to an even more strict constraint named consistency. Stated as : abs( H(x,G) - H(y,G))
The best explanation ever for A* algorithm. I have been confused how it works on a graph and not a node grid and finally I see.
this explained heuristics very well. Thank you. I was so confused on heuristics but after watching this video, it made me feel like I was stuck on nothing😭
This is absolutely the best tutorial of a* algorithm I've seen in youtube. This video deserve more views !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
The best explenation of the A* algorithm I've ever found! +1
It's 5 am and I have a midterm on this at 1pm with a shift from 9am-12pm. Thank you
Gold. You just made it so easy for everyone in such a short time. Thank you very much. You've earned a subscriber.
Wow, have tried hard to understand it for like an hour and finally found this video. get me understood just in 2 mins, thanks a bunch!
That's an amazing example and the clearest illustration😁.Make me understand it so quickly
Absolute gold! Great explanation!
I love this explanation, is easy to understand and fast, love it, thank you
never thought a mouse looking for cheese in a maze would make me understand such an algorithm so well, thank you!
that was such a nice way to introduce this concepts.
literally the only indian cs video I've ever seen to be actually be good, short and informative. cheers mate
A lot better explanation than our 40 min lecture on A*
Thank you, really good. Had a 3 minute or so video for Dijkstra and was looking for something quick as well for A*.
I'm glad that finally I can find this video
this explained it better than my professor, tysm
Bro, this is level A kind of explanation. Congrats
Bro you literally saved my life!
Cheers to you sir! I finally understand heuristics intuition.🙂
Great explanation. So it's just a priority queue that prioritizes nodes that are closer to the goal.
icb a mouse and a piece of cheese helped me understand an algorithm so much
Man we need a whole explained in 2 min playlist XD
LMAO bro 45 minutes literally in 2 minutes. This is nuts. Thanks for this
you are my god, thank you so much my brother
Oops. It was that easy but no one explained as you men. Thanks ❤❤❤
bro just explained 50 mins lecture in 2 mins that I watched at 2X i.e a minute.
YOU ARE THE GOAT
Simply incredible
Brilliant Explanation, shame it doesnt have more views
you explained it very clearly 👏👏👏
You are the BEST
super nice! what an explanation.
Great video with very simple explanation!
Great Explanation. Good one.
Great video
20min concept in 2min! ❤
So brother the a* is basically a subset of djikstras shortest path algorithm
perf, best explanation
But how did you assign values for the distances between nodes?
I get the concept, but HOW do you estimate a distance when we don't know?
Thank you!
Does Q* mean Queue (Heap) + A*? Amazing!!!
Great❤
dude you are a goat
very nicely explained!
A very interesting analogy.
Woah, super
amazing explanation...
Dude thank you so much.
i love you please come back
How to find heuristic value ?? Is that just random numbers??
good one
why do you have h number?
holy cow
nice explanation
Who was the original creator of this video to whom credit is due, from the accent I know that it is not you who explains the video. I am interested in the content of this creator, could you please give the link or the name of the author?
This video was created by Kamyar Ghiam and me. You can find our details in the description of this video.
Thank you for the information, I do really appreciate it
damn.
That's so wrong, A* is more than that, heuristic is just an estimation of the total distance from that point and not the actual distance in so many cases. Also it doesn't account for the obstacles in the way and ignores that it involves backtrack from end point to determine the best/ideal way
The most important part of this was not mentioned at all. How are the heuristic and distance values initially seeded?
Right. I think in a 2 minute video, you have to pick and choose what’s the most important thing to learn. The goal of this video was to try to give intuition behind why we use heuristics and what they actually represent, and it never claimed to cover heuristics extensively. Plus, I think your question was actually clarified in OP‘s comment above.
Kam Because adding eight seconds to the video to explain how the numbers are generated would have been too much. Yeah, okay. You also missed the part of my question asking about the distance. Thanks for your passive-aggressive response, though.
Hi Anthony. Sorry, I did not mean to come off as passive aggressive. You’re correct. It didn’t mention the part about distances.
It depends, but one way to determine heuristic value is to calculate the distance between the point where you are standing and the end goal and add it to the total travelled node. Another way to calculate heuristic value is using Manhattan distance.
and my Dumb as teacher couldnt explain it in 30 mins
Thank you!