I have a search graph v1-v30, V=vertex(node), I use time in minutes between the vertex on a road network traveling salesman problem.
how do I determine the heuristics between these vertices?
I have already draft up a heuristics table with assumptions (Educated Guesses) of the time it would take between the nodes.
For example: from v1-v2 i have 20 minutes obtain from google map with the location i am using. I then used a heuristics h(n) value of 30minutes based off pure observation and educated guess.
Am I on the right path by assuming the heuristics the way I did?
Also how does A* handle dead ends?
A* handles dead ends just fine. I don't think you should use that strategy for your heuristic though. If you are wrong (if for some reason you overestimate the time it will take), your A* is not guaranteed to find the optimal path. If you're using Google maps, you could use the straight line distance from start to finish using the lat/long values of map markers
Regarding dead ends, Since A* gives a lower priority to any states that it guesses will take a long time to complete, a state that has current_node = v22 and prev_node = v20 will have have a lower priority than the state that never went down that path to the dead end. In this way the A* algorithm will gracefully ignore these dead end states. So you don't really even need to worry about manually recursing back up the path yourself.