A* Search: Good Estimates Find Real Solutions Faster

** Apologies for the low volume. Just turn it up **
This video demonstrates A* search on a simple graph problem, and introduces the concept of a heuristic. An example is also shown of how A* search depends on the heuristic, and can even produce bad results of there are problems with the heuristic.

[@tatanichakorn7533]

what if heuristic values are not given and the start and the goal are the same place?
Could you explain how to find the best solution for such case?

[@JacobSchrum]

If you don't have a heuristic, then you can't use A* search. You would have to use some other approach, like Uniform Cost Search. However, if the start and goal are the same, then I'm not sure why you're searching in the first place.

[@galsoftware]

You can use dijkstra (if the costs are positive)

[@JacobSchrum]

@@galsoftware With some small caveats, Uniform Cost Search basically is Dijkstra's Algorithm

[@xinyuanfneg1260]

everything just become clear before my midterm

[@tommcnally3231]

Isn't 7 for E an inadmissible heuristic? Since 7 7

[@tommcnally3231]

It's also decreasing. f(E) = 15. f(F) = 14. So it's inconsistent. In this example, it finds the optimal path by accident, but it wasn't ensured.

[@JacobSchrum]

The only routes to the goal from E worth looking at closely are E-F-D-Goal (1+2+5 = 8) and E-D-Goal (4+5 = 9) which are both greater than the heuristic value of 7, so the heuristic is admissible

[@JacobSchrum]

@@tommcnally3231 Unfortunately, you are correct that the heuristic is not consistent. h(E) = 7 would have to be less then or equal to c(E,F) + h(F) = 1+5 = 6, but that is not true, so good catch. However, the algorithm would find the optimal path anyway with an inconsistent heuristic. All that is required to find the optimal path is for the heuristic to be admissible. Being inconsistent does mean that the search process could be inefficient, but the final result would still be optimal:
th-cam.com/video/CJmlP03ik5g/w-d-xo.html

[@oleksandrklimenkov5988]

What if B-D edge had a weight of 1? Then this should be the shortest path, but your algorithm flow would not even check it

[@JacobSchrum]

If the value of the edge from B-D were changed in the way you describe, the heuristic would not be "admissible" which is a concept explained in the next video of this playlist:
th-cam.com/video/CJmlP03ik5g/w-d-xo.html
Basically, A* is only guaranteed to give correct answers if you use an admissible heuristic.