A* 3机器人互相触摸

Question

这是关于三个机器人，命名为A，B，和C，可以移动他们的环境使用知情的搜索。环境有障碍。这三个机器人需要在某一时刻相遇，使它们行走的总距离最小。

为了使问题在计算上更简单，我们将把障碍限制为矩形。这三个机器人都是半径为1的圆，目标状态是让三个机器人(圆)相互接触，每两个机器人的中心之间的距离是一个单位。机器人在移动时，绝不能跨越任何障碍。在每一步中，三个机器人中的一个在四个方向上从当前位置移动一个单元:左、右、上、下。从一个点到另一个点的移动绝不能通过任何障碍。

，我只需要一个很好的启发式函数，它可以近似3个机器人之间的距离，你能帮我吗？

我解决了这个问题，这里是代码Github码

Answer 1

在这里，我假设您希望最小化总步数(一次只有一个机器人移动)。如果机器人同时移动，并且您希望最小化所需时间，则解决方案将有所不同。此外，一些微调是必要的，因为机器人应该只是触摸，而不是达到相同的点。

你实际上需要一个下界，而不是近似。一个好的下限可以通过忽略任何障碍和检查一个空场需要多少移动来计算。由于机器人只能水平或垂直移动，我们分别考虑这些方向。

先沿水平方向走。最左边和最右边的机器人需要在它们之间的某个地方相遇，所以在它们相遇的地方是独立的，总之，它们必须移动它们之间的水平距离。如果它们在中间机器人的水平位置相遇，中间就不需要移动。在任何情况下，水平步数都是最左边和最右边机器人之间的水平距离。把这叫做水平跨度。

垂直方向也有类似的论点。

因此，总的来说，下界是垂直跨度加上水平跨度。

Answer 2

如果每个机器人同时移动，并且知道障碍物在开始的位置(所以一个已知的地图)，而障碍物没有移动，这将是可行的。Uou需要使用波前算法生成各种类型的网格。这将在一开始对每个机器人进行。然后遍历每个网格，添加来自每个机器人的步骤。然后找到数量最少的网格。