我需要一个用于笔式绘图仪/TSP 的 A 星的良好启发式函数，其中我的系统的每个状态都有:
- 已走过的路径距离
- 笔当前所在的点
- 向上/向下画笔
“上笔/落笔”是指刚刚画完一条线或者移动到一个点开始新线的状态。
由于我必须在某个阶段遍历每个点，因此最终目标状态可能是任何点，这使得我在互联网上找到的任何启发法都无法正确使用。我已经尝试过以下方法，但未能从中获得良好的启发:
(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)
我也尝试过
the euclidean distance between the current state and the goal state (find the closest possible goal state).
这不起作用，因为它给你的启发式为 0，因为任何状态/点都可以是目标状态
最佳答案
Taxicab Geometry可能是一个解决方案。我已经尝试过使用结果来完成 sliding tile 的代码。拼图
关于java - astar 的启发式函数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7508312/