Heuristic function for astar
I need a good heuristic function for A star for the pen plotter/TSP, where each state of my system has:
开发者_C百科- Path distance, that has been traveled
- Point where the pen is at currently
- Pen up/down
The "pen up/down" refers to the state where, you have drawn a line just then or you are moving to a point to start a new line.
Seeing as I have to travel through every point at some stage, the final goal state could be any point making any of the heuristics I've found on the internet impossible to use properly. I have tried the following, but failed to get a good heuristic from it:
(g(x) divided by the sum of the total distance traveled) * number of states remaining (assuming you are alternating between drawing a line or moving to a new point to draw a line)
I've also tried
the euclidean distance between the current state and the goal state (find the closest possible goal state).
This does not work since it gives you a heuristic of 0 because any state/point can be the goal state
Taxicab Geometry may be a solution. I've experimented with code that uses the results for completing a sliding tile puzzle
精彩评论