开发者

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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜