目标是引导一个机器人从起点S到达终点G，并在途中经过所有检查点@（顺序不限）。标记为#的单元格无法进入。机器人可以移动到标记为.的位置。

#########@....G###.##@###[email protected]##@.....#########

一种解决方法是，从当前状态选择一个检查点作为目标，然后引导机器人到达该点。接着选择下一个检查点作为新的目标，当前检查点作为新的起点，再次引导机器人到达新的目标。最终从最后一个检查点引导机器人到达状态G。

但这种技术很大程度上依赖于遍历检查点的顺序。

我想知道是否有好的启发式方法来决定下一个要去的检查点？

回答：

我认为这个问题可以简化为旅行商问题。将S、G和@视为图的节点。然后计算每对节点之间的最小距离，考虑到任何墙壁的存在。这样你就得到一个图，其中节点之间的距离是有权重的。现在这变成了TSP问题，唯一的区别是你知道第一个和最后一个节点。